Advent of code 2021: Day 7
 3 minutes read  553 wordsOn the 7th day of the submarine Advent of Code 2021 adventure, I felt like the problem was getting a bit easier than it had been of late. If anything I felt a touch suspicious on whether I had been missing anything. In previous days I had to reframe the problem statement a bit to make it efficient (Day 4, Day 5 and Day 5). Either that or I’m starting to feel more comfortable with Haskell. In which case the Advent of Code is a success for me already as I’m learning lots.
The problem
This puzzle was all about lining up crab submarines!
 The input consists of a list of the crabs' horizontal positions
 The aim is to move all the crabs into the same position with the minimum amount of cost (moving 1 position costs 1 fuel)
More on the problem here
Initial thought
My first thought on this problem was whether this could be solved by using the mean or average of all positions, but I discounted that after checking whether this would work for the example, so I thought I’d just calculate the cost of moving each crab to each of the positions and then pick the minimum.
Implementing it
There was one optimisation that I could think of straight away, I’d use my trusty frequency list to check if any crabs were in the same position and then the cost can just be multiplied by the number of crabs at that position.


The grouppos
function would turn the list of positions into a list of tuples where it is
(position, number of occurrences)
.
I also created a function to calculate the cost of moving a single crab submarine:


Then I can put both together to create the total distance covered:


Essentially, just the distances multiplied by the occurrences and then summing it up.
Now I had all the building blocks to answer the question:


So I get the minimum and maximum position, then I try every position inbetween (calculating the distances of moving everyone there)  then I just need the minimum from this list.
Part two of the puzzle changed the cost of movement, by stating that each move is more expensive than
the last. So if a crab moves 3 positions, it will cost 1+2+3 fuel. That could easily be achieved
by adapting the distance
function to use a bit of Gauss:


Rest of the solution on GitHub
Conclusion
This puzzle almost felt like a little bit of a letdown as it didn’t feel as complex. Either that or my mathematics is letting me down to come up with a better approach.
Tags functional haskell adventofcodeIf you'd like to find more of my writing, why not follow me on Twitter or Mastodon?