advent of code 2020, day 3: lazy tobogganingWritten: 2020-12-02 to 2020-12-02
by Norman Liu
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
' ' 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]] = lines >>> fmap (cycle . fmap (fromEnum . (== '#')))format
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]] = (iterate (fmap (drop run) >>> tail) >>= zipWith const) >>> fmap headslide run
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 >>= f = \r -> f (x r) r x
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 _  :xs) = x : meander run (drop run <$> xs)meander run (x
Let’s try it out.
> slide 1 [[1,2,3],[4,5,6],[7,8,9]] 1,2,3],[5,6],] [[ > 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 = xs & (chunksOf rise >>> map head >>> slide run >>> map head >>> sum)toboggan xs run rise
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
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 = format >>> flip (flip toboggan 3) 1 day3Pt1 > 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) = [ (1, 1) slopes 3, 1) , (5, 1) , (7, 1) , (1, 2) , ( ]
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
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 = format >>> uncurry . stepSlope >>> (<$> slopes) >>> productday3Pt2
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!