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]

Arduino POV Device Part II

Last week I wrote about starting with digital electronics with the Arduino prototyping platform. Getting something working was easy enough but I was dissatisfied with ugly result, especially when my friend Lloyd showed up with his extremely tidy version of the same idea. The piece of cardboard had to go!

My first version used a breadboard and uncut LED leads because I thought that I would want to dismantle the components for reuse. However I have since realised that I am a grown man with a career and can easily afford the $4.50 material cost. Behold POV version 2:



I won’t be entering this in any soldering competitions but it works OK.

The code has also changed. Compiling in what amounts to a 2D bitmap was a quick way to get something up and running but it wasn’t very flexible, especially since in the future I want to display long strings of text. This means storing glyphs (letter shapes) for every letter of the alphabet (plus digits and symbols) – what I needed was a proper font; what I got was this:

I then turned to Python to generate the program data to embed in the new Arduino code. This script slices the image vertically, generating one byte (actually only 7 bits) for each slice of pixels. What comes out is a long list of byte values that can be output directly to the Arduino’s IO pins to display each section of the text, along with a set of indexes that map letters to the start and end positions of individual glyphs in the array.

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
40
41
42
43
44
45
46
47
48
49
50
51
52
import sys
 
def GetSlice(i, pos):
	t = 0
	for q in range( pos, len(i), len(i) / 7 ):
		t = t * 2
		if ( i[q] != '\x00' ):
			t = t + 1
	return t
 
def GetGlyph( i, pos ):
	end = pos
	start = pos
	data = []
	while (end < len(i) ):
		t = GetSlice( i, end )
		if ( t == 0 ):
			break;
		data.append( t )
		end = end + 1
	return (start, end, data)
 
def GetFont( d ):
    result = []
    i = 0
    currentIndex = 0
    indices = []
    while ( i < len(d) / 7 ):
	(start, end, data) = GetGlyph( d, i )
	if ( len(data) == 0 ):
		break
	i = end + 1
	indices.append( currentIndex )
	currentIndex = currentIndex + len(data)
	result.extend( data )
    return ( result, indices )
 
if __name__ == '__main__':
    if ( len(sys.argv ) != 3 ):
        print "USAGE: program <input> <output>"
        exit()
    data = []
    i = file( sys.argv[1], "rb" )
    data = i.read()
    i.close()
    ( d, indices ) = GetFont( data )
    o = file( sys.argv[2], "w" )
    o.write( "static const int indices[] = { " + ",".join(map(str, indices ) ) + " }; ")
    o.write("\n")
    o.write( "static const unsigned char fontdata[] = { " + ",".join(map(str, d)) + "};")
    o.write("\n")
    o.close()

This scheme is more complex that the original bitmap but allows arbitrary text to be display without lots of editing. The modified Arduino code now looks like this. The first two lines contain the new font data, and you can see that the text to display is simply declared on line 5.

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
static const int indices[] = { 0,4,8,12,16,19,22,26,30,33,37,42,45,52,59,63,67,71,75,79,82,86,91,96,101,106,111,116,121,126,131,136,141,146,151,156,161,163,165,167 }; 
static const unsigned char fontdata[] = { 63,72,72,63,127,73,73,54,62,65,65,34,127,65,65,62,127,73,65,127,72,64,62,65,69,39,127,8,8,127,65,127,65,2,1,1,126,127,8,20,34,65,127,1,1,63,64,64,60,64,64,63,127,32,16,8,4,2,127,127,65,65,127,127,72,72,48,62,65,71,62,127,72,76,51,50,73,73,38,64,127,64,126,1,1,126,112,12,3,12,112,126,1,15,1,126,65,54,8,54,65,96,16,15,16,96,67,69,73,81,97,62,69,73,81,62,17,33,127,1,1,71,73,73,73,49,65,65,73,73,54,24,40,72,127,8,121,73,73,73,6,62,73,73,73,6,65,66,68,72,112,54,73,73,73,54,48,73,73,73,62,3,3,123,123,27,27,127};
 
static int outputPins[] = { 12, 11, 10, 9, 8, 7, 6 };
static char text[] = "ANDREW";
 
void setup()
{
  for (int i = 6; i<=12; ++i)
  {
    pinMode(i, OUTPUT);     
    digitalWrite(i, HIGH);
  }
  pinMode(13, OUTPUT);
  digitalWrite(13, LOW);
  delay(2000);
}
 
void loop()
{
  byte row = 0;
  byte endRow = 0;
  char* currentChar = text;
 
  while (1)
  {
    if (*currentChar == 0)
      currentChar = text;
    if ( row == endRow )
    {
        char t = *currentChar;
        currentChar++;
        t = t - 'A';
        row = indices[t];
        endRow = indices[t+1];
    }
    while (row != endRow)
    {
      byte mask = 64;
      for (byte pin = 0; pin < (sizeof( outputPins) / sizeof(outputPins[0])); ++pin )
      {
        digitalWrite( outputPins[pin], (fontdata[row]&mask)? HIGH : LOW  );
        mask = mask / 2; // divide mask by two, moving it down one bit
      }
      row++;
      delay(1);
    }
    for (byte pin = 0; pin < (sizeof( outputPins) / sizeof(outputPins[0])); ++pin )
    {
      digitalWrite( outputPins[pin], LOW);
    }
 
    delay(1);
  }
}

Still to do: This code is not very efficient. It uses digitalWrite() in a loop to turn on the LEDs. digitalWrite() is very easy to use but if you look at the source code you will see it does all sorts of unnecessary stuff for this job. I plan to replace it with direct writes to the required Arduino IO registers.

I also want to make the whole thing interrupt driven to free up the CPU. Why would I want the extra CPU time? I have plans for that as well…

Starting with Arduino

I have a new hobby – digital electronics! Last week I bought an Arduino Uno on a whim from JayCar. Being a typical programmer, I have very little idea how computers actually work on the physical level so this gives me an easy introduction to lower-level coding and electronics in general.

The Arduino is a small board with a fairly capable 8 bit microprocessor (an ATmega328 to be precise) with the IO pins hooked up to convenient headers ready for attaching external devices. The CPU has its own RAM and programmable flash memory, and it comes with a bootloader that can reprogram the flash via the handy USB connection (which can also power the whole board). It is hard to imagine a more plug-n-play device.

I decided that I would follow the well-worn path and create a persistence of vision device for my first project. Mine consists of 7 LEDs hooked up to IO 7 pins (via appropriate resistors), the idea is to make the LEDs blink in such a way that recognisable shapes appear as the LEDs are waved quickly in front of your eyes.

My prototype is a little rough, but works fine in a darkened room (I was too cheap to spring for super bright LEDs and the darkness hides my shoddy soldering job.) The breadboard is too fragile to wave around so the LEDs are mounted on cardboard and connected using a couple of metres of CAT5, which conveniently has 8 internal wires to supply the 7 LEDs with a common ground. The total cost is less than $10, excluding the breadboard and the Arduino itself.

The Arduino programming environment is pretty nifty. The language used is a limited form of C++ (no standard library or runtime support for much of anything) with some extra libraries for managing the CPU’s features. Compiling and flashing the CPU is as simple as pushing a button. Here is the code that generated the above picture:

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// Array holding the graphic to display
static char* text[] = {
" XX   X     X  XX     XXXX   XXXX  X     X     ",
"X  X  XX    X  X  X   X   X  X     X     X     ",
"X  X  X X   X  X   X  X   X  X     X     X     ",
"XXXX  X  X  X  X   X  XXXX   XXX   X  X  X     ",
"X  X  X   X X  X   X  X X    X     X  X  X     ",
"X  X  X    XX  X  X   X  X   X     X  X  X     ",
"X  X  X     X  XXX    X   X  XXXX   XX XX      " };
 
static int outputPins[] = { 12, 11, 10, 9, 8, 7, 6 };
static int graphicLength;
 
 
void setup()
{
	// setup the initial state of the pins
  for (int i = 6; i<=12; ++i)
  {
    pinMode(i, OUTPUT);     
  }
	// pin 13 is hardwired to the onboard LED, turn it off
  pinMode(13, OUTPUT);
  digitalWrite(13, LOW);
 
  graphicLength = 0;
  for (char* t = text[0]; *t!=0; ++t)
  {
    ++graphicLength;
  }  
}
 
void loop()
{
  while (1)
  {
    for (int i = 0; i < graphicLength; ++i )
    {
		// find out if the pin is supposed to be on (HIGH) or off (LOW)
      for (int pin = 0; pin < (sizeof( outputPins) / sizeof(outputPins[0])); ++pin )
      {
        if (text[pin][i] == ' ')
        {
          digitalWrite( outputPins[pin], LOW );
        }
        else
        {
          digitalWrite( outputPins[pin], HIGH );
        }
      }
      delay( 1 );
    }
  }
}

Not very efficient but simple enough to get going. I am already working on a more functional version which will have its own font and interrupt driven display.

A Better Boost Book

Boost is a excellent resource for C++ programming, but suffers from inconsistent documentation and a daunting array of sub-projects. Trying to make sense of it all is a fairly serious undertaking. I tried to get my head around it by writing my occasional series of boost blog posts, but now I see that somebody has done a much better job.

The Boost C++ Libraries is a free book that clearly explains some of the more generally useful boost libraries, with lots of useful examples. It even covers advanced libraries like ASIO in an approachable way. I highly recommended bookmarking it if you do any C++ programming.

The HTML5 audio tag

I have been mucking around with the audio tag as part of my quest to understand where HTML5 is going. The <video> tag gets all the press but I think there are many more opportunities to use audio in web apps. HTML5 is closing the gap between plugin-based apps (Flash, Silverlight, Java, etc) and sound support is an important part of that goal.

(Those of you who don’t care how it works should go directly to the TV Themes demo puzzle. It works best in Firefox3.6 and the latest version of Safari, although most browsers should function to some degree.)

The audio tag is pretty flexible, able to handle both long form audio (songs and spoken passages – the theme medley on the demo page for example) and short snippets of background audio (alerts, and confirmations – the demo plays one of two short tones when you type an answer. Video game sound effects are another example.) Optionally, the audio tag can provide a user interface for starting and stopping the audio, useful for playing long streams of audio. Different browsers have different ideas about how this should look, but they all function much the same way.

In theory, the audio tag is as easy as embedding an image into HTML:

1
2
3
4
<audio controls>
	<source src="music.mp3">
	You can put HTML here that will be displayed if the browser does not understand the audio tag
</audio>

However, the devil is in the details. There are two problems with the audio tag that complicate matters. The first is that only the very latest browsers support the audio tag at all. This means that if you want to provide audio that everyone can use, you are going to have a fall-back method available. Before the audio tag, people used to use Flash for this purpose and it still works. A number of sites provide simple Flash-based audio players that you can embed – I ended up using the player provided by Google.

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
<object codebase="http://fpdownload.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=7,0,0,0" height="27" width="400" align="middle" classid="clsid:d27cdb6e-ae6d-11cf-96b8-444553540000">
	<param name="_cx" value="10583"><param name="_cy" value="714"><param name="FlashVars" value="">
	<param name="Movie" value="http://www.google.com/reader/ui/3247397568-audio-player.swf?audioUrl=http://full/path/to/music.mp3">
	<param name="Src" value="http://www.google.com/reader/ui/3247397568-audio-player.swf?audioUrl=http://full/path/to/music.mp3">
	<param name="WMode" value="Window"><param name="Play" value="0">
 
	<param name="Loop" value="-1">
	<param name="Quality" value="High">
	<param name="SAlign" value="LT">
	<param name="Menu" value="-1">
	<param name="Base" value="">
	<param name="AllowScriptAccess" value="never">
	<param name="Scale" value="NoScale">
	<param name="DeviceFont" value="0">
	<param name="EmbedMovie" value="0">
 
	<param name="BGColor" value="">
	<param name="SWRemote" value="">
	<param name="MovieData" value="">
	<param name="SeamlessTabbing" value="1">
	<param name="Profile" value="0">
	<param name="ProfileAddress" value="">
	<param name="ProfilePort" value="0">
	<param name="AllowNetworking" value="all">
	<param name="AllowFullScreen" value="false">
 
	<embed type="application/x-shockwave-flash" src="http://www.google.com/reader/ui/3247397568-audio-player.swf?audioUrl=http://full/path/to/music.mp3" allowscriptaccess="never" quality="best" bgcolor="#ffffff" wmode="window" flashvars="playerMode=embedded" pluginspage="http://www.macromedia.com/go/getflashplayer" height="27" width="400" />
</object>

Not exactly elegant, is it? Apart from being uuuuug-ly, the full URI of the sound file must be used (the audio tag can use relative paths). Also, the Flash players are not scriptable in the same way as inbuilt audio tag is, which can make doing tricky stuff like animating other content in response to the audio more difficult.

The second problem with the audio tag is the same codec problem I talked about in a previous rant (The HTML5 Video Tag’s Fatal Flaw) For legal reasons, different browsers play different formats of audio – most notably Firefox will not play mp3s while Safari will not play ogg. There is no single format that will play in all browsers except for uncompressed wavs, which are too fat to be useful except for very short snippets.

To get around this problem the audio tag allows multiple files to be specified. The first file that the browser thinks it can play will be used, but it does mean you have to encode and store multiple versions of each audio file.

1
2
3
4
5
<!-- Only one of these files will be downloaded -->
<audio controls>
	<source src="music.ogg" type="audio/ogg">
	<source src="music.mp3" type="audio/mpeg">
</audio>

The demo page also uses the audio tag to play sound effects in the background, using audio elements that do not have a user interface. For simplicity I used wav files (download from this awesome source of free effects.) Since they have no user interface, Javascript must be used to play them:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
<audio id="clicksound" preload="auto">
	<source src="click.wav" type="audio/wav">
</audio>
 
<script type="text/javascript">
function playSound( )
{
	var a = document.getElementById( "clicksound" );
	if ( !a ) return;
	if ( !a.play ) return; // will exit if the browser does not understand the audio tag
 
	a.play();
}
</script>

