Advent of Code #1 (in JavaScript & Haskell)

This is my first year participating in Advent of Code, and I thought I would use it as an opportunity to get better at Haskell and find similar approaches to problem solving in JavaScript. I'm actually planning to solve each puzzle in whatever method I think I can find the answer the fastest, then go back and find a better solution in Haskell after getting the right answer. (Today I used Excel, which is actually a great programming interface, but more on that some other time)

I will summarize the problems here, but you should really check out the website to get the full story and to join in!

Part One

The puzzle input gives a list of numbers, and we are asked to find the number of times that two consecutive numbers increase for the whole list. My initial thought when asked to compute a single value from a list of values is a fold/reduce. Unfortunately, each step in a fold for this problem would need to keep track of the running total of consecutive increases along with the previous number. A common trick to get this work in Haskell is to first zip the list with its own tail to end up with a list of pairs of consecutive numbers like so. (There are better ways to write this, but you'll see why I wrote it this way in part two)

list = [199, 200, 208, 210, 200, 207, 240, 269, 260, 263]
pairs :: [a] -> [(a, a)]
pairs (x:rest) = zip (x:rest) rest

Then we can fold over our list of pairs to calculate the total of consecutive increases:

answer = foldl (
  \ count (a, b) -> if b > a then count + 1 else count
) 0 (pairs list)

There is probably a better way to do this in Haskell. I tried to use a tuple as an accumulator containing the count and previous item, but couldn't seem to get that working. But that approach is relatively simple to follow in JavaScript:

[_, answer] = list.reduce(
  ([previous, count], current) => [
    current,
    current > previous ? count + 1 : count
  ], [Infinity, 0])

The initial value to the accumulator is a tuple of Infinity so that the comparison with the first item will always be smaller, and 0 for the start of the count. We use destructuring to pull the answer back out of the tuple at the end.

Part Two

This part is similar to the first one except we compare consecutive sums of three consecutive numbers. Sounds like we need triples from our list instead of pairs. We can just extend the zip concept with the zip3 function.

triples :: [a] -> [(a, a, a)]
triples (x:y:rest) = zip3 (x:y:rest) (y:rest) rest

Then we can map over that to get the sum of each triple. Once we've done that, we are back to a list of numbers, so we'll pair them up again to compare increases in consecutive sums and fold to get the total as before.

answer = foldl (
  \ count (a, b) -> if b > a then count + 1 else count
) 0 (pairs (map (\(x, y, z) -> x + y + z ) (triples list)))

There are ways to fix the mess of parentheses, but I won't get into that for now. The initial strategy of using the tuple to keep track of the previous item and the total kind of falls apart for this part of the problem, so we'll copy what we did in Haskell.

const zip = (a, b) => Array(Math.min(a.length, b.length))
  .fill().map((_,i) => [a[i], b[i]]);

const zip3 = (a, b, c) => Array(Math.min(a.length, b.length, c.length))
  .fill().map((_,i) => [a[i], b[i], c[i]]);

const pairs = ([x, ...rest]) => zip([x, ...rest], rest)

const triples = ([x, y, ...rest]) => zip3([x, y, ...rest], [y, ...rest], rest)

const answer = pairs(
  triples(list).map(([x, y, z]) => x + y + z)
).reduce((count, [a, b]) => b > a ? count + 1 : count, 0)

That is certainly not a very elegant solution, but we got there finally. It took me about five minutes to solve both these parts in Excel, but about two hours to put together these Haskell and JavaScript solutions.

How would you solve this problem in Haskell? What about in JavaScript? I'd love to see some better ways than what I hacked together.

Comments

[Kirk Shillingford]

Nice solve. I did a similar method to your js version, but in F#. Haskell definitely has some more elegant options though. F# isn't lazy, so all the solutions I thought of where I made pairs or triples would have me going through the entire list multiple times. But I feel good that someone else looked at it and immediately saw the folds. Because folds are amazing. :D

// read the data in as a list of strings then convert to integers
open System.IO

let data = 
    File.ReadAllLines(@"day1part1.txt") 
    |> Array.map int

Part one

let folder (increases, last) next =
    if next > last then increases + 1, next else increases, next

// System.Int32.MaxValue is .NET's largest int32 so the first value will always decrease

let day1part1solution =
    fst <| Array.fold folder (0, System.Int32.MaxValue) data

Part two

let folder2 (increases, last3) (index, next) =
    // we just fill up the triple for the first 3 iterations. 
    if index < 3 then
        increases, last3 @ [next]
    else
        let next3 = List.tail last3 @ [next]
        if List.sum next3 > List.sum last3 then increases + 1, next3 else increases, next3

// we can use the indexed function to convert our list of values to (index value) pairs

let day1part2solution =
    fst <| Array.fold folder2 (0, []) (Array.indexed data)

[Caleb Weeks]

This looks great, thanks for sharing! F# is on my to do list of languages to dig into more. I was actually looking for the pipe operator from F# when trying to make the Haskell version, but sadly, it isn't in the prelude. It's cool that you used a fold with a tuple!