Initial commit

1 files changed, 178 insertions, 0 deletions

diff --git a/d25/src/main.rs b/d25/src/main.rs
new file mode 100644
index 0000000..ab740d8
--- /dev/null
+++ b/d25/src/main.rs
@@ -0,0 +1,178 @@
+use std::collections::HashMap;
+use std::fs;
+
+// This implementation is more similar to day 23 than day 12
+#[derive(Copy, Clone, Debug)]
+enum Arg<'a> {
+    Reg(&'a str),
+    Lit(isize),
+}
+
+impl<'a> From<&'a str> for Arg<'a> {
+    fn from(s: &'a str) -> Self {
+        if s.chars().all(|c| c.is_ascii_digit() || c == '-') { // yes I know
+            Self::Lit(s.parse().unwrap())
+        } else {
+            Self::Reg(s)
+        }
+    }
+}
+
+#[derive(Copy, Clone, Debug)]
+enum Oper<'a> {
+    Inc(Arg<'a>),
+    Dec(Arg<'a>),
+    Out(Arg<'a>),
+    Cpy(Arg<'a>, Arg<'a>),
+    Jnz(Arg<'a>, Arg<'a>),
+}
+
+fn parse(lines: Vec<&str>) -> Vec<Oper> {
+    let mut insts = Vec::new();
+
+    for line in lines {
+        let words: Vec<&str> = line.split_ascii_whitespace().collect();
+
+        if words[0] == "inc" {
+            insts.push(Oper::Inc(Arg::from(words[1])));
+        } else if words[0] == "dec" {
+            insts.push(Oper::Dec(Arg::from(words[1])));
+        } else if words[0] == "out" {
+            insts.push(Oper::Out(Arg::from(words[1])));
+        } else if words[0] == "cpy" {
+            insts.push(Oper::Cpy(Arg::from(words[1]), Arg::from(words[2])));
+        } else if words[0] == "jnz" {
+            insts.push(Oper::Jnz(Arg::from(words[1]), Arg::from(words[2])));
+        }
+    }
+
+    insts
+}
+
+// We pause the program at each `Out' and save the state to resume later
+#[derive(Clone, Debug, PartialEq)]
+struct State<'a> {
+    regs: HashMap<&'a str, isize>,
+    ip: usize,
+}
+
+impl<'a> From<Vec<(&'a str, isize)>> for State<'a> {
+    fn from(init: Vec<(&'a str, isize)>) -> Self {
+        Self {
+            regs: init.into_iter().collect(),
+            ip: 0,
+        }
+    }
+}
+
+// Execute the program until the next `Out` instruction, return the transmission
+fn transmit_next<'a>(insts: &'a Vec<Oper>, state: &mut State<'a>) -> Option<isize> {
+    let mut transmit = None;
+
+    while state.ip < insts.len() && transmit.is_none() {
+        match insts[state.ip] {
+            Oper::Inc(arg) => {
+                if let Arg::Reg(dst) = arg {
+                    *state.regs.entry(dst).or_insert(0) += 1;
+                }
+            },
+            Oper::Dec(arg) => {
+                if let Arg::Reg(dst) = arg {
+                    *state.regs.entry(dst).or_insert(0) -= 1;
+                }
+            },
+            Oper::Out(arg) => {
+                let val = match arg {
+                    Arg::Reg(reg) => state.regs.get(&reg).copied().unwrap_or(0),
+                    Arg::Lit(lit) => lit,
+                };
+                transmit = Some(val);
+            },
+            Oper::Cpy(arg1, arg2) => {
+                // This `if let' is actually a leftover from day 23
+                if let Arg::Reg(dst) = arg2 {
+                    let val = match arg1 {
+                        Arg::Reg(src) => state.regs.get(&src).copied().unwrap_or(0),
+                        Arg::Lit(lit) => lit,
+                    };
+                    *state.regs.entry(dst).or_insert(0) = val;
+                }
+            },
+            Oper::Jnz(arg1, arg2) => {
+                let val = match arg1 {
+                    Arg::Reg(reg) => state.regs.get(&reg).copied().unwrap_or(0),
+                    Arg::Lit(lit) => lit,
+                };
+                if val != 0 {
+                    let off = match arg2 {
+                        Arg::Reg(reg) => state.regs.get(&reg).copied().unwrap_or(0),
+                        Arg::Lit(lit) => lit,
+                    };
+                    // Subtract 1 to compensate for `state.ip += 1;' below
+                    state.ip = ((state.ip as isize) + off - 1) as usize;
+                }
+            },
+        };
+
+        state.ip += 1;
+    }
+
+    transmit
+}
+
+fn solve_part1(insts: &Vec<Oper>) -> isize {
+    let mut a = 1;
+    loop {
+        // History of (transmission, state) for this value of `a'.
+        // We're looking for a periodic pattern in these tuples.
+        let mut history: Vec<(isize, State)> = Vec::new();
+
+        // Initialize a fresh state with the candidate value of `a'
+        let mut state: State = State::from(vec![("a", a)]);
+
+        // This puzzle is basically Turing's halting problem, so for practicality
+        // we arbitrarily assume that the periodicity is at most 100 transmissions
+        for _i in 0..100 {
+            let ot = transmit_next(insts, &mut state);
+
+            // Did the program exit?
+            if ot.is_none() {
+                break;
+            }
+
+            // Did we transmit something other than 0 or 1?
+            let t = ot.unwrap();
+            if t != 0 && t != 1 {
+                break;
+            }
+
+            // Didn't we transmit 0 after 1, or 1 after 0?
+            if history.len() > 0 && history.last().unwrap().0 != 1 - t {
+                break;
+            }
+
+            let ts = (t, state.clone());
+            // Have we seen this state before? If yes, we've found a solution!
+            if history.contains(&ts) {
+                return a;
+            } else {
+                // But the transmission pattern seems promising so far; store it
+                history.push(ts);
+            }
+        }
+
+        a += 1;
+    }
+}
+
+fn main() {
+    // Read assembly from input text file and parse it
+    let input = fs::read_to_string("input.txt").unwrap();
+    let lines = input.lines().collect();
+    let insts = parse(lines);
+
+    // Part 1 gives 158 for my input
+    println!("Part 1 solution: {}", solve_part1(&insts));
+
+    // There's no part 2, since this is the last day
+}