Enigmatic Code

Programming Enigma Puzzles

Enigma 1762: Quo Vadis? II

From New Scientist #2930, 17th August 2013 [link]

Enigma 1762

On the grid shown on the right, place the remaining 11 cards on the unshaded squares so that when you move from card to card the number of squares in the direction shown on each, you complete a circuit visiting all 12 unshaded squares once.

What are the numbers on the cards, from top to bottom, in the third column?

[enigma1762]

Advertisements

11 responses to “Enigma 1762: Quo Vadis? II

  1. Jim Randell 14 August 2013 at 6:33 pm

    Basically the same puzzle as Enigma 1748. So it is unsurprising that the same technique can be used to solve it. This Python program – the same as my solution for Enigma 1748, but with some parameters altered – runs in 38ms.

    from enigma import irange, printf
    
    # use integers to represent the cells in the centre of a 10x4 grid
    # so: (r, c) -> 10 * r + c + 3
    def rc2i(r, c, offset=3):
      return 10 * r + c + offset
    
    # empty grid
    g = dict((rc2i(r, c), None) for (r, c) in (
      (0, 0), (0, 1), (0, 2),
      (1, 0), (1, 2), (1, 3),
      (2, 0), (2, 2), (2, 3),
      (3, 1), (3, 2), (3, 3),
    ))
    
    # placed cards
    g[rc2i(0, 0)] = rc2i(+2, 0, 0)
    
    # unplaced cards
    cards = set(rc2i(r, c, 0) for (r, c) in (
      (+1, 0), (+3, 0),
      (-1, 0), (-2, 0), (-3, 0),
      (0, -1), (0, -2), (0, -3),
      (0, +1), (0, +2), (0, +3),
    ))
    
    # represent the card at position p
    def card(g, p):
      if p not in g: return 'XX'
      (r, c) = divmod(abs(g[p]), 10)
      if r == 0:
        return str(c) + ('R' if g[p] > 0 else 'L')
      else:
        return str(r) + ('D' if g[p] > 0 else 'U')
    
    # output a solution
    def output(g):
      for r in irange(0, 3):
        print(''.join('[' + card(g, rc2i(r, c)) + ']' for c in irange(0, 3)))
      print('')
    
    # return an updated dictionary
    def add(d, k, v):
      d = d.copy()
      d[k] = v
      return d
    
    # g - current grid
    # p - current position in grid
    # t - target position
    # cards - remaining cards
    def solve(g, p, t, cards):
      # are there any cards left to place?
      if len(cards) == 0:
        # have we reached the target
        if p == t: output(g)
        return
      # otherwise try placing a card
      for c in cards:
        # where does it point?
        n = p + c
        # if it's not the last card it should point to an empty square
        if n in g and (len(cards) == 1 or g[n] is None):
          # solve for the remaining cards
          solve(add(g, p, c), n, t, cards.difference([c]))
    
    # solve (2, 0) -> ... -> (0, 0)
    solve(g, rc2i(2, 0), rc2i(0, 0), cards)
    

    Solution: The numbers in the third column are: 3, 1, 2, 1.

    Here’s the completed grid:

    Enigma 1762 - Solution

  2. arthurvause 14 August 2013 at 7:27 pm

    And here’s my modified version of 1748:

    from itertools import product
    
    def add(u,v):
        return ( u[0]+v[0],u[1]+v[1])
    
    blank=(0,0)
    R1,R2,R3 = (1,0),(2,0),(3,0)
    L1,L2,L3 = (-1,0),(-2,0),(-3,0)
    U1,U2,U3 = (0,-1),(0,-2),(0,-3)
    D1,D2,D3 = (0,1),(0,2),(0,3)
    
    candidates = [ [D2], [L1,R1,R3], [L1,L2,D1,D3], [blank], \
                   [U1,D1,R2,R3], [blank], [L2,R1,U1,D1], [L3,L1,D1], \
                   [U1,R2,R3], [blank], [L2,R1,U2,U1,D1], [L3,L1,U1,D1], \
                   [blank], [U3,R1,R2], [U1,U2,U3,L1,R1], [L2,L1,U1,U2] ]
    
    for c in product(*candidates):
      if len(set(c))==13:
        pos = (0,0)
        for i in xrange(12):
          pos = add(pos,c[pos[0]+pos[1]*4])
          if pos == (0,0):
            if i<11:
              break
            else:
              for row in xrange(4):  
                print [c[4*row+col] for col in xrange(4)]
       
    
    • saracogluahmet 15 August 2013 at 3:10 pm

      Hi,
      Execution time of your code on my machine is almost 7.5 seconds

      • arthurvause 20 August 2013 at 8:21 am

        Indeed. Here is a faster version:

        R1,R2,R3,L1,L2,L3 = 1,2,3,-1,-2,-3
        U1,U2,U3,D1,D2,D3 = -4,-8,-12,4,8,12
        labels={1:"R1",2:"R2",3:"R3", -1:"L1",-2:"L2",-3:"L3", \
                -4:"U1",-8:"U2",-12:"U3", 4:"D1",8:"D2",12:"D3",  0:"  "}
        
        candidates = [ set((D2,)), set((L1,R1,R3,D3)), set((L1,L2,D1,D3)), set(), \
                       set((U1,D1,R2,R3)), set(), set((L2,R1,U1,D1)), set((L3,L1,D1)), \
                       set((U1,R2,R3)), set(), set((L2,R1,U2,U1,D1)), set((L3,L1,U1,D1)), \
                       set(), set((U3,R1,R2)), set((U1,U2,U3,L1,R1)), set((L2,L1,U1,U2)) ]
        
        available = set((R1,R2,R3,L1,L2,L3,U1,U2,U3,D1,D3))
        occupied = [D2,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0]
        counter=0
        pos=0
        
        def check(pos):
          moves = candidates[pos] & available
          for m in moves:
            if occupied[pos+m] in (0,D2):  
              available.remove(m)
              occupied[pos]=m
              if len(available)==0:
                for row in xrange(4):
                  for col in xrange(4):
                    print labels[occupied[col+4*row]],
                  print " "
              else:
                check(pos+m)  
              available.add(m)
              occupied[pos]=0
        
        check(D2)
        
  3. saracogluahmet 14 August 2013 at 9:59 pm

    I used the same approach where I did use in Enigma 1748,
    I start to walk from the first cell,

    1376513633.509371
    Cells [-1, 2, 5, 6, 1, 9, 7, 10, 0, 4, 8]
    1376513633.540597
    Timing in my machine is like above,

    
    import time
    print(time.time())
    path=[[False for i in range(5)]for i in range(5)]
    Rls=[False]*11
    path[0][0]=True
    cells=[-1]*11
    rule=[[0,1],[0,2],[0,3],[0,-1],[0,-2],[0,-3],[-1,0],[-2,0],[-3,0],[1,0],[3,0]]
    
    flag=False
    
    def valid(x,y,i):
    
        if Rls[i]==True:
            return False
    
        if x<0 or x>3:
            return False
        if y<0 or y>3:
            return False
        if x==0 and y==3:
            return False
        if x==1 and y==1:
            return False
        if x==2 and y==1:
            return False
        if x==3 and y==0:
            return False
        if x==0 and y==0:
            return False
        
        
        if path[x][y]==True:
            return False
        path[x][y]=True
        Rls[i]=True
        return True
    
    
    def traverse(cells,counter,x,y):
        global flag
    
        if flag==True:
            return 
        for i in range(11):
            a,b=rule[i]
            cells[counter]=i
            ##print("x=",x+a,"y=",y+b)
            if valid(x+a,y+b,i):
                ##print("x=",x+a,"y=",y+b)
                #print(cells)
                if counter==10:
                    print("Cells",cells)
                    flag=True
                else:
                    ##print ("IN",x,y,i,counter)
                    traverse(cells,counter+1,x+a,y+b)
                #print("hi",i,"x:",x,"y:",y,"a",a,"b",b)
                #print (i,x,y,a,b,path[x+a][y+b])
                Rls[i]=False
                path[x+a][y+b]=False
                ##print(path[x+a][y+b])
    
    
    traverse(cells,1,2,0)
    print(time.time())
    
    • saracogluahmet 14 August 2013 at 10:24 pm

      Cells [-1, 2, 6, 5, 1, 9, 7, 10, 0, 4, 8] must be replaced with the previous one, the first one in invalid and “path[0][0]= True” must be replaced with path[2][0]=True at the top of the code, and in the valid function [0][0] cell is not checked, instead, [2][0] cell will be checked, as the first cell has been given already, no need to check that.

      • Brian Gladman 15 August 2013 at 8:32 am

        Ahmet, why are you still using such an error prone method for timing your code when you know that this has caused you problems in the past?

        If for some reason you don’t want to use a better method, you could at least put ‘start=time.time()’ at the beginning and ‘print(time.time() – start)’ at the end to avoid the need to do the manual subtraction.

        • saracogluahmet 15 August 2013 at 11:18 am

          Hi Brian,

          You are right 🙂

          Cells [-1, 2, 6, 5, 1, 9, 7, 10, 0, 4, 8]
          0.015599966049194336
          I did that what you said, I guess this means 15 ms almost 16 ms, and my machine’s cpu 2.60 Hz and 6GB Ram.

          You would like to test the timing on your processors, if you wish.

          • Brian Gladman 16 August 2013 at 11:23 pm

            You are lucky to find the right path Ahmet as there is another bug in your code. When you reach the end of your path you need to check that the last move gets you back to the first cell but you don’t check this since you only use 10 of the eleven cards. As it happens the unused card on your path is (0,-1) so it does get back to (0, 0), which was lucky 🙂

            Here is a a commented and (I hope) corrected version of your code that uses Jim’s new timer in his latest enigma version

            from enigma import Timer
            
            timer = Timer()
            
            # the 11 possible moves as [down, right] where x is down and y is right 
            rules = [ [ 0, 1], [ 0, 2], [ 0, 3],
                      [ 0,-1], [ 0,-2], [ 0,-3],
                      [-1, 0], [-2, 0], [-3, 0],
                      [ 1, 0], [ 3, 0] ]
            
            # is a move to grid cell 
            def valid(x, y, i):
            
              # if the new position is outside the 4 by 4 grid 
              if ( x < 0 or x > 3 or y < 0 or y > 3 or
                   # or it is on a shaded cell
                   y == 0 and x == 3 or
                   y == 1 and x in (1, 2) or
                   y == 3 and x == 0 ):
                return False
            
              # return True if the cell is not yet on the path
              return not grid[x][y]
            
            def traverse(path, counter, x, y):
            
              # 'counter' is the position on the path and the contents of 
              # path[counter] is the rule used at this point on the path
              
              # apply all (unused) rules at this point on the grid
              for i, (a, b)  in enumerate(rules):
                # if the rule has not been used yet
                if not rule_used[i]:
                  xx, yy = x + a, y + b
                  # check if the prospective move is legal
                  if valid(xx, yy, i):
                    # if so, put this rule on the grid at the current position
                    path[counter] = i
                    # check if we have used all cards and are back at the first cell
                    if counter == 10 and xx == yy == 0:
                      # now find content of grid column three (yp == 2)
                      col3, xp, yp = [0] * 4, 2, 0
                      # move along the path
                      for r in path:
                        # the move for this point on the path 
                        a, b = rules[r]
                        # if in column three, store the card value indexed on x
                        if yp == 2:
                          col3[xp] = str(abs(a + b)) + ' and '  
                        # move to the next cell on the path
                        xp, yp = xp + a, yp + b
                      col3 = ''.join(col3).replace(' and ', ', ', 2)[:-5]
                      print('The values in the third column are {:s}.'.format(col3))
                    else:
                      # mark the grid position and the rule used 
                      grid[xx][yy] = True
                      rule_used[i] = True
                      # otherwise continue to build the path
                      traverse(path, counter + 1, xx, yy)
                      # free the grid position and the rule for use 
                      rule_used[i] = False
                      grid[xx][yy] = False
            
            # the 4 by 4 grid of path
            grid = [[False] * 4 for i in range(4)]
            # for marking the move rules as used
            rule_used = [False] * 12
            # start AFTER the move from the first cell
            grid[2][0] = True
            # initialises positions on the path
            path = [-1] * 11
            traverse(path, 0, 2, 0)
            

            Do not despair – you are not the only one with bugs this week!

  4. Brian Gladman 14 August 2013 at 10:22 pm

    I am sad to say that in doing this one I found a bug in my two solutions to enigma 1748 😦 I don’t like leaving buggy code around so if you could correct my two programs for that enigma, Jim, I would be most grateful – the return on line 45 in the first and line 48 in the second should be indented by two more spaces (one more level).

    Here is this one:

    # Each cell in the 4 by 4 array is represented by two characters
    # in a 32 character string,  starting at the top left and ending
    # at the bottom right.   The first character in a cell gives the
    # number of steps,  the second the direction (L, R, U, D), where
    # empty cells contain '  ' and shaded cells contain 'SH'.
    
    # the moves along the sequence as a function of a cell's contents
    moves = {'1L':-2, '2L': -4, '3L': -6, '1R':2, '2R': 4, '3R': 6,
             '1U':-8, '2U':-16, '3U':-24, '1D':8, '2D':16, '3D':24 }
    
    # place the next arrow in the next empty, unshaded cell
    def place(cells, arrows, crnt, l):
    
      # find the next vacant cell after the current one
      while True:
        # the contents of the current cell
        cell = cells[crnt:crnt+2]
        # break if it is empty
        if cell == '  ':
          break
        # otherwise move on to the next cell
        crnt += moves[cell]
      assert cells.count(' ') == len(arrows)
      # try each remaining arrow in this empty cell
      for p in range(0, len(arrows), 2):
        # the arrow symbol
        cell = arrows[p:p+2]
        # the position of the next cell in the sequence
        move = crnt + moves[cell]
        # ensure that Left/Right moves stay in the current row
        if cell[1] in ('L', 'R') and move // 8 != crnt // 8:
          continue
        # skip positions outside the sequence or occupied cells
        if not 0 <= move < len(cells) or move and cells[move] != ' ':
          continue
        # remove the chosen cell value from arrows
        new_arrows = arrows.replace(cell, '', 1)
        # and insert it into cells
        new_cells = cells[:crnt] + cell + cells[crnt+2:]
    
        # if we are about to move to the first (top left) cell
        if move == 0:
          # and we have placed all the arrow symbols
          if not new_arrows:
            # then output the ressult
            print('The numbers in the third column are {:s}.'.format(
              (' and '.join(new_cells[4:32:8])).replace(' and', ',', 2)))
            return
        else:
          # otherwise place the next arrow symbol
          place(new_cells, new_arrows, crnt, l + 1)
    
    # the given starting point
    cells = '2D    SH  SH      SH    SH      '
    # the arrow symbols to be placed
    arrows = '1R2R3R1L2L3L1U2U3U1D3D'
    place(cells, arrows, 0, 0)
    
  5. saracogluahmet 17 August 2013 at 10:56 am

    As I have forgotton to uncomment two lines in my previous code, I have deleted those two lines, and I have changed so, yeah, my code had a small bug, but the algorithm is the same as the previous one, sorry for that. This is the last one and the timing is the same as in the previous one, I am sorry to have uncommented those two lines.

    import time
    start=time.time()
    path=[[False for i in range(5)]for i in range(5)]
    Rls=[False]*11
    
    path[2][0]=True
    cells=[-1]*11
    rule=[[0,1],[0,2],[0,3],[0,-1],[0,-2],[0,-3],[-1,0],[-2,0],[-3,0],[1,0],[3,0]]
    
    flag=False 
    
    def valid(x,y,i):
    
        if Rls[i]==True:
            return False
    
        if x<0 or x>3:
            return False
        if y<0 or y>3:
            return False
        if x==0 and y==3:
            return False
        if x==1 and y==1:
            return False
        if x==2 and y==1:
            return False
        if x==3 and y==0:
            return False
        
        if path[x][y]==True:
            return False
        path[x][y]=True
        Rls[i]=True
        return True
    
    
    def traverse(cells,counter,x,y):
        global flag
    
        
        for i in range(11):
            a,b=rule[i]
            cells[counter]=i
            ##print("x=",x+a,"y=",y+b)
            if valid(x+a,y+b,i):
                ##print("x=",x+a,"y=",y+b)
                #print(cells)
                if counter==10:
                    print("Cells",cells)
                    #flag=True
                else:
                    ##print ("IN",x,y,i,counter)
                    traverse(cells,counter+1,x+a,y+b)
                #print("hi",i,"x:",x,"y:",y,"a",a,"b",b)
                #print (i,x,y,a,b,path[x+a][y+b])
                Rls[i]=False
                path[x+a][y+b]=False
                ##print(path[x+a][y+b])
    
    
    traverse(cells,0,2,0)
    print(time.time()-start)
    

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: