Enigmatic Code

Programming Enigma Puzzles

Enigma 442a: Hark the herald angels sing

From New Scientist #1592, 24th December 1987 [link]

“Have a mince pie.”

“Thanks. How did the carol singing go this evening?”

“Very well indeed. There were 353 of us. We started from the village church at 6:00pm and arrived here at the hall some time ago. Have a look at this map here on the wall.

Enigma 442a

“We divided into groups and between us we covered every one of the 12 roads once. For each road, the group would enter at one end, sing the carols as they walked along the road, and leave at the other end. At each of the five junctions, all the groups due to arrive at that junction would come together and then re-divide before setting off again.”

“Did you sing many carols?”

“On each road, every member of the group would sing one verse as a solo. A verse takes one minute to sing.”

“Did people get cold waiting at the junctions for the other groups to join them?”

“No. That is the marvellous thing. We had divided into groups so that, at each junction, all the groups for that junction arrived at precisely the same time. Similarly, all the groups arrived at the hall at the same time.”

“You were very fortunate — a little miracle.”

“Don’t forget,” said the vicar who had been standing with us, “it is Christmas Eve.”

What time did the singers arrive at the hall and what was the total number of verses that they sang?

[enigma442a] [enigma442]

5 responses to “Enigma 442a: Hark the herald angels sing

  1. Jim Randell 30 March 2018 at 7:57 am

    I labelled the nodes from A to G, with the Church being A and the Hall being G. In the program I added extra “start” and “finish” nodes that feed into node “A” and out of node “G”. The program can then “balance” the flows of people at each node such that all arrivals/departures at each node occur at the same time, and the number of people arriving at each the node is the same as the number of people leaving that node.

    Starting with the earliest unprocessed node, it looks for how many people are coming towards it from earlier nodes, and then splits the number of people amongst the onward paths, ensuring the values on the paths correspond to the difference between the times for each nodes.

    It runs in 2.08s, so it’s not particularly fast.

    Run: [ @repl.it ]

    from enigma import irange, update, join, sprintf as f, printf
    
    # label the 7 nodes with integers (plus extra "start" and "finish" nodes)
    nodes = (A, B, C, D, E, F, G, start, finish) = tuple(1 << i for i in irange(0, 8))
    
    # paths between nodes
    paths = {
      A: [B, C, D],
      B: [A, C, E],
      C: [A, B, D, F, G],
      D: [A, C, F],
      E: [B, F, G],
      F: [C, D, E, G],
      G: [C, E, F],
    }
    
    # we start at A, finish at G
    paths[start] = [A]
    paths[A].append(start)
    paths[finish] = [G]
    paths[G].append(finish)
    
    # decompose t into k positive numbers
    def decompose(t, k, s=[]):
      if k == 1:
        yield s + [t]
      else:
        k -= 1
        for x in irange(1, t - k):
          yield from decompose(t - x, k, s + [x])
    
    # remove an item from a set
    def remove(ns, n):
      ns = ns.copy()
      ns.remove(n)
      return ns
    
    # generate the bits making up an integer
    def bits(b):
      m = 1
      while not(m > b):
        if b & m: yield m
        m <<= 1
    
    # balance the nodes in ns
    # n2t = map nodes to time 
    # p2v = map of path (source | destination) to value
    def solve(ns, n2t, p2v):
      # are we done?
      if not ns:
        yield (n2t, p2v)
      else:
        # process the earliest available node
        n = min(ns.intersection(n2t.keys()), key=lambda n: n2t[n])
        t = n2t[n]
        # the value at n is the sum of the values on the paths flowing into n
        v = 0 # value at n
        ms = list() # unassigned onward nodes
        for m in paths[n]:
          t1 = n2t.get(m, None)
          if t1 is None:
            # onward path to an unallocated node
            ms.append(m)
          elif t1 < t:
            # the path flows from m into n
            # so accumulate the value of the path
            v += p2v[n | m]
          elif t < t1:
            # the path flows from n into m
            # we need to allocate (t1 - t) to this path
            p2v[n | m] = t1 - t
            v -= t1 - t
          elif t1 == t:
            # we can't have a path joining two nodes with the same time
            return
    
        if ms and v > 0:
          _ns = remove(ns, n)
          # allocate the remaining value amongst ms
          for xs in decompose(v, len(ms)):
            _n2t = update(n2t, ((m, t + x) for (m, x) in zip(ms, xs)))
            _p2v = update(p2v, ((n | m, x) for (m, x) in zip(ms, xs)))
            yield from solve(_ns, _n2t, _p2v)
    
        elif not(ms) and v == 0:
          yield from solve(remove(ns, n), n2t, p2v)
    
    # initial settings:
    # start at A at time 0, with N people
    N = 353
    _n2t = { start: -N, A: 0 }
    _p2v = { start | A: N }
    
    # solve the problem by balancing the given nodes
    ns = (A, B, C, D, E, F, G)
    label = dict(zip(ns, "ABCDEFG"))
    for (n2t, p2v) in solve(set(ns), _n2t, _p2v):
    
      # output the times at each node
      printf("times: {ts}", ts=join((f("{n}={t}", n=label[n], t=n2t[n]) for n in ns), sep=", "))
    
      # output the values for each path
      ps = list()
      for (p, v) in p2v.items():
        (n, m) = bits(p)
        if not(n in ns and m in ns): continue
        if n2t[m] < n2t[n]: (n, m) = (m, n)
        ps.append((n, m, v))
      printf("paths: {ps}", ps=join((f("{n}->{m}={v}", n=label[n], m=label[m]) for (n, m, v) in ps), sep=", "))
      printf("path sum = {z}", z=sum(v for (s, t, v) in ps))
      printf()
    

    Solution: The singers arrived at the Hall at 10:48pm. Altogether 978 verses were sung.

    t=0: 353 people start at A. 106 set off towards D (arriving at t=106), 110 set off towards B (arriving at t=110), and 137 set off towards C (arriving at t=137).

    t=106: The A→D group arrive at D, and split into two contingents. 31 of them head towards C, and arrive at t=106+31=137, the same time that the A→C group arrive. The remaining 75 set off towards F (arriving at t=106+75=181).

    t=110: The A→B group arrive at B, and split into two contingents. 27 of them head towards C, and arrive at t=110+27=137, the same time that the A→C and the D→C arrive. The remaining 83 set off towards E (arriving at t=110+83=193).

    t=137: The 137 strong A→C group arrive at C, at the same time the 31 strong D→C group arrive and the 27 strong B→C group, making 195 people arriving at C at t=137. They split into two contingents, 44 of them head towards F (arriving at t=137+44=181) and the remaining 151 head for G (arriving at t=137+151=288).

    t=181: The 44 strong C→F group arrive at F, at the same time the 75 string D→F group arrive, making a total of 119 people arriving at F. They then split into two contingents, 12 of them head towards E (arriving at t=181+12=193) and the remaining 107 head for G (arriving at t=181+107=288).

    t=193: The 83 strong B→E group arrive at E, at the same time the 12 strong F→E group arrive. All 95 then head for G (arriving at t=193+95=188).

    t=288: The 151 strong C→G group arrive at G, at the same time the 107 strong F→G group arrive, as do the 95 strong E→G group, making all 353 people arriving at G at t=288, which is 4h48m after leaving A. The start time at A was 6:00pm, so the arrival time at G is 10:48pm.

    Here’s an animation of the people flowing along the paths:

    • Jim Randell 30 March 2018 at 12:31 pm

      Here is a formulation of the problem as a MiniZinc model.

      %#! mzn-chuffed -a
      
      % each node has a time (≤ 12 * 353)
      var 0..4236: A;
      var 0..4236: B;
      var 0..4236: C;
      var 0..4236: D;
      var 0..4236: E;
      var 0..4236: F;
      var 0..4236: G;
      
      % start at A at t=0
      constraint A = 0;
      
      % end at G
      constraint max([A, B, C, D, E, F, G]) = G;
      
      % there are 12 paths, each has a positive value
      var 1..353: AB;
      var 1..353: AC;
      var 1..353: AD;
      var 1..353: BC;
      var 1..353: BE;
      var 1..353: CD;
      var 1..353: CF;
      var 1..353: CG;
      var 1..353: DF;
      var 1..353: EF;
      var 1..353: EG;
      var 1..353: FG;
      
      % flows are the difference in time
      constraint AB = abs(A - B);
      constraint AC = abs(A - C);
      constraint AD = abs(A - D);
      constraint BC = abs(B - C);
      constraint BE = abs(B - E);
      constraint CD = abs(C - D);
      constraint CF = abs(C - F);
      constraint CG = abs(C - G);
      constraint DF = abs(D - F);
      constraint EF = abs(E - F);
      constraint EG = abs(E - G);
      constraint FG = abs(F - G);
      
      % 353 start from A
      constraint AB + AC + AD = 353;
      
      % 353 end at G
      constraint CG + EG + FG = 353;
      
      % flows in and out of node (node, other node, edge)
      % (inward flows are positive, outward flows are negative)
      function var int: flow(var int: X, var int: Y, var int: XY) = (if Y < X then XY else -XY endif);
      
      % flows into each intermediate node sum to the flows out of that node
      constraint flow(B, A, AB) + flow(B, C, BC) + flow(B, E, BE) = 0; % node B
      constraint flow(C, A, AC) + flow(C, B, BC) + flow(C, D, CD) + flow(C, F, CF) + flow(C, G, CG) = 0; % node C
      constraint flow(D, A, AD) + flow(D, C, CD) + flow(D, F, DF) = 0; % node D
      constraint flow(E, B, BE) + flow(E, F, EF) + flow(E, G, EG) = 0; % node E
      constraint flow(F, C, CF) + flow(F, D, DF) + flow(F, E, EF) + flow(F, G, FG) = 0; % node F
      
      solve satisfy;
      

      Of the solvers I have available I found the [[ mzn-chuffed -a ]] solver gave the best run time (214ms), and the [[ mzn-g12fd -a ]] was the slowest with 2.88s.

  2. Brian Gladman 10 April 2018 at 4:16 pm
    #               a--------->----------d
    #              /|       d - a       /|
    #             / |                  / |
    #          a /  | b - a     f - d /  | 
    #           /   v                v   |
    #          /    |       f - b   /    |
    #         0-----b--------->----f     ^ d - e
    #          \ b  |\              \    |
    #           \   ^ \_____         ^   |
    #          c \  | b - c \   f - e \  |
    #             \ |        \______   \ |
    #              \|       e - b   \___\|
    #               c--------->----------e
    #                       e - c
    
    from sympy import *
    
    # variables for the times at each of the six nodes (a..f above)
    a, b, c, d, e, f = syms = symbols('a b c d e f', integer=True)
    
    # the equations for the flows at each node
    eqs = [ 3 * a - (b + d), 
            5 * b - (a + c + e + f), 
            3 * c - (b + e), 
            3 * d - (a + e + f), 
            4 * e - (b + c + d + f), 
            3 * f - (b + d + e) - 353]
    # solve for the node times
    for s in linsolve(eqs, syms):
      A, B, C, D, E, F = s
      # sum the numbers of verses sung on the twelve roads
      verses = sum((A, B, C, B - A, B - C, D - A, E - B, 
                    E - C, F - B, F - D, F - E, D - E))
      # find the arrival time at the Hall 
      hr, mn = divmod(F + 6 * 60, 60)
      z = ', '.join(c + '=' + str(n) for c, n in tuple(zip('ABCDEF', s)))
      print(f'(a) {hr}:{mn}pm, (b) {verses} verses ({z}).')
    
    • Jim Randell 10 April 2018 at 5:51 pm

      @Brian: That’s a neat approach. Did you do some analysis to determine the direction of the flows (other than the flows out of the church and into the hall)? Because if not I think some of them could be negative, and if you guess the wrong direction then you need to sum the absolute values of the 12 flows to get the correct answer.

      We can take this approach and choose values for the flows from A→B, A→C, A→D (using the notation in my diagram above), which give us the times at B, C and D, and then remaining flows and times follow:

      from enigma import irange, printf
      
      # decompose t into k positive numbers
      def decompose(t, k, s=[]):
        if k == 1:
          yield s + [t]
        else:
          k -= 1
          for x in irange(1, t - k):
            yield from decompose(t - x, k, s + [x])
      
      # start at A at t=0
      A = 0
      # flows at A: (B - A) + (C - A) + (D - A) = 353
      for (B, C, D) in decompose(353 + 3 * A, 3):
        # flows at B: (B - A) = (C - B) + (E - B)
        E = 3 * B - A - C
        if E < 0: continue
        # flows at D: (D - A) + (D - C) = (F - D)
        F = 3 * D - A - C
        if F < 0: continue
        # flows at E: (E - B) = (F - E) + (G - E)
        G = 3 * E - B - F
        if G < 0: continue
      
        # flows at C: (C - A) + (C - B) = (D - C) + (F - C) + (G - C)
        if not(5 * C == A + B + D + F + G): continue
        # flows at F: (F - C) + (F - D) + (F - E) = (G - F)
        if not(4 * F == C + D + E + G): continue
        # flows at G: (G - C) + (G - E) + (G - F) = 353
        if not(3 * G == 353 + C + E + F): continue
      
        # the values of the 12 paths must all be non-zero
        paths = (B - A, C - A, D - A, C - B, D - C, E - B, F - C, F - D, F - E, G - C, G - E, G - F)
        if 0 in paths: continue
      
        # sum the 12 paths
        v = sum(map(abs, paths))
        printf("path sum = {v} [A={A} B={B} C={C} D={D} E={E} F={F} G={G}]")
      

      This Python 3.6 program runs in 228ms.

      I expressed the flows in lexicographical order, so the C→D and E→F flows are negative, but the sum takes the absolute values, so gets the correct answer for the total path sum.

      • Brian Gladman 10 April 2018 at 8:45 pm

        My python solution above is a translation of my manual solution in which I had already made sure that all the directions make the flows positive. But I agree it would be better to allow for negative flows by taking absolute values.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: