Advent of Code (AoC) Day One

Intro

Hello all! This years Advent of Code has begun! If you are unfamiliar with this, every day from December 1st through the 25th, a new programming puzzle with two parts is posted. The prompts are language agnostic so you can use any language you wish. I enjoy using languages that I am learning with - it gets me away from tutorial learning and into problem solving!

This is the seventh year puzzles, if you want to check out previous years take a look at: 2015, 2016, 2017, 2018, 2019, 2020

For more info check about the page and creator check out the about page.

Also, check out the subreddit r/adventofcode to find solutions for previous years, see cool visualizations of problems being solved, and to see the mega thread where people post their solutions for the day if you need inspirations / are stuck.

This series will be my solutions to AoC, and for a TLDR I will post the full solution towards the start of each post, but then I will go into way too much explanation about the problem, my thoughts on how to solve it, and how I solved it.

Day One Solution

module Solutions.DayOne
  ( d1p1,
    d1p2,
  )
where

d1p1 :: [Int] -> IO ()
d1p1 depths = do
  print $ countLarger depths 0

d1p2 :: [Int] -> IO ()
d1p2 depths = do
  let depthGroups = mkDepthGroups depths
  print $ countLarger depthGroups 0

countLarger :: [Int] -> Int -> Int
countLarger depths@(x : y : _) count
  | x < y = countLarger (tail depths) (count + 1)
  | otherwise = countLarger (tail depths) count
countLarger _ count = count

mkDepthGroups :: [Int] -> [Int]
mkDepthGroups depths@(x : y : z : _) = x + y + z : mkDepthGroups (tail depths)
mkDepthGroups _ = []

Above is the full solution to day one, parts one and two: d1p1 is day one part one, d2p2 is day two part two. My future posts will follow a similar format.

The thing that isn't visible in the solution is some of the helper functions that I write to make to make my life easier. Basically, a lot of these puzzles require the programmer to read / parse text files, so most of my helpers focus around making that quicker for me.

In this case, I was given a text file that had 2000 lines of integers, one integer per line. Here is the truncated file, the first 10 lines:

104
105
109
120
124
113
120
121
122
123
...

To avoid putting a bunch of helper functions as the month goes on (I will put some this time to give an idea), I am making the choice to only show the code required to solve the problem. I will mention the steps I took to prep the data in the explanation

Explanation

Scenario

We are going deep into the ocean in a submarine. As soon as we are submerged, our helpful submarine starts to perform a sonar sweep of the ocean floor! From this, we get a report of the sonar sweep (our input), where each line is a measurement of the ocean floor depth, and the scan goes out from the submarine: the first line is below the submarine, the second a little further from the submarine, the third even further ... continuing until the furthest from the submarine being the last line of the report.

We are then given the following sample report:

199
200
208
210
200
207
240
269
260
263

Tip: Even though you can get the full puzzle input before solving, try writing a solution that solves the smaller sample given in the scenario. If you run into issues, its much easier to desk check the code when you know the expected solution!

Part One Objective

After given this information, we are told our objective: figure out how quickly the depth increases

We are also told how to determine this info: count the number of times a depth measurement increases from the previous measurement

So given our small input above, we can manually count how many times this occurs. For example 199 -> 200 is an increase, so that is 1. 200->208, 208->210 are also increases, so we are at 3. 210->200 is a decrease so we still have a count of 3, but then 200->207 is another increase so we now have a count of 4. If you do this for all of the remaining depths we end up with a total of 7 increases, which would be the answer to part one if this was your input!

Solving Part One

So, now that we know what the objective is as well as the solution expected with the sample input, we can write out the steps for how to solve. This is how I think of the flow, assuming the input is in a .txt file:

1. Load contents of text file as a String.
2. Split the contents of the file into a list, with each element of the list representing one line.
3. Since we are doing a mathematical comparisons of each line, convert that list of strings into a list of ints.
4. Go through the list comparing each element with the one succeeding it to get a total count of increases.

