advent of code 2020, day 3: lazy tobogganing

It’s December, so you know what that means.

Debt? Maybe. Alcoholism? No time. Time to save Santa again? Yep.

Advent of Code is finally back, and so everybody’s in full motion trying to contort their favourite languages into workable problem-solving tools, me included. I’ve been a huge fan of Advent of Code ever since I started programming, and I love going back and working on old problems when Leetcode and Codewars get boring. I’m hoping for some problems spread out over several days that involve incremental and visible progress, like last year’s Intcode computer.

Today’s problem is relatively simple - after saving Christmas for the past five years, you’ve earned yourself a little tropical vacation. Even though you’ve travelled through space, time, and into Santa’s computer, you still have to rely on sled-based transportation to get to the airport. This is a task fraught with danger, because trees litter the landscape more than potholes mark the 401. Given an ASCII map of the area and two integers denoting rise and run, your task is to figure out how many trees you’ll collide with on your path.

example :: [Char]
example = "
  ..##.......
  #...#...#..
  .#....#..#.
  ..#.#...#.#
  .#...##..#.
  ..#.##.....
  .#.#.#....#
  .#........#
  #.##...#...
  #...##....#
  .#..#...#.#
  "

#’s represent trees and .’s are empty land. Mercifully, we won’t need to deal with floating-point calculations for this problem.

The landscape repeats itself horizontally, so running off the right side of the map will just put you back where you started. Starting from the top left of the map and a rise and run of (3, 1), how many trees will we collide with?

Let’s start off by making our problem a little easier. We can’t directly add booleans in Haskell, and binary looks way cleaner anyways. Since we’re working with numbers, we have the power to shift our thinking and modify our landscape to suit our needs. Let’s look at a simpler example:

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

If we had a (rise, run) of (1, 1), our path would look like this: (replacing . with ' ' for clarity).

\ \## #
 \#\ # 
  \#\  
#  \ \ 
### \#\

But we’re working in a functional language, and our (regular) data structures don’t support random access. Let’s shift our perspective - instead of sledding to the right, why don’t we just make the trees come to us? We can turn our diagonal traversal into equivalent diagonal transformations of the landscape:

      our path
      |
      |
     | |## #
     |#| # 
     |#|  
  #  | | 
 ### |#|

By shifting the landscape, we only need to travel straight down. We’ll start off by extending our rows - our x-axis is infinite and we can take advantage of lazy evaluation to model that literally.

cycle takes a list and loops it in itself, creating an infinite generator.

import Control.Arrow
import Control.Applicative
import Data.List.Split
import Data.Function

format :: [Char] -> [[Int]]
format = lines >>> fmap (cycle . fmap (fromEnum . (== '#')))

We split the input into lines, turning each row into a collection of binary digits. We conjure an ouroboros from each line, with perimeters linked perpendicularly by a list. If you were writing this in a language where space matters, you could implement the rollover function using bit rotation. Lazy lists are more fun. The input string has lines 31-characters long, which I assume is to accommodate that approach.

Now, we weave a spell to terraform the landscape for our safe travel.

slide :: Int -> [[a]] -> [[a]]
slide run = (iterate (fmap (drop run) >>> tail) >>= zipWith const) >>> fmap head

We can just walk down our list of infinite rows, dropping the first run elements of each stream at every turn. It’s not too efficient for gigantic inputs, but it’s elegant. We take a list, repeatedly mapping drop run over it, and stepping down to the next stream. Using the Monad instance for functions (aka the Reader monad), we can take advantage of the fact that iterate (fmap (drop run) >>> tail) is a single-argument function, and zipWith const takes two arguments. This fulfills the m a -> (a -> m b) -> m b requirement for monadic binding, and so we can apply them to the same input without having to pollute our code with cruft. Can you imagine actually naming arguments?

instance Monad ((->) r) where
  return = const
  x >>= f = \r -> f (x r) r

You can do the same thing with liftA2 f x id, but that’s less concise and you can’t show off your monad wizardry. This might seem like dangerous code, as iterate doesn’t stop applying its given transformation, and tail is a partial function. Usually, you would incur a runtime error from taking the tail of an empty list, but that’s fine. zipWith is bounded to the length of the shorter input list, and so we consume exactly as many values from iterate as there are in the original list. Any more, and Haskell would crash on us. It’s still arguably less dangerous than crashing into trees.

A more intuitive version of slide might look like

meander :: Int -> [[a]] -> [[a]]
meander _ [] = []
meander run (x:xs) = x : meander run (drop run <$> xs)

Let’s try it out.

> slide 1 [[1,2,3],[4,5,6],[7,8,9]]
[[1,2,3],[5,6],[9]]

> map (take 8) $ slide 1 (map cycle [[1..5], [11..15], [21..25]])
[
  [1,2,3,4,5,1,2,3],
  [12,13,14,15,11,12,13,14],
  [23,24,25,21,22,23,24,25]
]

We’ve basically solved the problem at this point. We’ve figured out how to model stepping forward, and all that remains is to chain these functions together. Recall that the prompt is asking us to output the amount of trees that we have the misfortune of encountering on our journey, and so:

toboggan :: [[Int]] -> Int -> Int -> Int   
toboggan xs run rise = xs & (chunksOf rise >>> map head >>> slide run >>> map head >>> sum)

I’ve recently started using arrows to compose functions from left-to-right, and I’m loving the readability of my code now. We need to pass xs through chunksOf before slide, because each row’s transposition is relative to its position within the list. The reason why our arguments are backwards will become apparent in the second part of the problem. In the meantime though, we’re done.

day3Pt1 :: [Char] -> Int
day3Pt1 = format >>> flip (flip toboggan 3) 1

> day3Pt1 example
7

Infinite lists are magical when you don’t have to consume them in their entirety.

Part 2: Trees galore

Clearly, your original path wasn’t ideal. What about some other slopes? Given a series of (run, rise) pairs, we need to return the product of all the trees encountered during each path.

slopes :: (Int, Int)
slopes = [ (1, 1)
         , (3, 1)
         , (5, 1)
         , (7, 1)
         , (1, 2)
         ]

We gave stepSlope some non-ideal arguments earlier because we want to be able to pass it a constant area map as input, returning a function that’s more flexible when passing it run and rise values. Applicatives are great for this pattern if we have multiple functions and inputs that we want to take every combination of, but it’s overkill in this case. We can fall back on good-old fmap, creating a function from our input that we’ll map over our static list of slopes.

day3Pt2 :: [Char] -> Int
day3Pt2 = format >>> uncurry . stepSlope >>> (<$> slopes) >>> product

We wrap stepSlope up in uncurry so that it works on tuples, pass it in as our mapping function, and that’s it. For every pair (run, rise), we split the input rows by rise steps, taking the first row of every chunk, and starting our “diagonal” traversal.

That’s it for day 3, hopefully it gets even more interesting from here!