Jump to:
D1 | D2 | D3 | D4 | D5 | D6 | D7 | D8 | D9 | D10 | D11 | D12 | D13 | D14 | D15 | D16 | D17 | D18 | D19 | D20 | D21 | D22 | D23 | D24 | D25
Part 1
Things get a little more interesting in Day 3. We're given an infinitely wide 2D matrix (or rather, a way to generate an infinitely wide 2D matrix) and we need to count the number of non-zero elements ("trees") encountered as we draw a linear path through the matrix.
import D3input
-- input :: [String]
-- rightSteps :: Int
countTrees :: [String] -> Int -> Int
countTrees [] _ = 0
countTrees field col =
let numTrees = if ((head field) !! col == '#') then 1 else 0
numCols = length $ head field
in numTrees + countTrees (tail field) (mod (col + rightSteps) numCols)
solve :: Int
solve = countTrees input 0
main :: IO ()
main = print solve
Finally we get to write our own recursive algorithm! countTrees takes the input Strings, as well as the column we are starting at in the top row. We will pass 0 as the column in our top-level call, but it needs to be a parameter so that we can traverse the remainder of the matrix properly via recursion.
Our base case occurs when we have processed every row and are left with an empty list - we want to return 0 in this case. After that, the recursion is as follows: determine whether we are on a tree at the current row (computed as numTrees above), and, if so, add 1 to the result of traversing the rest of the matrix. Note that we are careful to update the col parameter to (col + rightSteps) so that we check the correct element in the recursive calls.
It's worth noting that our countTrees function is essentially just a foldr, with addition as the operation and 0 as the initial value. The challenge with this approach would be to transform our input from [String] to [Int], where the resulting list has a 1 if there is a tree on the path, and 0 otherwise. Here's what that might look like:
hasTreeInCol :: (Int, String) -> Int
hasTreeInCol (colIndex, row) =
let actualColIndex = colIndex `mod` (length row)
in if (row !! actualColIndex == '#') then 1 else 0
hasTreeOnPath :: Int -> [String] -> [Int]
hasTreeOnPath step field =
let indexed = zip [0,step..] field
in map hasTreeInCol indexed
countTrees :: [String] -> Int -> Int
countTrees field step = foldr (+) 0 (hasTreeOnPath step field)
I actually prefer the non-foldr version, even if it was a fun exercise to try to implement this as a foldr. I think that preference stems from the awkwardness in writing the hasTreeOnPath function above. Determining whether a given String should map to a 1 or a 0 cannot be done by looking at the String in isolation. Instead, we need to know which row we are considering. This is done by using zip to introduce additional state into the list.
Part 2
Part 2 asks us to repeat this calculation for multiple slopes. This would be a trivial extension from the part 1 solution if all slopes were of the form "right N, down 1", but one of tasks is "right 1, down 2", which forces us to be able to hop down more than 1 row.
We first separate the recursive function into a countTreesAux, and make it take the number of steps to the right as an additional parameter:
import D3input
-- input :: [String]
-- slopes :: [(Int, Int)]
takeEvery :: Int -> [a] -> [a]
takeEvery _ [] = []
takeEvery n (x:xs) = x : (takeEvery n (drop (n - 1) xs))
countTreesAux :: [String] -> Int -> Int -> Int
countTreesAux [] _ _ = 0
countTreesAux field col rightSteps =
let numTrees = if ((head field) !! col == '#') then 1 else 0
numCols = length $ head field
in numTrees + countTreesAux (tail field) (mod (col + rightSteps) numCols) rightSteps
countTrees :: [String] -> (Int, Int) -> Int
countTrees field (x, y) =
let stridedField = takeEvery x field
in countTreesAux stridedField 0 y
solve :: Int
solve = foldr (*) 1 (map (countTrees input) slopes)
main :: IO ()
main = print solve
Other than the additional parameter, though, countTreesAux is identical to part 1. The stepping down by multiple rows is handled by passing a filtered matrix to countTreesAux, computed as stridedField with the help of a takeEvery function. In other words, instead of modifying our recursive algorithm to jump by multiple rows, we remove all the rows that are not relevant before passing it to our algorithm.
The problem asks us to determine the answer for each slope and then multiply them all together. This multiplication is done by a foldr with multiplication as the operation. Since our slopes is given as a list of (Int, Int), we want to be able to convert from this [(Int, Int)] to [Int]; i.e., we need a function that takes a slope and returns the answer, and then map that function onto our list of slopes. Our new top-level countTrees has the parameters structured so that we can get this (Int, Int) -> Int function by partial application.
Jump to:
D1 | D2 | D3 | D4 | D5 | D6 | D7 | D8 | D9 | D10 | D11 | D12 | D13 | D14 | D15 | D16 | D17 | D18 | D19 | D20 | D21 | D22 | D23 | D24 | D25