The Software Alchemist

I participate in ‘the Calgary book club’, several developers come together every couple of weeks to discuss a book we’ve all been reading. Currently we’re working our way through Steven Skiena’s Algorithm Design Manual. It’s a pretty good walk through a lot of computer science fundamentals, particularly for those of us who didn’t study a straight CS course at university. The other week, we had a stab at the crypt kicker problem from the book. None of us managed to implement a solution that would be deemed acceptable by the online judge, but we did produce some ideas and partial solutions. Here's my idea, which you can find source code for at GitHub. The general concept is to build up a dictionary, or cipher, of possible letter substitutions based on each word in the input sentence. Progressing through the input from start to finish may cause several equally valid ciphers to be produced, so we keep a list of ciphers. Each word encountered may cause this list to be lengthened or shortened. We'll work through the example given in the problem description. Just to recap, the word list contains 6 words:

and
dick
jane
puff 
spot
yertle

And there is one sentence to decode:

bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn

Solution Stage 1 : Find ciphers for the first word

The first word from our input is bjvg. We'll try this word against every word in the dictionary. and : Too short, throw that right out dick : That works, we can substitute b → d, j →i, v → c and g → k jane : Also works puff : Appears to work at first, b → p, j → u, v → f, but wait... g can't stand in for f, because f is already taken. So that doesn't work spot : That works yertle : Too long So we end up with three ciphers, one each for dick, jane and spot:

Key	Cipher 1	Cipher 2	Cipher 3
b	d	j	s
j	i	a	p
v	c	n	o
g	k	e	t

Solution Stage 2 : Find ciphers for the second word

We now go through the same process for the second word, and come out with just one cipher:

Key	Cipher 1
x	a
s	n
b	d

Solution Stage 3 : Find all the valid combinations

This is where the magic happens. With any implementation of a solution to this problem, eliminating possibilities is as important as finding them. In this stage, we get all the ciphers found so far and merge them with all those found in the last step, so in this case we expect to get 3 x 1 = 3 new ciphers (if two were found in stage 2, we would get 3 x 2 = 6). We discard any combinations that conflict with each other. To start with, we get the first cipher from stage 1, and combine it with the result of stage 2. This yields the following:

Key	Stage 1, Ciper 1	Stage 2	Combination
x		a	a
s		n	n
b	d	d	d
j	i		i
v	c		c
g	k		k

Note that both ciphers have a substitute for b, but as it is the same in both, there is no conflict. On the other hand, the second cipher from stage 1 contains b → j, and the cipher from stage 2 contains b → d. Therefore the two cannot be merged, and we drop this possibility:

Key	Stage 1, Ciper 1	Stage 2	Combination
x		a	a
s		n	n
b	j	d	?
j	a		a
v	n		n
g	e		e

Finally, the third cipher from stage 1 contains b → s, which also conflicts with the stage 2 cipher. So after this stage, we have reduced ourselves to just one possibility. We discard all the ciphers we had before from stage 1 and 2.

Stage 4 : Keep going

We keep applying stages 2 and 3, generating ciphers, combining them and removing dead ends until we have reached the end of the input sentence. We should be left with all the possible ways to decode the sentence. There may be more than one cipher remaining at the end, but all of them should be able to decode the entire input sentence into words from the word list. Clear?