Advent of Code 2022 Days 11-15 in Rust and Haskell

I’ve given up following the narrative. There’s some kind of receiver and some beacons and maybe still some monkeys? I don’t know. The puzzles have gotten more challenging, more interesting, and more time-consuming.

General Observations

Algebraic data types have been the hero of the past set of puzzles. For example, to solve Day 15 I relied heavily on the function with signature

fn find_col(sensors: &Vec<Sensor>, row: i64, min: i64, max: i64) -> Option<i64> {
// ...
}

including unpacking it in a kind of iterative function with

for row in min..=max {
    match find_col(sensors, row, min, max) {
        Some(x) => return x * 4000000 + row,
        None => {},
    }
}

Probably the king of algebraic data type puzzles, though, was Day 13. This had us parsing nested sequences like

[[1],[2,[3,4],5]],6]

and comparing them. In a strongly typed language, there’s really only one way to handle this, which is with a kind of recursive type:

enum NestedList {
    Number(usize),
    List(Vec<NestedList>),
}

Solving the puzzle involved a lot of recursion, which is fine. It did raise a philosophical question: if my goal is to learn these languages, is it better for me to do this parsing by hand (as the puzzle presumably intends) or should I use a library that does it for me? The argument for using a library (like serde/serde_json for Rust) is that these types of text parsing problems are quite common in practice, and so practical knowledge of Rust must include knowledge of these parsing libraries. On the other hand, I’d be losing out on the hands-on experience with this kind of recursive typing if I let a crate do all the heavy lifting for me. I ended up dong it by hand in Rust, then getting annoyed and giving up in Haskell.

Rust Reflections

I’m still not 100% sold on all of Rust’s promises. Typing

my_vector.iter().map(|x| ...).collect()

several times per program has me wondering at the necessity of the .iter() and .collect(). Also, why does the compiler have such a hard time inferring types from these kinds of expressions? It can infer the type of the function in the map, and it knows the type in the iterable already, and it knows I’m starting with a vector… shouldn’t it be obvious? Like, if I have a function

fn my_func(a: A) -> B

and a vector my_vector: Vec<A>, then surely

my_vector.iter().map(|x| my_func(x)).collect()

is Vec<B>. Not to pile on the hate, but why can’t I just do

my_vector.iter().map(my_func).collect()

The analogous code in Haskell is literally

map myFunc myVec

Haskell Reflections

If it’s not clear by now, I really enjoy the succinctness of programming in Haskell. My solutions are often half the length of their Rust counterparts, and I’ve even stopped making deliberately obtuse one-line functions! My greatest Haskell triumph so far is my solution to Day 12, which was a graph search. I’ve seen it often expressed that Haskell is not a great language for BFS, but behold the following code.

pathLength :: Map.Map (Int, Int) (Int, Int) -> (Int, Int) -> (Int, Int) -> Int
pathLength parents start end
    | end == start = 0
    | otherwise = 1 + pathLength parents start (parents Map.! end)

bfs :: [String] -> (Int, Int) -> (Int, Int) -> [(Int, Int)] -> Map.Map (Int, Int) Bool -> Map.Map (Int, Int) (Int, Int) -> Maybe Int
bfs graph start end [] seen parents = Nothing
bfs graph start end (q:queue) seen parents
    | q == end = Just (pathLength parents start end)
    | otherwise = bfs graph start end (queue ++ z) (Map.union seen (Map.fromList [(z', True) | z' <- z])) (Map.union (Map.fromList [(z', q) | z' <- z]) parents)
    where z = filter (\x -> not $ x `Map.member` seen) (validNeighbors graph q)

BFS in 5 lines, and the path length calculation in just 3 more! More amazing still is the fact that I wrote this code as is and it compiled and executed flawlessly on my first try. It would be even simpler if I’d bothered to use a hashset instead of a hashmap for holding visited nodes. Actually, the validNeighbors function is the longest bit of code in the entire program:

validNeighbors :: [String] -> (Int, Int) -> [(Int, Int)]
validNeighbors graph (x, y) = filter (\(x', y') -> elevation (graph !! x !! y) >= elevation (graph !! x' !! y') - 1)[(x', y') |
   x' <- [x - 1 .. x + 1],
   0 <= x', x' < length graph,
   y' <- [y - 1 .. y + 1],
   0 <= y', y' < length (head graph),
   x' == x || y' == y, (x', y') /= (x, y)]

Is it all good with Haskell? Alas, no. In addition to multiple annoyances related to iterating through lists, I had a spectacular failure on Day 14. Ultimately, my code ran and got the right answer, but it took nearly a minute (i.e., nearly a minute longer than my Rust code took). I don’t know for sure what the problem is, but my best guess is that it has something to do with lazy evaluation and tail recursion. There are some known self-owns in Haskell, like the foldl function, which causes massive memory overflows because the program ends up storing a ton of unevaluated expressions. Probably something like that is happening in my Day 14 code, but I’m not sure where.

All my solutions can be found in my github repo