S2T2

Jim Randell 4:40 pm on 14 June 2024 Permalink Reply
Tags: by: Victor Bryant ( 139 )   

• 

  Jim Randell 4:52 pm on 14 June 2024 Permalink | Reply

  See also: Teaser 1858 and Enigma 14.

  I re-used the H() function from Teaser 1858 to calculate the number of moves required for a configuration of discs.

  This Python program runs in 65ms. (Internal runtime is 421us).

  Run: [ @replit ]

  from enigma import (Accumulator, irange, inf, nsplit, is_increasing, printf)
  
  # number of moves for sequence of discs (largest to smallest)
  def H(ns):
    t = 0
    m = 1
    for n in ns:
      t += m * n
      m *= 2
    return t
  
  # consider numbers of different size discs
  for n in irange(1, inf):
    r = Accumulator(fn=min)
    # duplicate one of the discs
    for i in irange(n):
      ns = [1] * n
      ns[i] += 1
      # calculate the number of moves
      t = H(ns)
      # answer is a 4 digit number consisting of strictly increasing digits
      if 999 < t < 10000 and is_increasing(nsplit(t), strict=1):
        printf("{ns} -> {t}")
      r.accumulate(t)
    if r.value >= 6789: break
  

  Solution: The minimum number of moves required is 1279.

  The arrangement of discs is:

  

  There are 11 discs (of 10 different sizes) and discs 9 and 10 (counting from the bottom) are the same size.

  So the number of moves is:

  1×1 + 1×2 + 1×4 + 1×8 + 1×16 + 1×32 + 1×64 + 1×128 + 2×256 + 1×512 = 1279

  ---

  With analysis:

  The number of moves for a standard “Tower of Hanoi”, is the sum of the powers of 2 corresponding to each disc.

  So for a tower of 4 discs we would have:

  1 + 2 + 4 + 8 = 15 moves

  When one of the discs is duplicated we also duplicate one of the powers of 2, and this gives us a 4-digit increasing number (the smallest is 1234, and the largest 6789).

  So our starting tower must have between 10 and 12 different sizes.

  Summing the first n powers of 2:

  n=10: sum(1..512) = 1023
  n=11: sum(1..1024) = 2047
  n=12: sum(1..2048) = 4095

  And we need to duplicate one of the powers of 2 to give a number with (strictly) increasing digits:

  1023 + 256 = 1279
  2047 + 512 = 2559 (increasing, but not strictly increasing)

  LikeLike