Advent of Code 2022 - Day 25

By Eric Burden | December 29, 2022

It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Rust. I’ll post my solutions and code to GitHub as well. After finishing last year (and 2015-2019) in Julia, I needed to spend some time with Rust again! If you haven’t given AoC a try, I S encourage you to do so along with me!

Day 25 - Full of Hot Air

Find the problem description HERE.

The Input - CABFuN: Clever Acronym for Base-Five Numbers

One of the most straightforward parsing days of the year! I though I might need to break out nom one more time, but no such luck. Given that a SNAFU number is a series of “numerals” (characters), it makes sense to represent them as Strings.

/// This represents one of our SNAFU numbers, which is just a String
/// in a Wrapper so we can have custom `From` implementations.
#[derive(Debug, Clone)]
struct Snafu(String);

/// Converting a line from the input into a Snafu is super complicated.
impl From<&str> for Snafu {
    fn from(line: &str) -> Self {
        Snafu(line.to_string())
    }
}

const INPUT: &str = include_str!("../../input/25/input.txt");

/// Parse that input!
 fn read() -> Vec<Snafu> {
    INPUT.lines().map(Snafu::from).collect::<Vec<_>>()
}

Mighty parsing indeed!

Part One - Great, Now There’s Another Standard

Come on, Bob! Aw, don’t look at me that way… I can’t stay mad at you! Besides, it’s not Bob’s fault that the manufacturer decided to invent their own numbering system. Not cool, manufacturer, not cool. Speaking of cool, we really need to add up these SNAFU numbers so we can calculate how much fuel each balloon with take so we can warm up that fuel and beat it!

/// Solve Day 25, Part 1
pub fn solve(input: &[Snafu]) -> String {
    let fuel_cost: i128 = input.iter().cloned().map(i128::from).sum();
    let snafu_cost = Snafu::from(fuel_cost);
    snafu_cost.0
}

/// Unit conversion from a SNAFU number to a base-10 integer. This is a pretty
/// common algorithm for converting base-whatever to decimal.
impl From<Snafu> for i128 {
    fn from(snafu: Snafu) -> Self {
        let mut total = 0;
        for (pow, glyph) in snafu.0.chars().rev().enumerate() {
            let mult = match glyph {
                '2' => 2,
                '1' => 1,
                '0' => 0,
                '-' => -1,
                '=' => -2,
                _ => unreachable!(),
            };
            total += 5i128.pow(pow as u32) * mult;
        }
        total
    }
}

/// Unit conversion from a decimal integer into a SNAFU number. This is a much
/// less common (to me) operation. The tricky bit is handling the fact that we have 
/// digits whose value is centered around zero instead of anchored at zero on the
/// least significant place. For a normal base-5 conversion, I'd take the result 
/// of the remainder % 5, then divide by 5 for each digit until no remainder was
/// left. Apparently, adding two each round lets us shift the digits. I'm not
/// 100% sure why this works, but it works. Math, amirite? This solution was inspired
/// by Google searches about "balanced ternary" number systems.
impl From<i128> for Snafu {
    fn from(number: i128) -> Self {
        let mut remainder = number;
        let mut out = String::default();
        while remainder > 0 {
            let glyph = match remainder % 5 {
                0 => '0',
                1 => '1',
                2 => '2',
                3 => '=',
                4 => '-',
                _ => unreachable!(),
            };
            out.push(glyph);
            remainder += 2;  // This works for some reason.
            remainder /= 5;
        }
        Snafu(out.chars().rev().collect::<String>())
    }
}

Part Two - Auld Lang Syne

If you haven’t heard, Day 25 - Part Two is always the “go back and finish the rest of the puzzles” challenge, so no extra coding needed here. Instead, I’d like to use this space to reflect on the Advent of Code puzzles for this year and my experience with them.

This is my third year with Advent of Code, and as I set in reflection over this year’s event, the thing that stands out to me the most is how big an impact AoC has as a community event. Don’t get me wrong, I love a good puzzle, I really enjoy coding puzzles, and I’m happy to set time aside put my head down to work on something fun and interesting all by myself. Thing is, though, there’s something about knowing that other people are working, thinking, struggling, solving, succeeding, failing, and re-starting at the same time as you that’s really invigorating. For one thing, outside of actual work projects or groups that are heavily invested in an open source project, it’s a rare thing to have people from all over who can look at your code and already be read in on exactly what you’re trying to accomplish. It’s like the world’s biggest code review! I’ve been really encouraged by engaging with the community on r/adventofcode and the #AdventOfCode hashtag on Mastodon. There are so many people doing so many interesting things, and it’s nice to see them all engaged in the same thing at the same time!

I’ve definitely gotten more engagement this year with the blog, which is encouraging for me as well. I get a lot of satisfaction out of helping others, and if I can do that while over-explaining a bit of code, so much the better! Honestly, writing this blog series is the biggest reason I’m able to finish all the days. Knowing that if I quit somebody is going to notice really helps keep me going. I don’t really imagine anyone is actually counting on me to finish all the days, but doing it in public really is a good approach for anything you really do want to finish. Speaking of finishing things, I went back and earned the rest of those stars this past year! I didn’t blog about them, because that would be a lot and probably not that interesting this long after they were posted, but I’m officially a member of the 400 star club! I solved years 2015 - 2019 in Julia, which I’d heartily recommend to anyone who’s considering learning that language. I know a lot of folks lean on Python for Advent of Code (and other puzzles), but I never found Julia to lack any convenience or ergonomics. In fact, the much better lambda syntax and rich standard library (including multi-dimensional arrays) really provide a powerful toolbox for problem-solving. You can check out the code yourself if you’d like here.

Of course, all that Julia meant that I was itching to try something else this year. I used the 2020 puzzles to learn Rust after the fact, initially solving them in R, and I’ve practiced a bit with Rust since then, primarily using it to implement functionality that I could call from R because trying to use C or C++ interop for someone who doesn’t know either language was a truly frustrating experience. I had hoped that, given my experience with Advent of Code and my budding familiarity with Rust, that I’d be able to finish all 25 days in Rust first this year, and I’m really proud of myself that I did. Not only that, I used Advent of Code to learn the nom parser combinator crate. While I struggled a bit with it in the early days, some of the later days really benefited from that style of parsing and eventually it felt like nom made approaching the solutions a bit easier, which is exactly what I was hoping for. A few other notable crates made appearances, such as rayon and itertools, but nom was definitely the most widely used. I also spent some time ahead of December 1st preparing my project setup, and I’d have to say that’s my #1 Advent of Code tip for anyone who plans to solve all the puzzles. If you’re not sure how, copy someone else’s. Just the amount of time and energy you save by not needing to think about how to structure your project each day, especially when you’re using a language as relatively strict as Rust, definitely makes it worth it. I knew when I started tackling the old years in Julia that I was going to want at least some templating for each day/year and a consistent way to run tests and benchmarks, and I basically just copied that idea into my Rust setup this year. There are definitely improvements I’d make, but having something is a lot better than nothing.

Just like last year, I’d like to send out a huge thank you to Eric Wastl and his crew of helpers for putting this event/phenomenon on and keeping it running. If you can, please consider donating to this effort to help keep the magic going, I guarantee there will be a lot of coders who will be glad you did.

If you’re interested, you can find all the code from this blog series on GitHub, please feel free to submit a pull request if you’re really bored. Happy Holidays!

comments powered by Disqus