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?

Yesterday, a fairly simple discussion of circle intersection came up: how do you subtract one circle from another to form a “cut out” Bezier path. This allows you to add an affordance or decoration to a circle, but add some space between the primary figure and the secondary bubble.

Exploring this question provided some interesting lessons that I thought I’d share in a quick post.

Embrace Core Graphics Types

When working with basic geometry, redirect your mathematics to Core Graphics. Bezier paths, points, rects, and other core geometric features use CGFloat, not Double. You minimize your pain by extending CGFloat as needed to address common geometric concerns such as exponentiation or mathematical constants rather than switching back and forth between Swift.Double and CGFloat:

/// Exponentiation operator
infix operator **: HighPrecedence

extension CGFloat {
    /// Returns base ^^ exp
    /// - parameter base: the base value
    /// - parameter exp: the exponentiation value
    public static func **(base: CGFloat, exp: CGFloat) -> CGFloat {
        return CGFloat(pow(Double(base), Double(exp)))
    }
    
    /// Tau
    public static var tau = CGFloat(Double.pi * 2.0)
}

Construct utility types

It helps to think about the kinds of types that will support your geometric challenge. For this example, I built two new types: a line segment (2 end points) and a circle (a center and a radius). Bringing these under the Core Graphics umbrella unified my representations with the tools they need to express their geometry:

/// 2-point representation of line segment
public struct Segment {
    public let (p1, p2): (CGPoint, CGPoint)
    var dx: CGFloat { return p2.x - p1.x }
    var dy: CGFloat { return p2.y - p1.y }
    public var length: CGFloat { 
        return sqrt(dx ** 2 + dy ** 2) 
    }
}

/// Center/Radius circle representation
public struct Circle {
    public let center: CGPoint
    public let radius: CGFloat
}

Being Core Graphic native enables you to leverage constructors using the appropriate types. For example, my circle can construct a path for drawing to a UIKit-compatible context:

/// Returns a Bezier path sweeping between two angles
public func path(from startAngle: CGFloat = 0, to endAngle: CGFloat = CGFloat.tau, 
    clockwise: Bool = true) -> UIBezierPath {
    return UIBezierPath(arcCenter: center, radius: radius,
                        startAngle: startAngle, endAngle: endAngle,
                        clockwise: clockwise)
}

This path method allows me to express each circle as a path, hiding the details of a UIBezierPath constructor. When I want to throw up a visual reference point, I just construct a circle at that point and fill it:

let p1 = Circle(center: segment.p1, radius: 2.5)
p1.path().fill()

Very handy.

Let the math be the math

When you’re working with standard algorithms, it helps to step back from your standard Swift key paths and use the terms of art you’re translating into code. For example, it can be convenient to break down some basic Swift into algorithm-specific terms:

let (x1, y1, r1) = (self.center.x, self.center.y, self.radius)
let (x2, y2, r2) = (other.center.x, other.center.y, other.radius)

It may not be “Swifty”, but doing so leads to easier inspection when comparing your implementation to the how-to reference in a book or paper.

Draw It

Playgrounds are great when it comes to testing drawing algorithms because you can use real data and get immediate results to see whether your assumptions and expectations are properly met.

In this example, the first two circles intersect, allowing the construction of the “chunked out” major circle and a condensed minor circle. The original circles are outlined and the two red points indicate the overlap points.

The second pair does not intersect, so it’s left simply as two outlines.

If you want to play around with this rough implementation, I left the code for this over at github. Feel free to expand or improve upon my approach, as it was very much an off-hand “here’s more or less how you can do this” exercise.