It is all pretty simple but as always there are problems. I did not find a good way of replicating this using Flash, so browsers that do not understand the audio tag do not play these background noises. Also, Google Chrome (which has otherwise excellent support) contains a weird bug that prevents it playing the first couple of seconds of an audio file, making it useless for short sounds. Apparently Firefox3.5 had the same problem, but it works perfectly in 3.6.

I created the demo to see if the audio tag could replicate the functionality of Flash-based applications for both long-form audio and background sound effects. It does seem to be possible provided you are targeting a modern browser and are prepared to work around certain annoyances. Hopefully the next few years will see an improvement in support for audio, I can see many uses for it especially if the iPad (which does not support Flash) takes off.

Using Exceptions in C++

C++ is big – it has been said that any given programmer only ever uses about 40% of the language’s features. The trouble is that it is a different 40% for each person. Exceptions are a great example of this, some people swear by them while many coding standards specifically ban/discourage them (cf: google, mozilla). It is ironic that a feature designed to make code safer is sometimes regarded as being too dangerous to use.

Personally I like exceptions, but even I realise that they have there limitations. This post is an attempt to formalise some guidelines about when exceptions should be used and when they should be avoided beyond the usual language rules. I should mention at this stage that most of my experience is in desktop client/server software. C++ is used in all sorts of places these days, and what works on desktops and beefy servers may not suit the embedded world (for example).

When to Catch

My rule of thumb is “Do not let exceptions escape from a function you didn’t explicitly call yourself“. This includes destructors, callbacks, thread functions, WNDPROCs, and any other miscellaneous way your functions can be entered (it does not include constructors or virtual functions – exceptions are very useful in those). In general, all these things should catch and handle all exceptions.

Your program will die if an exception escapes a thread. If you are lucky your runtime will do something clever and your program will die painlessly but possibly the OS will have to dispatch the process messily. Either way, your users will not be impressed, so you should always wrap thread functions in try{}catch blocks. In the best case you might be able to signal that an operation failed to the main thread, which can restart it if required. In the worst case you can at least log what happened before exiting.

Lots of third part libraries communicate with your code using callbacks that you supply. You should always ensure that any exceptions are caught before returning back into third party code, since you can never be sure if the library does the right thing. C style libraries like LibCURL are right out, they will probably leak handles and memory as the stack is unwound. C++ libraries may (or may not) be better but could do things you do not expect, like swallow the exceptions themselves instead of letting them fall through (boost::iostreams). Also, some libraries actually call you back on a different thread (boost::asio) so the advice in the previous paragraph also applies here.

You should always be prepared to catch any exceptions that are documented by any C++ libraries you use, especially things like boost::filesystem which can throw at any time.

What to Throw

My advice is to create a small hierarchy that is derived from std::runtime_exception unless you are already using a custom exception class. Don’t try to get clever and throw std::string or char*. Design your hierarchy around how the exceptions are to be handled, rather than what can go wrong. For instance, if there are 5 different ways your program throw exceptions, but only 3 different things that can happen in response then you only need 3 types of exceptions.

In my experience, exceptions fall into two categories: recoverable and fatal. Recoverable exceptions will be caught within a layer, or perhaps the next layer up which can then reattempt the operation (or perhaps just log and ignore the problem if the operation was not crucial.) Fatal errors are usually not caught until the outer loop of the program, where they are logged before the program can be shutdown cleanly. In general, the exceptions you expect to recover from should derive from exceptions you expect to be fatal.

I tend to name my exception types based on how they are handled and what circumstance they represent, like so:

1
2
3
4
5
6
7
8
9
10
11
12
13
class UnrecoverableFileReadException : public std::runtime_error
{
	// thrown when a file cannot be read correctly, ie: the file exists but is misformatted
public:
	UnrecoverableFileException( const std::string& msg ):std::runtime_error(msg) {};
};
 
class FileReadException : public UnrecoverableFileReadException
{
public:
	// thrown when a file cannot be read but the user can be prompted to select another file
	TemporaryFileException( const std::string& msg ):UnrecoverableFileReadException(msg) {};
};

When throwing, always construct the exception with a sensible message if only for logging and debugging purposes. Normally this message would not be shown to the user since it will be hard to localise. Add additional members to your exception class if you want to include other information with the exception. Just remember that exceptions must be copyable.

1
2
3
ostringstream oss;
oss << "Could not open file " << filename << " the error was: " << errno;
throw TemporaryFileException( oss.str() );

If you really want to go the whole hog consider using boost::exception which builds upon similar ideas.

When to Throw

Exceptions should never be thrown if everything is running perfectly. Only when something goes wrong should throwing an exception be considered an option. I have seen code that threw exceptions to signal the end of an enumeration or to signal that the results of a query were empty – I consider these examples to be a terrible use of the feature. Remember that an exception is not just an error, but something really outside of normal program flow.

