- commit
- bd4fddf63a014f5046cba68ea17435ed392657c4
- parent
- c72b57251130d870803925ca2c5271f84d84e342
- Author
- Tobias Bengfort <tobias.bengfort@posteo.de>
- Date
- 2021-12-25 00:24
simplify
Diffstat
| M | 2021/24/part1.rs | 270 | ++++++++++++++++++++++++++++++++----------------------------- |
1 files changed, 141 insertions, 129 deletions
diff --git a/2021/24/part1.rs b/2021/24/part1.rs
@@ -3,11 +3,6 @@ use std::fs::File; 3 3 use std::io::BufRead; 4 4 use std::io::BufReader; 5 56 -1 fn s2c(s: &str) -> char {7 -1 assert_eq!(s.len(), 1);8 -1 return s.chars().next().unwrap();9 -1 }10 -111 6 #[derive(PartialEq, Debug, Copy, Clone)] 12 7 enum Token { 13 8 Add, @@ -15,8 +10,8 @@ enum Token { 15 10 Div, 16 11 Mod, 17 12 Eql,18 -1 Int(i16),19 -1 Var(char),-1 13 Int(i64), -1 14 Var(usize), 20 15 Input(u8), 21 16 } 22 17 @@ -60,9 +55,6 @@ fn print_formular(formular: &mut std::slice::Iter<'_, Token>) { 60 55 Some(Token::Int(i)) => { 61 56 print!("{}", i); 62 57 },63 -1 Some(Token::Var(c)) => {64 -1 print!("{}", c);65 -1 },66 58 Some(Token::Input(i)) => { 67 59 print!("in{}", i); 68 60 }, @@ -70,143 +62,163 @@ fn print_formular(formular: &mut std::slice::Iter<'_, Token>) { 70 62 } 71 63 } 72 6473 -1 fn optimize(input: Vec<Token>) -> Vec<Token> {74 -1 let mut stack = input;75 -1 let mut dirty = true;76 -1 while dirty {77 -1 let mut new = vec![];78 -1 dirty = false;79 -1 let mut i = 0;80 -1 while i < stack.len() - 2 {81 -1 match stack[i..i+3] {82 -1 [Token::Mul, Token::Var(_), Token::Int(0)] => {83 -1 new.push(Token::Int(0));84 -1 i += 2;85 -1 dirty = true;86 -1 },87 -1 [Token::Mul, Token::Int(0), Token::Var(_)] => {88 -1 new.push(Token::Int(0));89 -1 i += 2;90 -1 dirty = true;91 -1 },92 -1 [Token::Mul, Token::Int(1), Token::Var(b)] => {93 -1 new.push(Token::Var(b));94 -1 i += 2;95 -1 dirty = true;96 -1 },97 -1 [Token::Mul, Token::Var(a), Token::Int(1)] => {98 -1 new.push(Token::Var(a));99 -1 i += 2;100 -1 dirty = true;101 -1 },102 -1 [Token::Add, Token::Int(0), Token::Var(b)] => {103 -1 new.push(Token::Var(b));104 -1 i += 2;105 -1 dirty = true;106 -1 },107 -1 [Token::Add, Token::Var(a), Token::Int(0)] => {108 -1 new.push(Token::Var(a));109 -1 i += 2;110 -1 dirty = true;111 -1 },112 -1 [Token::Div, Token::Var(a), Token::Int(1)] => {113 -1 new.push(Token::Var(a));114 -1 i += 2;115 -1 dirty = true;116 -1 },117 -1 [Token::Add, Token::Int(a), Token::Int(b)] => {118 -1 new.push(Token::Int(a + b));119 -1 i += 2;120 -1 dirty = true;121 -1 },122 -1 [Token::Mul, Token::Int(a), Token::Int(b)] => {123 -1 new.push(Token::Int(a * b));124 -1 i += 2;125 -1 dirty = true;126 -1 },127 -1 [Token::Div, Token::Int(a), Token::Int(b)] => {128 -1 new.push(Token::Int(a / b));129 -1 i += 2;130 -1 dirty = true;131 -1 },132 -1 [Token::Mod, Token::Int(a), Token::Int(b)] => {133 -1 new.push(Token::Int(a % b));134 -1 i += 2;135 -1 dirty = true;136 -1 },137 -1 [Token::Eql, Token::Int(a), Token::Int(b)] => {138 -1 new.push(Token::Int(if a == b {1} else {0}));139 -1 i += 2;140 -1 dirty = true;141 -1 },142 -1 _ => new.push(stack[i]),143 -1 }144 -1 i += 1;145 -1 }146 -1 while i < stack.len() {147 -1 new.push(stack[i]);148 -1 i += 1;149 -1 }150 -1 stack = new;151 -1 }152 -1 return stack;153 -1 }154 -1155 -1 fn main() {-1 65 fn get_data() -> Vec<(Token, Token, Token)> { 156 66 let path = args().nth(1).unwrap(); 157 67 let file = File::open(path).unwrap(); 158 68 -1 69 let mut lines = vec![]; 159 70 let mut input = 0;160 -1 let mut stack = vec![Token::Var('z')];161 71162 -1 // FIXME: reverse163 -1 for (i, line) in BufReader::new(file).lines().enumerate() {-1 72 for line in BufReader::new(file).lines() { 164 73 let l = line.unwrap(); 165 74 166 75 match l.split(" ").collect::<Vec<&str>>()[..] { 167 76 ["inp", a] => {168 -1 let mut new = vec![];169 -1 for token in stack {170 -1 if token == Token::Var(s2c(a)) {171 -1 new.push(Token::Input(input));172 -1 } else {173 -1 new.push(token);174 -1 }175 -1 }176 -1 stack = new;-1 77 lines.push(( -1 78 Token::Input(input), -1 79 Token::Var(match a { -1 80 "z" => 0, -1 81 "y" => 1, -1 82 "x" => 2, -1 83 "w" => 3, -1 84 _ => unreachable!(), -1 85 }), -1 86 Token::Int(0), -1 87 )); 177 88 input += 1; 178 89 }, 179 90 [op, a, b] => {180 -1 let mut new = vec![];181 -1 for token in stack {182 -1 if token == Token::Var(s2c(a)) {183 -1 new.push(match op {184 -1 "add" => Token::Add,185 -1 "mul" => Token::Mul,186 -1 "div" => Token::Div,187 -1 "mod" => Token::Mod,188 -1 "eql" => Token::Eql,-1 91 lines.push(( -1 92 match op { -1 93 "add" => Token::Add, -1 94 "mul" => Token::Mul, -1 95 "div" => Token::Div, -1 96 "mod" => Token::Mod, -1 97 "eql" => Token::Eql, -1 98 _ => unreachable!(), -1 99 }, -1 100 Token::Var(match a { -1 101 "z" => 0, -1 102 "y" => 1, -1 103 "x" => 2, -1 104 "w" => 3, -1 105 _ => unreachable!(), -1 106 }), -1 107 match b.parse::<i64>() { -1 108 Ok(bi) => Token::Int(bi), -1 109 Err(_) => Token::Var(match b { -1 110 "z" => 0, -1 111 "y" => 1, -1 112 "x" => 2, -1 113 "w" => 3, 189 114 _ => unreachable!(),190 -1 });191 -1 new.push(Token::Var(s2c(a)));192 -1 new.push(match b.parse::<i16>() {193 -1 Ok(bi) => Token::Int(bi),194 -1 Err(_) => Token::Var(s2c(b)),195 -1 });196 -1 } else {197 -1 new.push(token);198 -1 }-1 115 }), -1 116 }, -1 117 )); -1 118 }, -1 119 _ => unreachable!(), -1 120 } -1 121 } -1 122 -1 123 return lines; -1 124 } -1 125 -1 126 fn foo(inputs: &[Option<i64>; 14], lines: &Vec<(Token, Token, Token)>) -> bool { -1 127 let mut mins = [0; 4]; -1 128 let mut maxs = [0; 4]; -1 129 -1 130 for line in lines.iter() { -1 131 match line { -1 132 (Token::Input(input), Token::Var(c), _) => { -1 133 match inputs[*input as usize] { -1 134 Some(value) => { -1 135 mins[*c] = value; -1 136 maxs[*c] = value; -1 137 }, -1 138 None => { -1 139 mins[*c] = 1; -1 140 maxs[*c] = 9; -1 141 }, -1 142 } -1 143 }, -1 144 (op, Token::Var(c), b) => { -1 145 let left_min = mins[*c]; -1 146 let left_max = maxs[*c]; -1 147 -1 148 let (right_min, right_max): (i64, i64) = match b { -1 149 Token::Int(bi) => (*bi, *bi), -1 150 Token::Var(bc) => (mins[*bc], maxs[*bc]), -1 151 _ => unreachable!(), -1 152 }; -1 153 -1 154 match op { -1 155 Token::Add => { -1 156 mins[*c] = left_min + right_min; -1 157 maxs[*c] = left_max + right_max; -1 158 }, -1 159 Token::Mul => { -1 160 mins[*c] = *vec![left_min * right_min, left_max * right_min, left_min * right_max, left_min * right_min].iter().min().unwrap(); -1 161 maxs[*c] = *vec![left_min * right_min, left_max * right_min, left_min * right_max, left_min * right_min].iter().max().unwrap(); -1 162 }, -1 163 Token::Div => { -1 164 mins[*c] = *vec![left_min / right_min, left_max / right_min, left_min / right_max, left_min / right_min].iter().min().unwrap(); -1 165 maxs[*c] = *vec![left_min / right_min, left_max / right_min, left_min / right_max, left_min / right_min].iter().max().unwrap(); -1 166 }, -1 167 Token::Mod => { -1 168 if left_min == left_max && right_min == right_max { -1 169 let v = left_min % right_min; -1 170 mins[*c] = v; -1 171 maxs[*c] = v; -1 172 } else { -1 173 mins[*c] = 0; -1 174 maxs[*c] = right_max - 1; -1 175 } -1 176 }, -1 177 Token::Eql => { -1 178 if left_min == left_max && right_min == right_max { -1 179 let v = if left_min == right_min {1} else {0}; -1 180 mins[*c] = v; -1 181 maxs[*c] = v; -1 182 } else { -1 183 mins[*c] = 0; -1 184 maxs[*c] = 1; -1 185 } -1 186 }, -1 187 _ => unreachable!(), 199 188 }200 -1 stack = new;201 189 }, 202 190 _ => unreachable!(), 203 191 } -1 192 } -1 193 -1 194 return mins[0] <= 0 && maxs[0] >= 0; -1 195 } 204 196205 -1 stack = optimize(stack);-1 197 fn bar(i: usize, mut solution: &mut [Option<i64>; 14], lines: &Vec<(Token, Token, Token)>) -> bool { -1 198 if i == 5 { -1 199 println!("{:?}", solution); -1 200 } -1 201 for value in (1..=9).rev() { -1 202 solution[i] = Some(value); -1 203 if foo(solution, lines) { -1 204 if i == 13 { -1 205 return true; -1 206 } -1 207 if bar(i + 1, solution, lines) { -1 208 return true; -1 209 } -1 210 } -1 211 } -1 212 solution[i] = None; -1 213 return false; -1 214 } 206 215207 -1 // println!("{} {:?}", i, stack);208 -1 println!("{}", i);209 -1 // print_formular(&mut stack.iter());210 -1 // println!("");-1 216 fn main() { -1 217 let lines = get_data(); -1 218 let mut solution = [None; 14]; -1 219 bar(0, &mut solution, &lines); -1 220 for i in solution.iter() { -1 221 print!("{}", i.unwrap()); 211 222 } -1 223 println!(""); 212 224 }