S2T2

Jim Randell 9:16 am on 7 October 2021 Permalink Reply
Tags: by: Dr V W Bryant ( 5 )   

• 

  Jim Randell 9:17 am on 7 October 2021 Permalink | Reply

  This Python program runs in 144ms.

  Run: [ @replit ]

  from enigma import (empty, Accumulator, ordered, tuples, SubstitutedExpression, irange, translate, join, cached, printf)
  
  # adjacency matrix
  adj = [
    [1, 3, 4], # 0
    [0, 2, 5], # 1
    [1, 3, 6], # 2
    [0, 2, 7], # 3
    [0, 5, 7, 8], # 4
    [1, 4, 6, 8], # 5
    [2, 5, 7, 8], # 6
    [3, 4, 6, 8], # 7
    [4, 5, 6, 7], # 8
  ]
  
  # distances for each edge
  dist = {
    (0, 1): 314, (1, 2): 314, (2, 3): 314, (0, 3): 314, # = 100 pi
    (0, 4): 100, (1, 5): 100, (2, 6): 100, (3, 7): 100,
    (4, 5): 157, (5, 6): 157, (6, 7): 157, (4, 7): 157, # = 50 pi
    (4, 8): 100, (5, 8): 100, (6, 8): 100, (7, 8): 100,
  }
  
  # find paths from A to B, avoiding Xs
  def paths(A, B, Xs=empty, s=[]):
    if A == B:
      yield s
    else:
      # move forward from A
      for x in adj[A]:
        if x not in s and x not in Xs:
          yield from paths(x, B, Xs, s + [x])
  
  # find minimal distance paths
  @cached
  def min_path(A, B, Xs=empty):
    r = Accumulator(fn=min, collect=1)
    for s in paths(A, B, Xs, [A]):
      d = sum(dist[ordered(x, y)] for (x, y) in tuples(s, 2))
      r.accumulate_data(d, s)
    return r
  
  # is there a minimal path with n intermediates, that include incs?
  def check(A, B, Xs, n=None, incs=[]):
    incs = set(incs)
    r = min_path(A, B, frozenset(Xs))
    for p in r.data:
      if len(p) == n + 2 and incs.issubset(p): return True
    return False
  
  # check distance avoiding Xs is over twice as far
  def check2(A, B, Xs):
    r1 = min_path(A, B)
    r2 = min_path(A, B, frozenset(Xs))
    return (r2.value > 2 * r1.value)
  
  # make a solver
  p = SubstitutedExpression(
    [
      # M -> S passes only T
      "check(M, S, [], 1, [T])",
      # N -> Q passes L and 1 other
      "check(N, Q, [], 2, [L])",
      # P -> N passes 1 other plant
      "check(P, N, [R, S, T], 1)",
      # but she has to walk over twice as far going from O -> M
      "check2(O, M, [R, S, T])",
    ],
    digits=irange(0, 8),
    env=dict(check=check, check2=check2),
    verbose=0,
  )
  
  # run the solver
  for s in p.solve():
    # map positions to symbols
    m = dict((v, k) for (k, v) in s.items())
    # remove duplicate layouts
    if not (m[1] < m[3] and m[0] < min(m[1], m[2], m[3])): continue
  
    # output solution: (outer) (inner) (centre) -> wife's path from N to M
    printf("{m}", m=translate("({0} {1} {2} {3}) ({4} {5} {6} {7}) ({8})", (lambda x: m[int(x)])))
    r = min_path(s['N'], s['M'], frozenset([s['R'], s['S'], s['T']]))
    for p in r.data:
      printf("-> {p}", p=join((m[x] for x in p), sep=" "))
    printf()
  

  Solution: The plants passed are: Orpine, Polyanthus, Quitch.

  ---

  Here is a layout of the plants (reflections/rotations of this layout also work), with the wife’s best route from N to M indicated:

  

  LikeLike

  • 

    Frits 11:39 am on 7 October 2021 Permalink | Reply

    @Jim, I would say there is no solution as normally “twice as far” would mean twice the distance, not at least twice the distance.

    LikeLike

    • 

      Jim Randell 11:50 am on 7 October 2021 Permalink | Reply

      @Frits: the puzzle text says “she has to walk over twice as far”, so the wife has to travel more than twice the distance of the shortest path.

      LikeLike

      • 

        Frits 11:56 am on 7 October 2021 Permalink | Reply

        @Jim, you are right.

        LikeLike