Learning Haskell Day 2

On day 1 of learning Haskell and going through advent of code, we used foldl to move up and down floors to see what floor we ended up on. Day 2 is trickier as we need to do the same, but stop when we reach floor -1 for the first time. The result is how many floors we have traversed

The added challenges are

• How do I iterate until a certain condition is met (until we arrive at floor -1)
• How do I keep track of two things – the floor I am on and how many floors we traversed to get there

In my first round of googling I found there is a foldr that does something similar, but unlike foldl it doesn’t need to work through the full list.

I tried using foldr but as it works from right to left I reversed the list first, this didn’t seem to work, even though you can break out early if a condition is met. Instead I tried using scanl, this does something similar to foldl, but it returns each intermediate result and allows me to break out when a condition is met.

This is what I ended up with

main :: IO ()

floorDirection :: Char -> Int
floorDirection '(' = 1
floorDirection ')' = -1

main = do
	contents <- readFile "input.txt"
    let cleanContents = filter (`elem` "()" ) contents
	let floors = map floorDirection cleanContents
	let result = length (takeWhile (/= -1) (scanl (+) 0 floors))
	print result

I will ignore the code that is the same as the previous day, with a small mention that I removed the default pattern, the reason being that I want it to error if there are any chars except for ‘(‘ and ‘)’. This issue caused me a lot of debugging in this exercise as I need to count the length after we find our target floor, but I didn’t realise invisible characters were being read in like newlines and carriage returns. As an extra protection against this I also added

    let cleanContents = filter (`elem` "()" ) contents

To remove all other characters we don’t care about.

The interesting line that solves this puzzle is

	let result = length (takeWhile (/= -1) (scanl (+) 0 floors))

Here we first scanl the input, which has a similar signature to foldl, it iteratively adds to the previous total, and shares the intermediate results. To illustrate the differences

foldl (+) 0 [1, 2, 3, 4]

1. Step 1: 0 + 1 = 1
2. Step 2: 1 + 2 = 3
3. Step 3: 3 + 3 = 6
4. Step 4: 6 + 4 = 10

Output of foldl: 10

scanl (+) 0 [1, 2, 3, 4]

1. Step 0: Starting accumulator: 0
2. Step 1: 0 + 1 = 1
3. Step 2: 1 + 2 = 3
4. Step 3: 3 + 3 = 6
5. Step 4: 6 + 4 = 10

Output of scanl: [0, 1, 3, 6, 10]

You can see that foldl will just give us the final result, whereas scanl gives us a list of all results at each step, we can get the same result as foldl by fetching the last element from the result of scanl.

The reason we do it in this case is it is a way for us to keep track of how many steps we take to get to the basement floor (floor -1). We can simply take the length of the list. I guess this might not be the most efficient as we could instead track the floor number and the number of steps as two integers rather than an integer and a list, but I don’t know how to do that yet and this seems fine for now.

The final function I learnt an incorporated is takeWhile, this takes a slice of the list until the condition is met <code class=”language-json”>(/= -1)</code>. takeWhile will take the list from scanl once we reach the basement, then calculating the length gives us the final result.

PS C:\Users\ryanm\Documents\Haskell\AdventOfCode\2015\part2> ghc .\sol2.hs
[1 of 2] Compiling Main             ( sol2.hs, sol2.o ) [Source file changed]

sol2.hs:8:1: warning: [-Wtabs]
    Tab character found here, and in four further locations.
    Suggested fix: Please use spaces instead.
  |
8 |         contents <- readFile "input.txt"
  | ^^^^^^^^
[2 of 2] Linking sol2.exe [Objects changed]
PS C:\Users\ryanm\Documents\Haskell\AdventOfCode\2015\part2> .\sol2.exe
1797