AoC has ended for the year! Congrats to everyone who participated

Here are some stats from the instance leaderboard

Top 10 Users

1. SekoiaTree
2. Leo Uino
3. Michon van Dooren
4. funnyboy-roks
5. PhiliPdB
6. jhuang97
7. Alex Utter
8. hades
9. Jindřich Ivánek
10. abclop99

Misc Stats

• 91 Users got at least 1 star
• 14 Users got 50 stars

Day 22: Sand

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

• What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
• Where do I participate?: https://adventofcode.com/
• Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465

Day 20: Pulse

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

• What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
• Where do I participate?: https://adventofcode.com/
• Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465

Day 19: Aplenty

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

• What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
• Where do I participate?: https://adventofcode.com/
• Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465

Day 18: Lavaduct Lagoon

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

• What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
• Where do I participate?: https://adventofcode.com/
• Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465

Day 17: Clumsy Crucible

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

• What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
• Where do I participate?: https://adventofcode.com/
• Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465

Day 16: The Floor Will Be Lava

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

• What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
• Where do I participate?: https://adventofcode.com/
• Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465

Day 15: Lens Library

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)
• Code block support is not fully rolled out yet but likely will be in the middle of the event. Try to share solutions as both code blocks and using something such as https://topaz.github.io/paste/ , pastebin, or github (code blocks to future proof it for when 0.19 comes out and since code blocks currently function in some apps and some instances as well if they are running a 0.19 beta)

FAQ

• What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
• Where do I participate?: https://adventofcode.com/
• Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465

🔒 Thread is locked until there's at least 100 2 star entries on the global leaderboard

Edit: 🔓 Unlocked

Day 14: Parabolic Reflector Dish

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)
• Code block support is not fully rolled out yet but likely will be in the middle of the event. Try to share solutions as both code blocks and using something such as https://topaz.github.io/paste/ , pastebin, or github (code blocks to future proof it for when 0.19 comes out and since code blocks currently function in some apps and some instances as well if they are running a 0.19 beta)

FAQ

• What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
• Where do I participate?: https://adventofcode.com/
• Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465

🔒 Thread is locked until there's at least 100 2 star entries on the global leaderboard

Edit: 🔓 Unlocked

Day 13: Point of Incidence

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)
• Code block support is not fully rolled out yet but likely will be in the middle of the event. Try to share solutions as both code blocks and using something such as https://topaz.github.io/paste/ , pastebin, or github (code blocks to future proof it for when 0.19 comes out and since code blocks currently function in some apps and some instances as well if they are running a 0.19 beta)

FAQ

• What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
• Where do I participate?: https://adventofcode.com/
• Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465

🔒 Thread is locked until there's at least 100 2 star entries on the global leaderboard

🔓 Unlocked

So I managed to get part 1 of the day, but it took 2 seconds to run on the real input, which is a bad sign.

I can't see any kind of optimisation that means I can skip checks and know how many combinations are in those skipped checks (aside from 0.) I can bail out of branches of combinations if the info so far won't fit, but that still leads me to visiting every valid combination which in one of the examples is 500k. (And probably way more in the input, since if I can't complete the example near instantly the input is not happening.)

Right now I take the string, then replace the first instance of a ? with the two possible options. Check it matches the check digits so far then use recursion on those two strings.

I can try to optimise the matching, but I don't think that solves the real problem of visiting every combination.

I don't think (or hope) it's just bad code but this is my code so far (python.)

edit:

Day 12: Hot Springs

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)
• Code block support is not fully rolled out yet but likely will be in the middle of the event. Try to share solutions as both code blocks and using something such as https://topaz.github.io/paste/ , pastebin, or github (code blocks to future proof it for when 0.19 comes out and since code blocks currently function in some apps and some instances as well if they are running a 0.19 beta)

FAQ

• What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
• Where do I participate?: https://adventofcode.com/
• Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465

🔒 Thread is locked until there's at least 100 2 star entries on the global leaderboard

🔓 Unlocked after 25 mins

Day 11: Cosmic Expansion

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)
• Code block support is not fully rolled out yet but likely will be in the middle of the event. Try to share solutions as both code blocks and using something such as https://topaz.github.io/paste/ , pastebin, or github (code blocks to future proof it for when 0.19 comes out and since code blocks currently function in some apps and some instances as well if they are running a 0.19 beta)

FAQ

• What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
• Where do I participate?: https://adventofcode.com/
• Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465

🔒 Thread is locked until there's at least 100 2 star entries on the global leaderboard

🔓 Unlocked after 9 mins

Day 10: Pipe Maze

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)
• Code block support is not fully rolled out yet but likely will be in the middle of the event. Try to share solutions as both code blocks and using something such as https://topaz.github.io/paste/ , pastebin, or github (code blocks to future proof it for when 0.19 comes out and since code blocks currently function in some apps and some instances as well if they are running a 0.19 beta)

FAQ

• What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
• Where do I participate?: https://adventofcode.com/
• Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465

🔒 Thread is locked until there's at least 100 2 star entries on the global leaderboard

🔓 Unlocked after 40 mins

Day 9: Mirage Maintenance

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)
• Code block support is not fully rolled out yet but likely will be in the middle of the event. Try to share solutions as both code blocks and using something such as https://topaz.github.io/paste/ , pastebin, or github (code blocks to future proof it for when 0.19 comes out and since code blocks currently function in some apps and some instances as well if they are running a 0.19 beta)

FAQ

• What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
• Where do I participate?: https://adventofcode.com/
• Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465

🔒 Thread is locked until there's at least 100 2 star entries on the global leaderboard

🔓 Unlocked after 5 mins

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!()
}

Day 8: Haunted Wasteland

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)
• Code block support is not fully rolled out yet but likely will be in the middle of the event. Try to share solutions as both code blocks and using something such as https://topaz.github.io/paste/ , pastebin, or github (code blocks to future proof it for when 0.19 comes out and since code blocks currently function in some apps and some instances as well if they are running a 0.19 beta)

FAQ

• What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
• Where do I participate?: https://adventofcode.com/
• Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465

Day 7: Camel Cards

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)
• Code block support is not fully rolled out yet but likely will be in the middle of the event. Try to share solutions as both code blocks and using something such as https://topaz.github.io/paste/ , pastebin, or github (code blocks to future proof it for when 0.19 comes out and since code blocks currently function in some apps and some instances as well if they are running a 0.19 beta)

FAQ

• What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
• Where do I participate?: https://adventofcode.com/
• Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465

🔒 Thread is locked until there's at least 100 2 star entries on the global leaderboard

🔓 Thread has been unlocked after around 20 mins

Survey by u/jeroenheijmans Closes Dec 22

Day 6: Wait for 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)
• Code block support is not fully rolled out yet but likely will be in the middle of the event. Try to share solutions as both code blocks and using something such as https://topaz.github.io/paste/ , pastebin, or github (code blocks to future proof it for when 0.19 comes out and since code blocks currently function in some apps and some instances as well if they are running a 0.19 beta)

FAQ

• What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
• Where do I participate?: https://adventofcode.com/
• Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465