Day 3 - Read, read, read!

Opening the page for day 3 gives me a small scare... grids, it's the first thing that catches my eye. As you may have guessed, I'm not a fan of grid assignments. I knew that they were coming, but so soon in the competition? After my initial reaction, I started reading the assignment, luckily for me, I learned while reading the assignment that solving it would not require building a grid and finding a path through it.

Two earn our stars today we do have to slide through a forest with the toboggan, but the path we take is already set out for us, so basically, that drills down to probing our array with certain indexes and that is not too complex. This is our example input

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

We have to walk from the top-left position downwards by taken three steps right and one step down. If we start doing this we will reach the right side of our grid very fast, but this actually will not be the case, because the pattern will endlessly loop to the right. The answer to this assignment is the number of trees (marked by #) we will encounter,

Again we will use recursion to solve our problem. We will evaluate each line of our forest and recurse into the rest of the lines taking the current column index and the total number of counted trees as parameters.

solve :: Int -> [[Char]] -> Int
solve left input = go 0 0 input where
  rowLength = length $ head input
  go _ count [] = count
  go ind  count (x:xs) = go new_ind new_count xs where
    inc '#' = 1
    inc _   = 0
    cell = x !! ind
    new_ind = (ind + left) `mod` rowLength
    new_count = count + inc cell

Just like in our last assignment we are using small functions, but this time the are in the scope of the main function (using the where syntax.) The first function is inc, this would return 1 for a tree or 0 otherwise, we use this to calculate the new count. The function go is the recursive function it takes three parameters ind, the index within the row of the path we are taking. Count is the number of trees that have been counted. The last parameter is the array of input lines. When the array is empty the function will return the count, otherwise it will recurse taking the index increased with the number of steps left modulus the length of the line (this will create the looping effect.) The main function will take the amount of steps left, and the inout and call the go function with its initial parameters. We test it again on our example which works, and also it gives us the first star of the day.

Part 2

We now have a list of slopes, since not all of the slopes take exactly one step down, but also two, we need to change our algorithm. We shall still recurse, but not on the lines of the input. We will use the row index instead. Our stop condition will be when the row index is greater than the number of rows. We will take the next slope with each recursion and cycle over the list since our input is bigger than the number of slopes.

solve :: [(Int, Int)] -> [[Char]] -> Int
solve slopes input = go 0 0 0 (cycle slopes) where
  rowLength = length $ head input
  go _ ind_r count _ | ind_r >= length input = count
  go ind_c ind_r count (s:ss 0= go new_ind_c new_ind_r new_count ss where
    inc '#' = 1
    inc _   = 0
    cell = (input !! ind_r) !! ind_c
    new_ind_c = (ind_c + fst s) `mod` rowLength
    new_ind_r = ind_r + snd s
    new_count = count + inc cell

solve1 = solve [(3,1)]
solve2 = solve [(1,1), (3,1), (5,1), (7,1), (1,2)]

Above you see our adjusted function and two calls, one with the original slope (in a list) and the second with the slopes from part two. Running this gives us the same correct answer for part 1, but if we check the answer for the second part it is not correct. We have a good look at our code but don't see any mistakes, and we know that the algorithm works because we still have the correct answer for part 1.

Let's check with the example again. Reading the assignment talks about multiplying the number of trees for each slope....Wait, what, we still have only one count, what is meant by multiplying them. Let's get over it again, we have to count the number of trees for each of the slopes of the list, so the slopes are not changing for each step down the slope like we just programmed. Damn, I didn't read the assignment correctly. After some thought, I found that I could still reuse most of my code. The go function needs to be adjusted to take a single slope instead of a list and traversing it. From the outer function, we have to map over the slopes and call the go function for each slope. This will result in a list of the number of trees. We can call product on that list to get the answer.

solve :: [(Int, Int)] -> [[Char]] -> Int
solve slopes input = product $ map (go 0 0 0) slopes where
  rowLength = length $ head input
  go _ ind_r count _ | ind_r >= length input = count

So only small changes on two lines. And we can run again to get the final answer. Not too complex today only very basic Haskell in use, and we learned that we should read our assignments more carefully. Luckily this time the mistake could be easily corrected, but this will not always be the case if you misread your assignment. I finished 7th place for the day, which averaged out to 4th place for the competition. Let's see if we can back to third tomorrow.