Advent of Code F# — Day 11

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

 

Day 11

See details of the chal­lenge here.

Today is per­haps the first AOC chal­lenge that is real­ly chal­leng­ing and required a lot of thought, and I real­ly enjoyed it!

First, let’s mod­el the prob­lem domain.

and we’ll need a way to deter­mine if microchips are fried or we have suc­ceed­ed in our mis­sion after a move.

 

At its core the prob­lem here is sim­i­lar to the Lev­el Order Tree Tra­ver­sal prob­lem we saw yes­ter­day, where from each move you have a no. of fol­low-up moves you can make:

  • giv­en the floor the ele­va­tor lands at, you can take 1 or 2 items from the floor in the next move
  • giv­en the floor the ele­va­tor lands at, you can move up or down a floor

For instance, giv­en this state:

F4 .  .  .  .  .  
F3 E  HG HM LG .  
F2 .  .  .  .  .  
F1 .  .  .  .  LM 

Here are the 6 pos­si­ble com­bi­na­tions of items that can be loaded onto the ele­va­tor for the next move:

  • HG
  • HM
  • LG
  • HG, HM
  • HG, LG
  • HM, LG

addi­tion­al­ly, you can also move the ele­va­tor up or down, lead­ing to a total of 12 pos­si­ble moves from this point.

The trick, how­ev­er, is to ensure you don’t make a move that will results in a state that you had already been pre­vi­ous­ly. This opti­miza­tion alone is suf­fi­cient for you to solve part 1 of the chal­lenge in under a minute, but it wasn’t quite enough for part 2…

The key real­iza­tion for the sec­ond opti­miza­tion is that, the ele­ments them­selves don’t mat­ter, ie. all three of these con­fig­u­ra­tions rep­re­sent the same prob­lem:

F4 .  .  .  .  .  
F3 .  .  .  LG .  
F2 .  HG .  .  .  
F1 E  .  HM .  LM 
F4 .  .  .  .  .  
F3 .  .  .  HG .  
F2 .  LG .  .  .  
F1 E  .  LM .  HM 
F4 .  .  .  .  .  
F3 .  HG .  .  .  
F2 .  .  .  LG .  
F1 E  .  LM .  HM 

because the essence of the prob­lem have not changed:

  • the ele­va­tors is at floor 1
  • there’s an ele­ment whose Gen­er­a­tor is on floor 3 and microchip is on floor 1
  • there’s an ele­ment whose Gen­er­a­tor is on floor 2 and microchip is on floor 1

So if we can rep­re­sent states in this way then we can iden­ti­fy equiv­a­lent states and avoid repeat­ing them.

With that in mind, let’s over­ride the State type’s ToString method so that a state like this

F4 .  .  .  .  .  
F3 E  HG HM LG .  
F2 .  .  .  .  .  
F1 .  .  .  .  LM 

is rep­re­sent­ed as “3-(3, 1)(3, 3)” where the tuples rep­re­sents the (gen­er­a­tor floor, microchip floor) for each ele­ment and the order­ing is deter­mined only by the floor val­ues.

So now, we can drill into the meat of the solu­tion.

There are cou­ple of things to note here:

  • I’m using a muta­ble Hash­Set instead of F#‘s immutable Set for per­for­mance rea­sons, but not expos­ing that muta­bil­i­ty to the out­side
  • item­Com­bos func­tion returns all pos­si­ble com­bi­na­tions of items that can be loaded onto the ele­va­tor, it’s doing extra work to gen­er­ate dupli­cates (and then fil­ter­ing them out with Seq.distinct) but can be eas­i­ly rec­ti­fied away
  • for every com­bi­na­tion of items, we gen­er­ate 1 or 2 new states depend­ing on the ways the ele­va­tor can move
  • each new state is added to the cache using its string rep­re­sen­ta­tion above
  • those states that lead to fried microchips are ignored and not used to gen­er­ate even more states

 

The solu­tion to part 1 looks like this:

 

Part 2

You step into the clean­room sep­a­rat­ing the lob­by from the iso­lat­ed area and put
on the haz­mat suit.

Upon enter­ing the iso­lat­ed con­tain­ment area, how­ev­er, you notice some extra
parts on the first floor that weren’t list­ed on the record out­side:

An eleri­um gen­er­a­tor.
An eleri­um-com­pat­i­ble microchip.
A dilithi­um gen­er­a­tor.
A dilithi­um-com­pat­i­ble microchip.
These work just like the oth­er gen­er­a­tors and microchips. You’ll have to get
them up to assem­bly as well.

What is the min­i­mum num­ber of steps required to bring all of the objects,
includ­ing these four new ones, to the fourth floor?

With both opti­miza­tions in place, part 1 took 1s and part 2 took 8s on my MBP, pret­ty sweet! 

 

Links