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

```

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):
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):
```

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