Advent of Code F# — Day 13

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

 

Day 13

See details of the chal­lenge here.

Today’s chal­lenge involves solv­ing two sep­a­rate prob­lems:

  • count­ing set bits in an inte­ger
  • lev­el order tree tra­ver­sal

For the first prob­lem, I rec­om­mend read­ing through this blog post which cov­ers sev­er­al approach­es and opti­miza­tions for this well defined prob­lem.

I exper­i­ment­ed with 3 of the solu­tions described in the post, and the results were telling. I skipped the lookup table ver­sion because I don’t feel it makes sense in the con­text of this AOC chal­lenge.

 

I recent­ly post­ed about Lev­el Order Tree Tra­ver­sal in F# recent­ly, which I also used to solve Day 11. We can apply the same tech­nique and opti­miza­tion (not count­ing a pre­vi­ous­ly vis­it­ed coor­di­nate) here and use Seq.unfold to return an infi­nite sequence of move count with all the new coor­di­nates that are vis­it­ed in that move.

Anoth­er opti­miza­tion we can apply is to use mem­o­iza­tion to avoid com­put­ing if a coor­di­nate is an open space more than once.

To solve part 1 we need to find the first round of coor­di­nates that con­tains our tar­get.

 

Part 2

How many loca­tions (dis­tinct x,y coor­di­nates, includ­ing your start­ing loca­tion)
can you reach in at most 50 steps?

Since we’ve done most of the hard work with the trav­el func­tion (which returns only the dis­tinct coor­di­nates), the hard­est thing about part 2 is to remem­ber to add 1 to account for the start­ing posi­tion (which I for­got to ini­tial­ly of course )

 

Links