Enigmatic Code
Programming Enigma Puzzles
Enigma 807: Track tickets
Posted by on 30 January 2023
From New Scientist #1962, 28th January 1995 [link] [link]
Susan is on a 2-day holiday, staying near one of the stations on the East-West railway line. There are stations every mile along the line. Tickets are sold in packs. The Go East pack contains a random selection of 9 tickets and each one is for travel of 1 or 2 or 3 or 4 or 5 miles in an easterly direction. The Go West pack contains a random selection of 5 tickets and each one is for travel of 1 or 2 or 3 or 4 or … or 9 miles in a westerly direction.
Susan’s plan for the first day of her holiday starts at her local station, where she will buy one pack of each kind. From the Go East pack she will choose a ticket at random and catch a train going east. When the ticket is used up she will alight; she will then take the pack for travel towards her home station, select a ticket at random, catch a suitable train and alight when the ticket is used up. She hopes to carry on in this way until she alights at a station she has been to before; she will then walk home.
The second day of her holiday again starts at her local station with her buying one pack of each kind. She will sort through the two packs and try to find a selection of East tickets and a selection of West tickets so that the total distances for the two selections are the same; she will then use all the selected tickets to make a trip that ends at her home station.
Q1. On day one, is there a possibility Susan might find herself on a station, wanting a ticket in a particular direction and having none of those left?
Q2. On day one, is she certain eventually to reach a station she has been to before?
Q3. On day two, is she certain to be able to find selections of tickets that meet her requirements?
[enigma807]
Enigmatic Code 
The only way Susan’s plan for the first day can fail is if she arrives at a station she has visited before, and has no valid ticket to allow her to travel towards the starting station.
So we can look for this situation happening. If it can happen then the answer to Q1 is “Yes”, and the answer to Q2 is “No”. If it can’t happen then the answer to Q1 is “No”, and the answer to Q2 is “Yes”.
For the second day, the only way to fail is if there is a set of tickets in one direction that is not balanced by a set of tickets in the other direction.
This Python program looks for failure scenarios for both days. It runs in 508ms.
Run: [ @replit ]
from enigma import (irange, subsets, peek, printf) # possible E, W tickets E = set(irange(1, 5)) W = set(irange(-1, -9, step=-1)) def advance(X, p, ps): for x in X: q = p + x if q not in ps: yield q # look for an unsuccessful journey for day 1 def day1(p, nE, nW, ps=[]): ps_ = ps + [p] # do we need to travel E? if p < 0 or not ps: if nE > 0: # we can travel E for q in advance(E, p, ps_): yield from day1(q, nE - 1, nW, ps_) else: # no remaining tickets yield ps_ return # do we need to travel W? if p > 0: if nW > 0: for q in advance(W, p, ps_): yield from day1(q, nE, nW - 1, ps_) else: # no remaining tickets yield ps_ return # can we find a failure for day1? ps = peek(day1(0, 9, 5), default=None) if ps: printf("q1 = Y; q2 = N; fail = {ps}") else: printf("q1 = N; q2 = Y") # is every possible set of tickets in one direction matched with a set # of tickets in the other direction? def day2(): # consider partial sums pE = set(sum(s) for s in subsets(E, min_size=1, max_size=9, select='R')) pW = set(abs(sum(s)) for s in subsets(W, min_size=1, max_size=5, select='R')) return pE.symmetric_difference(pW) # can we find a failure for day2? d2 = day2() printf("q3 = {q3}", q3=('N' if d2 else 'Y'))Solution: Q1: No; Q2: Yes; Q3: Yes.
So Susan’s plans for both the first and second day must both succeed.