S2T2

Jim Randell 10:08 am on 31 October 2019 Permalink Reply
Tags: by: A K Austin ( 4 )   

• 

  Jim Randell 10:10 am on 31 October 2019 Permalink | Reply

  This Python 3 program runs in 77ms.

  Run: [ @repl.it ]

  from enigma import update, join, printf
  
  # the towns, the buses, the roads
  towns = (A, B, C, D, E) = list("ABCDE")
  buses = "rbgy" 
  roads = {
    A: (B, C, D),
    B: (A, C, E),
    C: (A, B, D),
    D: (A, C, E),
    E: (B, D),
  }
  
  # follow a journey
  # bs = buses remaining to take
  # p = current location
  # t = target location
  # m = current map
  # return (map, towns)
  def journey(bs, p, t, m, s=None):
    if s is None: s = [p]
    # are we done?
    if not bs:
      # can we reach the target in one hop?
      if t in roads[p]:
        # is the road already on the map
        if (p, t) in m:
          yield (m, s + [t])
        # can we add it to the map?
        elif (t, p) not in m:
          yield (update(m, [(p, t)], ['?']), s + [t])
    else:
      # choose an onward road
      for x in roads[p]:
        # is it already in the map?
        if (p, x) in m:
          # and is it the right colour?
          if m[(p, x)] == bs[0]:
            # solve for the remaining buses
            yield from journey(bs[1:], x, t, m, s + [x])
          elif m[(p, x)] == '?':
            yield from journey(bs[1:], x, t, update(m, [(p, x)], [bs[0]]), s + [x])
        # can we add it to the map?
        elif (x, p) not in m:
          # solve for the remaining buses
          yield from journey(bs[1:], x, t, update(m, [(p, x)], [bs[0]]), s + [x])
  
  # solve for a collection of journeys between s and t
  def solve(s, t, js, m={}, ss=[]):
    # are we done?
    if not js:
      yield (m, ss)
    else:
      # solve for the first journey
      for (m1, s1) in journey(js[0], s, t, m):
        # and then for the remaining journeys
        yield from solve(s, t, js[1:], m1, ss + [s1])
  
  # solve the journeys
  for (m, ss) in solve(A, E, ["rbybgy", "grbgrbr", "gybybr"], { (A, B): '?' }):
    # output solution
    printf("map: {m}", m=join((join((k[0], '->', k[1], ' = ', v)) for (k, v) in m.items()), sep="; "))
    for (i, s) in enumerate(ss, start=1):
      printf("day {i}: {s}", s=join(s, sep=" -> "))
    printf()
  

  Solution: The bus that runs from Catville to Dogchester is red.

  The bus routes are as shown in the following diagram:

  

  The journeys are:

  Day 1: A → B → E → D → A → C → B → E
  Day 2: A → C → D → A → C → D → A → B → E
  Day 3: A → C → B → E → D → A → B → E

  This is the only solution with a bus running from A to B. However if the bus ran from B to A the solution would be:

  A → C = green
  A → D = red
  B → A = blue
  C → B = red
  C → D = yellow
  D → E = blue
  E → B = yellow

  LikeLike