Advent of Code F# – Day 9

The source code for this post (both Part 1 and Part 2) is avail­able here and you can click here to see my solu­tions for the oth­er Advent of Code chal­lenges.

Descrip­tion for today’s chal­lenge is here.

 

The input for Day 9 looks like this:

Alpha­Cen­tau­ri to Snowdin = 66

Alpha­Cen­tau­ri to Tam­bi = 28

Alpha­Cen­tau­ri to Faerun = 60

Snowdin to Tam­bi = 22

Snowdin to Faerun = 12

there are sim­i­lar­i­ties between this chal­lenge and Day 7 in that they’re essen­tial­ly a graph prob­lem. In that case, let’s mod­el this prob­lem as a graph:

day09_01

in our mod­el of this prob­lem, we have a set of cities, and the con­nec­tions between them (where the key is the city to trav­el from, and the val­ue is a map of the cities that you can trav­el to and the dis­tance between the pair).

Like we did in Day 7, let’s add a helper func­tion to help con­nect two cities — a and b — togeth­er, along with the dis­tance between them.

day09_02

Armed with the above, we can now go back to our input, parse each line into two cities and their dis­tance, and then fold over them to build up a graph:

day09_03v2

notice that the infor­ma­tion we get from the input list is actu­al­ly bi-direc­tion­al, which is why in the fold we have to add the direc­tion from a to b, as well as from b to a.

Next, start­ing with each cities, we want to find the routes that’ll vis­it each city once and only once.

day09_04

aside: in hind­sight, both the mod­el and the path find­ing algo­rithm here can be sim­pli­fied, I sim­ply didn’t realise the dis­tance data is bi-direc­tion­al (it was implied through the exam­ple which I skimmed over and got start­ed writ­ing code…). For instance, the data is set up such that every city is con­nect­ed to every oth­er city, so the steps I have tak­en above to deter­mine ‘which cities can I trav­el from here’ is redun­dant.

That said, I decid­ed to keep the solu­tion as it is because:

a) it can solve a more gen­er­al prob­lem where cities do not form a mesh net­work

b) it works, and pret­ty easy to under­stand, so why change 


The last build­ing block we need to com­pose our final solu­tion is the abil­i­ty to cal­cu­late the total dis­tance we have to trav­el in a route:

day09_05

and to answer the chal­lenge:

day09_06

in hind­sight, it might be bet­ter to write the above as:

    graph |> find­Paths |> Seq.map cal­cDis­tance |> Seq.min

 

Part 2

To work out the longest dis­tance one can trav­el, sim­ply flap the last line to look for the max dis­tance instead, sim­ple:

day09_07