S2T2

Jim Randell 10:27 am on 17 November 2020 Permalink Reply
Tags: by: Richard Beetham ( 2 )   

• 

  Jim Randell 10:28 am on 17 November 2020 Permalink | Reply

  We can drastically reduce the number of possibilities we have consider:

  When the game is played the squares are filled out in a particular order. If, when we play the game, instead of filling in numbers we just note how many times the value in each particular square is trebled, then at the end we can find the minimum score for that particular ordering of squares by assigning 9 to the square that is trebled the fewest number of times (i.e. the final square filled out), 8 to the next lowest number of treblings, and so on until 1 is assigned to the square with the largest number of treblings.

  This Python program considers all possible orderings for filling out the squares. It runs in 420ms.

  Run: [ @repl.it ]

  from enigma import grid_adjacency, subsets, irange, printf
  
  # numbers to fill out
  nums = list(irange(1, 9))
  
  # grid adjacency matrix
  adj = grid_adjacency(3, 3)
  
  # multipliers (for number of treblings)
  mul = [1, 3, 9, 27, 81]
  
  # find the minimal score for a ordering of squares
  def play(js):
    # initial grid
    grid = [None] * 9
    # place the numbers
    for j in js:
      # place the number
      grid[j] = 0
      # and increase adjacent counts
      for i in adj[j]:
        if grid[i] is not None:
          grid[i] += 1
    # determine the minimum score
    return sum(n * mul[k] for (n, k) in zip(nums, sorted(grid, reverse=1)))
  
  # choose an ordering for the squares, and find the minimum score
  r = min(play(js) for js in subsets(irange(9), size=len, select="P"))
  printf("min score = {r}")
  

  Solution: The smallest possible score is 171.

  One way of getting this total is:

  [ A, B, C ] [ D, E, F ] [ G, H, J ]
  [ 2, B, C ] [ D, E, F ] [ G, H, J ]
  [ 6, 3, C ] [ D, E, F, ] [ G, H, J ]
  [ 6, 9, 4 ] [ D, E, F ] [ G, H, J ]
  [ 6, 27, 4 ] [ D, 1, F ] [ G, H, J ]
  [ 18, 27, 4, ] [ 5, 3, F ] [ G, H, J ]
  [ 18, 27, 12 ] [ 5, 9, 6 ] [ G, H, J ]
  [ 18, 27, 12 ] [ 15, 9, 6 ] [ 7, H, J ]
  [ 18, 27, 12 ] [ 15, 27, 6 ] [ 21, 8, J ]
  [ 18, 27, 12 ] [ 15, 27, 18 ] [ 21, 24, 9 ] = 171

  We can make the program run faster by exploiting the symmetry of the grid. For example, for the first move, we only need to consider one corner square, one edge square and the central square. It does make the program longer though.

  LikeLike

• 

  Frits 11:02 am on 19 November 2020 Permalink | Reply

  The first part finds the minimum score for different kind of treblings under the condition that they add up to 12. It turns out this minimum can also be achieved by our number placing rules.

  I didn’t immediately see how I could check if a list [A,B,C,D,E,F,G,H,J] from the result can be achieved so I reused Jim’s code to find the first permutation which has a score equal to this minimum.

  from enigma import SubstitutedExpression, grid_adjacency, subsets
  
  # numbers to fill out
  nums = list(range(1, 10))
  
  # grid adjacency matrix
  adj = grid_adjacency(3, 3)
  
  # multipliers (for number of treblings)
  mul = [1, 3, 9, 27, 81]
  
  score = lambda li: sum(n * mul[k] 
                     for (n, k) in zip(nums, sorted(li, reverse=1)))
  
  # the alphametic puzzle
  p = SubstitutedExpression(
    [
    # if field x has adjacent fields x1...xn and k of them have already been set
    #
    # then k fields will now get trebled which previously didn't treble field x
    # and (n - k) fields will not get trebled now but later on will treble 
    # field x (n - k) times. So for every trebling there is an instance of 
    # non-trebling.
    #
    # adjacent field matrix;
    #
    #  2  3  2    sum of all elements is 24  
    #  3  4  3    half of them will not get trebled
    #  2  3  2
    "sum([A,B,C,D,E,F,G,H,J]) == 12", 
    ],
    answer="score([A,B,C,D,E,F,G,H,J]), A,B,C,D,E,F,G,H,J",
    digits=range(0, 5),
    env=dict(score=score),
    accumulate=min,  
    d2i={3 : "ACGJ", 4: "ACGJBDFH"},
    distinct="",
    verbose=0)   
    
  # solve the puzzle
  r = p.run()
  min = list(r.accumulate)[0]
  
  lst = []
  prt = ["A", "B", "C", "D", "E", "F", "G", "H", "J"]
  
  # check if this minimum can be achieved
  for js in subsets(range(9), size=len, select="P"):
    grid = [None] * 9
    # place the numbers
    for j in js:
      # place the number
      grid[j] = 0
      # and increase adjacent counts
      for i in adj[j]:
        if grid[i] is not None:
          grid[i] += 1
          
    if score(grid) == min:
      print("smallest possible score:", min, "\n\nexample:\n")
     
      # sort grid (descending)
      lst = sorted(grid, reverse=True)
     
      # print all the steps
      for i in range(9):  
        for k, j in enumerate(js):
          if j != i: continue
          g = grid[k]
          ind = lst.index(g) 
          lst[ind] = -1          # set to "processed"
          prt[k] = ind + 1       # set field
          
          # treble adjacent fields
          for m in adj[k]:
            if type(prt[m]) == int:
              prt[m] *= 3
            
          print(f"{prt[:3]} {prt[3:6]} {prt[6:]}")
      break  # we only print one example
      
  # smallest possible score: 171
  #
  # example:
  #
  # [2, 'B', 'C'] ['D', 'E', 'F'] ['G', 'H', 'J']
  # [6, 3, 'C'] ['D', 'E', 'F'] ['G', 'H', 'J']
  # [6, 9, 4] ['D', 'E', 'F'] ['G', 'H', 'J']
  # [6, 27, 4] ['D', 1, 'F'] ['G', 'H', 'J']
  # [18, 27, 4] [5, 3, 'F'] ['G', 'H', 'J']
  # [18, 27, 12] [5, 9, 6] ['G', 'H', 'J']
  # [18, 27, 12] [15, 9, 6] [7, 'H', 'J']
  # [18, 27, 12] [15, 27, 6] [21, 8, 'J']
  # [18, 27, 12] [15, 27, 18] [21, 24, 9]    
  

  LikeLike