I also tend not to use exceptions for logic errors. If an algorithm can fail then the calling code should be prepared to handle a return code signalling an error. Likewise I would not throw if a database query returned no results – an empty result set is inside the bounds of normal program flow. However, I would consider throwing an exception if the query failed due to the database being unavailable.

The best places to use exceptions are in situations where your program is using resources that are not under your control, including anything to do with IO. Both files and network connections exist outside of your program and can become unavailable at any point due to any number of reasons. In many cases the problems are transient and all your program needs to do is try again in a few minutes – a program that quits each time the DNS, directory server, or external database cannot be reached will not survive for very long in any production environment. Exceptions allow you to back out of an operation without too much trouble and handle the problem in a sensible location.

One problem you might encounter is that is often hard to retrofit exceptions into code that wasn’t designed for them. In this case, my advice about not letting exceptions fall through 3rd party code also applies to legacy code that you own. This is not to say that you cannot use exceptions at all, just that you may have to take steps to keep exception handling within the layers of your application.

UIButton.titleLabel is not as useful as it looks

I have been doing some iPhone development lately. Nothing too amazing, just some test apps to get a feel for the system. Now, some people will tell you that Cocoa Touch is an API sent from God and frankly it is pretty good (especially given what passes for UI on other embedded devices), but that doesn’t mean it doesn’t have some annoyances.

Here is something that tripped me up for a while. The UIButton class has a property called titleLabel which (obviously) returns the UILabel that is used to display the text of the button. You can use this property to modify the parameters of the label, like so:

1
2
3
m_addButton.titleLabel.font = [UIFont systemFontOfSize: 7];
m_addButton.titleLabel.textColor = [UIColor blackColor];		 
m_addButton.titleLabel.textAlignment = UITextAlignmentRight;

What you can’t do is this:

1
m_addButton.titleLabel.text = @"Add Stuff";

Although nothing I have found in the documentation says so, the text of the button cannot be set from the titleLabel property. What you have to do is this:

1
[m_addButton setTitle:@"Add Stuff" forState: UIControlStateNormal];

Setting the title this way works, and has the advantage that you can specify different text for different states:

1
2
[m_addButton setTitle:@"Add Stuff" forState: UIControlStateNormal];
[m_addButton setTitle:@"Add Stuff (not now)" forState: UIControlStateDisabled];

This is perhaps not that interesting for text titles, but is an excellent way to control the image the button shows based on whether the button is enabled, highlighted, and/or selected.

The C++ Boost Libraries Part 6 – boost::any

