Enigmatic Code

Programming Enigma Puzzles

Enigma 1565: It’s a rollover

From New Scientist #2728, 3rd October 2009 [link]

Joe’s puzzle was no rollover for Penny. Joe drew a mini-chess board on a card and made a dice with the letters ENIGMA in place of the numbers. Penny had to select a letter and then place the dice on the X with the selected letter on the top. Then she moved the dice, by rolling it (rotating it by 90 degrees), from square to square to the corresponding lettered square on the right of the board, finishing with the selected letter on top. For each letter the number of moves had to be a minimum. What are the minimum number of moves for each of the letters E, N, I, G, M and A?

[enigma1565]

Advertisements

One response to “Enigma 1565: It’s a rollover

  1. jimrandell 21 February 2012 at 10:01 pm

    The following Python program implements a depth first search and runs in 124ms.

    # ROLL tells us what happens to U if we roll the die
    # maps "UDLRFB" = "012345" -> new positions
    ROLL = {
      'E': (2, 3, 1, 0, 4, 5),
      'N': (4, 5, 2, 3, 1, 0),
      'W': (3, 2, 0, 1, 4, 5),
      'S': (5, 4, 2, 3, 0, 1)
    }
    
    def roll(dir, die):
      return "".join(die[i] for i in ROLL[dir])
    
    # implement a depth first search
    def solve(letter, tx, ty, pos):
    
      solved = 0
      next = []
      # go through each element in the list and make a list of the next positions
      for i in pos:
        (die, x, y, rolls) = i
    
        # are we there yet?
        if x == tx and y == ty and die[0] == 'U':
          print("{l} = {n} [{r}]".format(l=letter, n=len(rolls)-1, r=rolls[1:]))
          solved = 1
    
        elif not solved:
          # otherwise try rolling the dice in each allowable direction
          if x < 5 and rolls[-1] != 'W': next.append((roll('E', die), x+1, y, rolls + 'E'))
          if x > 0 and rolls[-1] != 'E': next.append((roll('W', die), x-1, y, rolls + 'W'))
          if y < 5 and rolls[-1] != 'S': next.append((roll('N', die), x, y+1, rolls + 'N'))
          if y > 0 and rolls[-1] != 'N': next.append((roll('S', die), x, y-1, rolls + 'S'))
    
      # if we're not finished try from the next set of positions
      # note this is tail-recursive, so we could use a loop if we wanted to
      if not solved:
        solve(letter, tx, ty, next)
    
    
    # find the minimal solutions for each letter
    for (i, l) in enumerate('ENIGMA'):
      # NOTE: we only care about U so 'U?????' would do just as well
      # and we used '.' to indicate the initial placement, so that rolls[-1] is always defined
      # but this means len(rolls) is one bigger than the number of rolls
      solve(l, 5, 5-i, [('UDLRFB', 0, 0, '.')])
    

    Solution: The minimum number of moves for each letter are: E=10, N=9, I=8, G=7, M=8, A=7.

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: