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))")
                // Generate the next value in the triangle
                // wave pattern to determine the distance
                // from the center
                current += direction
                if abs(current) == radius { direction *= -1 }

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?


  • For part 1 of day 3 I used the following Haskell code which builds the infinite spiral starting from the center location as a series of steps in the given direction, i.e. [R, U, L, L, D] is the path from 1 to 6
    (I like to think in Haskell for algorithmic problems):

    -- Possible steps (Up, Down, Left, Right)
    data Step = U | D | L | R deriving (Eq, Show)

    -- Steps to build the spiral starting from center
    spiral :: [Step]
    spiral = concat $ zipWith replicate spiralStepCounts (cycle [R, U, L, D])
    spiralStepCounts = dup [1..]
    dup [] = []
    dup (x:xs) = x:x:dup xs

    -- Merge steps, i.e. D cancels U and L cancels R
    -- answering the total number of the remaining steps
    mergeSteps :: [Step] -> Int
    mergeSteps xs = go 0 0 xs
    go countRight countUp [] = abs countRight + abs countUp
    go countRight countUp (x:xs) = case x of
    R -> go (countRight + 1) countUp xs
    L -> go (countRight - 1) countUp xs
    U -> go countRight (countUp + 1) xs
    D -> go countRight (countUp - 1) xs

    -- Number of steps needed to reach position n
    spiralDistance n = mergeSteps $ take (n - 1) spiral

    • Adding part 2 (with a refactoring for part 1 to enable reuse):

      -- Possible steps (Up, Down, Left, Right)
      data Step = U | D | L | R deriving (Eq, Show)

      -- Steps to build the spiral starting from center
      spiral :: [Step]
      spiral = concat $ zipWith replicate spiralStepCounts (cycle [R, U, L, D])
      spiralStepCounts = dup [1..]
      dup (x:xs) = x:x:dup xs

      -- Coordinates of the spiral
      coords :: [Step] -> [(Int, Int)]
      coords = scanl coord (0, 0)
      coord (x, y) step = case step of
      R -> (x + 1, y)
      L -> (x - 1, y)
      U -> (x, y + 1)
      D -> (x, y - 1)

      -- Part 1

      -- Number of steps needed to reach position n
      spiralDistance n = numSteps $ coords spiral !! (n - 1)
      numSteps (x, y) = abs x + abs y

      resultDay3Part1 = spiralDistance 265149

      -- Part 2

      type Storage = Map (Int, Int) Int

      storage = scanl store initial (tail $ coords spiral)
      initial = Map.insert (0, 0) 1 Map.empty
      store s pos = Map.insert pos (value s pos) s
      value s pos = sum $ mapMaybe (\d -> Map.lookup (offset pos d) s) neighbors
      offset (dx, dy) (x, y) = (x + dx, y + dy)
      neighbors = [(dx, dy) | dx <- [-1, 0, 1], dy <- [-1, 0, 1]]

      storageValues = map maximum storage

      resultDay3Part2 = head $ dropWhile (<= 265149) storageValues

      • Is there anything I have to do besides encapsulating my code in ... to make it look pretty?
        Seems like each line got wrapped in … 🙁

        • oops, I meant “encapsulating my code in <code>…</code>” and “wrapped in <p>…&lt/p>” respectively…

  • I also took the mathematical approach of reasoning squares of odds as counting distance from inside out and centre laterally. I agree that this also was no help for the 2nd half. I suspect the person writing the problem knew that people would avoid populating a grid in part 1 if they didn’t have to.

    Thank you for posting about this. I wouldn’t have heard about it otherwise.

  • My solution for the first half of day 3 is really simple. No loops !!!
    Of course it doesn’t works for the second half of day 3.

    This is the code in swift for Playground

    func compute1(_ value:Int) {
    let c = (Int(sqrt(Double(value - 1))) + 1) / 2
    let start = (c * 2 - 1) * (c * 2 - 1) + 1
    let offset = (value - start) % (c * 2)
    let result = c + abs(offset + 1 - c)
    print("\(value) -> \(result)")


    I see numbers like circles (or squares) around the 1. c is the circle number.
    circle 1 contains numbers from 2 to 9, circle 2, numbers from 10 to 25, etc…
    if x is the initial value, its circle can be known with c = Int( (Int(srqt(x-1)) + 1) / 2 )
    then the first number in the circle is start = (2c-1)^2 + 1
    the count of numbers in a circle is 8c,
    the offset of the value from the begin of the circle = value – start
    By symmetry, you can limite the calcul to the first quarter of the circle. To do that, I get the modulo 2c of the offset.
    To move from the center to the circle, you must first move c steps (to left, right top or bottom) than a number of step depending of the offset of the position of the value from the center of the quarter of the circle. these steps can be get with abs(offset + 1 – c)