AoC '20: Totally Tobogganal!

AoC '20: Totally Tobogganal!

Password predicaments a thing of the past, and toboggan in hand, we head to the slopes. We stand proud, gazing out upon a sea of trees erupting from the snow. Curiously, these trees have grown in a perfect grid, infinitely repeating to the right as far as the eye can see. There are no straight lines in nature; we think to ourselves as we muse upon the vast expanse before us.

Day 3: Toboggan Trajectory

We scan the area, mentally noting all of the trees before us. Our toboggan is a reasonably cheap one, capable of following just a few slopes down this hillside. And, strangely, preferring rational numbers. Several steps define each gradient to the right, and then down. Let's look at an example.

..##.......
#...#...#..
.#....#..#.
..#.#...#.#
.#...##..#.
..#.##.....
.#.#.#....#
.#........#
#.##...#...
#...##....#
.#..#...#.#

We mark trees with a pound and open spaces with a point. Remembering that this grid repeats infinitely to the right, we can visualise it like so.

..##.........##.........##.........##.........##.........##.......  --->
#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..
.#....#..#..#....#..#..#....#..#..#....#..#..#....#..#..#....#..#.
..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#
.#...##..#..#...##..#..#...##..#..#...##..#..#...##..#..#...##..#.
..#.##.......#.##.......#.##.......#.##.......#.##.......#.##.....  --->
.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#
.#........#.#........#.#........#.#........#.#........#.#........#
#.##...#...#.##...#...#.##...#...#.##...#...#.##...#...#.##...#...
#...##....##...##....##...##....##...##....##...##....##...##....#
.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#  --->

We think to ourselves that following a gradient of three to the right and one down might be a good starting point. Our goal is to count the number of trees we would encounter in doing so. Starting at the top left, in our example, we would hit seven trees. Visualised, where X represent encounters with trees, and O stops in clear spaces, it would look like this.

..##.........##.........##.........##.........##.........##.......  --->
#..O#...#..#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..
.#....X..#..#....#..#..#....#..#..#....#..#..#....#..#..#....#..#.
..#.#...#O#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#
.#...##..#..X...##..#..#...##..#..#...##..#..#...##..#..#...##..#.
..#.##.......#.X#.......#.##.......#.##.......#.##.......#.##.....  --->
.#.#.#....#.#.#.#.O..#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#
.#........#.#........X.#........#.#........#.#........#.#........#
#.##...#...#.##...#...#.X#...#...#.##...#...#.##...#...#.##...#...
#...##....##...##....##...#X....##...##....##...##....##...##....#
.#..#...#.#.#..#...#.#.#..#...X.#.#..#...#.#.#..#...#.#.#..#...#.#  --->

Part 0 — Parsing our Input

When reading through the problem statement, we can observe that we don't care about open spaces — just the locations of trees on the grid. Therefore, we'll first define a structure to hold information about a grid reference.

struct Coordinate {
    var x: Int, y: Int

    static var zero = Coordinate(0, 0)

    init(_ x: Int, _ y: Int) {
        self.x = x
        self.y = y
    }

    static func += (_ lhs: inout Coordinate, _ rhs: Coordinate) {
        lhs.x += rhs.x
        lhs.y += rhs.y
    }
}

Our coordinate structure contains two integer values, x and y, an initialiser and an overload of the plus-equals operator. We explored operator overloading in my previous post. With this structure created, we can make a start!

var temp = [Coordinate]()
let rows = input.components(separatedBy: .newlines)
for y in 0..<rows.count {
    let cols = Array(rows[y])
    for x in 0..<cols.count {
        if (cols[x] == "#") {
            temp.append(Coordinate(x, y))
        }
    }
}

We start by creating an array of coordinate structures, which we'll populate with the location of trees. Ordinarily, we'd split the input into lines and compact map the result. However, on this occasion, we need the two-dimensional position of each character in the input grid. Therefore, we split the input into lines and then iterate over them, zero-indexed. For each line, we extract it to an array — remember, strings are just character arrays — and iterate over it. Then, for each pound character, we append a new coordinate using the y (row) and x (column) coordinate of the tree. Lastly, we record the height (number of rows) and width (size of the first column) of the grid. We'll need these later.

Our trees successfully mapped out, let's get to riding those slopes. Radical!

Part 1

Our first goal is to assess the number of trees we will encounter if we follow the line defined by y=x/3. Using our coordinate structure, that's (3, 1): Three steps to the right, and then one down. We'll need to keep following this line until the value of y is greater than the length (or height) of the slope.

var result = 0
var offset = Coordinate(3, 1)
var position = Coordinate.zero
while (position.y < h) {
    /* ... */
}

We'll use a while loop, such that our program runs until we meet the exit condition. We also declare our current position, which is the top left corner; our slope in coordinate form, (3, 1), named offset; and an integer called result to hold the number of trees encountered.

position += offset
position.x %= w

if (data.contains(position)) {
    result += 1
}

Each time we loop, we'll add the offset to our current position. We then set x equal to itself modulo the width of our grid. The second of these operations create a wrap-around effect, where x can effectively continue infinitely to the right as, if we exceed the width, the remainder will be the correct position. Lastly, we check whether there is a tree recorded in our new location. If there is, we increment the result by one.

Executing this loop yields a result of 171 encounters of the tree kind.

Part 2

The second stage of this challenge requires us to perform the same test for several slopes, and multiply the resulting number of trees encountered for our solution. We can start by extracting our part 1 solution into a separate function.

func solveFor(_ offset: Coordinate) -> Int {
    var result = 0
    var position = Coordinate.zero
    while (position.y < h) {
        position += offset
        position.x %= w

        if (data.contains(position)) {
            result += 1
        }
    }
    return result
}

Next, we'll define an array of the gradients we need to test.

let slopes = [
    Coordinate(3,1),
    Coordinate(1,1),
    Coordinate(5,1),
    Coordinate(7,1),
    Coordinate(1,2)
]

Lastly, we create a map of the solutions to each slope and multiply the results using the reduce method. Reduce works by acting, in this case using multiplication, on the value with each value of the input array.

let result = slopes.compactMap { slope in solveFor(slope) }.reduce(1, *)

Our new code produces a result of 1206576000.

Complete Code

You can find my complete solution here.

Show Comments