S2T2

Jim Randell 7:49 am on 21 January 2025 Permalink Reply
Tags: by: Danny Roth ( 84 )   

• 

  Jim Randell 7:50 am on 21 January 2025 Permalink | Reply

  I reused the code written to solve Enigma 1600, which is a similar puzzle.

  With 6 weights we can combine them in pairs to make C(6, 2) = 15 pairs, so to make exactly 14 values only one of them is repeated.

  So we can either make:

  [13 values], [not 100, 101], [102] = [87..102] \ {100, 101}
  [99], [not 100, 101], [13 values] = [99..114] \ {100, 101}

  This Python 3 program runs in 68ms. (Internal runtime is 1.6ms).

  from enigma import (irange, diff, C, div, multiset, subsets, is_prime, printf)
  
  # extend <ss> with <k> more values to make numbers in <ns>
  def pairs(ns, ss, k):
    # are we done?
    if k == 0 or not ns:
      if k == 0 and not ns:
        yield ss
    elif C(k, 2) + k * len(ss) >= len(ns):
      # add in the next smallest value
      for x in irange(ss[-1] + 1, max(ns) - ss[-1]):
        # and solve for the remaining numbers
        ns_ = diff(ns, set(x + y for y in ss))
        yield from pairs(ns_, ss + [x], k - 1)
  
  # find <k> values that can be used in pairs to make <ns>
  def solve(ns, k):
    # suppose the values start [0, a, ...]
    # then the pairs start [a, ...]
    m = ns[-1] - ns[0] + 5 - 2 * k
    for a in irange(1, m):
      # reduce the numbers so that they start at a
      d = div(ns[0] - a, 2)
      if d is None: continue
      vs = list(n - 2 * d for n in ns)
      # solve the reduced list
      for ss in pairs(vs[1:], [0, a], k - 2):
        # return (<values>, <pair sums>)
        ss = tuple(v + d for v in ss)
        ps = sorted(x + y for (x, y) in subsets(ss, size=2))
        yield (ss, ps)
  
  # consider a sequence of 16 consecutive values that includes 100, 101
  for i in [87, 99]:
    ns = diff(irange(i, i + 15), {100, 101})
    for (ss, ps) in solve(ns, 6):
      # now find what values we can make, and check duplicates
      (ds, xs) = multiset.from_seq(ps).differences(ns)
      if xs or ds.size() != 1: continue
      # the duplicate value is prime
      d = ds.peek()
      if not is_prime(d): continue
      # output solution
      printf("{ss} -> {ns}; duplicate = {d}")
  

  Solution: The weights of the medallions are: 43, 44, 45, 46, 49, 53 grams.

  Taken in pairs these make the values:

  87, 88, 89 (twice), 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 102

  LikeLike