Hackoff 2010 Problem 5

Problem is to extract the letters highlighted in red from an animated gif. We assume the frames of the gif have already been pulled apart into pnm files.

#!/usr/bin/env python

import pygame, sys, time, numpy

Our character grid is 10 by 12 with a one pixel border that contains the highlight, so we note that down for reference and create a surface that we'll copy our character into to play with later:

# x 10 +12x
# y  8 +14y

target = pygame.Surface((10,12))
targetrect = target.get_rect()

Once we've got the character we'll want to "OCR" it and remember it for later; we'll use two arrays for that:

found = []
redbits = []

The "found" array just keeps track of the different bitmaps for each character we've seen (so there'll be one bitmap for every "A" and one for every "4" etc), and the "redbits" tells us which bitmap was found. Later we'll associate a bitmap from found with an actual character, and can then convert redbits into a string which will contain the answer we need.

So to handle each frame we first load it, then iterate over every potential character, checking for a red border. If we found one we copy the character onto its own surface, convert that into a simple python list representing the bitmap, and then either find it in found and note the index in redbits, or add it to found, and note the index in redbits.

def handle_frame(name):
    frame = pygame.image.load(name)
    framerect = frame.get_rect()

    for x in range(10, framerect.width, 12):
        for y in range(8,framerect.height, 14):
            col = frame.get_at((x,y))
            if col == (255,0,0,255):
                target.blit(frame, targetrect, pygame.Rect(x+1,y+1,10,12))
                z = pygame.surfarray.array2d(target).tolist()
                for idx in range(len(found)):
                    if z == found[idx]:
                        redbits.append(idx)
                        break
                    else:
                        redbits.append(len(found))
                        found.append(z)

Our initial job is then to load each frame:

for i in range(1,1349):
    handle_frame("05-red-pill-blue-pill.gif.%04d.gif.pnm" % i)

And once we've done that, we need to OCR the characters. It turns out there's only 16 different ones, so there's no problem passing that off to the user:

translate = []
for f in found:
    print numpy.array(f)
    translate.append(sys.stdin.readline().strip())

Well, there is a minor problem in that numpy.array ends up getting the bitmap printed out rotated and mirror-imaged or something, but that's pretty easy to deal with.

As is getting the actual answer at that point:

print "".join([translate[i] for i in redbits])

Et voila.