Advent of Code F# — Day 24

ps. look out for all my oth­er solu­tions for Advent of Code chal­lenges here.

 

Day 24

See details of the chal­lenge here.

Today’s chal­lenge is a mix of Breadth-First Search (or Lev­el Order Tree Tra­ver­sal) and the Trav­el­ling Sales­man Prob­lem.

First, let’s parse the input file into a 2D array to make it eas­i­er for us to work with.

My first attempt at solv­ing this chal­lenge with the same BSF approach that has been so use­ful in this year’s AOC chal­lenges proved unsuc­cess­ful. Unlike pre­vi­ous chal­lenges, today’s prob­lem can involve back­track­ing so we can’t rely on a naive cache of posi­tions we have passed through thus far.

How­ev­er, we can still use BSF to find out the short­est dis­tance between any two num­bered nodes.

From here, we can build up a dic­tio­nary of the dis­tance between every pair of num­bered nodes and turn this BSF prob­lem into a Trav­el­ling Sales­man Prob­lem and find the path through all the num­bered nodes with the low­est total dis­tance.

Now we can solve part 1 of the chal­lenge with a sim­ple recur­sive func­tion.

This solu­tion ran in 109ms on my lap­top, includ­ing the time to build up the dis­tances between pairs of nodes.

 

Part 2

Of course, if you leave the clean­ing robot some­where weird, some­one is bound to notice.

What is the fewest num­ber of steps required to start at 0, vis­it every non-0 num­ber marked on the map at least once, and then return to 0?

A slight twist on part 1, but we can use the same approach as before but sim­ply stip­u­late that when all num­bered nodes have been tra­versed we also take into account the dis­tance from the last node back to num­ber 0.

This ran in 113ms on my lap­top, includ­ing the time to build up the dis­tance between pairs of nodes (or, 14ms if reusing the exist­ing pairDis­tances)

 

Links