Day 3: Toboggan Trajectory

Advent of Code 2020

Now we have a toboggan, we need to calculate various trajectories through a repeating forest to see how many trees we’ll hit on our way down. 🎄

This is a classic problem where various Sequence types and operators can be used to make a really succinct solution. Especially helpful is the recently created swift-algorithms package which already has many sequence and collection algorithms that make these kinds of puzzles a lot easier to solve.

We are given a two dimensional grid representing a forest and are asked to calculate how many trees occur in given direction, given as integer amounts moved right and down. The task wants us to start in the top left and go along an amount right and down an amount down and see whether the character there is a # which represents a tree, continuing until we reach the bottom of the forest. Oh and also the forest repeats to the right ad infinitum…

func part1(_ input: Input) throws -> Int {
  count(input: input, right: 3, down: 1)
}

func count(input: Input, right: Int, down: Int) -> Int {
  let columns = (0...).striding(by: right)
  let rows = input.lines.striding(by: down).map { $0.cycled() }
  return zip(columns, rows).count(where: { column, row in
    var iterator = row.dropFirst(column).makeIterator()
    let character = iterator.next()!
    return character == "#"
  })
}

For my solution, this count function is the entirety of the logic of the calculation, albeit using operators from the swift-algorithms package. To calculate the number of trees hit, it performs the following steps:

Get a never-ending sequence of columns we’re interested in

The striding(by:) function steps over any columns we don’t care about for this run.
Get the rows that we’re interested in

Again striding(by:) skips over the rows that aren’t needed for calculations. These are then mapped to a cycled sequence using another function from the swift-algorithms package which repeats the row forever. This will allow us to inspect columns well beyond the length of the original row. It’s important to note that while each row is now infinte, this sequence of rows is finite.
Use zip to iterate through each column and row to inspect

This provides pairs of elements from the sequences given to it and is really useful here for finding a specific column index in a given row.zip is a function that will end once one of the provided sequences ends, if both inputs were infinite, this function would go on forever!
Use count(where:) to sum the number of trees

This is a custom Sequence operator which was due to be added to the standard library, but was pulled due to it’s potential to be a source-breaking change after Swift started caring about be source-breaking.
Find the character at the given column in the row

Because cycled is infinite, it cannot be a Collection which must provide an endIndex, so instead is a Sequence and sequences cannot be subscripted in to. For this reason, I drop the first column number of elements and get the next character out of the iterator.
Check if the character is a tree

