08

6 files changed, 806 insertions, 0 deletions

diff --git a/08/Cargo.toml b/08/Cargo.toml
new file mode 100644
index 0000000..dbfa6d2
--- /dev/null
+++ b/08/Cargo.toml
@@ -0,0 +1,11 @@
+[package]
+name = "advent_08"
+version = "0.1.0"
+authors = ["Irene Knapp <ireneista@gmail.com>"]
+edition = "2018"
+
+[dependencies]
+advent_lib = { path = "../lib" }
+
+[dev-dependencies]
+assert_cmd = "0.10"
diff --git a/08/input b/08/input
new file mode 100644
index 0000000..1089fa5
--- /dev/null
+++ b/08/input
@@ -0,0 +1,623 @@
+acc +37
+acc -4
+nop +405
+jmp +276
+acc +39
+acc +40
+acc -3
+jmp +231
+acc +44
+acc +12
+jmp +505
+acc +35
+jmp +282
+acc +23
+jmp +598
+nop +392
+acc +18
+acc +44
+acc +18
+jmp +297
+nop +460
+jmp +152
+nop +541
+acc +33
+jmp -11
+acc -5
+acc +9
+jmp +327
+acc +30
+acc -1
+acc -3
+jmp +50
+acc +22
+acc +18
+acc +33
+acc +37
+jmp +57
+acc -17
+acc -6
+acc -2
+jmp +535
+acc -15
+jmp +279
+acc +34
+acc +44
+acc +41
+jmp +349
+acc +2
+acc +6
+nop +351
+nop +252
+jmp +505
+jmp +1
+jmp +1
+nop +61
+jmp +524
+nop +351
+jmp +399
+acc +1
+nop +397
+acc +39
+nop +141
+jmp +134
+acc +46
+acc +14
+acc +26
+jmp +236
+acc +7
+acc -6
+acc +35
+jmp +397
+acc +15
+jmp +140
+acc +3
+acc -4
+acc +37
+acc +12
+jmp +86
+jmp +416
+jmp +1
+jmp +55
+acc -19
+jmp +536
+jmp +1
+acc -11
+acc +15
+jmp -61
+acc +25
+jmp -25
+acc +50
+acc +43
+jmp +1
+jmp +140
+acc +46
+nop -53
+acc +1
+nop +440
+jmp +488
+jmp +396
+nop +443
+acc +41
+jmp +168
+acc +25
+nop +383
+acc +12
+acc -19
+jmp +21
+acc +29
+acc +30
+jmp +497
+jmp +502
+jmp +417
+nop +351
+acc -15
+jmp +243
+acc +21
+acc +16
+jmp +332
+acc +28
+acc +22
+acc +38
+jmp +476
+acc +8
+acc -11
+jmp +458
+acc +9
+jmp +246
+acc +40
+acc +31
+acc +26
+jmp +218
+acc +27
+acc +9
+nop +347
+jmp +478
+nop +28
+nop +106
+acc +25
+acc -15
+jmp +397
+acc +31
+jmp +231
+acc -4
+nop +136
+acc +14
+jmp +181
+jmp +361
+acc +16
+acc +11
+jmp -108
+nop +299
+acc +21
+acc -2
+jmp -106
+jmp +246
+acc +31
+jmp +407
+jmp +377
+acc +43
+acc -12
+nop +142
+acc +8
+jmp -91
+jmp +1
+acc +34
+acc +5
+acc +31
+jmp +12
+acc +34
+acc +7
+acc +34
+acc +20
+jmp -45
+acc -11
+acc +41
+acc +10
+jmp +310
+nop -106
+jmp -36
+acc +23
+acc +46
+acc +46
+jmp +112
+acc +41
+nop +179
+acc +17
+nop +356
+jmp +147
+acc +42
+nop +49
+jmp +119
+acc +0
+acc +7
+acc -18
+acc -8
+jmp +11
+acc +12
+acc +38
+acc +39
+jmp +281
+nop +186
+jmp +162
+acc +44
+acc +20
+jmp +153
+jmp +395
+acc +49
+jmp +1
+acc +2
+jmp +1
+jmp -31
+jmp +301
+nop +97
+jmp -102
+jmp +262
+acc +28
+acc -15
+acc +44
+acc -13
+jmp +191
+jmp +281
+acc +36
+acc +1
+nop +15
+jmp +211
+acc +6
+acc -4
+jmp +42
+acc +34
+acc +0
+jmp +104
+jmp +311
+jmp +84
+acc +43
+acc -8
+acc -10
+acc +38
+jmp -90
+acc +49
+jmp +303
+nop +132
+jmp +301
+nop +60
+acc +37
+nop +96
+jmp +182
+acc +16
+acc +18
+nop +152
+acc +19
+jmp +325
+jmp -63
+acc +28
+jmp +56
+acc +18
+acc +29
+acc +33
+jmp -115
+acc +47
+acc +19
+jmp +1
+nop +41
+jmp +1
+jmp -207
+nop -62
+acc -9
+acc +42
+acc -12
+jmp -56
+acc +28
+jmp -163
+acc +25
+acc +17
+jmp -217
+acc +7
+jmp +272
+acc +43
+acc +22
+jmp +70
+acc -17
+jmp -117
+acc +24
+acc +26
+nop -275
+jmp -46
+nop +87
+acc +19
+acc +28
+jmp -34
+acc +4
+acc +9
+acc +6
+jmp +1
+jmp +28
+acc -6
+nop -67
+acc -10
+jmp +271
+acc +40
+acc +25
+acc -4
+jmp -63
+acc +46
+jmp +78
+acc +41
+nop -126
+nop +70
+jmp +1
+jmp +172
+nop +270
+jmp +30
+jmp +1
+acc +38
+nop +68
+acc +29
+jmp +253
+acc -18
+jmp -89
+acc +18
+acc +30
+jmp +147
+acc +24
+acc +11
+acc +50
+jmp -225
+jmp -210
+acc -18
+acc +1
+acc +38
+jmp +1
+jmp -79
+acc +45
+acc +12
+jmp +209
+jmp -207
+acc +32
+acc +4
+acc +32
+acc +14
+jmp +83
+acc +13
+acc +1
+acc +46
+acc +38
+jmp +28
+nop +153
+acc -17
+jmp -73
+acc +11
+jmp +248
+acc +29
+acc +45
+acc +16
+jmp +96
+jmp -273
+acc +34
+jmp +87
+nop +99
+acc -3
+jmp -74
+acc +12
+nop -119
+jmp -141
+acc -18
+nop -79
+acc +1
+acc +6
+jmp +9
+acc +3
+acc +44
+acc +39
+jmp -165
+acc +6
+jmp +44
+acc +25
+jmp -133
+acc +0
+jmp +14
+jmp +1
+acc +1
+jmp -223
+jmp +71
+nop -1
+acc +22
+acc +11
+jmp -274
+jmp -330
+acc +45
+jmp +1
+acc +15
+jmp -158
+jmp -128
+acc +50
+acc +26
+jmp -73
+nop +99
+jmp +71
+acc +35
+acc +7
+jmp +192
+acc +13
+jmp +190
+acc +4
+acc -1
+acc +40
+acc -15
+jmp +50
+acc +29
+jmp -337
+jmp -75
+acc +41
+jmp +1
+jmp -387
+acc +28
+acc +18
+acc +19
+jmp -62
+nop -196
+jmp -410
+jmp +1
+acc -17
+jmp -267
+acc +22
+jmp -301
+nop -98
+acc -15
+jmp -124
+acc +45
+acc -18
+acc +15
+acc +42
+jmp -296
+nop -10
+acc +29
+jmp -371
+acc +3
+jmp +1
+nop +61
+acc +5
+jmp -361
+acc -5
+nop -326
+jmp -379
+acc -10
+jmp +1
+acc +44
+jmp -231
+acc +3
+jmp -94
+acc +1
+jmp +113
+jmp -336
+acc +4
+jmp -299
+acc -13
+jmp +1
+acc +13
+jmp +143
+acc -11
+acc -19
+acc +18
+nop -390
+jmp -27
+acc +42
+jmp -232
+acc +15
+jmp -228
+acc +21
+acc +39
+acc +47
+acc +6
+jmp +57
+acc +28
+acc +27
+acc +50
+jmp -397
+acc +12
+jmp -445
+acc +30
+jmp -352
+acc -4
+acc +26
+acc +48
+jmp +1
+jmp -205
+jmp +22
+nop -284
+acc -1
+nop -361
+acc +0
+jmp -368
+acc -17
+nop -223
+jmp -41
+acc +4
+acc +46
+jmp +79
+jmp -370
+jmp -260
+acc +42
+jmp -14
+acc +30
+acc +50
+acc +13
+jmp -61
+acc +46
+jmp -63
+nop -55
+nop -320
+jmp -11
+acc +10
+jmp -424
+jmp -11
+acc +3
+jmp -71
+acc +42
+acc -13
+jmp +4
+nop -155
+nop -138
+jmp +62
+acc +11
+acc +19
+acc +15
+acc +17
+jmp -73
+acc -11
+jmp -273
+acc +8
+acc +6
+acc -7
+acc +41
+jmp -311
+jmp -111
+jmp -260
+jmp +50
+jmp -60
+jmp +1
+nop -89
+acc +36
+acc +14
+jmp -220
+nop -415
+acc +28
+jmp -402
+acc +41
+jmp -165
+acc +9
+acc -13
+acc -18
+acc +18
+jmp -504
+acc -9
+acc +29
+acc +44
+jmp -444
+acc +5
+acc +47
+jmp -545
+acc +23
+acc +7
+nop -240
+jmp -320
+jmp -141
+jmp +1
+acc +28
+nop -287
+jmp -118
+acc +44
+acc -7
+jmp -550
+acc +10
+acc +20
+acc -3
+jmp -401
+acc +45
+acc +36
+jmp -375
+jmp -485
+acc +9
+jmp -338
+jmp -510
+jmp -196
+acc -16
+jmp -372
+acc +0
+jmp -380
+acc -3
+nop -473
+nop -361
+jmp -311
+acc +0
+nop +20
+jmp -436
+acc +9
+jmp +1
+jmp -215
+acc +19
+jmp -451
+jmp -43
+acc -13
+acc -10
+acc -5
+jmp -208
+acc -11
+jmp -156
+acc +11
+acc -2
+nop -357
+jmp -73
+acc +21
+jmp -159
+acc +28
+acc -16
+acc +12
+acc +1
+jmp -282
+jmp -131
+acc -11
+acc +45
+acc +0
+acc +28
+jmp +1
diff --git a/08/src/main.rs b/08/src/main.rs
new file mode 100644
index 0000000..b25d85e
--- /dev/null
+++ b/08/src/main.rs
@@ -0,0 +1,149 @@
+use advent_lib::prelude::*;
+
+use std::convert::TryFrom;
+use std::collections::BTreeSet;
+
+#[derive(Clone, Debug)]
+enum Operation {
+  Accumulator(isize),
+  Jump(isize),
+  NoOp(isize),
+}
+
+#[derive(Clone, Debug)]
+struct MachineState {
+  accumulator: isize,
+  program_counter: usize,
+}
+
+impl MachineState {
+  fn new() -> MachineState {
+    MachineState {
+      accumulator: 0,
+      program_counter: 0,
+    }
+  }
+}
+
+
+fn main() -> Result<()> {
+  let mut args = std::env::args();
+  if args.len() != 2 {
+    eprintln!("Usage: advent input");
+  }
+  let _ = args.next();
+  let filename = args.next().unwrap();
+
+  let input = advent_lib::read_lines_file(&filename)?;
+
+  let program = parse_program(&input)?;
+
+  find_first_loop(&program);
+
+  find_patch_to_terminate(&program);
+
+  Ok(())
+}
+
+
+fn parse_program(input: &Vec<String>) -> Result<Vec<Operation>> {
+  let mut program: Vec<Operation> = Vec::new();
+
+  for line in input {
+    let mut words = Vec::new();
+    for word in line.split(' ') {
+      words.push(word);
+    }
+
+    let operand = words[1].parse::<isize>()?;
+    match words[0] {
+      "acc" => program.push(Operation::Accumulator(operand)),
+      "jmp" => program.push(Operation::Jump(operand)),
+      "nop" => program.push(Operation::NoOp(operand)),
+      _ => panic!()
+    }
+  }
+
+  Ok(program)
+}
+
+
+fn simulate_one(program: &Vec<Operation>, state: &MachineState) -> MachineState {
+  let mut new_state = state.clone();
+
+  match program[new_state.program_counter] {
+    Operation::Accumulator(operand) => {
+      new_state.accumulator += operand;
+      new_state.program_counter += 1;
+    },
+    Operation::Jump(operand) => {
+      new_state.program_counter = usize::try_from(
+        isize::try_from(new_state.program_counter).unwrap()
+        + operand).unwrap();
+    },
+    Operation::NoOp(_) => {
+      new_state.program_counter += 1;
+    },
+  }
+
+  new_state
+}
+
+
+fn find_first_loop(program: &Vec<Operation>) -> () {
+  let mut visited_lines: BTreeSet<usize> = BTreeSet::new();
+  let mut state = MachineState::new();
+
+  loop {
+    if visited_lines.contains(&state.program_counter) {
+      println!("{}", state.accumulator);
+      break;
+    }
+
+    visited_lines.insert(state.program_counter);
+    state = simulate_one(&program, &state);
+  }
+}
+
+
+fn find_patch_to_terminate(program: &Vec<Operation>) -> () {
+  for i in 0..program.len() {
+    let mut patched_program = program.clone();
+
+    match patched_program[i] {
+      Operation::Accumulator(_) => {
+        continue;
+      },
+      Operation::Jump(operand) => {
+        patched_program[i] = Operation::NoOp(operand);
+      },
+      Operation::NoOp(operand) => {
+        patched_program[i] = Operation::Jump(operand);
+      },
+    }
+
+    let mut visited_lines: BTreeSet<usize> = BTreeSet::new();
+    let mut state = MachineState::new();
+    let mut normal_exit = false;
+
+    loop {
+      if visited_lines.contains(&state.program_counter) {
+        break;
+      }
+
+      if state.program_counter == patched_program.len() {
+        println!("normal exit {}", state.accumulator);
+        normal_exit = true;
+        break;
+      }
+
+      visited_lines.insert(state.program_counter);
+      state = simulate_one(&patched_program, &state);
+    }
+
+    if normal_exit {
+      break;
+    }
+  }
+}
+
diff --git a/08/tests/main.rs b/08/tests/main.rs
new file mode 100644
index 0000000..3761615
--- /dev/null
+++ b/08/tests/main.rs
@@ -0,0 +1,14 @@
+use assert_cmd::prelude::*;
+use std::process::Command;
+
+
+#[test]
+fn personal_input() -> Result<(), Box<dyn std::error::Error>> {
+  let mut command = Command::cargo_bin("advent_08")?;
+
+  command.arg("input");
+  command.assert().success().stdout("1801\nnormal exit 2060\n");
+
+  Ok(())
+}
+
diff --git a/Cargo.lock b/Cargo.lock
index 48da977..9a04392 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -59,6 +59,14 @@ dependencies = [
 ]
 
 [[package]]
+name = "advent_08"
+version = "0.1.0"
+dependencies = [
+ "advent_lib",
+ "assert_cmd",
+]
+
+[[package]]
 name = "advent_lib"
 version = "0.1.0"
 
diff --git a/Cargo.toml b/Cargo.toml
index 48403e3..e72d2a8 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -8,4 +8,5 @@ members = [
   "05",
   "06",
   "07",
+  "08",
 ]