S2T2

Jim Randell 10:09 am on 26 March 2024 Permalink Reply
Tags: by: Peter G Chamberlain ( 11 )   

• 

  Jim Randell 10:10 am on 26 March 2024 Permalink | Reply

  There are (10 + 4 + 10×4) = 54 possible scores, and we can move in either direction.

  So, when we start on a square the reachable squares spread out from it in both directions. If we have 56 consecutive numbers, and we can make 54 of them using the dice, this would be the maximum possible. And so the largest possible square we can be on is 57 and the smallest possible is 44. And we can’t afford more than 6 non-usable scores.

  We cannot afford more than 1 gap in the scores from 1 to 43 (as any gaps will be mirrored on the other side), or more than 2 gaps overall (if they are close to the end, the gaps could be on the same side – although this seems improbable if they are both primes).

  This Python program considers possible sets of primes on the second die, and let looks for an appropriate starting square. (We could just consider all possible combinations of primes, but it is a bit faster check we don’t introduce too many gaps or overlaps as we build up the sets).

  It runs in 58ms. (Internal runtime is 1.3ms).

  Run: [ @replit ]

  from enigma import (irange, primes, printf)
  
  # squares on the board
  squares = set(irange(1, 100))
  
  # die 1
  d1 = list(irange(1, 10))
  
  # fill out die 2
  def die2(ns, d1, ds, d2=list()):
    k = len(d2)
    if k == 4:
      yield (d2, ds)
    else:
      # choose the next number on die 2
      for (i, n) in enumerate(ns):
        # update the set of deltas
        ds_ = ds.union([n], (n + x for x in d1))
        m = 11 * k + 10
        # check for overlaps and gaps
        if len(ds_) < m + 5: continue
        if len(set(irange(1, m)).difference(ds_)) > (1 if k < 3 else 2): continue
        # fill out the remaining faces
        yield from die2(ns[i:], d1, ds_, d2 + [n])
  
  # die 2 has 4 [different] primes
  ps = list(primes.between(5, 50))
  
  # consider possible die 2 and deltas
  for (d2, ds) in die2(ps, d1, set(d1)):
    n = len(ds)
    # consider starting on square i
    for i in irange(98 - n, 5 + n):
      # find unreachable squares
      missing = squares.difference((i - x for x in ds), (i + x for x in ds), [i])
      # there are exactly 2 primes missing, that are not on d2
      if len(missing) != 2: continue
      if any(x in d2 or x not in primes for x in missing): continue
      # output solution
      printf("die2={d2}; square={i}; missing={missing}", missing=sorted(missing))
  

  Solution: (a) You were on square 51; (b) The numbers on the second die are: 11, 23, 31, 41.

  And the squares that cannot be reached are 29 and 73.

  ---

  Manually we can adopt a “greedy” strategy to maximise the reach of the dice while minimising the gaps:

  Die 10 will cover deltas 1..10 on either side, and if 11 is not on die 2, then both deltas of 11 and 12 are unreachable, which would make at least 4 unreachable squares (2 on each site). So 11 must be on die 2 and we can cover deltas 1..21.

  The next missing delta is now 22 (which is not prime), so we either leave 22 as unreachable, or we put a prime less than 22 on die 2.

  If we leave 22 as unreachable, and put 23 on die 2 then we can cover deltas 1..33, our unreachable values are at ±22, and we can’t have any more gaps.

  The next missing delta is 34, which is not a prime, so the largest prime we can add to die 2 is 31, which means we can cover deltas 1..41 (except 22).

  The next missing delta is 42, so the largest prime we can add is 41, and so with die 2 = (11, 23, 31, 41) we can cover deltas 1..51 (except 22).

  Starting on squares 49..52 we have the following unreachable squares:

  49 → 27, 71 [not both prime]
  50 → 28, 72 [not both prime]
  51 → 29, 73 [both prime, not on die 2 ⇒ solution]
  52 → 30, 74 [not both prime]

  So we have found a single candidate solution, but we can continue and confirm this is the only candidate:

  If we choose to cover 22, by placing the largest possible prime (i.e. 19) on die 2, then we can cover deltas 1..29.

  The next missing delta is now 30, we could choose to leave ±30 unreachable, and place 31 on die 2, so we can cover 1..41 (except 30).

  And then we place 41 on die 2, and we can cover 1..51 (except 30).

  This gives the following unreachable squares with die 2 = (11, 19, 31, 41):

  49 → 19, 79 [both prime, but 19 on die 2]
  50 → 20, 80 [not both prime]
  51 → 21, 81 [not both prime]
  52 → 22, 82 [not both prime]

  This gives no solutions.

  So we need to cover 30, so we place 29 on die 2, we can then cover deltas 1..39.

  We can leave 40 as unreachable and place 41 on die 2, and we cover 1..51 (except 40).

  This gives the following unreachable squares with die 2 = (11, 19, 29, 41):

  49 → 9, 89 [not both prime]
  50 → 10, 90 [not both prime]
  51 → 11, 91 [not both prime]
  52 → 12, 92 [not both prime]

  This gives no solutions.

  So we need to cover 40, so we place 37 on die 2, and we cover 1..47, and this is not enough to leave just 2 unreachable squares.

  And we have found no further candidate solutions.

  LikeLike

  • 

    Hugo 11:39 am on 26 March 2024 Permalink | Reply

    A ten-sided die is not very practical, and a tetrahedron doesn’t roll.
    I suggest using an icosahedron and an octahedron, with each number occurring twice
    (for example, on opposite faces).

    LikeLike

    • 

      Jim Randell 12:23 pm on 26 March 2024 Permalink | Reply

      @Hugh: I think I have seen 10 sided dice based on a pentagonal trapezohedron [@wikipedia]. You could also roll a long dodecahedral prism. A square prism might not be so good though.

      LikeLike

      • 

        Lise Andreasen 4:34 pm on 4 April 2024 Permalink | Reply

        There are standard 4 and 10 sided easily available, among other things for paper RPG.

        LikeLike

• 

  Frits 10:47 pm on 26 March 2024 Permalink | Reply

   
  # primes up to 100
  P = [3, 5, 7]
  P = [2] + P + [x for x in range(11, 100, 2) if all(x % p for p in P)]
  
  # this program tries to follow Jim's manual solution.
  
  # for delta's 1 - 43 we can afford to miss one delta
  
  # add a new prime allowing only 1 gap for the first 43 delta's
  def solve(d, ds=[], skip=0):
    if len(ds) == 4:
      # check number of possible reachable squares
      if 2 *(ds[-1] + 10 - (skip > 0)) > 96:
        yield (ds, skip)
    else:
      # try to make delta <d> or ...
      if d in P:
        yield from solve(d + 11, ds + [d], skip)    
      else:
        # largest prime we can add to die 2
        lp = [p for p in P if p < d and p != skip][-1]
        yield from solve(lp + 11, ds + [lp], skip)    
      # ... leave delta <d> as unreachable
      if not skip:
        yield from solve(d + 1, ds, d)  
  
  # deltas 1-10 will be covered by the first die
  for d2, skip in solve(11):
    # we can cover deltas 1..r except possible <skip>
    r = d2[-1] + 10
    
    # one delta must have been skipped, otherwise the number of possible
    # reachable squares is too low
    
    # consider starting on square <pos>
    for pos in range(100 - r, r + 2) :
      # non-reachables
      nr = [pos - skip, pos + skip] 
      if any(x for x in nr if x not in P or x in d2): continue
      print(f"answer: Peter was on square {pos}, "
            f"the four numbers on the second die are: {d2}")    
  

  LikeLike