Steps 1-3 are done with helper functions in this case:

readFileByLines :: FilePath -> IO [String]
readFileByLines f = do
  fileExists <- doesFileExist f

  if fileExists
    then do
      content <- readFile f
      pure $ lines content
    else error $ "File Does Not Exist: " ++ f ++ " does not exist!"

readFileOfInts :: FilePath -> IO [Int]
readFileOfInts f = do
  contents <- readFileByLines f
  pure $ map read contents

Basically I just write something like readFileOfInts "input/day-1.txt" and I get my list of ints, as shown in the function signature. That takes care of the first 3 steps!

Step 4 is the core of the problem, and from the solution posted at the start, it is:

d1p1 :: [Int] -> IO ()
d1p1 depths = do
  print $ countLarger depths 0

d1p1 uses the list of ints (depths) and passes it to another function called countLarger that takes the depths and an initial count, which is 0.

The function signature for countLarger is [Int] -> Int -> Int and it is the core of the logic:

countLarger :: [Int] -> Int -> Int
countLarger depths@(x : y : _) count
  | x < y = countLarger (tail depths) (count + 1)
  | otherwise = countLarger (tail depths) count
countLarger _ count = count

I want to look at the two definitions provided for countLarger to illustrate their purpose.

countLarger First Definition

countLarger depths@(x : y : _) count
  | x < y = countLarger (tail depths) (count + 1)
  | otherwise = countLarger (tail depths) count

The first definition of countLarger makes use of pattern matching to extract out the first two elements of the list (x : y : _) as well as give a name to the entire list depths@(x: y: _) to refer to it as a whole later. This pattern matching ensures that we have at least 2 elements to compare, x and y. Once this pattern matches, we go into the guard to check if x < y. If it is, then we see that there was an increase and we recursively call countLarger again with all of the depths except for the first one, and an increased count by 1.

Otherwise, if x < y is not true then we hit the otherwise guard and recursively call countLarger with all of the depths except for the first one and no change in count.

The way we get the the depths without the first element is by using the built in function tail. If you have a list [1,2,3,4] and you invoke tail [1,2,3,4] you are returned the list [2,3,4]

Basically, as long as we had at least two elements we will always end up recursively calling countLarger with the tail of depths (all depths except x). The only difference is if we increase our count or not!

countLarger Second Definition

countLarger _ count = count

This second definition is what we call our base case. Ever recursive function needs at least one base case if you want it to terminate!

This can be read as if you didn't pattern match the first definition requiring at least two elements, we are done comparing so return the provided count.

countLarger examples

I am going to over explain the execution of countLarger. If you are comfortable with recursion you can skip this.

countLarger [] 0
0

If we call countLarger like above, we will fail to match the first definition, and end up matching the second definition. The second definition just returns the value provided for count, which is 0 when we invoke the function, so the result is 0

countLarger [10] 15
15

With this, we call countLarger with a list with a single element which means that it will fail to match the first definition again. Since we invoked the function with a count of 15, we end up with the result of 15 since the second definition just returns the value provided for count!

countLarger [10, 11] 0
countLarger [11] 1
1

If we pass at least 2 elements then we will match the first definition. In this case, since 10 < 11 we enter the first guard and call countLarger again with the tail and an increased count.

When we call countLarger the second time, it will fail to match the first definition and we end up at the base case, giving us the final result of 1 which was the last value provided for count.

countLarger [199, 200, 208, 210, 200, 207, 240, 269, 260, 263] 0
countLarger [200, 208, 210, 200, 207, 240, 269, 260, 263] 1
countLarger [208, 210, 200, 207, 240, 269, 260, 263] 2
countLarger [210, 200, 207, 240, 269, 260, 263] 3
countLarger [200, 207, 240, 269, 260, 263] 3
countLarger [207, 240, 269, 260, 263] 4
countLarger [240, 269, 260, 263] 5
countLarger [269, 260, 263] 6
countLarger [260, 263] 6
countLarger [263] 7
7

