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

Building a new, super cheap transcoder using AWS Lambda and Layers

So remember that post I wrote a bit back about the Transcoder?  Yeah,  that’s old hat now.  I wrote a new one.  In an afternoon.  On a Sunday.

No joke, and it was super, super easy.

I’ve been experimenting with Golang a lot lately (and it is absolutely beautiful, I gotta point that out).  I started off yesterday reading about the newest option in AWS Lambda – layers.

For those who aren’t familiar, layers are a way to include necessary files in Lambda functions.  At its core, layers are uploaded as zip files, with the zip file essentially being mounted to /opt on the instance.  By including other binaries in the layer, you have a clean, simple way to put statically-linked (this part is important!) binaries into your Lambda instances.

In this case, I made a zip file containing a directory, “ffmpeg”, which contains a statically-linked build of ffmpeg.  Since the zip file gets mounted to /opt, this means I can call ffmpeg at /opt/ffmpeg/ffmpeg, and pass in its options like I normally would.

From there, it’s just a matter of building the glue to do all of this.  What started out as an experiment in Go is now chugging away in production.  Who knows what’s next for a cruddy afternoon?