Advent of Code 2018 – Day 1

For the day one puzzle, we are given a long list of numbers, of the format

+xx

-y

The first-blush (naive) implementation for part 1 can work something like this

sum := 0
for _, line := range inputLines {
add, _ := strconv.Atoi(line)
sum += add
}
fmt.Println(sum)

On its face, this is pretty reasonable!  It’s compact, it’s not awful slow… except for one thing: once we get to the second part of this day’s puzzle, parsing through the strings over and over will get extremely expensive, so instead, let’s do part one by parsing the strings into a slice of ints.

lines := []int{}
for i, line := range inputLines {
lines[i], error := strconv.Atoi(line)
}
sum := 0
for _, add := range lines {
sum += add
}
fmt.Println(sum)

This is a very simple, straightforward problem, right?  Sure, then we get to part two.

In part two, we need to find the first number that repeats after adding the list to itself over and over… until we finally have a repeated number.  The looping part is very straightforward:

i := 0
sum := 0
for {
if i >= len(lines) {
i = 0
}
sum += lines[i]
i += 1
}

This works great, except for one problem: this will never actually break out because we aren’t checking to see what’s been repeated.  We have a few options for how we can go about this.

First, we could try making a slice of the ones we’ve seen before, like this:

seen = []int{}
{ ...
sum += lines[i]
i += 1
seen = append(seen, sum)
for _, value := range seen {
if sum == value {
fmt.Println(sum)
}
}
}

This works, but it has one major downside – as we add more, it will take longer and longer and longer to check for a match.

If we add 5 elements to the list, we have to check 4+3+2+1=10 numbers as we insert them; for 50000, we will need to check over 1.25 BILLION times.  Assuming we have actually hit our repeat for part two by then, this will still take a long time, to say nothing of the additional steps required.  

We can do this using something like a search tree (which will greatly reduce the amount of time needed to find each one), but we can do this a little faster, even, if we’re willing to trade memory for faster execution.

We can just estimate what our highest value is we are likely to see, and create a slice of booleans, like this:

seen := make([]bool, 250000)

This will take up a little extra memory, but access for a slice in Go a single operation, essentially.  We can do it like this:

if seen[sum] == true {
break
} else {
seen[sum] = true
}

So by doing it this way, we’re able to really speed up execution, but at the cost of a little extra memory.  All about constraints.

If you’re curious, you can see my entire solution on GitHub: https://github.com/hmschreck/Advent2018/tree/master/Dec1

Leave a Reply

Your email address will not be published. Required fields are marked *