S2T2

Jim Randell 3:09 pm on 15 January 2024 Permalink Reply
Tags: by: Ian Duff ( 2 )   

• 

  Jim Randell 3:09 pm on 15 January 2024 Permalink | Reply

  Numbers that map to their double must be in the range 01 – 49, and numbers that map to their triple in the range 01 – 33, and we need more than 10 of them.

  If start with any number we always get a chain of 10 numbers before we reach the intended number. So the reassignment of digits must form a complete (length 10) cycle.

  We could generate all possible complete cycles and look for any that meet the remaining conditions, but this is a slow approach (although quite short to program).

  This Python program considers possible mappings that give 11 or more numbers that map to their triple, and then attempts to fill out the remaining values such that a complete cycle is formed.

  It runs in 73ms. (Internal runtime is 9.9ms).

  from enigma import (irange, diff, subsets, peek, map2str, printf)
  
  digits = list(irange(0, 9))
  
  # check a mapping is a complete cycle
  def is_cycle(m):
    if not m: return
    k = peek(m.keys())
    (v, n) = (m[k], 1)
    while v != k:
      v = m[v]
      n += 1
    return n == len(m.keys())
  
  # update a mapping
  def update(m, ks, vs):
    m = m.copy()
    for (k, v) in zip(ks, vs):
      # must be a derangement
      if k == v: return
      # existing key
      if k in m:
        if m[k] != v: return
      else:
        # new key
        if v in m.values(): return
        # make the update
        m[k] = v
    return m
  
  # construct mappings with more than 10 triples
  def solve(k=0, m=dict(), ts=set()):
    # are we done?
    if k > 33:
      if len(ts) > 10:
        yield m
    else:
      # consider mapping k -> 3k
      m_ = update(m, divmod(k, 10), divmod(3 * k, 10))
      if m_:
        yield from solve(k + 1, m_, ts.union({k}))
      # or not
      if m_ != m:
        yield from solve(k + 1, m, ts)
  
  # look for potential mappings
  for r in solve():
    # map remaining keys to remaining values
    ks = diff(digits, r.keys())
    vs = diff(digits, r.values())
    for ss in subsets(vs, size=len, select='P'):
      m = update(r, ks, ss)
      # the map must form a complete cycle
      if not is_cycle(m): continue
      # find doubles and triples
      (ds, ts) = (list(), list())
      for k in irange(0, 49):
        (a, b) = divmod(k, 10)
        v = 10 * m[a] + m[b]
        if v == 2 * k: ds.append(k)
        if v == 3 * k: ts.append(k)
      # we need exactly 4 doubles and more than 10 triples
      if not (len(ds) == 4 and len(ts) > 10): continue
      # output solution
      printf("{m}", m=map2str(m, arr="->", enc=""))
      printf("doubles = {ds}")
      printf("triples = {ts}")
      printf()
  

  Solution: 01 → 13; 23 → 69; 45 → 20; 67 → 84; 89 → 57.

  So the 4 numbers that map to their doubles are:

  05 → 10
  07 → 14
  15 → 30
  17 → 34

  and the 11 numbers that map to their triples are:

  04 → 12
  06 → 18
  11 → 33
  12 → 36
  13 → 39
  21 → 63
  22 → 66
  23 → 69
  31 → 93
  32 → 96
  33 → 99

  LikeLike

• 

  Frits 2:34 pm on 19 January 2024 Permalink | Reply

  Nice solution.

  I also tried the same setup starting with mappings of exactly 4 doubles but that was a lot slower.
  I can’t find the “Run” button anymore when using the replit link.

  LikeLike

  • 

    Jim Randell 5:38 pm on 19 January 2024 Permalink | Reply

    It looks like replit have changed their interface so you can no longer directly run someone else’s code. Now you need to fork it to your own account before you can run it.

    It seems like this means you can no longer use replit to share code as easily as before, which is a bit annoying.

    LikeLike