Day 10: Hoof It

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

  • Gobbel2000@programming.dev
    2·
    12 days ago

    Rust

    This was a nice one. Basically 9 rounds of Breadth-First-Search, which could be neatly expressed using fold. The only difference between part 1 and part 2 turned out to be the datastructure for the search frontier: The HashSet in part 1 unifies paths as they join back to the same node, the Vec in part 2 keeps all paths separate.

    Solution 
    use std::collections::HashSet;

fn parse(input: &str) -> Vec<&[u8]> {
    input.lines().map(|l| l.as_bytes()).collect()
}

fn adj(grid: &[&[u8]], (x, y): (usize, usize)) -> Vec<(usize, usize)> {
    let n = grid[y][x];
    let mut adj = Vec::with_capacity(4);
    if x > 0 && grid[y][x - 1] == n + 1 {
        adj.push((x - 1, y))
    }
    if y > 0 && grid[y - 1][x] == n + 1 {
        adj.push((x, y - 1))
    }
    if x + 1 < grid[0].len() && grid[y][x + 1] == n + 1 {
        adj.push((x + 1, y))
    }
    if y + 1 < grid.len() && grid[y + 1][x] == n + 1 {
        adj.push((x, y + 1))
    }
    adj
}

fn solve(input: String, trailhead: fn(&[&[u8]], (usize, usize)) -> u32) -> u32 {
    let grid = parse(&input);
    let mut sum = 0;
    for (y, row) in grid.iter().enumerate() {
        for (x, p) in row.iter().enumerate() {
            if *p == b'0' {
                sum += trailhead(&grid, (x, y));
            }
        }
    }
    sum
}

fn part1(input: String) {
    fn score(grid: &[&[u8]], start: (usize, usize)) -> u32 {
        (1..=9)
            .fold(HashSet::from([start]), |frontier, _| {
                frontier.iter().flat_map(|p| adj(grid, *p)).collect()
            })
            .len() as u32
    }
    println!("{}", solve(input, score))
}

fn part2(input: String) {
    fn rating(grid: &[&[u8]], start: (usize, usize)) -> u32 {
        (1..=9)
            .fold(vec![start], |frontier, _| {
                frontier.iter().flat_map(|p| adj(grid, *p)).collect()
            })
            .len() as u32
    }
    println!("{}", solve(input, rating))
}

util::aoc_main!();

    Also on github