From 57ab4ffec7aa770207306564ffcc50f5145160e1 Mon Sep 17 00:00:00 2001 From: Jesse Luehrs Date: Wed, 9 Dec 2020 01:10:29 -0500 Subject: day 8 --- data/8.txt | 675 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/2020/8/mod.rs | 125 ++++++++++ src/2020/mod.rs | 4 + 3 files changed, 804 insertions(+) create mode 100644 data/8.txt create mode 100644 src/2020/8/mod.rs diff --git a/data/8.txt b/data/8.txt new file mode 100644 index 0000000..296e397 --- /dev/null +++ b/data/8.txt @@ -0,0 +1,675 @@ +acc -8 +jmp +5 +acc +0 +acc +44 +acc +42 +jmp +324 +acc -17 +jmp +1 +acc -17 +jmp +51 +acc -13 +acc +4 +jmp +1 +nop +608 +jmp +274 +acc -17 +jmp +169 +acc +28 +nop +508 +jmp +1 +jmp +570 +acc +22 +acc -14 +jmp +377 +acc -13 +acc +27 +jmp +474 +acc -5 +jmp +1 +acc +12 +jmp +37 +jmp +184 +acc +36 +acc +32 +acc -8 +jmp +465 +acc -13 +acc +18 +jmp +169 +acc +20 +acc +26 +acc +23 +jmp +333 +jmp +584 +acc +9 +acc +28 +acc +28 +nop +571 +jmp +143 +acc +39 +acc +39 +acc -16 +jmp +361 +acc +48 +acc +3 +acc +15 +nop +4 +jmp +504 +acc +6 +jmp +285 +acc +26 +acc +33 +jmp +1 +acc +36 +jmp +577 +acc +36 +jmp +6 +nop +498 +acc +42 +jmp +496 +acc +10 +jmp +74 +acc +17 +acc +16 +acc +30 +jmp +254 +acc -3 +acc +16 +acc -2 +nop +106 +jmp +541 +acc -15 +jmp +579 +jmp +165 +acc +22 +acc -6 +acc +29 +acc -19 +jmp +342 +acc -19 +jmp +340 +acc +13 +acc +25 +acc +29 +jmp +269 +acc -14 +acc +27 +acc +41 +acc +49 +jmp +181 +nop +350 +jmp +1 +nop +437 +acc +34 +jmp +494 +acc +19 +acc +2 +acc +44 +jmp +558 +acc +10 +jmp +44 +nop +4 +nop -80 +nop +540 +jmp +16 +acc +28 +jmp +14 +acc +13 +nop +399 +acc +29 +nop -60 +jmp -6 +acc +41 +acc +30 +jmp +232 +acc +28 +nop +495 +acc +15 +acc +48 +jmp +157 +nop +483 +jmp -59 +acc +5 +acc +30 +acc +30 +acc +2 +jmp +349 +acc +11 +acc +27 +acc +1 +jmp +367 +acc +8 +acc +45 +acc +11 +jmp +171 +jmp -113 +acc +48 +jmp -38 +acc +12 +jmp +145 +acc +8 +nop +29 +nop +319 +jmp +154 +nop +166 +jmp +395 +nop +15 +jmp +237 +acc +22 +acc +3 +acc +42 +acc +1 +jmp +288 +jmp -63 +nop +489 +acc +33 +jmp +247 +jmp +1 +acc -8 +acc +9 +jmp +413 +acc -17 +acc +3 +acc +3 +jmp +432 +nop -17 +acc +36 +nop +198 +acc +45 +jmp +109 +nop +242 +acc +40 +acc +11 +jmp +448 +jmp +437 +acc +3 +acc +49 +acc +27 +jmp +221 +nop +158 +jmp +143 +acc +50 +jmp -70 +acc +46 +acc +8 +acc +35 +acc -3 +jmp +104 +acc +11 +acc +0 +jmp +34 +nop +132 +jmp +425 +jmp +219 +acc -12 +acc +48 +jmp +21 +jmp +434 +acc +30 +acc +1 +acc +40 +jmp +435 +jmp +132 +acc +40 +jmp +236 +jmp +179 +jmp -149 +acc +25 +acc +40 +acc -9 +acc +49 +jmp +445 +nop +399 +acc -14 +nop +374 +acc +0 +jmp +152 +acc +39 +nop +322 +acc +49 +nop +117 +jmp -19 +acc +24 +jmp +385 +acc +17 +acc +39 +acc +44 +acc -8 +jmp -58 +acc -18 +nop -76 +jmp +66 +acc +14 +jmp +427 +acc +11 +acc +47 +acc +9 +jmp +1 +acc +42 +jmp -7 +acc -16 +acc -13 +jmp +409 +acc +1 +acc +35 +acc +34 +jmp +371 +acc +24 +acc +46 +acc -4 +jmp +367 +acc +19 +acc +27 +acc -8 +acc +41 +jmp -184 +nop -185 +acc +23 +acc -8 +acc +35 +jmp -9 +acc -7 +nop -101 +nop +121 +acc +37 +jmp -72 +acc +24 +jmp +1 +nop -124 +jmp +163 +acc +37 +acc -12 +jmp +331 +acc -12 +acc +1 +jmp +232 +jmp -233 +jmp -72 +acc +28 +jmp +169 +acc +43 +acc +18 +nop +108 +jmp -184 +acc -4 +acc -10 +nop +317 +acc +48 +jmp +173 +nop +45 +jmp -73 +acc +35 +jmp +198 +acc -15 +acc +46 +acc +31 +jmp +41 +nop +169 +jmp +1 +nop -92 +nop -271 +jmp -113 +jmp +1 +nop -42 +jmp +42 +nop -283 +acc +22 +nop +200 +jmp -17 +jmp +1 +acc +49 +nop +35 +nop -185 +jmp +298 +acc +1 +jmp +1 +nop +301 +acc +19 +jmp -34 +jmp +163 +jmp +1 +acc +49 +jmp -115 +jmp -62 +acc +8 +acc +5 +acc -6 +jmp -146 +acc -4 +nop -202 +acc +47 +jmp -114 +acc +8 +jmp +57 +acc +37 +jmp +61 +jmp +267 +acc +2 +acc +28 +nop -20 +jmp -186 +acc +24 +nop +269 +acc +48 +acc +45 +jmp -22 +acc +11 +acc +36 +jmp -267 +acc +7 +nop -45 +nop -231 +jmp +32 +nop +220 +acc +19 +jmp -250 +acc +33 +jmp -169 +acc +45 +acc -13 +acc +0 +acc +44 +jmp +6 +acc +42 +jmp +84 +acc +48 +jmp -332 +jmp +213 +acc -16 +acc +31 +acc +17 +acc +3 +jmp -75 +jmp +1 +acc +11 +acc +4 +jmp -271 +acc -12 +nop +97 +nop +11 +jmp -43 +acc +30 +jmp +1 +jmp +49 +jmp -379 +nop -51 +acc +0 +acc -8 +nop -191 +jmp -346 +jmp -255 +acc +2 +acc +21 +acc -16 +nop +217 +jmp -30 +acc +31 +jmp -270 +jmp -324 +jmp +130 +acc +49 +nop +179 +jmp -37 +acc +11 +acc +15 +acc +29 +acc +17 +jmp -237 +acc +47 +acc -13 +acc +6 +jmp +169 +nop +54 +acc -12 +jmp -233 +nop +33 +acc +17 +acc +14 +acc +21 +jmp -275 +acc -8 +acc +1 +nop +229 +jmp +1 +jmp +119 +jmp -193 +nop +217 +jmp +95 +acc -2 +acc +1 +acc +41 +jmp -332 +acc +44 +nop -343 +acc +23 +jmp -165 +acc +7 +acc -12 +nop -339 +jmp +9 +nop -390 +acc -17 +acc +43 +jmp -138 +nop -247 +acc +42 +acc +0 +jmp +170 +acc +48 +jmp -139 +acc +6 +acc +13 +acc +35 +jmp -85 +nop -117 +jmp -307 +acc +25 +acc -10 +acc -14 +acc +0 +jmp -355 +jmp +102 +acc -8 +acc +47 +acc +36 +jmp +42 +acc +33 +acc +17 +acc +46 +jmp -331 +jmp +1 +acc -11 +jmp +1 +acc +27 +jmp +147 +acc -14 +nop -28 +acc +32 +jmp -482 +acc +11 +nop -390 +jmp -485 +acc -12 +acc +37 +acc +33 +acc +28 +jmp -32 +acc +42 +acc -11 +jmp -460 +acc +36 +acc +6 +acc +39 +jmp +80 +nop +123 +acc -13 +jmp -97 +acc +25 +acc +46 +acc +13 +nop -450 +jmp +84 +acc +3 +nop -260 +jmp +1 +acc +22 +jmp -510 +acc -4 +acc +17 +acc -19 +jmp -420 +acc -14 +acc +26 +acc +29 +acc +17 +jmp -458 +acc -10 +acc +23 +nop -2 +jmp -196 +acc -5 +jmp -416 +acc +49 +jmp -165 +acc +4 +acc +7 +acc +20 +nop -217 +jmp +103 +jmp +5 +acc -1 +acc +2 +jmp +1 +jmp +84 +acc -14 +jmp -518 +jmp +1 +acc +30 +acc +21 +jmp -202 +nop -18 +jmp -344 +jmp -88 +nop -472 +acc -5 +acc +13 +jmp -295 +nop -315 +acc +41 +nop -317 +jmp -299 +nop +105 +jmp -86 +acc +7 +jmp -226 +nop -277 +acc +21 +acc +13 +acc +47 +jmp -283 +acc -11 +acc -1 +jmp -408 +acc +47 +nop -553 +acc +37 +acc -11 +jmp -468 +acc +43 +nop -299 +acc +40 +acc +2 +jmp -275 +acc +24 +acc -14 +acc +13 +acc +36 +jmp -249 +acc +35 +jmp -45 +acc +47 +acc +31 +acc -19 +jmp -151 +jmp -33 +acc +6 +jmp -160 +jmp -553 +acc +25 +jmp +1 +nop -267 +jmp -430 +acc +23 +nop +63 +acc +37 +jmp -434 +nop -579 +jmp +11 +acc +25 +acc -17 +acc +22 +acc +27 +jmp +15 +jmp -546 +acc -4 +acc +41 +acc +0 +jmp -261 +acc +20 +jmp -404 +jmp -408 +acc +26 +jmp -464 +acc +34 +nop -80 +acc -12 +jmp -43 +jmp -410 +acc -13 +acc -3 +jmp -310 +nop -433 +acc -7 +acc -11 +acc +9 +jmp -29 +nop -564 +acc -5 +acc -16 +acc +36 +jmp -587 +jmp -115 +acc +24 +acc +35 +nop -638 +jmp -573 +acc +31 +acc +14 +jmp -609 +acc +25 +acc -10 +acc +18 +jmp -308 +acc +25 +acc +33 +acc +21 +acc -12 +jmp -172 +nop -37 +acc +12 +jmp -316 +acc +41 +acc +14 +jmp -415 +acc +40 +jmp -112 +jmp -613 +acc +26 +nop -151 +jmp -471 +acc +50 +acc +16 +nop -119 +acc +46 +jmp +1 diff --git a/src/2020/8/mod.rs b/src/2020/8/mod.rs new file mode 100644 index 0000000..0e5d686 --- /dev/null +++ b/src/2020/8/mod.rs @@ -0,0 +1,125 @@ +use anyhow::Context as _; + +#[derive(Clone, Copy)] +enum OpType { + Nop, + Acc, + Jmp, +} + +impl std::str::FromStr for OpType { + type Err = anyhow::Error; + + fn from_str(s: &str) -> std::result::Result { + Ok(match s { + "nop" => Self::Nop, + "acc" => Self::Acc, + "jmp" => Self::Jmp, + _ => return Err(anyhow::anyhow!("invalid optype {}", s)), + }) + } +} + +#[derive(Clone, Copy)] +struct Op { + ty: OpType, + arg: i64, +} + +impl std::str::FromStr for Op { + type Err = anyhow::Error; + + fn from_str(s: &str) -> std::result::Result { + let rx = regex::Regex::new(r"^([^ ]*) ((?:-|\+)[0-9]+)$").unwrap(); + let captures = rx.captures(s).context("failed to parse line")?; + let ty = captures.get(1).unwrap().as_str().parse()?; + let arg = captures + .get(2) + .unwrap() + .as_str() + .parse() + .context("invalid arg")?; + Ok(Self { ty, arg }) + } +} + +pub fn part1() -> anyhow::Result { + let input = crate::util::read_file_str("data/8.txt")?; + let opcodes = parse(&input)?; + let (acc, success) = run(&opcodes)?; + if success { + return Err(anyhow::anyhow!("unexpectedly succeeded")); + } + Ok(acc) +} + +pub fn part2() -> anyhow::Result { + let input = crate::util::read_file_str("data/8.txt")?; + let opcodes = parse(&input)?; + for i in 0..opcodes.len() { + match opcodes[i].ty { + OpType::Nop => { + let mut attempt = opcodes.clone(); + attempt[i].ty = OpType::Jmp; + let (acc, success) = run(&attempt)?; + if success { + return Ok(acc); + } + } + OpType::Acc => {} + OpType::Jmp => { + let mut attempt = opcodes.clone(); + attempt[i].ty = OpType::Nop; + let (acc, success) = run(&attempt)?; + if success { + return Ok(acc); + } + } + } + } + Err(anyhow::anyhow!("failed to find corrupted opcode")) +} + +fn parse(input: &str) -> anyhow::Result> { + input.lines().map(|line| line.parse()).collect() +} + +fn run(opcodes: &[Op]) -> anyhow::Result<(i64, bool)> { + let mut seen = vec![false; opcodes.len()]; + let mut pc = 0; + let mut acc = 0; + loop { + if pc >= opcodes.len() { + return Ok((acc, true)); + } else if seen[pc] { + return Ok((acc, false)); + } + seen[pc] = true; + + match opcodes[pc].ty { + OpType::Nop => { + pc += 1; + } + OpType::Acc => { + acc += opcodes[pc].arg; + pc += 1; + } + OpType::Jmp => { + let arg = opcodes[pc].arg; + if arg >= 0 { + if arg as usize > opcodes.len() + || pc > opcodes.len() - arg as usize + { + return Err(anyhow::anyhow!("invalid jmp")); + } + pc += arg as usize; + } else { + if pc < (-arg as usize) { + return Err(anyhow::anyhow!("invalid jmp")); + } + pc -= -arg as usize; + } + } + } + } +} diff --git a/src/2020/mod.rs b/src/2020/mod.rs index 165d2ab..b8f6a20 100644 --- a/src/2020/mod.rs +++ b/src/2020/mod.rs @@ -12,6 +12,8 @@ mod day5; mod day6; #[path = "7/mod.rs"] mod day7; +#[path = "8/mod.rs"] +mod day8; pub fn run(day: u8, puzzle: u8) -> anyhow::Result { match (day, puzzle) { @@ -29,6 +31,8 @@ pub fn run(day: u8, puzzle: u8) -> anyhow::Result { (6, 2) => day6::part2(), (7, 1) => day7::part1(), (7, 2) => day7::part2(), + (8, 1) => day8::part1(), + (8, 2) => day8::part2(), _ => Err(anyhow::anyhow!("unknown puzzle {}-{}", day, puzzle)), } } -- cgit v1.2.3-54-g00ecf