Advent of Code F# – Day 13

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 13 looks like the fol­low­ing:

Alice would lose 2 hap­pi­ness units by sit­ting next to Bob.

Alice would lose 62 hap­pi­ness units by sit­ting next to Car­ol.

Alice would gain 65 hap­pi­ness units by sit­ting next to David.

Bob would gain 93 hap­pi­ness units by sit­ting next to Alice.

Bob would gain 19 hap­pi­ness units by sit­ting next to Car­ol.

Bob would gain 5 hap­pi­ness units by sit­ting next to David.

So first, let’s parse the impor­tant infor­ma­tion out of each line:

  • who (x)
  • sit­ting next to whom (y)
  • how much does the hap­pi­ness change as result

day13_01

we can then build up a Map of this infor­ma­tion.

For con­ve­nience sake, let’s also cre­ate a type alias for this Map, and let’s call it a Graph.

day13_02v2

You might have noticed that, where x is found in the graph, we’re using Add to update both the inner and out­er Map. This might seem odd/suspicious, but whilst it’s not men­tioned in the doc­u­men­ta­tion the behav­iour of Add is actu­al­ly ‘add or update’ — try this in the F# REPL to see for your­self:

> let m = Map.ofList [ 1, “1”];;

val m : Map<int,string> = map [(1, “1”)]

> m.Add(1, “2”);;

val it : Map<int,string> = map [(1, “2”)]

Once we have parsed the input into a ‘graph’, let’s find all pos­si­ble sit­ting arrange­ments:

day13_03

For each arrange­ment, we’ll need to score it based on the total hap­pi­ness of the peo­ple in this arrange­ment:

day13_04

The tricky thing here is to deal with mis­match between the actu­al sit­ting arrange­ment — where every­one sits in a cir­cle — to our rep­re­sen­ta­tion of it as an array. Which is why I cre­at­ed left­Of and rightOf func­tions to deal with cas­es when the index has under/overflown.

Final­ly, just score every arrange­ments and find the high­est score:

day13_05

 

Part 2

After con­sid­er­ing a few approach­es, I decid­ed it’ll be eas­i­est to just mod­i­fy the input so that all the down­stream code we wrote for Part 1 would still work just fine.

So, we first need to know who are all the peo­ple that will be sit­ting at the table:

day13_06

so we can inject addi­tion­al lines (bi-direc­tion­al­ly) into the input:

day13_07