Advent of Code 2022 Days 6-10 in Rust and Haskell

The elves are on their expedition. They’re building tree houses and tossing people into rivers. A computer was involved somehow. We approached this with both Rust and Haskell.

General Observations

• Each challenge has two components, but both use the same input. This means you have some opportunity to write your code very flexibly for the first component and have a realistic hope of reusing it for the second.
• I’m always doing the Haskell after the Rust, which makes the Haskell coding very fast. I know exactly what I need to do and I don’t need to worry about what might happen in the second component.

Rust Reflections

The borrow checker really ruined my day once during this set. Day 7 involved modeling a file system directory tree, and it turns out trees are super annoying to implement in Rust. For example, you might try to do something like this:

struct TreeNode {
  data: i32,
  children: Vec<&TreeNode>, // Will not compile!
  parent: &TreeNode,
}

struct Tree {
  nodes: Vec<&TreeNode>,
}

Already there’s an issue: Rust says it has no idea how big a TreeNode is, and therefore doesn’t know how to allocate memory for it. Ok, so you have to use something like Box or Rc. No big deal, right? Well, you also can’t do stuff like

fn add_node(parent: &mut TreeNode, data: i32) {
  let new_child = TreeNode { data: data, children: vec![], parent: &parent };
  parent.children.push(&new_child);
} // new_child goes out of scope

because the new_child data goes away at the end of the function. Again, you can fix this with tricky implementations with Rc or whatever. Anyway, I ended up choosing a completely different method of representing a tree in Rust, which also happens to work well in Haskell. The idea is that the children field in the TreeNode only keeps track of some indicies for its children. The Tree keeps track of the association between index and node. Something like this:

struct TreeNode {
  data: i32,
  children: Vec<i32>,
  parent: i32,
  id: i32,
}

struct Tree {
  nodes: Vec<TreeNode>,
}

Now adding a node involves pushing it onto the Tree.nodes field and updating its parent by pushing its id into the parent’s children vector. I used the index of the node in the nodes vector as its index to easily keep track of them. Here’s what I ended up implementing.

struct DirectoryNode {
    name: String,
    parent: Option<usize>,
    children: Option<Vec<usize>>,
    files: Option<Vec<usize>>,
    id: usize,
}

impl DirectoryNode {
    fn size(&self) -> usize {
        match &self.files {
            None => 0,
            Some(x) => x.iter().sum(),
        }
    }
}

struct FileTree {
    cwd: usize,
    nodes: Vec<DirectoryNode>,
}

impl FileTree {
    fn new_child(&mut self, parent: usize, child_name: String) {
        let new_idx = self.nodes.len();
        self.nodes.push(DirectoryNode {
            name: child_name,
            parent: Some(parent),
            children: None,
            files: None,
            id: new_idx,
        });

        match self.nodes[self.cwd].children {
            Some(ref mut y) => y.push(new_idx),
            None => self.nodes[self.cwd].children = Some(vec![new_idx]),
        };
    }
}

Because the tree owns all the nodes, there’s no issue with bad references or reference lifetimes. Obtaining a node is as easy as tree.nodes[index]. The only real modification here is that because of the parameters of the problem, I never had to update a node that wasn’t the current working directory, so I kept the index of the cwd as a data field in the tree.

Haskell Reflections

I have given up writing Haskell one-liners. The last one was the glorious Day 6 solution:

module Main where
import Data.List( nub )

main :: IO ()
main = do
    rawData <- readFile "input.txt"
    let n = 14
    print $ head (filter (\y -> nub (take n (drop y rawData)) == take n (drop y rawData)) [1..length rawData - n]) + n

Ok, not technically one line, but you can see pretty easily how to make it one line.

For reasons related to time and lack thereof, I haven’t done all of the recent challenges in Haskell. I am still enjoying it when I do use it, but I am starting to have complaints about the tooling surrounding Haskell. For example, there’s two package managers: stack and cabal.

I have cabal installed, so that’s what I’ve been using, but it’s causing its own set of issues. In order to add a dependency to a project, you need to update the .cabal file. This is already annoying. I’d prefer if I could do cabal add <package name> or something and have it do that work for me. But whatever. Then once the project has the dependency added, the rest of the tooling, like the linter, seems to break. I then have to restart VS Code, sometimes more than once, to get everything going again.

For this reason I’ve found it easier to just globally install the packages I need, which is not a great practice, but I feel forced into it. Also, surely tools like HashMap should be part of the base Haskell installation. So maybe it’s not terrible that I’ve added them globally.

All my solutions can be found in my github repo