We were talking about puzzles on friday, and the old 'head' to 'tail' puzzle came up. I commented off the cuff that I thought it could be done in 5 lines, Jay took this as a challenge. When he told me that, I felt obliged to find such a solution.

I first coded up the straightforward BFS solution, but it was 16 lines.

import re def headToTail(start, end): w = [l for l in [l.strip() for l in open("/usr/share/dict/words")] if re.match('[a-z]{4,4}$', l) != None] G = {k:set(v for v in w if 1 == sum(k[i] != v[i] for i in range(4))) for k in w} Q = [(0,start)] index = 0 while w != end: prev,w = Q[index] Q += [(index, x) for x in G[w]] index += 1 path = [] while prev != 0: prev,w = Q[prev] path.append(w) print [start]+list(reversed(path))+[end]headToTail('head', 'tail')

this is without 'cheating', and is nearly reasonable code. Try as I might, I couldn't see a nice way to do the pointer chasing in fewer lines. Time for some more weird stuff. The biggest win was to switch from BFS to DFS emulating BFS:

#G as above def dfs(s, d): if s == 'tail': return [s] if d: for w in G[s]: xs = dfs(w, d-1) if xs: return xs+[s]for d in range(1, 100): xs = dfs('head', d) if xs: print xs break

but this is still quite long. The next step was to simplify the path code - rather than performing the path construction on the way out, let's construct it on the way down:

def dfs(s, d, l=[]): if s == 'tail': raise Exception(str(l)) if d: for w in G[s]: dfs(w, d-1, l+[s])for d in range(1, 100): dfs('head', d)

We also use the exception system to bail out, avoiding all the checking, and also to provide the final printing. However, raise can not be used as an expression, only a statement. We need to find a way to throw an exception and have the value printed out. If we use python3, we can use the expression (print(l) or [] + None), but there is no obvious way to transform that into python without extra function defs or imports. Jay came up with getattr('', str(l)), which does what we want:

# G as above def dfs(s, d, l=[]): s == 'tail' and getattr(s, str(l+[s])) or (d and [dfs(w, d-1, l+[s]) for w in G[s]]) [dfs('head', d) for d in range(1, 100)]

Better, can we do best?

This is harder because we need to perform recursion without using the def which chews up a line. Closures to the rescue:

[(lambda a:lambda v:a(a,v))(lambda dfs,(s, d, l, G): s == 'tail' and getattr(s, str(l+[s])) or (d and [dfs(dfs,(w, d-1, l+[s],G)) for w in G[s]]))(('head', d,[],{k:set(v for v in w if 1 == sum(k[i] != v[i] for i in range(4))) for k in w})) for d in range(1, 100) for w in [[l for l in [l.strip() for l in open("/usr/share/dict/words")] if len(l) == 4 and all(c in 'qwertyuiopasdfghjklzxcvbnm' for c in l)]]]

That's just one line, and runs in a reasonable amount of time:

... AttributeError: 'str' object has no attribute '['head', 'heal', 'teal', 'tell', 'tall', 'tail']'