Above is the "full" example of how countLarger is being recursively called with the sample input. Each call has a list that is smaller by 1 element, and the count is incremented if x < y, until we hit the base case and return the final count.

Phew, that was a lot, hopefully it makes some sense though! If not, I can try and make a better diagram to illustrate the recursion.

Wrapping up Part One

So back to the function that is called for part one:

d1p1 :: [Int] -> IO ()
d1p1 depths = do
  print $ countLarger depths 0

We can see that we just call countLarger with a list of Int and set our initial count to 0. When it resolves, it will give us the total count and it is printed to the terminal!

Part Two Objective

Part two usually throws a wrench into things: it adds an extra requirement, or asks to interpret the data in a different way, or any number of other things.

In this case, we are asked to interpret the data differently:
Looking at every measurement is causing too much noise! What if we considered creating a three measurement sliding window, where we sum the measurements in each window and then compare the windows the same way we compared each measurement!

New goal: count the number of times the sum of measurements in this sliding window increases from the previous sum.

Solving Part Two

In this case, we are lucky that our solution to part one still applies to the solution to part two. We still want to compare two measurements, and update a count in the same way.

The only difference is we want to find the sums of windows and compare those measurements. If you look at the function that kicks off part two, the majority of the function should look very familiar!

d1p2 :: [Int] -> IO ()
d1p2 depths = do
  let depthGroups = mkDepthGroups depths
  print $ countLarger depthGroups 0

The only change is the addition of let depthGroups = mkDepthGroups depths that does something to the depths that we were provided. Lets take a look at its implementation:

mkDepthGroups :: [Int] -> [Int]
mkDepthGroups depths@(x : y : z : _) = x + y + z : mkDepthGroups (tail depths)
mkDepthGroups _ = []

First thing to note is the signature of [Int] -> [Int] which tells us that we are taking an int list and returning one as well.

We can also see that the definition of this function is also recursive, the first definition calls mkDepthGroups.

From that we can see the base case mkDepthGroups _ = [] which can be read as if we fail to pattern match on a list with three or more elements (x : y: z : _) then we return an empty list

The more interesting definition is:

mkDepthGroups depths@(x : y : z : _) = x + y + z : mkDepthGroups (tail depths)

This definition matches on three elements (x, y, z) and names the list as depths. We then sum those three elements, and start constructing a new list with the cons operator (:) with the list returned from mkDepthGroups (tail depths) which makes use of tail again! As soon as our list of depths has less than 3 elements to sum, we terminate with an empty list.

So we ultimately end up with a new list of ints that represent the sums of the sliding windows. This list is what we pass to our original countLarger function and we end up with our result!

Wrapping up Part Two

d1p2 :: [Int] -> IO ()
d1p2 depths = do
  let depthGroups = mkDepthGroups depths
  print $ countLarger depthGroups 0

Looking at the function one more time, hopefully you can see the flow. We take the original depths and pass it to mkDepthGroups to create a new list that represents our sliding window group sums. We then hand our new list off to countLarger to do our original operation.

I didn't go into as much detail into the recursion in the mkDepthGroups function, but I challenge you to map out all of the intermediate values / calls that would occur if you passed in the sample input list. To get you started:

mkDepthGroups [199, 200, 208, 210, 200, 207, 240, 269, 260, 263]
    -> 607 : mkDepthGroups [200, 208, 210, 200, 207, 240, 269, 260, 263]
        -> 607 : 618 : mkDepthGroups [208, 210, 200, 207, 240, 269, 260, 263]
            -> ...

Conclusion

I will be honest, this post is the epitome of over explaining. The core of this is pretty simple, I just wanted to talk through every part of the problem and solution. For that reason, please don't let the length of this post scare you from trying to solve these problems! Try doing this same one with a different language if Haskell is unfamiliar.

If you enjoyed the over explanation let me know and I will try to do some more as the event goes on.