Skip to content

Sunday Times Teaser 3201 – Spare Routes

by BRG on January 26, 2024

by Colin Vout

Published Friday January 26 2024 (link)

Three companies run scenic coach trips either way between some pairs of towns in my holiday destination. Each route between two towns is served by just one company, but has one or more alternatives via another town. In particular, every Redstart route could be replaced by a unique combination of two Bluetail routes, every Bluetail by a unique combination of two Greenfinches, and every Greenfinch by a unique combination of a Redstart and a Greenfinch. This wouldn’t be possible with fewer towns or fewer routes.

I toured one route each day, starting from the town I’d arrived at the previous day but changing the company, never repeating a route in either direction, and involving as many of the routes as I could.

Which companies did I use, in order (as initials, eg, R,B,G,B)?

From → Uncategorized

4 Comments Leave one →
  1. BRG permalink

    The teaser took a lot of effort over most of the week since publication!

  2. John Z permalink

    With a number of improvements to my previous versions suggested by Brian (line 16) or inspired by his code (line 7 and line 53: pump priming) and a few of my own such as completing alternate route verification in one pass rather than three and moving the function out of the body of the main program

    The order of routes ‘BGRX’ in the ‘product’ function (line 49) gives a much faster execution time than ‘RGBX’ or ‘XRGB’.

  3. John Z permalink

    I kept fiddling with this and finally decide to go for stict application of the “This wouldn’t be possible with fewer towns or fewer routes.” criterion. My code was already applying ‘fewer towns’ it now ensures ‘fewest routes’ even though I don’t think this is strictly necessary. The result is the same except that it takes longer to produce.

    • John Z permalink

      Replacing ‘max’ in line 50 with ‘min’ gives exactly the same result indicating that the ‘fewest routes’ criterion is superfluous. About 4 extra lines of code were required to apply this criterion not a huge burden.

Leave a Reply

Note: HTML is allowed. Your email address will not be published.

Subscribe to this comment feed via RSS