Advent of Code F# – Day 24

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 descrip­tion for the chal­lenge is quite long and wordy, but ulti­mate­ly there are only three things we need to remem­ber:

  1. the total weight of pack­ages need to be even­ly divid­ed into 3 groups
  2. the first group needs to have fewest pack­ages pos­si­ble
  3. giv­en the same num­ber of pack­ages (fewest pos­si­ble), the quan­tum entan­gle­ment (i.e. the prod­uct…) of the weights of pack­ages in the first group needs to be the small­est pos­si­ble

Based on these infor­ma­tion, we can have the fol­low­ing:

day24_01

For my input, all the weights are odd num­bers, and the aver­age weight is an even num­ber. Which means we need an even num­ber of pack­ages in each group, fur­ther­more, based on the input the small­est num­ber of pack­ages that can add up to the aver­age weight is 6.

So rather than a brute force approach (which I tried and failed with) we can be smarter and:

  1. only con­sid­er the first group (since that’s all we need to answer the ques­tion)
  2. only con­sid­er groups of length 6

So, for each pack­age, we will:

  • yield the 6-pack­age groups that can be formed with it
  • yield the 6-pack­age groups that can be formed with­out it

and we’ll short cir­cuit a path if after col­lect­ing 6 pack­ages in a group but the total weight of the group doesn’t add up to the aver­age.

This is exact­ly what the fol­low­ing code snip­pet does, it returns all the 6-pack­age groups that has a total weight equalling the aver­age weight:

day24_02

Final­ly, we just need to find the small­est quan­tum entan­gle­ment val­ue of all the pos­si­ble com­bi­na­tions:

day24_03

 

Part 2

Same approach as above, but slight­ly dif­fer­ent set­up.

day24_04

Now that we’re divid­ing the total weight of all the pack­ages by 4 instead of 3, the aver­age is now an even num­ber — mean­ing we’ll need an odd num­ber of pack­ages per group. Also, the small­est num­ber of pack­ages per group is now 5:

day24_05