Showing posts from 2016

Don't forget to use unsigned char while working with bytes

The other day I made the mistake of using type `char` in a buffer accepting bytes read from an image file, specifically a PNG. The correct script is below for your perusal.
/* Test file reading and see if there's random data */ #include <stdio.h> #include <stdlib.h> #include <malloc.h> #define PNG_BYTES_TO_CHECK 8 int main(void) { char fname[] = "../images/2.png"; FILE *fp = fopen(fname, "rb"); if (fp == NULL) abort(); unsigned char *buffer = malloc(sizeof(char) * PNG_BYTES_TO_CHECK); if (fread(buffer, 1, PNG_BYTES_TO_CHECK, fp) != PNG_BYTES_TO_CHECK) abort(); unsigned i; for (i = 0; i < PNG_BYTES_TO_CHECK; ++i) printf("%.2X ", buffer[i]); printf("\n"); rewind(fp); free(buffer); fclose(fp); return 1; } The idea is to ensure that the 8 signature bytes match those of a valid PNG image, viz.
89 50 4E 47 0D 0A 1A 0A (the bytes 50 4E 47 represent ascii cha…

Getting two finger scrolling in Windows 7

I just wanted to write a quick post and highlight a cool GitHub project by Arkadiusz Wahlig that enables two finger scrolling. I've recently re-installed Windows 7 Professional on my laptop, and I miss the two finger scroll that was supported by Ubuntu/open source drivers.

The only thing it doesn't provide is natural scrolling--I'm still looking for a setting to reverse it.

Compiling and uploading Arduino C code over serial in Linux

I had a spare hour this evening so I decided to flex my bash skills and write a script that will compile and upload code you've written in C for your Arduino. I happen to have the Arduino UNO, so you may have to look up the values that correspond to your microcontroller by referencing the AVR options and hardware specs from Atmel. I originally got this idea by reading a post by Balau.
#! /bin/bash # Compile avr-gcc and upload via serial # ensure we're root user if [ $UID -ne 0 ] then echo "Must be root" 1>&2 exit 1 fi # ensure we have the correct number of arguments - only the first is used if [ $# -lt 1 ] then echo "** Must submit file for compilation" 1>&2 exit 1 elif [ $# -gt 1 ] then echo "** Warning: only using first argument as file name" fi check_compilation() { # check if there are input arguments use them as error message if [ $# -eq 1 ] then FNAME=$1 if ! [ -e $FNAME ] …

Recovering your Python 3 code from its *.pyc

There aren't many ways to (attempt to) recover your source after you've made the classic mistake of typing rm <some file> in the Linux terminal.

That's what I did early this morning, when I should have been sleeping.

After looking into a few command line tools, I found that pycdc worked wonderfully for converting files __pycache__/*.pyc in the directory your Python source was located. I looked into bash tools like foremost, but it required a config file in /etc, and it's not straightforward/intuitive regarding how to locate Python scripts in memory (after all, it's just a text file, there aren't any file signatures; maybe just special characters like #! or """).

The only negative side effect was that all of my comments and annotations were gone, which is a small price to pay for getting most of my code back!

Subsampling image arrays in Python

Recently, as I was writing a class that performs Dokkum's algorithm for cosmic ray detection, I came across a nifty math trick. One of the steps is to subsample the image. At first thought, one may interpret that word as meaning that the image will be scaled down.

Au contraire.

By subsample the author actually means to subsample an individual pixel to a square array of pixels before convolution, each the same count as the original. So if we had an array that looked like
our goal (if we wish to subsample only once) is to make it look like
\begin{align}B=\begin{bmatrix}a&a&b&b&c&c\\a&a&b&b&c&c\\d&d&e&e&f&f\\d&d&e&e&f&f\\g&g&h&h&i&i\\g&g&h&h&i&i\end{bmatrix}.\end{align} This is where the Kronecker product comes in. It was an odd step at first because I usually don'…

Extract numbers from a random string and sum them

I came across a link to this simple problem while I was surfing SO, listed here, and thought I'd write a pretty complete little script in Python 3.
#! /usr/bin/env python3.4 # -*- coding: utf-8 -*- """ Extract numbers from a string and sum them """ import re import random from string import ascii_lowercase, digits def randomString(length: int =0) -> str: """ generate a random string with ascii digits and characters """ base = ascii_lowercase + digits return ''.join(random.choice(base) for _ in range(length)) def sumNumbers(string: str ='') -> int: """ Sum numbers in a string """ numbers = re.findall('[1-9]+', string) # show it print('Numbers: ', end='') for n, num in enumerate(numbers): numbers[n] = int(num) print(num, end=' ') else: print() return sum(numbers) if …

Finding domain names with Python

There was a hackathon at my University this past weekend and one of the benefits of attending was a free domain, courtesy of Choosing a domain name is hard, and I've owned about half a dozen of them or so. However, I was curious to know if there were any 3 letter DNs that weren't registered. As it turns out, there are only \(\displaystyle\binom{26}{3}=2600\) combinations, so searching all of them is more than within reach.
This is a quick Python script I whipped up that I'm sure could be drastically expanded upon and improved. It just prints the DNs one by one as it determines that the expiration date is less than the current date (if that's possible...I don't think that's a good method) and if it doesn't have a listing with whois, which seems to be the case the majority of the time, it's printed as well.
#! /usr/bin/env python3.4 # -*- coding: utf-8 -*- """ Iterate over all 2600 3 letter domain names x3 for .net, .org and .c…

Binary Search in Python and C

Earlier this year I was writing a Python script wherein I had to search a two dimensional grid of longitude and latitude values to retrieve the correct elevation at that point. I originally started with linear search, but it became evident when that grid became fine enough that linear search was wasting precious time. Instead, I read up on binary search (also, interpolation search, which is even faster given that the data are evenly distributed, but that's a topic for a future post).

Binary search will locate a point in a sorted array in \(\mathcal{O}(\log(N))\) time. If you're curious about the mathematics/reasoning for this conclusion, see this answer on SO; I'll paraphrase the logic here, because it's really quite interesting.

Binary search works by starting in the middle of the array, as opposed to either end. Next, we ask, is the entry we're looking for greater than, less than, or equal to the current one? If it's greater, we move to the middle of the upp…

Matrix multiplication in Python

Linear algebra is absolutely everywhere, and many algorithms and data structures use this basic mathematical operation. There are several ways we can multiply arrays of data together in Python - some slow, and some extremely efficient/fast.

First and foremost, we have NumPy's dot method, which multiplies two arrays together (I, however, tend to write something along the lines of from numpy import dot as mult, so the fact that it's a matrix multiplication is more obvious). EDIT: It should also be noted that in Python 3.5+, the __matmul__ method defines the @ infix operator, so instead of, arr2), we may write arr1 @ arr2 (c.f. PEP 465).

We may also use NumPy's einsum method, which was recently brought to my attention by a friend. For example, given two matrices:
>>> X = np.random.randn(4, 4) >>> Y = np.random.randn(4, 4) >>> X array([[ 1.65507608, -0.39287161, -1.05303575, -0.61274276], [-0.88893625, -0.06474647, 0.78705911, 2…

Bubble Sort in C and Python

This blog is just going to be filled with programming/algorithm examples, which are sometimes thorough, and sometimes not.

Here's an example of bubble sort in Python (probably easier to understand than C).
#! /usr/bin/env python3.4 # -*- coding: utf-8 -*- """ A quick implementation of Bubble Sort """ from random import randint from array import array from typing import Iterable from types import FunctionType def checkReturnArray(f: FunctionType) -> bool: """ Decorator to ensure array has been sorted """ def new_f(*args, **kwds) -> bool: res = f(*args, **kwds) for i in range(len(res) - 1): if (res[i] < res[i + 1]): return False else: return True return new_f @checkReturnArray def bubbleSort(arr: array =array('I', [0])) -> Iterable[int]: """ O(N^2) time complexity """ arrLength = len(a…