Advent of Code 2020

2020 has been a bear but every December there's Advent of Code! I found day 9 to be really interesting, and came up with a decent way to solve it, I think so anyway.

Ah, 2020.

Advent of Code is underway. It's ok so far, nothing magical yet, on this 9th day of December. I've been solving the problems in well under an hour. I caught up a bunch over the weekend then have been doing them the following morning for the past few.

Day 9 was interesting. It's a list of integers. Given an integer after the 25th index, there will exist 2 integers in the previous 25 (so sliding) that will add up to that integer.

Or there won't be and that's Part 1's answer.

Now, given that number, there's a contiguous list of integers in the list that will add up to the answer from part 1. My first dumb thought was like a loop inside a loop. So dumb.

Obviously this can be solved with a queue. So that's what I did.

Given a number and the list of numbers, instantiate a new Queue (in Go, just a slice is fine). Since the list is "kind of" ordered, if the current number is bigger than the number we're looking for, I just stop. Then I check the sum of the queue (first pass is 0, since no numbers), and if it's greater than, and while it's greater than, I remove numbers from the front of the queue.

If the sum is equal to the number we're looking for, then I just return the current queue.

I then add the current number to the end of the queue, and loop.

You can view that function and the whole solution over on my github.

 

blog comments powered by Disqus