Tag Archives: programming

An Odd Conversation

People in America are charmingly direct, and Bostonians even more-so. Perhaps it is because I am a foreigner but I have had more random conversations in the last 3 months than in all the years I lived in Auckland.

The following slice-of-life took place during my walk in The Blue Hills Reservation. I was climbing up a narrow, rocky incline when I stopped to let a group of older people scramble down. One of the group, a man of about 60, apologized for the delay and I told him I didn’t mind. He immediately picked up on my accent.

Man : English or Australian?
Me : New Zealander (This is not unusual, for some reason the New Zealand accent sounds very English to America ears)
Man : Visiting?
Me : No, I have been living here for the last 3 months.
Man : Engineer?
Me : Sort of, computer programmer
Man : What language?
Me : C++ mainly
Man : What data structures do you use?
Me : What?
Man : You know, data structures!
Me : … well it depends.
Man : Binary tree?
Me : Yes
Man : Linked list?
Me : Sure
Man : Prefix tree?
Me : umm, not sure about that one…
Man : OK, have a nice day

It turns out that Prefix Tree is just another name for a Trie. If that is what he meant then I have implemented a prefix tree as an experiment at a previous job. It didn’t work out, tries have a lot of overhead.

I wonder what would have happened if I had said yes.

Finding the Dimensions of a JPEG file in Python

For a project I am working on I had to quickly throw together a Python function to grab the width and height of JPEG files on disk. There is nothing in the python standard library to do this and although some third party projects that read JPEG files (micro-jpeg-visulaizer, PIL) they seem like overkill if all you want are the dimensions.

A quick trip to the JPEG standards document provided the information I needed. In case anyone else needs something similar, here is what I came up with:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from struct import unpack
 
def GetWidthAndHeight(stream):
	""" Extract the dimensions from a jpeg file as a tuple (width, height)
 
	Keyword arguments:
	stream -- a stream (eg: open()ed). Must be opened in binary mode
 
	Author: Andrew Stephens http://sandfly.net.nz/
	License: use in any way you wish
	"""
	while (True):
		data = stream.read(2)
		marker, = unpack(">H", data)
 
		# some markers stand alone
		if (marker == 0xffd8):	# start of image
			continue
		if (marker == 0xffd9):	# end of image
			return;
		if ((marker >= 0xffd0) and (marker <= 0xffd7)):	# restart markers
			continue
		if (marker == 0xff01): # private marker:
			continue
 
		# all other markers specify chunks with lengths
		data = stream.read(2)
		length, = unpack(">H", data)
 
		if (marker == 0xffc0):	# baseline DCT chunk, has the info we want
			data = stream.read(5)
			t, height, width = unpack(">BHH", data)
			return (width, height)
 
		# not the chunk we want, skip it
		stream.seek(length - 2, 1)

This should be quicker than other solutions since it skips over parts of the stream it doesn’t need and is flexible enough to work on anything that looks like a seekable file. Beware, it may misbehave on malformed files.

Usage is simple:

1
2
3
f = open("somepicture.jpg", "rb")	# need to open the stream in binary mode
w, h = GetWidthAndHeight(f)
f.close()

An Open Letter to IT Recruiters

Dear Recruiters,

I realise that yours is a difficult job and that sometimes you have to quickly hustle to fill a position. I have always admired the way you manage to extract money by mediating contact between two parties in a manner that would make a real estate agent blush with shame.

And I also know that I am on shaky ground criticising other people’s writing style since mine is best characterised as shoddy and barely coherent. However…

Recruiters, you are in an industry that has direct consequences on people’s lifestyles and financial health. The IT industry has a well deserved reputation for informality but I like to think the people who may be responsible for my future employment are taking things seriously. I am all for individual expression and colloquialism but there is a time for formal writing. Please do not use txtspk in an unsolicited introductory email.

Hi Andrew Found you on a search, will you be looking for a new role this yr? Appreciate you’re in Auckland so this may not be of interest; I’m seeking a Developer with sockets programming exp, knowldge of Network protocols, & good C# skills for a WLG role if you know anyone pls? rgds [redacted]

Yours faithfully,
Andrew Stephens

A (Horrible) Method of Hard Resetting an Arduino

Ethernet ArduinoLast year I worked on a little home project involving an Arduino Ethernet board. It all worked perfectly except that my program would hang after a few days operation. The time to failure wasn’t consistent, sometimes it failed after only a couple of hours, often it took a week. But sooner or later it would stop sending data across the network and require a hard reset. Adding logging told me only that it was the network code that was stuck.

It turns out that this is a common problem with the Arduino Ethernet hardware. The fancy pants W5100 TCP/IP chip just goes on strike and needs to be reset. Using the Arduino’s watchdog interrupt to software reset the CPU isn’t enough, the W5100 needs to reset as well.

Reading the schematic provided a clue. The W5100′s reset line is connected to the normal Arduino reset line (via a small reset controller IC), so resetting the Arduino by pulling the RESET line low resets the network chip as well.

There is a right way to do this that involves a bunch of extra circuitry, and a wrong way that involves a piece of wire.

Photo of Arduino showing a wire soldered to the reset pin
Connecting the reset pin to one of the Arduino’s digital IO pins is not recommended. The CPU requires that the reset line is help low for a certain amount of time to reset correctly and it can’t hold the line low and reset simultaneously. That wouldn’t make sense. Except that when I tried it the CPU reset every time and took the network chip with it. There is a capacitor between the RESET pin and GRD that I think helps out here, but my electronics is very weak.

I am still making use of the watchdog interrupt but instead of letting it reset the CPU, I handle the interrupt and bring the RESET line low using the digital IO pin.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <avr/wdt.h>
 
#define RESET_IO_PIN 3
 
