advent of code 2020, day 3: lazy tobogganing
Written: 20201202 to 20201202by 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 problemsolving 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 sledbased 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 floatingpoint 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]]
= 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 31characters 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 head slide 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 singleargument 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],[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
= xs & (chunksOf rise >>> map head >>> slide run >>> map head >>> sum) toboggan xs run rise
I’ve recently started using arrows to compose functions from lefttoright, 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
= 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)
, ( ]
We gave stepSlope
some nonideal 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 goodold fmap
, creating a function from our input that we’ll map over our static list of slopes.
day3Pt2 :: [Char] > Int
= format >>> uncurry . stepSlope >>> (<$> slopes) >>> product day3Pt2
We wrap stepSlope
up in uncurry
so that it works on tuples, pass it in as our map
ping 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!