# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1711: Illuminated artwork

From New Scientist #2878, 18th August 2012 [link]

In our town square is a piece of installation art consisting of 300 rods of equal length arranged in a cubic lattice. The whole structure balances on a single vertex, with the diagonally opposite vertex at the top. Each rod contains an LED strip light, which can be independently switched on and off. A microprocessor controls this, lighting up the rods that form the shortest continuous path between the bottom and top vertices.

Each combination of rods (meeting the shortest continuous path criterion) is lit up for 10 seconds, then another and so on, until all combinations have been displayed, when the cycle starts again.

How long does it take to complete a full cycle?

[enigma1711]

### 4 responses to “Enigma 1711: Illuminated artwork”

1. Jim Randell 15 August 2012 at 5:19 pm

The following Python program recursively enumerates all shortest paths. It runs in 100ms

```from enigma import cached, printf

# the number of rods in an m x n x p lattice is:
# (p + 1) * (m * (n + 1) + n * (m + 1)) + p * (m + 1) * (n + 1)
# so a 4 x 4 x 4 cubic lattice is composed of 300 rods

# we need to find the number of shortest paths from (0,0,0) to (4,4,4)

# count the number of paths between (0, 0, 0) and (x, y, z)
@cached
def paths(x, y, z):
# are we done?
if x == y == z == 0: return 1
# if not try advancing in each direction
n = 0
if x > 0: n += paths(x - 1, y, z)
if y > 0: n += paths(x, y - 1, z)
if z > 0: n += paths(x, y, z - 1)
return n

n = paths(4, 4, 4)
printf("{n} paths")

# how long at 10s per path?
(m, s) = divmod(n * 10, 60)
(h, m) = divmod(m, 60)
printf("{h}h{m}m{s}s")
```

Solution: A complete cycle takes 96 hours and 15 minutes.

• Jim Randell 15 August 2012 at 6:44 pm

The On-line Encyclopedia of Integer Sequences, has a formula that lets you calculate the answer directly.

Although another way of looking at it is that a minimal path from (0, 0, 0) to (x, y, z) has x + y + z steps (as there are x steps in the x-direction, y steps in the y-direction and z steps in the z-direction). So, considering the path as being a sequence of x + y + z slots each to be filled with the direction of travel, we can see that for the x-direction there are C(x + y + z, x) ways of filling these out (where C(n, k) is the standard combinatorial choice function), then for the y-direction we can choose y slots from the remaining y + z, so C(y + z, y), and then all the remaining slots are in the z-direction.

Hence the number of minimal paths is:

C(x + y + z, x) × C(y + z, y) = ((x + y + z)! / (x! (y + z)!)) × ((y + z)! / (y! z!))
= (x + y + z)! / (x! y! z!)

So for paths from (0, 0, 0) to (n, n, n) this simplifies to (3n)!/(n!)^3.

2. arthurvause 15 August 2012 at 9:34 pm

By generalising the construction of Pascal’s triangle to 3 dimensions (and using memoization):

```def memoize(f):
cache= {}
def memf(*x):
if x not in cache:
cache[x] = f(*x)
return cache[x]
return memf

@memoize
def routes(a,b,c):
if a<0 or b<0 or c<0:
return 0
elif a==b==c==0:
return 0
elif  a==b==0 or a==c==0 or b==c==0:
return 1
else:
return routes(a-1,b,c) + routes(a,b-1,c)+routes(a,b,c-1)

r=routes(4,4,4)
secs=10*r
print r, secs//3600,":",(secs-(secs//3600)*3600)//60,":",secs%60

```
3. Brian Gladman 15 August 2012 at 11:03 pm

My solution was so similar to Jim’s that I wasn’t going to publish but Arthur’s use of caching reminded me of just how powerful this technique can be. To test this, here is a version of the code to enumerate the number of shortest paths in a 100 x 100 x 100 cubic lattice:

```from math import factorial

def memorise(function):
cache = {}
def wrapper(*args):
a = tuple(sorted(args))
if a in cache:
return cache[a]
else:
rv = function(*a)
cache[a] = rv
return rv
return wrapper

@memorise
def traverse(p, q, r):
if (p, q, r) == (0, 0, 0):
return 1
else:
tot = 0
if p:
tot += traverse(p - 1, q, r)
if q:
tot += traverse(p, q - 1, r)
if r:
tot += traverse(p, q, r - 1)