# Megan visits all the stations

The other day I was waiting for a train and had just popped into the nearby branch of Costa Bean for a coffee, when who should I run into but my old friend Megan and her partner Ricky, studying a travel brochure.

"We're planning to spend a few days to ride on this railway." Ricky replied, handing me the brochure. It was for The Diamond Of Wales Line. "The line's only recently been opened. I want to look round all the stations. So we've booked a hotel which is nice and convenient for the terminus at Abercydabra. We'll start there, then for each of the other stations, we'll take one train there, get off and have a look around, then get on a different train there, and so on until we get back to Abercydabra. We're going to visit all the stations."

I opened the brochure, which gave the timetable:

Abercydabra   08:00       16:00  Maenddygap    09:00       17:00
Brynpen Hill  08:12       16:12  Llanllewllwyd 09:12       17:12
Caerlesli     08:24 then  16:24  Kington       09:24 then  17:24
Dynower       08:36       16:36  Joneston      09:36       17:36
Egynbeicyn    08:48 every 16:48  Isicyl        09:48 every 17:48
Fforestffair  09:00       17:00  Hardllyr      10:00       18:00
Greenweli     09:12  two  17:12  Greenweli     10:12  two  18:12
Hardllyr      09:24       17:24  Fforestffair  10:24       18:24
Isicyl        09:36 hours 17:36  Egynbeicyn    10:36 hours 18:36
Joneston      09:48       17:48  Dynower       10:48       18:48
Kington       10:00 until 18:00  Caerlesli     11:00 until 19:00
Llanllewllwyd 10:12       18:12  Brynpen Hill  11:12       19:12
Maenddygap    10:24       18:24  Abercydabra   11:24       19:24

All trains are steam trains except the 10:00 from Abercydabra and the 17:00 from Maenddygap, which are diesel.

"That's not many trains per day and a lot of stations." I noted. "You're surely not going to manage to visit all of them in one day?"

"No, I don't think we can, but I want to work out an itinerary which minimises the number of days we'll need. Returning to our hotel at the end of each day."

"Of course! I'm not having us spending the night at a station!" Megan added. "Do the trains have dining-cars?"

"It doesn't look like it" her partner said, looking at the brochure again. "But I expect we can grab a bite to eat at a station café or somewhere near -- depending on where we happen to be at lunchtime. All the stations have cafés where we can have lunch."

"I'll want a proper lunch, what with all the train-hopping we'll be doing. So let's allow at least an hour for that, and not on a train. And at a reasonable hour, too, say some time between 12 and 2. Can you allow for that on our itinerary?"

"I expect so. Now I like steam trains but don't care so much for diesel ones. So let's see how we can do this in a way which minimises how much time we spend on diesels."

So, how many days will they need? And what will be their daily itineraries?

(I was inspired by this project.)

(Here's Geoff Marshall, with Vicki Pipe, explaining the specific bit which inspired my puzzle.)

• how long does it take from one station to another? an hour?and how the train station works exactly? let say how I can go to J from A? a map would be nice to think over. – Oray Oct 1 '17 at 21:36
• @Oray - My reading of the timetable says that the stations are all on a single line from A to M, and it takes exactly 12 minutes to go from station to station, which you can do once every 2 hours. – Bobson Oct 1 '17 at 22:15
• What are the priorities for requirements (days and diesel minimisation)? i.e. Is 1 day with 2 diesel trains better than 2 days with 1 diesel train? – Alpha Oct 2 '17 at 22:28
• @Alpha Minimise days. Having done that, minimise diesel. – Rosie F Oct 3 '17 at 5:54

It's possible to visit all stations in

2 days,

which is clearly the minimum time it can take since

visiting 13 stations means arriving at 13 stations on 13 different trains, and there are only 10 trains per day (the 08:00, 10:00, 12:00, 14:00, and 16:00 from Abercydabra, and the 09:00, 11:00, 13:00, 15:00, and 17:00 from Maenddygap), so it cannot be done in just 1 day.

The following is one possible itinerary, although I don't know if it minimises the use of the diesel train. Moving horizontally in this tabulation corresponds to changing trains at the station on that row, arriving at the left hand time and leaving at the right hand time, and moving vertically corresponds to taking a train from the station on the upper row to the station on the lower row. An L denotes that lunch is eaten at the station on that row. Trains in bold travel towards Maenddygap, and trains not in bold travel towards Abercydabra. Trains in italics are diesel trains, and trains not in italics are steam trains.

Day 1

 Abercydabra 08:00
Maenddygap  10:24    11:00
Kington              11:24   12:00
Llanllewllwyd                12:12 L 13:12
Hardllyr                             14:00   15:24
Isicyl                                       15:36   15:48
Fforestffair                                         16:24   17:00
Greenweli                                                    17:12   18:12
Abercydabra                                                          19:24
(This takes the morning diesel only one stop / 12 minutes, between Kington and Llanllewllyed, but takes the evening diesel six stops / 1 hour and 12 minutes, between Greenweli and Abercydabra.)

Day 2
 Abercydabra 08:00
Joneston    09:48    11:36
Caerlesli            13:00 L 14:24
Dynower                      14:36   14:48
Brynpen Hill                         15:12   16:12
Egynbeicyn                                   16:48   18:36
Abercydabra                                          19:24

(This completely avoids the morning diesel, but takes the evening diesel four stops / 48 minutes, between Egynbeicyn and Abercydabra.)

• This itinerary travels on four out of the five scheduled trains in each direction on the first day, missing out the 12:00 from Abercydabra and the 09:00 from Maenddygap. On the second day, it travels on three of the five trains in each direction, and again the 12:00 from Abercydabra and the 09:00 from Maenddygap are among those missed out. I'm curious as to whether it's possible to visit all stations in 2 days, still adhere to the lunch requirements, and travel on each of the scheduled services at some point during the itinerary. – Neremanth Oct 2 '17 at 3:24