Up the Down Penrose Staircase

I recently stumbled upon this little problem on Wired, inspired by the Penrose Staircase:

http://www.wired.com/magazine/2010/11/pl_decode_staircase

Although I'm pretty sure it was meant to be solved by hand (as a Sudoku problem would be, presumably) I thought it would be nice to find a solution less tediously, using a few lines of Python. Plus, my recursive function writing ability being a little rusty, this would make me practice a bit. So I started with a very simple way of representing the problem space:

stairs = [6, 1, 2, 6, 5, 3, 5, 2]

Even though the staircase itself is rather circular (or infinite), our data structure needs not to be, of course: it just has to wrap around. Next we need two helper functions to go up and down the stairs, using the special rules (N-1 steps when going up, N+1 when going down). It's also worth noting that our algorithm makes use of the step positions (or array index, i.e. 0 to n_stairs-1), not their values (which would be ambiguous anyway, because some of them are used twice). So these two functions take a position as their input, and they also return a position. Their only complication are the wrap around cases, which must be handled using the right position calculations.

# 0 (6) -> 5 (3)
# 5 (3) -> 7 (2)
# 6 (5) -> 2 (2)
def up(pos, stairs):
    k = stairs[pos] - 1
    if pos + k < len(stairs): return pos + k
    else: return k - (len(stairs) - pos)

# 0 (6) -> 1 (1)
# 5 (3) -> 1 (1)
# 6 (5) -> 0 (6)
def down(pos, stairs):
    k = stairs[pos] + 1
    if pos - k >= 0: return pos - k
    else: return len(stairs) - (k - pos)

With these, we can now write a function to explore the possible paths leading to a solution. It's rather reasonable to explore them all, in a brute force kind of way, given that the problem imposes a fixed length for a solution to be valid (it wouldn't make sense to continue searching beyond this bound). Our function is recursive: at each step in the exploration of a given path, it first checks if it yields a valid solution (i.e. (1) with the right length, (2) all the positions having been visited and (3) we are back to where we have started), in which case it prints it (in both the position and value spaces) and returns, and if not, it calls itself twice (up and down) to continue the exploration.

def solve(solution, stairs):
    n_stairs = len(stairs)
    # is solution valid?
    if len(solution) == (n_stairs + 1):
        if range(n_stairs) == sorted(solution[1:]) and solution[-1] == 0: 
            print solution, [stairs[p] for p in solution]
        return
    # go up
    solve(solution + [up(solution[-1])])
    # go down
    solve(solution + [down(solution[-1])])

It's also possible to get rid of the helper functions altogether by dissolving their logic in previous function's body (which makes it a little bit harder to read and interpret, admittedly, but produces a more compact solution):

def solve(solution, stairs):
    n_stairs = len(stairs)
    if len(solution) == (n_stairs + 1):
        if range(n_stairs) == sorted(solution[1:]) and solution[-1] == 0: 
            print solution, [stairs[p] for p in solution]
        return
    p = solution[-1]
    up = stairs[p] - 1
    down = stairs[p] + 1
    solve(solution + [p + up if p + up < n_stairs else up - (n_stairs - p)], stairs)
    solve(solution + [p - down if p - down >= 0 else n_stairs - (down - p)], stairs)

To use either of these solvers, we pass it an incomplete solution (which must begin on the first step, hence the first position (0) already given) and the staircase data structure:

solve([0], stairs)

Finally, if you enjoy this kind of problem, requiring some programming to solve (although not necessarily), I suggest you take a look at Project Euler, which is very challenging and fun.

Tweet