advent of code 2020, day 3: lazy tobogganing
Written: 2020-12-02 to 2020-12-02by Naomi Liu
Part 1 of 2 in this series.
[prev] [index] [next]
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]]
= 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 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
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],[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
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
= 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 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
= 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!