In C++ if you have a variable that you say is of type “Person” (for instance), you can be fairly certain (more or less) that it always actually contains a Person (or perhaps a subclass of Person. If you have a container of Persons, then you know (more or less) that every member is also a Person (or a subclass).

This is all very good, prevents a lot of runtime errors, and generally makes C++ a great language if you care about correctness. But sometimes, very rarely, you actually want to store a whole bunch of messy, unrelated types in a container without trying to ram them into some sort of class hierarchy. Parsers are a good example of this. It is often convenient just to chuck tokens of various types into a data structure for later processing without worrying too much about the specific type (string, int, float, etc).

boost::any is a small class that can hold values from almost any type, designed for just such messy applications. Using boost::any is very simple:

1
2
boost::any a1 = std::string("Moose");
boost::any a2 = 6;

Of course, getting the values back again is a little harder.

1
2
3
4
5
6
7
8
9
try
{
	std::string v1 = boost::any_cast< std::string >(a1); // this works, a1 is a string
	std::string v2 = boost::any_cast< std::string >(a2); // nope, will throw an exception at runtime
}
catch ( const boost::bad_any_cast& e )
{
	// tried to any_cast into something that wouldn't go
}

Of course, you can query a boost::any for the typeid of the stored object. Just don’t do it when Scott Meyers is in the vicinity.

1
2
3
4
5
std::string v;
if ( a1.type() == typeid(std::string) )
{
	v = boost::any_cast< std::string >( a1 ); // this should never throw, since we checked first
}

A single boost::any is perhaps not that useful, but a container of them can store almost anything we want:

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
typedef std::vector< boost::any > AnyVector;
AnyVector values;
 
values.push_back( 5 );
values.push_back( std::string("Hello") );
values.push_back( 5.3 );
 
try 
{
	for ( AnyVector::const_iterator p = values.begin();
			p != values.end();
			++p )
	{
		if ( p->type() == typeid(int) )
			cout << "Int = " << any_cast<int>(*p) << endl;
		else if ( p->type() == typeid(std::string) )
			cout << "String = " << any_cast<string>(*p) << endl;
		else 
		{
			cout << "Unhandled type: " << p->type().name() << endl;
		}
	}
} 
catch ( const boost::bad_any_cast &e )
{
	cout << "Bad any_cast<>" << e.what() << endl;
}

Any type that you put into a boost::any must be copy constructable (the any makes a copy, not a reference). You also have to make sure that its destructor doesn’t throw (but of course you do that anyway!)

Although I wouldn’t recommend boost::any for everyday use, it does come into its own when the only alternative is a huge class structure or (even worse) void *s.

Python and The Very Slow Server

I don’t usually do a lot of Python programming, but I always enjoy it when the opportunity arises. Python is in no way a “clean” language, it has all sorts of warts and limitations that mean that it tends to not get used for big projects. Despite this (or maybe because of it), Python remains my go-to language for Getting Small Things Done Quickly. It is impossible to overstate the utility of just being able to start coding a function by bashing away at the python console – nothing else has given me the same sense of instant gratification since I started programming in BASIC back in the 80s.

The other big advantage of Python is the useful utility libraries that come with it as standard. Want to send twenty thousand emails? Just import smtplib. Want to generate code based on data from a spreadsheet? Import csv and away you go. Need a file that is exactly 32Mb is size? No problem. These are real examples from my job where Python has saved me many hours.

The most recent use I have put Python to is a slow server. For various murky and uninteresting reasons I need a rate-limiting HTTP server, one that I can easily control the speed at which it sends data. Enter Python’s very handy BaseHTTPServer module, which allows you to create custom HTTP servers with only a few lines of code by subclassing a request handler. Although the BaseHTTPServer is fairly useless for serving real files, it is perfect for this type of thing since it does all the boring work of parsing headers and returning status codes.

I don’t care about the contents of the data, just its size and how long it takes to serve. Since I will be varying these parameters a lot, I decided to make them part of each request so that each request could take a different amount of time – this means I don’t have to restart the server between each test run. Modifying the code to serve actual file data would be very simple.

I enjoyed writing this server so much that I regret that it didn’t take longer. Now I actually have to use it for its intended purpose, which I can assure you is not going to be as pleasant.

Here is the complete Python source:

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
# A very simple HTTP server designed to for testing situations where the data returned
# is not important but the rate at which it comes down is. This server can be started
# using the command: python delayserver.py
#
# Once started, it will listen for requests on port 8000
# Requests should be of the form http://<address>:8000/size=<bytes>,duration=<seconds>
# where: <bytes> is the size of the response data
# and    <seconds> is how long you want it to take (at minimum, it may take longer)
#
# Notes:
# * The timing is pretty inaccurate for small byte sizes, this isn't a problem for
#   what I need it for
# * Press ctrl-c to stop serving
 
 
import time
import BaseHTTPServer
 
class MyHTTPRequestHandler(BaseHTTPServer.BaseHTTPRequestHandler):
 
	def do_GET(self):
		request = self.path.strip("/")
		duration = 1
		size = 1024
 
        	validRequest = False
		params = request.split(",")
		for p in params:
                    temp = p.partition("=")
                    if (temp[0] == "size"):
                        size = int(temp[2])
                        validRequest = True
                    elif (temp[0] == "duration"):
                        duration = int(temp[2])
                        validRequest = True
 
                if (validRequest == False):
                   self.send_error(404)
                   return
 
                self.send_response( 200 )
                self.send_header( "Content-Length", str(size) )
                self.send_header( "Pragma", "no-cache" )
                self.end_headers()
                self.slowWrite( self.wfile, size, duration )
 
 
        def slowWrite(self, output, size, duration):
                bytesWritten = 0
                startTime = time.time()
                while ( bytesWritten < size ):
                        now = time.time()
                        if (duration != 0):
                                desiredBytes = ( (now - startTime) / duration ) * size
                        else:
                                desiredBytes = size
                        desiredBytes = min( size, desiredBytes )
                        if (desiredBytes < bytesWritten ):
                                time.sleep(0.2)
                        else:
                                while (bytesWritten < desiredBytes):
                                        output.write('A')
                                        bytesWritten = bytesWritten + 1
                                output.flush()
                now = time.time()
                self.log_message( "Request took %f seconds",   now - startTime  )	
 
if __name__ == "__main__":
    http = BaseHTTPServer.HTTPServer( ('', 8000), MyHTTPRequestHandler )
    print "Listening on 8000 - press ctrl-c to stop"
    http.serve_forever()

I should point out that I am by no means an expert at Python, so take this code with a pinch of salt.

The HTML5 Video Tag’s Fatal Flaw

Back in the day there was no standard way to publish video on the web. You could put any kind of video file you wanted on the server, but there was no guarantee that your readers would have the correct plugin required to view it. Everyone had to have a bunch of plugins installed to have any hope of viewing the majority of video files.

Flash video solve this problem. Flash was installed on nearly every computer anyway, so once they added a video decoder it seemed obvious to provide video content in Flash, even if it was in many ways not as good as the older plugins. Flash video uses massive amounts of processor time and slows down everything else on your computer. On the other hand, websites like Flash because it is easy to skin the player to fit in with the look of the site, and it makes downloading the raw video file (slightly) more difficult.

The <video> tag is supposed to replace Flash by linking to video files in the same way that the <img> tag links to images. In practice this is more complicated than it sounds because videos typically require the ability to skip and rewind content. This means that the browser must be prepared to download different parts of the file and cache things carefully to maintain performance. But these problems have long been solved.

I have been waiting for the big sites to make announcements, and today seems to be <video> day all over the internet. Both YouTube and Dailymotion have demo pages up showing <video> content:

YouTube’s HTML5 Page is designed to show how the <video> tag can replicate the functionality of their famous Flash-based player exactly. Unless you looked at the source (or your OS’s process monitor) you would never know you were using a different player.

The Dailymotion HTML5 Demo is even more impressive, using the <video> tag in combination with fancy Javascript to post-process the video and extract frames.

All this is very cool, but the two demos reveal the video tag’s fatal flaw : codecs. When the video tag was proposed, all browsers were supposed to support an unencumbered decoder named Ogg Theora (no seriously, that’s its name). There were just three problems:

  • Ogg Theora’s quality was not as good as other codecs
  • Although Ogg Theora was designed to be free of patent issues, it was felt that it may be a bit of a lightning rod for litigation.
  • Certain companies may have a vested interest in seeing their own codecs used.

So the requirement to support Ogg Theora was dropped. This means that although all HTML5 browsers will support <video>, there is no guarantee that they will be able to play and particular file. Firefox (at least the 3.5 beta) plays Ogg Theora, but Safari plays H.264 (a superior but expensive to license codec) but not vice versa. For instance, one of the demos above plays in Firefox, the other plays in Safari. This puts us in the farcical situation of having no standard way to publish video, exactly where we started.

There is also the small point that the most widely used browser (IE) does not support the video tag, and probably won’t for years. I predict that Flash video will be around for a while yet, and I am not happy about it.

The C++ Boost Libraries Part 5 – boost::filesystem

The standard C++ iostreams library is very good (well, some would say sort-of good) at reading and writing a file’s contents, but it does so in such a way as to completely ignore file names. I am sure there was a good reason for this omission, but whatever it was is long out of date. There isn’t even a standard way to iterate through a directory, for God’s sake! You end up either falling back to the C standard library (ick) or using operating specific APIs just to find out how big a file is.
Continue reading

The Boost C++ Libraries Intermission – Getting Boost Used

A former colleage of mine (Hi Nigel!) frequently wore the greatest geek tee-shirt I have ever seen to work. Ineptly reproduced here, it summarizes the realities of software development – when deciding what to implement technical considerations are often overruled by more prosaic influences.
9-layer-osi

Take this comment by another old colleage. It is a example of how a lot of companies fail to exploit the huge amount of well-tested code available for reuse. There are lots of reasons why a company might ban boost, in my opinion none of them are that compelling.

The main reason cited is the fear of legal retribution (before continuing, I should point out that I am not a lawyer and the following is not legal advice.)

More than one company has been stung by employees including code they do not own into a commercial product, even accidental violations can attract huge penalties with big companies being particularly at risk. This has resulted in a climate where a company will pass every decision on third-party libraries through their lawyers. Lawyers by nature are cautious, they live in a world of contracts, indemnities and assigned liabilities. The default answer is almost always going to be “no” unless there is a contract to sign and someone to blame if it goes pear-shaped.
Continue reading

The Boost C++ Libraries Part 4 – boost::date_time

Living on a spherical planet can sometimes be a real pain in the neck. It makes what should be a simple concept, Time, inordinately complex. Timezones, daylight savings, leap years (and worse: leap seconds) all conspire to destroy any simple abstraction. So boost provides a complex one.

First up is the gregorian::date class, which specifies a day in the gregorian calendar (sorry fans of the French Revolutionary Calendar, boost::date_time is not for you). Along with normal days, gregorian::date supports positive/negative infinite dates as well as a special not_a_date_time value that make certain algorithms very easy.

A closely related type is gregorian::days, which represents duration. Durations can be freely added or taken away from dates to create new dates. Special classes for longer units also exist: gregorian::weeks, gregorian::months, and gregorian::years come in very handy. gregorian::months and gregorian::years even have special handling to ensure that dates “snap” to the end of the month during calculations.

gregorian::date leapYearMonth( 2008, Feb, 29 );
gregorian::months oneMonth(1);
gregorian::date endOfMarch = leapYearMonth + oneMonth;
// endOfMarch == 31/3/2008, not 29/3/2008

gregorian::date_period represents a fixed period between two dates, and has the methods you would expect for determining if a date exists within a period or two periods overlap. Because the date class can represent abstract concepts like dates infinity days into the future or past, date_periods can represent segments of time without fixed ends.

gregorian::date_period untilFurtherNotice( gregorian::day_clock::local_day(),
                                           gregorian::pos_infin );

Date Iterators and Generators are both very cool concepts. Iterators produce a series of dates that are all some duration (ie: 1 month) apart. Generators provide even more complex factories for producing non-uniform dates such a “the last monday in January” for a given year.

Times are just dates with an offset into the specified day. In boost::date_time this is handled by the posix_time::ptime class. Like date, ptime can represent positive and negitive infinity as well as not_a_date_time giving great flexibility. Also like gregorian::date there are time_duration, time_period, and time_iterator classes which serve the same purpose.

I haven’t even mentioned the most useful part of boost::date_time yet – a full set of streaming operators and conversions to and from standard string formats. If for some reason the standard input/output formats aren’t enough it is possible to imbue a stream with a custom date/time facet for that fancy touch of class.

Aside from strings, dates and times are probably the most common data-types that must be represented in programs dealing with human affairs. It is a pleasure to finally have a library that is up to the task.

The C++ Boost Libraries Part 3 – string algorithms

One of the many, many legitimate criticisms that could be leveled at C++ is that string handling is abysmal. Sure std::string can hold some chars for you, but there is a distinct lack of utility functions to actually do anything with those characters. Enter the Boost String Algorithm library, or string_algo to its many friends.

String_algo contains all those fiddly little functions that you write yourself to process text, as well as some clever extensions. The simple stuff is very simple:

string mixedCase = “Hello there”;
to_upper(mixedCase);

string allLower = to_lower_copy(mixedCase);
// mixedCase == “HELLO THERE”
// allLower == “hello there”

string weirdFormat = ” .;text;;;;.. “;
trim(weirdFormat);

// remove punctuation with a predicate
trim_if(weirdFormat, is_punct());
// weirdFormat == “text”

The is_punct() function returns a predicate – string_algo defines a bunch of useful predicates so you will rarely have to roll your own. Not shown in the above is the ability to pass a std::locale to handle strings in other languages.

There is the full compliment of find, replace, and erase substring options:

string statement = “I like cheese, cheese, and cheese”;
replace_nth( statement, “cheese”, -2, “bacon” );
replace_last( statement, “cheese”, “eggs” );
erase_first( statement, “cheese” );
erase_all( statement, “,” );

(the -2 parameter for replace_nth means “replace the 2nd from last occurance” – very useful)

And check this out:

vector words;
string anthem = “God of nations! at Thy feet\n”
                ”In the bonds of love we meet,”;
split( words, anthem, is_any_of(” \n!,”) );

I haven’t even mentioned the ability to do fancy things with regular expression and the concept of find iterators that advance over the substrings that match. Also, the library is generic enough to work with any container that looks vaguely like a sequence of characters, not just std::string.

String_algo is replacing vast numbers of little hacked-together functions in my code. If nothing else it will reduce the temptation to use the God-forsaken CString classes.

The C++ Boost Libraries (Part 2 – boost::assign)

We are still only in the low lands of boost territory but already we are coming across useful discoveries. Today’s stop is boost::assign, one of those clever little pieces of code that makes life easier for everyone. Often you just want to load up a container with some small amount of data. The STL containers do not make such a task particularly easy:

vector<string> faceCards;
faceCards.push_back(“jack”);
faceCards.push_back(“queen”)
faceCards.push_back(“king”);
faceCards.push_back(“ace”);

What a pain in the neck! With boost::assign it becomes:

vector<string> faceCards;
faceCards += “jack”,”queen”, “king”, “ace”;

Neat.

It gets better. A lot of the time you want to fill a container with some data for testing but you don’t really care what that data is:

list<int> data;
// data will contain 1,2,5,5,5,5,5,5,5,5,7
data += 1, 2, repeat(8, 5), 7;

Or even:

list<int> randomData;
// data will contain 1,2,(8 random numbers),7
randomData += 1, 2, repeat_fun(8, &rand),7;

Of course, other containers are supported. This example uses the more flexible insert function (there are other functions for inserting at specific points for containers that support such things):

map<string, string> maoriColors;
insert(maoriColors)(“ma”, “white”)
                   (“whero”, “red”)
                   (“kakariki”, “green”)
                   (“kowhai”, “yellow” );

As with all the boost libraries, a lot of thought has gone into to making the interface safe and flexible. The library can even be extended to non-standard containers if the need should arise.

All the best magic tricks are really just smoke and mirrors, boost::assign is really just functions that secretly return functor objects and operator,() abuse. Unlike most magic, knowing how it works makes it even more delightful; the library is very well documented.

Although boost::assign is useful anywhere, it really shines in simple throwaway programs and test harnesses, where small, simple and easily modifiable code is the goal. I keep finding more and more places to use it.