Posts

Binary Search in Haskell and Python 3.6

I've been learning a lot about Haskell lately, so I decided to write my own implementation of binary search after coming across Jacob Sheehy's implementation. In my own I wanted a nicer functional interface to locating a value in an entire list though. I also wanted it to be safe, using the Maybe monad in the event a value doesn't exist or the list is empty.
module Search where -- A humble implementation of binary search in Haskell binarySearch :: Int -> [Int] -> Maybe Int binarySearch _ [] = Nothing binarySearch value list = search 0 ((length list) - 1) where search :: Int -> Int -> Maybe Int search i j sublist = do if i > j then Nothing else do let midPoint = ((i + j) `quot` 2) currentValue = list !! midPoint -- compare outputs one of LT, GT, EQ case compare value currentValue of LT -> search i (midPoint - 1) GT -> search (midPoint + 1) j EQ -> Just mi…

A string hash problem

Image
Earlier this week I was looking through various software developer jobs and I came across this one by Fog Creek. They've posted the following interesting problem, which is the subject of this post.
Find a 9 letter string of characters that contains only letters from acdegilmnoprstuw such that the `hash(the_string)` is 945924806726376 if `hash` is defined by the following pseudo-code: Int64 hash (String s) { Int64 h = 7 String letters = "acdegilmnoprstuw" for (Int32 i = 0; i < s.length; i++) { h = (h * 37 + letters.indexOf(s[i])) } return h } I had no clue what to do when I first read this. In fact, my first attempt was to brute force my way through \({16}^{9}\sim 68\cdot {10}^9\) possibilities. Obviously we need a better method than that.
from typing import Optional from itertools import product alphabet = 'acdegilmnoprstuw' def hash(string: str) -> int: "&quo…

Setting up ath10k

This post is meant as a simple reminder of how to get WIFI working in the event that I have to reinstall Debian on my Lenovo Flex 5, which appears to be a newer firmware.

First, run mkdir -p /lib/firmware/ath10k to create the subdirectory ath10k if it doesn't already exist. Now copy the QCA6174 directory from this GitHub repo there and rename the files QCA6174/hw*/firmware-5.bin* to just firmware*.bin.

Now reboot, and whoala! WIFI works.

Unfortunately, there still appears to be a few fails while loading the firmware, which I'll have to look into at some point. But for now, this is a quick fix to get things moving.
$ sudo dmesg | grep ath10k [ 2.186725] ath10k_pci 0000:03:00.0: pci irq msi oper_irq_mode 2 irq_mode 0 reset_mode 0 [ 2.463755] ath10k_pci 0000:03:00.0: firmware: failed to load ath10k/pre-cal-pci-0000:03:00.0.bin (-2) [ 2.463756] ath10k_pci 0000:03:00.0: Direct firmware load for ath10k/pre-cal-pci-0000:03:00.0.bin failed with error -2 [ 2.463765] ath10k_…

Tips and tricks I learned at PyCon 2017

This was my first PyCon, and it was a lot of fun! I wanted to write about my four favorite talks, and some 'tricks' I learned from them.

First is Decorators Unwrapped, by Katie Silverio. While I'm comfortable with decorators, I thought some of her silly 'useless' decorators were good examples. For instance, her no_op decorator, which is basically the identity.
from typing import Callable def no_op(func: Callable) -> Callable: # do nothing return func Another concept I hadn't really thought about was where *args and **kwargs come from in the following simple example, which calls the original function on some supplied arguments (it basically does the same thing as that above).
from typing import Any from functools import wraps def args_kwargs(func: Callable) -> Callable: @wraps(func) def new_function(*args, **kwargs) -> Any: res = func(*args, **kwargs) return res return new_function Note that *args and **kwargs a…

Matching stars between frames

Image
Lately I've been trying to find algorithms that will match stars between two consecutive CCD images. Needless to say, the task isn't at all easy, and my `naive' implementations have rather costly time complexities. However, with a little tuning, it's possible to get pretty descent results.

To begin, I installed Source Extractor (on Debian and Ubuntu, just type sudo apt-get install sextractor). Then I wrote this Python script to generate NN filters. As an example use, try running the following.
./psf.py --gaussian -i $(echo 3.1 > gaussian.conf && echo gaussian.conf) -s 6 -o gauss.conv && rm gaussian.conf && cat gauss.conv In the terminal you should see the following.
# Gaussian convolution filter for params 3.1 0.013196 0.019866 0.024375 0.024375 0.019866 0.013196 0.019866 0.029908 0.036695 0.036695 0.029908 0.019866 0.024375 0.036695 0.045023 0.045023 0.036695 0.024375 0.024375 0.036695 0.045023 0.045023 0.036695 0.024375 0.019866 0.029908 0…

Gradient descent for fitting models to stars

Image
This is a topic I've written about before, but I wanted to update my code and simplify things. You can clone the GitHub repo if you'd like an example to run for yourself as well.

Basically, the goal is to fit a two dimensional Gaussian distribution to a star in astronomical data (though it'd be easy to generalize this algorithm to the N-dimensional case).

The Gaussian is a good model in most cases, and it's easy to compute; in the past I tried fitting the Moffat function as well, but I found its parameter \(\beta\)  hard to fit, so an iterative method probably isn't optimal.

To start, I'll restate the gradient descent (GD) algorithm (you'll find it peppered throughout the literature because it's so well known).
\begin{align}\vec{\theta}_{\kappa+1}&=\vec{\theta}_{\kappa}-\eta\vec{\nabla}_{\vec{\theta}}\text{cost}(\vec{\theta}_{\kappa}),\end{align}
where
\begin{align}\text{cost}(\vec{\theta}_{\kappa}):=\dfrac{1}{MN}\displaystyle\sum_{i,j=1}^{N,M}[m(i…

Monads in Python, 2

Today I worked with monads again. In the process I wrote an implementation of the Maybe monad in Python, using the same ABC I wrote in my former post. I also came across another interesting topic, but I'll get to that in a bit; below is my implementation of Maybe.
#! /usr/bin/env python3.6 # -*- coding: utf-8 -*- from typing import Any from types import FunctionType as Function from monads1 import Monad class Maybe(Monad): def __init__(self, value: Any =None, just: bool =True) -> None: self.value = value self.just = just def __str__(self) -> str: if self.just: return f'Just({self.value})' else: return 'Nothing' def __repr__(self) -> str: return self.__str__() def bind(self, f: Function) -> 'Maybe': """ Action upon value in Maybe context that returns a new Maybe context """ if self.just: return f(…