-
Notifications
You must be signed in to change notification settings - Fork 0
/
08.rs
125 lines (96 loc) · 3.23 KB
/
08.rs
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#![feature(test)]
use std::collections::HashMap;
use nom::{
bytes::complete::tag,
character::complete::{alphanumeric1, anychar, newline},
combinator::map_res,
multi::{count, many1, separated_list0},
IResult,
};
use rayon::prelude::*;
advent_of_code_2023::solution!(8);
pub fn part_1(input: &str) -> Option<u64> {
let (input, (instructions, network)) = parse_input(input).unwrap();
assert_eq!(input, "");
Some(count_steps(&instructions, &network, "AAA", |n| n == "ZZZ"))
}
pub fn part_2(input: &str) -> Option<u64> {
let (input, (instructions, network)) = parse_input(input).unwrap();
assert_eq!(input, "");
let steps = network
.par_iter()
// Get all node ids (no method for getting keys in parallel)
.map(|(k, _)| k)
// Find all the starting node ids
.filter(|k| k.ends_with('A'))
// Find the individual path for each node
.map(|node| count_steps(&instructions, &network, node, |n| n.ends_with('Z')))
// Find the LCM of all the paths to find the total step count
.reduce(|| 1, num::integer::lcm);
Some(steps)
}
fn count_steps(
instructions: &InstructionList,
network: &Network,
starting_node: &str,
end_condition_predicate: fn(&str) -> bool,
) -> u64 {
let mut steps = 0;
let mut current_node = starting_node;
'outer: loop {
for instruction in instructions {
if end_condition_predicate(current_node) {
break 'outer;
}
let node = network.get(current_node).unwrap();
current_node =
match instruction {
Instruction::Left => node.0,
Instruction::Right => node.1,
};
steps += 1;
}
}
steps
}
// ================== TYPES ==================
#[derive(Debug)]
enum Instruction {
Left,
Right,
}
impl TryFrom<char> for Instruction {
type Error = ();
fn try_from(value: char) -> Result<Self, Self::Error> {
let instruction =
match value {
'L' => Self::Left,
'R' => Self::Right,
_ => return Err(()),
};
Ok(instruction)
}
}
type Node<'a> = (&'a str, (&'a str, &'a str));
type Network<'a> = HashMap<&'a str, (&'a str, &'a str)>;
type InstructionList = Vec<Instruction>;
// ================== PARSING ==================
fn parse_input(input: &str) -> IResult<&str, (InstructionList, Network)> {
let (input, instructions) = many1(parse_instruction)(input)?;
let (input, _) = count(newline, 2)(input)?;
let (input, nodes) = separated_list0(newline, parse_node)(input)?;
let network: HashMap<_, _> = nodes.into_iter().collect();
Ok((input, (instructions, network)))
}
fn parse_node(input: &str) -> IResult<&str, Node> {
let (input, node_id) = alphanumeric1(input)?;
let (input, _) = tag(" = (")(input)?;
let (input, left) = alphanumeric1(input)?;
let (input, _) = tag(", ")(input)?;
let (input, right) = alphanumeric1(input)?;
let (input, _) = tag(")")(input)?;
Ok((input, (node_id, (left, right))))
}
fn parse_instruction(input: &str) -> IResult<&str, Instruction> {
map_res(anychar, Instruction::try_from)(input)
}