## Posts

Showing posts from 2017

### 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

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 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

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…

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(…

### Levenshtein distance metric

While reading about BK-trees this morning (a topic I may write about at some point in the future), articles kept mentioning a distance metric on strings called the Levenshtein (Левенште́йн) metric. Because I've never written an implementation of this algorithm before (and some of the links to Python source seem to be broken), I've written my own.
#! /usr/bin/env python3.6 # -*- coding: utf-8 -*- """ An implementation of the Levenshtein distance """ from typing import List class Levenshtein: """ Compute the Levenshtein distance between two strings """ def __init__(self, s1: str, s2: str) -> None: self.s1 = s1 self.s2 = s2 self._l1 = len(s1) self._l2 = len(s2) self._mat = self._constructMat(self._l1, self._l2) @staticmethod def _constructMat(dim1: int, dim2: int) -> List[List[int]]: """ Get a list of lists of zeros for updating; re…

### Partial functions, currying and composition

I've been working through Functional Programming in Scala by Chiusano and Bjarnason lately, and it's been a really awesome book. This morning I worked on a few exercises on partial function application, currying and composition that I think demonstrate how powerful Scala can be. I just wanted to paste my solutions here and their translations to Python (3.6), because it's really cool and I'd love feedback on them.

Partial Function Application
First is partial function application. In Scala my solution to this exercise looks as follows.
object HOF_Testing { def partial[A, B, C](a: A, f: (A, B) => C): B => C = (b: B) => f(a, b) def main(args: Array[String]): Unit = { // Test this partial function method on an anonymous function val x = 5 val y = 6 println("** Partial function application: " + partial[Int, Int, Int](x, (u, v) => u + v)(y)) } } // ** Partial function application: 11 In Python we can achieve the same result…

### Fixing ImportError: No module named _ssl' while building Python from source in Ubuntu

This is just a reminder in case I ever come across this issue again.

Upon switching my Laptop's OS back to Ubuntu 16.04 today, I re-installed Python 3.6. Then I tried to pip install a module, and I found that the library ssl had a problem. The solution was, quite simply, to install libssl-dev (apparently this doesn't ship with Ubuntu), then rebuild Python 3.6.

### Automate content inclusion after a certain date in LaTeX

While writing my resume in $$\LaTeX$$ there were several events I wanted to add, but only after a certain date. Also, I don't want to wait until that date to include them; I want to type them up now, while I have time.

After a little research, I came across pgfcalendar. This page was probably the most helpful in describing its contents/functionality. It allows you to perform some action after, before, or on a certain date, in addition to a bunch of other things.

I've written the following macro utilizing this package. As an example date, we'll use PyCon (because I'm really hoping to be able to attend).
\usepackage{pgfkeys} \usepackage{pgfcalendar} \def\PyConDate{2017-05-17} % YYYY-MM-DD \newcommand\ifdateisbeyond[3]{% \pgfcalendarifdate{\year-\month-\day}{at least=#1} {#2} % if true {#3} % if false } We may use this command as follows.

### Iterators and Iterables in Python 3

Lately I've been examining the difference between iterators and iterables in Python more closely. There's a subtle but distinct difference between the two that's easy to overlook (or simply ignore); however, most every time you've typed a for-loop, such as for i in [1, 2, 3, 4, 5]: print(i), you've used both an iterable and an iterator.

According to the Python 3.6 documentation, iterator types define special methods __iter__ and __next__. Together these form something in Python called the iterator protocol. Moreover, __iter__ typically just returns self, so we only have to worry about writing a definition for __next__. While collections.abc already contains an abstract Iterator base class (see e.g. collections.abc.Iterator.__abstractmethods__), instead of importing it I'm going to write it as follows.
from abc import abstractmethod from typing import Any class Iterator: # c.f. PEP 234, PEP 322 @property @abstractmethod def _state(self) -> …

### RX Algorithm in C

Earlier this year I was trying to learn more C by working on a project formerly left over from drone club. After a couple weeks of toiling with memory leaks (Valgrind is an awesome tool), I finally came up with an implementation of the RX algorithm that's almost fast enough to be useful on a drone for basic anomaly detection.

The code is hosted on GitHub, and I welcome suggestions for improvements as C is definitely not my first language. I suspect there are many memory improvements that could be made; nevertheless, it can compute the Mahalanobis metric on one million RGB vectors in about 1/5 of a second.

As a test, I created the following video from data collected by Terry Sims. Even 4K frames only take about 2s to compute on my modest laptop.
The hardest part was probably figuring out how to read images from disk with libpng. I mostly read through the example.c file to understand how this library works.

I understand now that file specifications/formats are extremely intricate …

### Playing with monads in Python, 1

There are a number of topics in computer science that I have on my list of `stuff to understand at some point'. One of them is monads, which originally perplexed me when I came across Peter Thatcher's article about a year ago.

My favorite way to structure the code is to start with a base class Monad, which requires any subclass (type of monad we're defining, that is) to define methods bind and unit.
from abc import abstractmethod from types import FunctionType as Function class Monad: @abstractmethod def bind(self, f: Function) -> 'Monad': raise NotImplementedError def __rshift__(self, f: Function) -> 'Monad': return self.bind(f) @classmethod @abstractmethod def unit(cls, *args) -> 'Monad': raise NotImplementedError As Thatcher wrote in his own implementation, I've overloaded the special method __rshift__ to mean bind, which gets us closer to Haskell's syntax (>>=).

I liked…

### Professional Developer Tools for Students from JetBrains

If you're a student like me, you should definitely head over to JetBrains' site and sign up for their free professional developer pack. It grants you a year-long subscription to their products.

I've downloaded both PyCharm and CLion, and I look forward to using the latter more frequently. I've enjoyed using Vim, but the benefits of using these IDEs are that they teach you about the language as you're going along. PyCharm doesn't catch every bug in my code, but it catches nearly all minor issues, and many mid-level package issues too. I hope CLion will help as I learn more about C too.

### Clean simple FITS data

This won't be a lengthy discussion about methods to clean amateur astronomical FITS data; instead, since I've written about it before (albeit when I didn't know very much about Python), I'd rather post some new code I wrote to do the same process in a much clearer way.

#! /usr/bin/env python3.6 # -*- coding: utf-8 -*- """ Reduce a quick batch of FITS data. Currently run with input file list /home/brandon/Downloads/Astronomy_Data/V1283_Her/fixed_gain_V1283_Her_*.fit /home/brandon/Downloads/Astronomy_Data/V1283_Her/Dark-60s_*.fit /home/brandon/Downloads/Astronomy_Data/V1283_Her/Flat-V_*.fit -o _Finished_Feb_08_2016 """ from typing import Generator, Tuple from astropy.io import fits as FITS from astropy.io.fits import Header as HDU from argparse import ArgumentParser from glob import iglob from datetime import datetime import numpy as np _EXT = 'fits' def get_fits_file(name: str, axis: int =0) -> Tuple[np.ndarray, HDU]: &q…

### Making GUIs with Gtk+ in Python

While I was looking through old scripts the other day I came across one that produces a visual verification of Gauss' Circle Problem with Matplotlib. I thought it'd be fun to wrap it in a simple GUI with buttons to re-plot with different radii! The result is the following class.
#! /usr/bin/env python3.4 # -*- coding: utf-8 -*- """ Main application--embed Matplotlib figure in window with UI """ import gi gi.require_version('Gtk', '3.0') import numpy as np from gi.repository import Gtk, GObject from matplotlib.figure import Figure # make sure cairocffi is installed, pycairo doesn't support FigureCanvasGTK3Agg from matplotlib.backends.backend_gtk3agg import FigureCanvasGTK3Agg \ as FigureCanvas from matplotlib.patches import Ellipse from typing import List, Tuple, Union from math import sqrt class Main(Gtk.Window): """ Main window UI """ SIGMA = 10 INVERT = -1 def __init__…

### BST Implementation in Python

I've been going through John Washam's Google interview repo on GitHub and checking off concepts that I feel confident about. Because I don't use binary trees (BTs) in my code that often, I've felt that I need to brush up on them.

I wrote the following little implementation of the data structure in Python. While I'm more than comfortable with recursion, it's the base and edge-cases that can be tricky at times. For instance, when I was working with discrete convolution algorithms, recursively solving for the ranges over which to spatially iterate an image with each core in my laptop was more difficult to write than the convolution algorithm, and what I have there still isn't an optimal solution (e.g. what if the number of cores isn't a power of two?). [I think I'll attempt that again in the future.]

I'm still not positive I've weeded out all the errors. I'm writing unit tests though, and if I find any, I'll update it. I've written…