Marketing Pitch and Impressions#

Rust

A language empowering everyone to build reliable and efficient software.

— rust-lang.org

A somewhat understated soundbite briefly covering Rust’s impact on the software industry.

Rust is currently a highly favored systems programming language, a position it has earned to a significant degree. In my view, its significant popularity can sometimes lead to its selection in scenarios where other languages might be a more productive choice. Perhaps similar but orthogonal to the position that Python enjoys.

Visual Studio Code support for Rust is great. I hear RustRover from JetBrains is excellent, but I have not used it.

The Code#

Not my favourite solution this year. Usually I try to make solutions stand-alone using only standard libraries for whatever language I’m using. Unfortunately that did not happen for this problem.

For part 1 I used BFS to find the solution while I was still labouring under the misapprehension that I would be able to solve the problem without using external libraries. It’s not efficient, but Rust’s execution speed does a great job of wallpapering over the algorithmic issues. Part 1 is a search over GF(2) for the number of button presses, so the search space is limited.

For part 2 it was pretty obvious that the search space is now many orders of magnitude larger and BFS wasn’t going to work. Considering how much time I believed it would take me to write a solver (plus resolve any quirks with under/over-constrained problems and non-integer solutions in the set) compared to how much time I had before my workday started, I basically caved, and started looking for a Rust ILP solver.

It turns out that if you type “Rust ILP solver” into Google, the first solver that comes up is good_lp. I just went with the microlp feature as it looked good enough and did not require any additional dependencies.

For the solver problem, we have integer $X_i, X_i \ge 0$ representing the number of button presses for each button. We want to minimise $\sum{X_i}$. Next we add the constraints for joltage summing to the number of button presses.

Fortunately, the following day u/tenthmascot posted a great solution on Reddit that I have implemented in Day 10 Redux— Kotlin. The implemented solution meets my self-imposed and completely arbitrary requirements for being both stand-alone and fewer than 100 lines long!

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100

use std::collections::{HashSet, VecDeque};
use good_lp::{
    constraint, default_solver, variable,
    variables, Expression, Solution, SolverModel
};

#[derive(Debug, Clone)]
struct Machine {
    indicators: HashSet<usize>,
    buttons: Vec<HashSet<usize>>,
    joltage: Vec<i32>,
}

fn solve_machine1(
    indicators: &HashSet<usize>,
    buttons: &[HashSet<usize>]
) -> usize {
    let mut queue = VecDeque::from([(HashSet::new(), 0)]);
    let mut seen: HashSet<Vec<usize>> = HashSet::from([vec![]]);

    while let Some((curr, steps)) = queue.pop_front() {
        if curr == *indicators {
            return steps;
        }

        for button in buttons {
            let new_state: HashSet<_> = curr.symmetric_difference(button)
                .copied().collect();
            let mut new_vec: Vec<_> = new_state.iter().copied().collect();
            new_vec.sort_unstable();

            if seen.insert(new_vec.clone()) {
                queue.push_back((new_state, steps + 1));
            }
        }
    }
    0
}

fn solve_machine2(joltage: &[i32], buttons: &[HashSet<usize>]) -> f64 {
    let mut vars = variables!();
    let x: Vec<_> = (0..buttons.len())
        .map(|i| vars.add(variable().min(0).integer().name(format!("x_{i}"))))
        .collect();

    let mut problem = vars.minimise(
        x.iter().copied().map(Expression::from).sum::<Expression>()
    ).using(default_solver);

    for (i, &target) in joltage.iter().enumerate() {
        let sum: Expression = buttons.iter().zip(&x)
            .filter(|(b, _)| b.contains(&i))
            .map(|(_, &var)| Expression::from(var))
            .sum();
        problem = problem.with(constraint!(sum == target));
    }

    problem.solve().map_or(f64::INFINITY, |sol| x.iter().map(|&v| sol.value(v))
        .sum())
}

fn parse_machines(input: &str) -> Vec<Machine> {
    input.lines().map(|line| {
        let parts: Vec<_> = line.split_whitespace().collect();

        let indicators = parts[0].trim_matches(|c| c == '[' || c == ']')
            .chars().enumerate()
            .filter_map(|(i, c)| (c == '#').then_some(i))
            .collect();

        let buttons = parts[1..parts.len() - 1].iter()
            .map(|s|
                s.trim_matches(|c| c == '(' || c == ')').split(',').map(|n|
                    n.parse().unwrap()
                ).collect()
            ).collect();

        let joltage = parts.last().unwrap()
            .trim_matches(|c| c == '{' || c == '}')
            .split(',').map(|n| n.parse().unwrap()).collect();

        Machine { indicators, buttons, joltage }
    }).collect()
}

fn main() {
    let input = std::fs::read_to_string("../y25d10.txt")
        .expect("Failed to read file");
    let machines = parse_machines(&input);

    let result1: usize = machines.iter().map(|m|
        solve_machine1(&m.indicators, &m.buttons)
    ).sum();
    println!("Result1: {result1}");

    let result2: f64 = machines.iter().map(|m|
        solve_machine2(&m.joltage, &m.buttons)
    ).sum();
    println!("Result2: {result2}");
}

Install Rust and run#

The recommended way to install Rust is via rustup, but your package manager probably has installable packages.

# I installed from Homebrew
brew install rust

# rust-lang.org recommends using rustup
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

# Execute the code
cd d10 && cargo run