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

Python Queues

Thanks to my job, I found myself needing to set up a way to have tasks go into and out of a Python script.  Especially when I’m trying to make something that we’ll be sending tasks to over a longer period, I need to have something a bit more solid.

Python queues work pretty simply.  You create a queue, then have a worker pull tasks off the top of the queue.  The worker works the tasks, then notifies the queue the task is complete, and the tasks pulls another queue.  At any point in this process, you can add more tasks. Continue reading “Python Queues”

Speaking @ Memphis Ruby Users Group

I recently spoke at the Memphis RUG about my most recently completed project.  Unfortunately, due to an ongoing concern at work regarding intellectual property deals with a competitor, I am unable to publish the slides in their entirety at this time.

I spoke on building an imaging system using Ruby, Rails, and Linux.  If anyone else would like to see the slides or have me present, feel free to contact me.

ROI on Tech Projects (Part 1)

Recently, I was asked to calculate the ROI of an internal project at work, and after I ran the numbers, I discovered that not only was the project incredibly financially sound, but the value of being a technical person who can do these sorts of things is remarkable.

In this section, I’ll start off with some basic terminology and give you a basic rundown of how ROI calculations work and what they’re useful for.  This is something that anyone with a technical inclination can easily pick up, and is the sort of knowledge that can improve a career, make work less stressful, and can help you make a case for why a project is a good (or bad) idea. Continue reading “ROI on Tech Projects (Part 1)”