void setup()
{
	//  Some people recommend setting the IO pin to HIGH on start up
	//  but it is better to leave it floating as INPUT. Pulling it HIGH interferes 
	//  with the normal reset mechanism, and the pin is held HIGH by a pull-up   						  
	//  resister anyway
	//  digitalWrite( RESET_IO_PIN, HIGH );
	//  pinMode( RESET_IO_PIN, OUTPUT );
 
	noInterrupts();
	wdt_reset();
	// these cryptic lines set the watchdog timer control register
	// to trigger an interrupt (not reset) after 8 seconds. The normal
	// Arduino function assumes you want to reset, so we can't use it here.
	// See the ATmega328P Datasheet section 10.9.2 for the gory details
	MCUSR &= ~(1<<WDRF);
	WDTCSR |= (1<<WDCE) | (1<<WDE);
	WDTCSR = (1<<WDP0) | (1<<WDP3) | (1<<WDIE); /* 8.0 seconds */
	interrupts();
}
 
ISR(WDT_vect)
{
	// The watchdog timer has fired, pull the pin low
	digitalWrite( RESET_IO_PIN, LOW );
	pinMode( RESET_IO_PIN, OUTPUT );
}
 
 
void loop()
{
	wdt_reset();
	// do some stuff here, if you don't call wdt_reset() more frequently
	// than 8 seconds the Arduino will reset
}

I spent weeks trying to figure out what was going on, hopefully this post will help somebody in the same situation.

Jumping Frogs – Using Python to Solve Puzzles

A few months ago I came across the following puzzle in a video game I was playing:

The starting position for the siz frogs puzzleThree frogs are happily hopping along a narrow board together when they meet another group of three frogs traveling in the opposite direction. These frogs can only move in the direction they are facing, and only if there is a space directly in front of them. Additionally, a frog can jump over the frog in front but only if there is clear space on the other side to land in.

How can the frogs (moving one at a time) pass each other and continue on their way?

Of course, this is a hoary old puzzle that most people come across and solve as children. It should be only a couple of minutes work with a pen and paper to confirm that it is possible to exchange both sets of frogs but I wouldn’t be much of a programmer if I used a piece of paper where hundreds of dollars of computer equipment would do just as well.

To solve a puzzle like this programatically requires three things: a representation of the current state of the problem, a way of generating every possibly legal move from a given position, and a way of figuring out when is a good time to stop.

Firstly, the representation of the board is a simple python list:

1
start = [1, 1, 1, 0, -1, -1, -1]

Frogs traveling right or left are represented by “1″ and “-1″ respectively. Empty spaces that frog can move into are represented by “0″. The advantage of this representation is that you can calculate the new position of a frog by:

1
newPos = pos + (representation * distance)

where pos is the current index in the array, distance is the size of the hop (either 1 or 2) and representation is either 1 or -1.

Next, we need a way of generating legal moves for a given position:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def legalMoves(board):
	moves = []
	for pos, piece in enumerate( board ):
		jumpmove = pos + (piece * 2)
		move = pos + (piece)
		if ( piece == 0 ):
			continue
		if (not (( jumpmove < 0 ) or ( jumpmove >= len(board)))):
			if (board[jumpmove] == 0):
				t = list(board)
				t[pos] = 0
				t[jumpmove] = piece
				moves.append(t)
		if (not ((move < 0) or ( move >= len(board)))):
			if ( board[move] == 0):
				t = list(board)
				t[pos] = 0
				t[move] = piece
				moves.append(t)
	return moves

Now we need a way of keeping track of all board positions we have seen, so once we find the target we can print the states that led to the solution:

1
2
3
4
5
6
7
8
9
10
11
def evalAll( current, target ):
	next = []
	for a in current:
		n = legalMoves(a[-1])
		for q in n:
			t = list(a)
			t.append(q)
			if ( q == target ):
				return t
			next.append(t)
	return next

This code keeps a list of lists, each sublist being it’s own list of the sequence of moves investigated so far. For each sequence of moves, the next legal moves are discovered and new sequences are added to be investigated the next time this function is called. Technically this is called a breadth-first search because at all of the current legal moves are investigated before moving on the next stage. This is a very simplistic way of doing the job, but in this case the puzzle is small enough that it works well enough.

Finally, a simple wrapper that we can use to set things up and return the final result.

1
2
3
4
5
6
7
def solve(start):
	temp=[[start]]
	end = list(start)
	end.reverse()
	while(temp[-1] != end):
		temp = evalAll(temp, end)
	return temp

So now we can do this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
print solve([1, 1, 1, 0, -1, -1, -1])
 
[[1, 1, 1, 0, -1, -1, -1],
 [1, 1, 0, 1, -1, -1, -1],
 [1, 1, -1, 1, 0, -1, -1],
 [1, 1, -1, 1, -1, 0, -1],
 [1, 1, -1, 0, -1, 1, -1],
 [1, 0, -1, 1, -1, 1, -1],
 [0, 1, -1, 1, -1, 1, -1],
 [-1, 1, 0, 1, -1, 1, -1],
 [-1, 1, -1, 1, 0, 1, -1],
 [-1, 1, -1, 1, -1, 1, 0],
 [-1, 1, -1, 1, -1, 0, 1],
 [-1, 1, -1, 0, -1, 1, 1],
 [-1, 0, -1, 1, -1, 1, 1],
 [-1, -1, 0, 1, -1, 1, 1],
 [-1, -1, -1, 1, 0, 1, 1],
 [-1, -1, -1, 0, 1, 1, 1]]

Success!

You might say this is a waste of time since you figured out the problem in your head. Good for you, but try this on for size:

1
[1, 1, 1, 1, 1, 1, 1, 1, 0, -1, -1, -1, -1, -1, -1, -1, -1]