Archive for December, 2017

Advent day 3, part 1

Are you playing along with Advent of Code? I got started a little late this year, so I’m doing a couple of days each day until I catch up.

The basis of Advent of Code isn’t so much the beauty of your code as it is the correctness. Because of this, a lot of my code is hideously ugly, with design choices best described as “questionable”. For example, at one point, I used flatMap.count¬†on returned optionals instead of returning zeroes and ones and reducing them with +. I’m using Swift because that’s the language that’s currently dominant in my brain, although a lot of the memory manipulation would have been easier with straight C.

I wanted to share my solution for the first half of day 3. The challenge stipulates a squared spiral pattern of numbers in a grid and then asks you to calculate the distance from each number to the center. The approach I came up with for part I proved completely useless for the second half of day 3, where I had to start over from scratch. (Normally, you just modify the first code with an extra function and you go from part I to part II pretty easily.)

I took a road with part I that really didn’t fit the mindset of the challenge givers. For me, I was thinking geometrically, noticing that this was a degenerate case of a series of concentric circles. However instead of calculating the distance with a sin-cos solution, the concentric squares created a stepped triangle wave instead. Because of this, I built my solution to traverse the triangle wave and deduce the distance as the radius + the phase of the wave for any given number.

I thought I’d share my code for this because it’s pretty short and I think it’s pretty unusual for the problem domain.

for n in [1024, 12, 23, 312051] {
    for i in sequence(first: 1, next: { $0 + 2 }) {
        // Find least bounding square that contains number
        let boundingSize = i * i
        if boundingSize >= n {
            // Start of the outer edge sequence
            let firstValue = (i - 2) * (i - 2) + 1
            
            // Calculate distance to center
            let radius = (i - 1) / 2
            
            // The first number is always positioned at the
            // bottom right, one up from the bottom
            var current = radius - 1
            
            // The `direction` differential is the basis of
            // the triangle wave generator. It flips at the
            // minimum (-radius) and maximum (radius) offsets
            var direction = -1
            
            // One trip through the outer edge will be
            // sufficient to find the value
            for value in firstValue ... boundingSize {
                if value == n {
                    print("Result for \(n) is \(radius + abs(current))")
                    break
                }
                
                // Generate the next value in the triangle
                // wave pattern to determine the distance
                // from the center
                current += direction
                if abs(current) == radius { direction *= -1 }
            }
            break
        }
    }
}

Needless to say, my solution for part II had nothing to do with this wave approach. Instead, I actually constructed the 2D array, populated it with numbers and then used those as an addressing scheme to collect sums. Outside the addressing, it was basically applying a 3×3 sum filter in an address-driven convolution. Much longer, not pretty, but reasonably effective.

In the end, if I had done my “fill then look up locations” approach I used for part II for the first puzzle, it would have provided a much quicker solution although I don’t think it would have been as short or, in my opinion, nifty.

What approach did you end up using for day 3? And what made you go with that design?