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]

Advertisements

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)
        return tot
    
    n = 100
    print(factorial(3 * n) // factorial(n) ** 3)
    print(traverse(n, n, n))
    

    It enumerates the paths in the cube in around 1 second to give:
    376523493564631064367712071965768747782444205128669798396168767743500485766630075466163294008566118208045715304490994009624725072511252178400

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: