Enigmatic Code

Programming Enigma Puzzles

Tantalizer 481: Happy Christmas

From New Scientist #1032, 23rd December 1976 [link]

tantalizer-481

Oops! What the message is meant to say is of course:

HAPPY CHRISTMAS TO YOU FROM THE NEW SCIENTIST.

Perhaps you would like to put it right by sliding on word at a time along a line into a vacant oval. If you are not too saturated with Christmas pud, you should manage it in 26 moves.

[tantalizer481]

Advertisements

One response to “Tantalizer 481: Happy Christmas

  1. Jim Randell 24 May 2017 at 8:52 am

    This Python 3 program exhaustively examines all possible sequences of 26 moves or less. It runs in 3.72s (under PyPy).

    The moves are calculated using the indices of the slots, but the output() is used to output the positions of the labels as they are moved around in the sequence leading to a solution.

    from enigma import update, printf
    
    # adjacency matrix
    adj = {
      0: [1, 3],
      1: [0, 2, 4],
      2: [1, 5],
      3: [0, 4, 6],
      4: [1, 3, 5, 7],
      5: [2, 4, 8],
      6: [3, 7],
      7: [4, 6, 8],
      8: [5, 7],
    }
    
    # find moves from start to target
    def solve(start, target, empty, m, moves=[], last=-1):  
      if start == target:
        yield moves
      elif m:
        # move a word into the empty space
        for x in adj[empty]:
          # don't just undo the last move
          if x == last: continue
          yield from solve(update(start, [(empty, start[x]), (x, start[empty])]), target, x, m - 1, moves + [x], empty)
    
    # output the pieces moved
    def output(start, moves):
      empty = start.index("")
      printf("start = {start}, empty = {empty}")
      for x in moves:
        w = start[x]
        start = update(start, [(empty, start[x]), (x, start[empty])])
        printf("\"{w}\" -> {empty} {start}")
        empty = x
    
    # start position
    start = [ "New", "from", "the", "Scientist", "Christmas", "happy", "you", "to", "" ]
    
    # target
    target = [ "happy", "Christmas", "to", "you", "from", "the", "New", "Scientist", "" ]
    
    for moves in solve(start, target, start.index(""), 26):
      printf("{n} moves, {moves}", n=len(moves))
      output(start, moves)
      printf()
    

    Solution: There are six ways to achieve the following message in 26 moves:

    happy Christmas to you from the New Scientist <blank>

    We can use any of the following sequences:

    1. happy the from Christmas to you Scientist New Christmas to you happy the from to you happy Scientist New happy you Christmas happy you from the

    2. happy the from Christmas to you Scientist New Christmas to you happy the you happy Scientist New happy you from to Christmas happy you from the

    3. happy Christmas to happy Christmas the from to happy Christmas the from to happy Christmas you Scientist New happy Christmas you Scientist New you from the

    4. to Christmas happy the from happy Christmas to the Christmas to you Scientist New happy from Christmas to you Scientist New you from Christmas to the

    5. to Christmas happy the from happy Christmas to the Christmas to you Scientist New happy to Christmas from to Christmas you Scientist New you from the

    6. to Christmas happy the from happy Christmas to the Christmas to you Scientist New happy to you Scientist New you Christmas from to Christmas from the

    The third of these is the published solution.

    However, if we don’t care where the blank is we can make the message in only 25 moves:

    happy <blank> Christmas to you from the New Scientist

    By the following sequence of moves:

    happy the from Christmas Scientist you to Scientist the happy Scientist the happy from Christmas New you happy New you happy to the New you

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: