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
126
127
128
129
|
use itertools::Itertools;
use regex::Regex;
use std::fmt;
struct Operator {
name: char,
f: Box<dyn Fn(u64, u64) -> u64>,
}
impl fmt::Display for Operator {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{}", self.name)
}
}
#[allow(dead_code)]
fn op_chain_to_string(chain: &Vec<&Operator>) -> String {
format!("[{}]", chain.iter().map(|o| o.to_string()).join(", "))
}
#[derive(Debug)]
struct Equation {
result: u64,
values: Vec<u64>,
}
impl Equation {
fn parse(s: &str) -> Self {
let re = Regex::new("^([0-9]+): ((?:[0-9]+ ?)+)$").unwrap();
let caps = re.captures(s).unwrap();
let (_full, [result, values]) = caps.extract();
Equation {
result: result.parse().unwrap(),
values: values.split(' ').map(|n| n.parse().unwrap()).collect(),
}
}
fn is_solution(&self, chain: &Vec<&Operator>) -> bool {
let mut chain_it = chain.iter();
let mut self_it = self.values.iter();
let mut acc: u64 = *self_it.next().unwrap();
for value in self_it {
let Some(op) = chain_it.next() else {
panic!("Impossible")
};
acc = (op.f)(acc, *value);
if acc > self.result {
return false;
}
}
// // TODO why does this not work?
// self.values.iter()
// .reduce(|v1, v2| {
// let Some(op) = chain_it.next() else { panic!("Impossible") };
// (op.f)(v1, v2)
// });
acc == self.result
}
fn find_solution<'a>(&self, ops: &'a [Operator]) -> Option<Vec<&'a Operator>> {
// println!("Finding solution for {self:?}...");
let op_chains = itertools::repeat_n(ops, self.values.len() - 1).multi_cartesian_product();
for chain in op_chains {
// print!(" Trying chain {}... ", op_chain_to_string(&chain));
if self.is_solution(&chain) {
// println!("YES!");
return Some(chain.clone());
}
// println!("nope");
}
None
}
fn has_solution(&self, ops: &[Operator]) -> bool {
self.find_solution(ops).is_some()
}
}
fn sum_solutions(input: &str, ops: &[Operator]) -> u64 {
let equations: Vec<Equation> = input.lines().map(|l| Equation::parse(l)).collect();
// println!("Equations: {equations:?}");
equations
.iter()
.filter(|e| e.has_solution(&ops))
.map(|e| e.result)
.sum()
}
fn p1(input: &str) -> String {
let ops: [Operator; 2] = [
Operator {
name: '+',
f: Box::new(|x, y| x + y),
},
Operator {
name: '*',
f: Box::new(|x, y| x * y),
},
];
sum_solutions(input, &ops).to_string()
}
fn p2(input: &str) -> String {
let ops: [Operator; 3] = [
Operator {
name: '+',
f: Box::new(|x, y| x + y),
},
Operator {
name: '*',
f: Box::new(|x, y| x * y),
},
Operator {
name: '|',
f: Box::new(|x, y| {
format!("{}{}", x.to_string(), y.to_string())
.parse()
.unwrap()
}),
},
];
sum_solutions(input, &ops).to_string()
}
fn main() {
aoc2024::run_day("7", p1, p2);
}
|
