this post was submitted on 08 Dec 2023
5 points (100.0% liked)

Advent Of Code

770 readers
1 users here now

An unofficial home for the advent of code community on programming.dev!

Advent of Code is an annual Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like.

AoC 2023

Solution Threads

M T W T F S S
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

Rules/Guidelines

Relevant Communities

Relevant Links

Credits

Icon base by Lorc under CC BY 3.0 with modifications to add a gradient

console.log('Hello World')

founded 1 year ago
MODERATORS
 

I had 6 parallel paths, and for all of them, the goal node was found at the point where the directions string repeated. So I actually only had to search each of the paths for the point where I was on the goal position and the first direction. This worked on the input data, but not the example. See the assert in the code, and note that the statement println!("Found non-repeat at {node} step {step} (num dirs {num_directions})"); is never executed.

At the end there's also the first attempt of brute-forcing the solution which seems like it would have taken nearly forever.

use std::collections::HashMap;

use regex::Regex;

use crate::input::Source;

pub fn execute(source: Source) -> impl std::fmt::Debug {
    let lines = source.lines();
    let ([directions], [empty, nodes @ ..]) = lines.split_at(1) else {
        panic!("Wrong format");
    };
    assert!(empty.is_empty());

    let node_re = Regex::new(r"(...) = \((...), (...)\)").unwrap();
    let nodes: HashMap = nodes
        .iter()
        .map(|line| {
            let caps = node_re.captures(line).unwrap();
            let name = caps[1].to_string();
            let left = caps[2].to_string();
            let right = caps[3].to_string();
            (name, (left, right))
        })
        .collect();

    let start_nodes: Vec = nodes.keys().filter(|n| n.ends_with('A')).cloned().collect();
    let repeat_lengths: Vec = start_nodes
        .iter()
        .map(|node| {
            let (repeat_length, goal_steps) = find_repeats(node, directions, &nodes);
            assert!(goal_steps.is_empty()); // not a given, but that's what the input looks like
            dbg!(node, repeat_length, goal_steps);
            repeat_length
        })
        .collect();

    repeat_lengths.iter().cloned().reduce(num::integer::lcm)
}

/// (repeat length, steps to goal node within repeat)
fn find_repeats(
    starting_node: &str,
    directions: &str,
    nodes: &HashMap,
) -> (usize, Vec) {
    let mut node = starting_node.to_string();
    let num_directions = directions.chars().count();
    let mut goals = Vec::new();
    for (step, dir) in directions.chars().cycle().enumerate() {
        if node.ends_with('Z') {
            if step % num_directions == 0 {
                println!("Found repeat at {node} step {step} (num dirs {num_directions})");
                return (step, goals);
            }
            println!("Found non-repeat at {node} step {step} (num dirs {num_directions})");
            goals.push(step);
        }
        let (left, right) = &nodes[&node];
        node = match dir {
            'L' => left.clone(),
            'R' => right.clone(),
            other => panic!("Unknown dir {other}"),
        }
    }
    unreachable!()
}

// too slow
#[allow(dead_code)]
fn find_parallel(
    start_nodes: &[String],
    directions: &str,
    nodes: &HashMap,
) -> usize {
    let mut current_nodes = start_nodes.to_vec();
    for (step, dir) in directions.chars().cycle().enumerate() {
        if current_nodes.iter().all(|n| n.ends_with('Z')) {
            return step;
        }
        for node in current_nodes.iter_mut() {
            let (left, right) = nodes[node].clone();
            *node = match dir {
                'L' => left,
                'R' => right,
                other => panic!("Unknown dir {other}"),
            }
        }
    }
    unreachable!()
}
you are viewing a single comment's thread
view the rest of the comments
[–] SpeakinTelnet 4 points 11 months ago

On one side I'm really sad it was so because I felt ready to deal with advanced math and started to program around an offset. On the other side I'm damn grateful it was this way because I was far from as ready as I felt.