Head to tail in 1 line

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']'



[æ]