Enigmatic Code

Programming Enigma Puzzles

Enigma 12: Cubic walks

From New Scientist #1154, 10th May 1979 [link]

The picture shows a perfectly smooth one-inch cube of sugar floating freely in space. Dotty and Potty are two very tiny space-flies, and each goes for a walk on the surface of the cube. Each starts where she chooses. Dotty must end up at her starting point; Potty need not. On the way, Dotty likes to take a nibble at each face of the cube. On her way, Potty wants a nibble at each edge.

If each takes the shortest walk which meets her own requirements, how long are each of their walks?

This is the 250th Enigma Puzzle to be added to the Enigmatic Code site!

[enigma12]

Advertisements

2 responses to “Enigma 12: Cubic walks

  1. Jim Randell 5 November 2012 at 3:44 pm

    I took the view that a space-fly positioned on a vertex of the cube would be able to nibble three faces and three edges without having to move.

    Solution: Both Dotty and Potty walk 3√2 inches (approximately 4.243 inches).

    Here are diagrams showing example paths (Dotty in blue on the left, Potty in red on the right):

    There are many possible minimal paths for Dotty, although I like the one depicted above for several reasons. Not only does it visit each face, but it crosses each face, and has an equal length of path on each face. If you were to balance the cube on one vertex (the “South Pole”) with its opposite (antipodal) point directly above it (the “North Pole”) then this path is the “equator” of the cube, and if you were to slice the cube along this path the cut face would be a regular hexagon.

    In fact any slice through such a cube in a plane parallel to the equator between the “Tropic of Cancer” (a plane defined by the other ends of the three edges the meet at the North Pole) and the “Tropic of Capricorn” (defined by the vertices of the edges emanating from the “South Pole”) defines a minimal traversal of the cube that crosses each face.

    There is essentially only one minimal path for Potty, which is to start at a pole, travel diagonally across a face to a vertex on a tropic, and then travel diagonally across two more faces to take in the remaining two points on that tropic.

    Here are the paths drawn out as straight lines on the net of the cube (again, Dotty in blue on the left, Potty in red on the right):

    I found this a tricky problem to attack programatically. The approach I finally used was to divide the edges of the cube into n segments and then consider paths composed of straight lines across faces between these points. So that dividing the edges into 1 segment means considering only paths that join vertices of the cubes. Dividing the edges into 2 segments considers the vertices of the cube and also the mid-points of edges, and so on.

    Fortunately there are minimal solutions when the edges are 1-segments, and shorter paths are not found when we consider 2-, 3- or 4-segment edges. I think considering the cube made of 4-segment edges is most informative as it considers the vertices, mid-points of edges and also “quarter points” half-way between the mid-point of an edge and the vertex. Although it takes a while to run the algorithm for 4-segments (it should be possible to reduce the run time by eliminating symmetrical paths), it’s enough to satisfy me that there are no shorter solutions.

    The program actually considers an n × n × n cube (which keeps the co-ordinates of the points nice and simple), and scales the distances down to correspond to the unit cube.

    As written the code will find all minimal paths that start at points from a vertex to the mid-point of a selected edge. You can specify on the command line which path you which to find (“D”, “P” or “DP”) and how many segments to divide the edges into. The default values are: “DP 2”.

    I’d be interested to see any more direct proofs (programmatic or non-programmatic) that show the paths are minimal.

    from collections import defaultdict
    from itertools import combinations
    from enigma import sqrt, irange, Accumulator, printf
    
    # create data for the cube
    def make_cube(n):
      points = list([None] * (4 * n) for i in range(6)) # points for each face
      faces = defaultdict(set) # faces for each point
    
      def process(f, i, ps):
        for (j, p) in enumerate(ps):
          points[f][j * n + i] = p
          faces[p].add(f)
    
      for i in range(0, n):
        process(0, i, ((i, 0, 0), (n, i, 0), (n - i, n, 0), (0, n - i, 0))) # z=0
        process(1, i, ((i, 0, 0), (n, 0, i), (n - i, 0, n), (0, 0, n - i))) # y=0
        process(2, i, ((0, i, 0), (0, n, i), (0, n - i, n), (0, 0, n - i))) # x=0
        process(3, i, ((i, 0, n), (n, i, n), (n - i, n, n), (0, n - i, n))) # z=n
        process(4, i, ((i, n, 0), (n, n, i), (n - i, n, n), (0, n, n - i))) # y=n
        process(5, i, ((n, i, 0), (n, n, i), (n, n - i, n), (n, 0, n - i))) # x=n
    
      faces = dict(faces)
    
      # and what points are adjacent to other points
      # i.e. the can be reached along the surface of the cube from the original point
      adj = dict((p, set().union(*(points[f] for f in faces[p]))) for p in faces.keys())
    
      return (points, faces, adj)
    
    # distance metric
    def distance(a, b, n):
      (ax, ay, az) = a
      (bx, by, bz) = b
      return sqrt((ax - bx) ** 2 + (ay - by) ** 2 + (az - bz) ** 2) / n
    
    # tolerance
    T = 1e-6
    
    # dotty is a closed path visiting all faces
    def dotty(n, points, faces, adj, p, fs, pts, d, m):
      # do we already have a better path?
      d2 = distance(pts[0], pts[-1], n)
      if m.value + T < d + d2: return
      # have we visited all faces?
      if len(fs) == 6:
        # can we close the path?
        if faces[pts[0]].intersection(faces[pts[-1]]):
          d += d2
          pts.append(pts[0])
          m.accumulate(d)
          if abs(d - m.value) < T:
            print(d, pts)
          return
      # move to an adjacent point
      for p2 in adj[p]:
        if p2 in pts: continue # must be a new point
        dotty(n, points, faces, adj, p2, fs.union(faces[p2]), pts + [p2], d + distance(p, p2, n), m)
    
    # potty is a path (not necessarily closed) visiting all edges
    def potty(n, points, faces, adj, edges, p, es, pts, d, m):
      # do we already have a better path?
      if m.value + T < d: return
      # have we visited all edges?
      if len(es) == 12:
        m.accumulate(d)
        if abs(d - m.value) < T:
          print(d, pts)
        return
      # move to an adjacent point
      for p2 in adj[p]:
        if p2 in pts: continue # must be a new point
        potty(n, points, faces, adj, edges, p2, es.union(edges[p2]), pts + [p2], d + distance(p, p2, n), m)
    
    import sys
    run = 'DP' if len(sys.argv) < 2 else sys.argv[1].upper()
    n = 2 if len(sys.argv) < 3 else int(sys.argv[2])
    
    (points, faces, adj) = make_cube(n)
    
    # initial minimum value
    M = 3 * sqrt(2) # or you can start from higher if you like
    
    if 'D' in run:
      m = Accumulator(fn=min, value=M)
      # start dotty at a certain point, upto half way along an edge
      for p in points[0][0:n // 2 + 1]:
        dotty(n, points, faces, adj, p, set(faces[p]), [p], 0.0, m)
    
      printf("dotty: min distance = {m.value}")
    
    
    # make a map of points to edges
    edges = defaultdict(set)
    for (p, fs) in faces.items():
      for (a, b) in combinations(fs, 2):
        edges[p].add(tuple(sorted((a, b))))
    
    if 'P' in run:
      m = Accumulator(fn=min, value=M)
      # start potty at a certain point, up to half way along an edge
      for p in points[0][0:n // 2 + 1]:
        potty(n, points, faces, adj, edges, p, set(edges[p]), [p], 0.0, m)
    
      printf("potty: min distance = {m.value}")
    

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: