**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.

“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]

### Like this:

Like Loading...

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 ]Solution:The singers arrived at the Hall at 10:48pm. Altogether 978 verses were sung.Here’s an animation of the people flowing along the paths:

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

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.@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:

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.

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.