Once we have the chacter we can check if it is a tree (a hash # symbol).

Part two gives us some more vectors to inspect, counting the trees on our way down which are then multiplied together to get our answer. Here I just take an array of the solutions and calculate the product() on them using the shared function I added to sequence on day 1.

func part2(_ input: Input) throws -> Int {
  [
    count(input: input, right: 1, down: 1),
    count(input: input, right: 3, down: 1),
    count(input: input, right: 5, down: 1),
    count(input: input, right: 7, down: 1),
    count(input: input, right: 1, down: 2)
  ].product()
}

Speed improvements

I will also add a warning from the get go that the rest of this post explains how I chipped away mere milliseconds of time for my solution to run. Currently my solution for part 2 runs in 67.099ms, which is totally acceptable in my book, however I was again goaded by Mike’s claim that his solution ran in just over a millisecond. So I was confident that I may find a much faster time, at the small expense of a few hours in the evening!

As my Advent of Code is set up to run unit tests, I easily added performance measurements to it and Xcode takes care of running the code 10 times to find the average time taken, showing a nice little graph of the deviations of each test run from this avergage. I have commited these baseline times in my repository and each section title below is a link to the respective commit where you will be able to see the code diff.

Using the modulo operator

The first thing I looked at was removing the iterator. This was needed in the original code because cycled returned only a sequence and so elements couldn’t be accessed randomly by index. Essentially the cost to access the columnth element was iterating column times; it’s an O(n) lookup!

Instead of using a fancy new algorithms pacakge, I instead (re)discovered the modulo operation! I had taken the puzzle too literally when it said “the same pattern repeats to the right many times” and I had cycled my input forest. I could instead use the column modulo the length of the row to find the correct character instead, saving me from having to drop down to a sequence and be able to directly access the element using the calculated index.

This change was pretty obvious in hindsight as Swift doesn’t provide any niceties to accessing elements directly, so should have been a big clue that I was doing something unwise.

This brings our run time down to 6.6704ms, ten times faster!

func count(input: Input, right: Int, down: Int) -> Int {
  let columns = (0...).striding(by: right)
  let rows = input.lines.striding(by: down)
  return zip(columns, rows).count(where: { column, row in
    Array(row)[column % row.count] == "#"
  })
}

Remove conversion from `String` to `Array<Character>`

Next on my list was to access the character in the string directly instead of converting to an array of characters. I did this initially because it always seems so tedious to calculate a String.Index to then use it, but it’s more tedious to sit around waiting for these tests to complete!

We’re now down to 2.8001ms.

func count(input: Input, right: Int, down: Int) -> Int {
  let columns = (0...).striding(by: right)
  let rows = input.lines.striding(by: down)
  return zip(columns, rows).count(where: { column, row in
    let index = row.index(row.startIndex, offsetBy: column % row.count)
    return row[index] == "#"
  })
}

Retrieve the length of the rows once

The performance of some collection operations depends on the type of index that the collection provides. For example, a random-access collection, which can measure the distance between two indices in O(1) time, can calculate its count property in O(1) time. Conversely, because a forward or bidirectional collection must traverse the entire collection to count the number of contained elements, accessing its count property is an O(n) operation.

This is from the documentation on Collection, where it turns out that String.count is another O(n) operation. We know that for this puzzle the length of each line in the input is the same, so we can take the count early on and reuse it for each calculation. Give my puzzle input is 323 lines long, this reduces just over 1400 calls to String.count down to just one.

This one weird trick drops another millisecond off the running time, to bring us down to 1.8175ms.

func count(input: Input, right: Int, down: Int) -> Int {
  let columns = (0...).striding(by: right)
  let rows = input.lines.striding(by: down)
  let count = input.lines[0].count
  return zip(columns, rows).count(where: { column, row in
    let index = row.index(row.startIndex, offsetBy: column % count)
    return row[index] == "#"
  })
}

Use `stride(from:to:by:)` for column indices

Sequence.striding(by:) is an operator provided by the swift-algorithms project which essentially takes the base sequence and provides a sequence starting at the first element and stepping over the given number of elements. As Mike points out I almost certainly chose the new shiny over the as-good stride(from:to:by) function provided by the standard library.

Replacing this call for the columns is almost indistinguishable at a time of 1.8056ms.

func count(input: Input, right: Int, down: Int) -> Int {
  let columns = stride(from: 0, to: .max, by: right)
  let rows = input.lines.striding(by: down)
  let count = input.lines[0].count
  return zip(columns, rows).count(where: { column, row in
    let index = row.index(row.startIndex, offsetBy: column % count)
    return row[index] == "#"
  })
}

Use `stride(from:to:by:)` for row indices

However, you may see that I’m making good use of striding(by:) to skip over any rows that we don’t care about. In doing so, the resulting Stride is actually looping internally to do the skipping of elements. I’m paying slightly more than an O(1) cost to get the next element.

The Stride sequence that is created here will actually conform to Collection and RandomAccessCollection because its base sequence – the array of lines – does. This means that Stride should provide the index after and subscripting with O(1) complexity because that’s the performance garauntee RandomAccessCollection provides. So what’s going on here?

The problem here is that zip takes two sequences and even if either were a collection, it only knows about the sequence pathways, so can only use them to calculate the next elements, bypassing any benefits one might see from using the Collection-level index(after:) function and subscript.

If instead we replace the use of striding(by:) with stride(from:to:by) to give the indices of the rows rather than the rows themselves, we can then use the subscript on array to get the each row which as we’ve learned, is an O(1) operation.

func count(input: Input, right: Int, down: Int) -> Int {
  let columns = stride(from: 0, to: .max, by: right)
  let rows = stride(from: 0, to: input.lines.count, by: down)
  let count = input.lines[0].count
  return zip(columns, rows).count(where: { column, row in
    let row = input.lines[row]
    let index = row.index(row.startIndex, offsetBy: column % count)
    return row[index] == "#"
  })
}

Conclusion

The result of all these changes is that we’re down to running in 1.0675ms, down from the 67.099ms we started at! That’s 62x faster; you wouldn’t even need to buy a new M1-based machine!

There are some things here that might be worth paying the small price for. For instance I actually quite like the last use of striding(by:) because it makes the code just a little easier to read. This excercise reveals the tradeoffs we must sometimes make. Programs that are easier to read and reason about may be far more useful than ones that run fractionally faster. Other times faster solutions need to be found, like when your friend is teasing you for your Advent of Code performance.

As ever in programming, it all depends on the context.

Other notes

u/tymscar managed to burn the trees before hitting them in a raytraced visualisation in Blender 3D.