A guide to Advent of Code 2019's Intcode problems

# Cargo.toml
[package]
name = "intcode"
version = "0.1.0"
edition = "2021"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
color-eyre = "0.5"
strum = "0.23"
strum_macros = "0.23"
argh = "0.1.7"

use argh::FromArgs;
use color_eyre::eyre;
use std::fs;
use std::io;
use std::path::PathBuf;
use strum_macros::EnumString;

mod day_2;

fn main() -> eyre::Result<()> {
    let Args {
        program,
        input_file,
    } = argh::from_env();
    let raw_intcode = if let Some(path) = input_file {
        println!("Reading from {:?} ...", path);
        fs::read_to_string(path)?
    } else {
        println!("Reading from stdin ...");
        read_stdin()?
    };
    let intcode = parse_intcode(&raw_intcode)?;
    println!("Successfully read and parsed intcode.");

    match program {
        Program::Day2Part1 => day_2::part_1(intcode)?,
    };
    Ok(())
}

fn read_stdin() -> io::Result<String> {
    use io::Read;
    let mut stdin = io::stdin();
    let mut string = String::new();
    stdin.read_to_string(&mut string)?;
    Ok(string)
}

#[derive(Debug, Clone, FromArgs)]
/// An interpreter for the Intcode language introduced in Advent of Code 2019.
///
/// Currently implemented programs are:
/// day2part1
struct Args {
    /// the program you want to run
    #[argh(positional)]
    program: Program,

    /// the file to parse Intcode from. If excluded, reads from stdin
    #[argh(positional)]
    input_file: Option<PathBuf>,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, EnumString)]
enum Program {
    #[strum(serialize = "day2part1", serialize = "d2p1")]
    Day2Part1,
}

type Intcode = Vec<i32>;

fn parse_intcode(raw: &str) -> eyre::Result<Intcode> {
    Ok(raw
        .split(',')
        .map(str::trim)
        .map(str::parse)
        .collect::<Result<Vec<_>, _>>()?)
}

// day_2.rs
use color_eyre::eyre;

pub fn part_1(mut intcode: Vec<i32>) -> eyre::Result<()> {
    intcode[1] = 12;
    intcode[2] = 2;
    let mut current = 0;
    loop {
        match intcode[current] {
            1 => {
                let param_1 = intcode[current + 1] as usize;
                let param_2 = intcode[current + 2] as usize;
                let param_3 = intcode[current + 3] as usize;
                intcode[param_3] = intcode[param_1] + intcode[param_2];
                current += 4;
            }
            2 => {
                let param_1 = intcode[current + 1] as usize;
                let param_2 = intcode[current + 2] as usize;
                let param_3 = intcode[current + 3] as usize;
                intcode[param_3] = intcode[param_1] * intcode[param_2];
                current += 4;
            }
            99 => {
                break;
            }
            opcode @ _ => eyre::bail!("Unknown opcode {}", opcode),
        }
    }
    println!("{}", intcode[0]);
    Ok(())
}

// runner.rs
use color_eyre::eyre;

#[derive(Debug, Clone)]
pub struct Intcode {
    pub memory: Vec<i32>,
    current: usize,
}
impl Intcode {
    pub fn from_vec(vec: Vec<i32>) -> Self {
        Self {
            memory: vec,
            current: 0,
        }
    }

    pub fn execute(&mut self) -> eyre::Result<()> {
        loop {
            match self.memory[self.current] {
                1 => {
                    let param_1 = self.memory[self.current + 1] as usize;
                    let param_2 = self.memory[self.current + 2] as usize;
                    let param_3 = self.memory[self.current + 3] as usize;
                    self.memory[param_3] = self.memory[param_1] + self.memory[param_2];
                    self.current += 4;
                }
                2 => {
                    let param_1 = self.memory[self.current + 1] as usize;
                    let param_2 = self.memory[self.current + 2] as usize;
                    let param_3 = self.memory[self.current + 3] as usize;
                    self.memory[param_3] = self.memory[param_1] * self.memory[param_2];
                    self.current += 4;
                }
                99 => {
                    break;
                }
                opcode @ _ => eyre::bail!("Unknown opcode {}", opcode),
            }
        }
        Ok(())
    }
}

// main.rs diff
+mod day_2;
+pub mod runner;
+
+use crate::runner::Intcode;
 use argh::FromArgs;
 use color_eyre::eyre;
 use std::fs;
...
 use std::path::PathBuf;
 use strum_macros::EnumString;

-mod day_2;
-
 fn main() -> eyre::Result<()> {
...
     match program {
         Program::Day2Part1 => day_2::part_1(intcode)?,
+        Program::Day2Part2 => day_2::part_2(intcode)?,
     };
...
 /// An interpreter for the Intcode language introduced in Advent of Code 2019.
 ///
 /// Currently implemented programs are:
-/// day2part1
+/// day2part1,
+/// day2part2
 struct Args {
...
 enum Program {
     #[strum(serialize = "day2part1", serialize = "d2p1")]
     Day2Part1,
+
+    #[strum(serialize = "day2part2", serialize = "d2p2")]
+    Day2Part2,
 }

-type Intcode = Vec<i32>;
-
 fn parse_intcode(raw: &str) -> eyre::Result<Intcode> {
-    Ok(raw
+    let vec = raw
         .split(',')
         .map(str::trim)
         .map(str::parse)
-        .collect::<Result<Vec<_>, _>>()?)
+        .collect::<Result<Vec<_>, _>>()?;
+    Ok(Intcode::from_vec(vec))
 }

// day_2.rs (new)
use crate::runner::Intcode;
use color_eyre::eyre;
use eyre::eyre;

pub fn part_1(mut intcode: Intcode) -> eyre::Result<()> {
    intcode.memory[1] = 12;
    intcode.memory[2] = 2;
    intcode.execute()?;
    println!("{}", intcode.memory[0]);
    Ok(())
}

pub fn part_2(intcode: Intcode) -> eyre::Result<()> {
    for noun in 0..100 {
        for verb in 0..100 {
            let mut intcode = intcode.clone();
            intcode.memory[1] = noun;
            intcode.memory[2] = verb;
            intcode.execute()?;
            if intcode.memory[0] == 19690720 {
                println!("{}", noun * 100 + verb);
                return Ok(());
            }
        }
    }
    Err(eyre!("no output found"))
}

// runner.rs
impl Intcode {
    fn get_param_values<const N: usize>(&self) -> [i32; N] {
        let mut param_modes = get_param_modes(self.memory[self.current]);
        let mut i = self.current;
        [(); N]
            .map(|_| {
                i += 1;
                i
            })
            .map(|i| {
                let mode = param_modes.next().unwrap();
                match mode {
                    0 => self.memory[self.memory[i] as usize],
                    1 => self.memory[i],
                    other => panic!("Unknown parameter mode {}.", other),
                }
            })
    }
}

fn get_opcode(num: i32) -> i32 {
    num % 100
}

fn get_param_modes(num: i32) -> impl Iterator<Item = i32> {
    use std::iter;
    iter::repeat(()).scan(num / 100, |state, _| {
        let out = *state % 10;
        *state /= 10;
        Some(out)
    })
}

// runner.rs diff
     pub fn execute(&mut self) -> eyre::Result<()> {
         loop {
-            match self.memory[self.current] {
+            match get_opcode(self.memory[self.current]) {
                 1 => {
-                    let param_1 = self.memory[self.current + 1] as usize;
-                    let param_2 = self.memory[self.current + 2] as usize;
-                    let param_3 = self.memory[self.current + 3] as usize;
-                    self.memory[param_3] = self.memory[param_1] + self.memory[param_2];
+                    let [param_1, param_2] = self.get_param_values::<2>();
+                    let out_index = self.memory[self.current + 3] as usize;
+                    self.memory[out_index] = param_1 + param_2;
                     self.current += 4;
                 }
                 2 => {
-                    let param_1 = self.memory[self.current + 1] as usize;
-                    let param_2 = self.memory[self.current + 2] as usize;
-                    let param_3 = self.memory[self.current + 3] as usize;
-                    self.memory[param_3] = self.memory[param_1] * self.memory[param_2];
+                    let [param_1, param_2] = self.get_param_values::<2>();
+                    let out_index = self.memory[self.current + 3] as usize;
+                    self.memory[out_index] = param_1 * param_2;
                     self.current += 4;
                 }
+                3 => {
+                    use std::io::{stdin, stdout, Write};
+                    print!("Enter an integer> ");
+                    stdout().flush();
+                    let mut line = String::new();
+                    stdin().read_line(&mut line)?;
+                    let int = line.trim().parse()?;
+
+                    let out_index = self.memory[self.current + 1] as usize;
+                    self.memory[out_index] = int;
+                    self.current += 2;
+                }
+                4 => {
+                    let [param] = self.get_param_values::<1>();
+                    println!("Output> {}", param);
+                    self.current += 2;
+                }
+
                 99 => {
                     break;
                 }
                 opcode @ _ => eyre::bail!("Unknown opcode {}", opcode),
             }
         }
         Ok(())
     }

// day_5.rs
use crate::runner::Intcode;
use color_eyre::eyre;
use eyre::eyre;

pub fn part_1(mut intcode: Intcode) -> eyre::Result<()> {
    intcode.execute()?;
    Ok(())
}

                     self.current += 2;
                 }
+                5 => {
+                    let [param_1, param_2] = self.get_param_values::<2>();
+                    if param_1 != 0 {
+                        self.current = param_2 as usize;
+                    } else {
+                        self.current += 3;
+                    }
+                }
+                6 => {
+                    let [param_1, param_2] = self.get_param_values::<2>();
+                    if param_1 == 0 {
+                        self.current = param_2 as usize;
+                    } else {
+                        self.current += 3;
+                    }
+                }
+                7 => {
+                    let [param_1, param_2] = self.get_param_values::<2>();
+                    let out_index = self.memory[self.current + 3] as usize;
+                    self.memory[out_index] = (param_1 < param_2) as i32;
+                    self.current += 4;
+                }
+                8 => {
+                    let [param_1, param_2] = self.get_param_values::<2>();
+                    let out_index = self.memory[self.current + 3] as usize;
+                    self.memory[out_index] = (param_1 == param_2) as i32;
+                    self.current += 4;
+                }

                 99 => {
                     break;

-    let raw_intcode = if let Some(path) = input_file {
-        println!("Reading from {:?} ...", path);
-        fs::read_to_string(path)?
-    } else {
-        println!("Reading from stdin ...");
-        read_stdin()?
-    };
-    let intcode = parse_intcode(&raw_intcode)?;
+    println!("Reading from {:?} ...", input_file);
+    let raw_intcode = fs::read_to_string(input_file)?;
+    let intcode = raw_intcode.parse()?;
     println!("Successfully read and parsed intcode.");
...
 struct Args {
     /// the program you want to run
     #[argh(positional)]
     program: Program,

-    /// the file to parse Intcode from. If excluded, reads from stdin
+    /// the file to parse Intcode from
     #[argh(positional)]
-    input_file: Option<PathBuf>,
+    input_file: PathBuf,
 }
...
-
-fn parse_intcode(raw: &str) -> eyre::Result<Intcode> {
-    let vec = raw
-        .split(',')
-        .map(str::trim)
-        .map(str::parse)
-        .collect::<Result<Vec<_>, _>>()?;
-    Ok(Intcode::from_vec(vec))
-}

                 99 => {
                     break;
                 }
-                opcode @ _ => eyre::bail!("Unknown opcode {}", opcode),
+                opcode @ _ => eyre::bail!("Unknown opcode {} at position {}", opcode, self.current),
             }
         }
...

+#[inline]
 fn get_opcode(num: i32) -> i32 {
     num % 100
 }

// day_5.rs (new)
use crate::runner::Intcode;
use color_eyre::eyre;

pub fn exec(mut intcode: Intcode) -> eyre::Result<()> {
    println!("Enter 1 for part 1 and 5 for part 2.");
    intcode.execute()?;
    Ok(())
}

// runner.rs diff
 impl Intcode {
-    pub fn execute(&mut self) -> eyre::Result<()> {
+    pub fn execute_without_io(&mut self) -> eyre::Result<()> {
+        match self.execute(None)? {
+            HaltReason::NormalHalt => (),
+            other @ _ => eyre::bail!(
+                "Unexpected halt reason {:?} when executing without io",
+                other
+            ),
+        }
+        Ok(())
+    }
+    pub fn execute(&mut self, mut input: Option<i32>) -> eyre::Result<HaltReason> {
         loop {
             match get_opcode(self.memory[self.current]) {
                 1 => {
...
+
                 3 => {
-                    use std::io::{stdin, stdout, Write};
-                    print!("Enter an integer> ");
-                    stdout().flush()?;
-                    let mut line = String::new();
-                    stdin().read_line(&mut line)?;
-                    let int = line.trim().parse()?;
-
-                    let out_index = self.memory[self.current + 1] as usize;
-                    self.memory[out_index] = int;
-                    self.current += 2;
+                    if let Some(input) = input.take() {
+                        let out_index = self.memory[self.current + 1] as usize;
+                        self.memory[out_index] = input;
+                        self.current += 2;
+                    } else {
+                        break Ok(HaltReason::NeedInput);
+                    }
                 }
                 4 => {
-                    let [param] = self.get_param_values::<1>();
-                    println!("Output> {}", param);
+                    let [output] = self.get_param_values::<1>();
                     self.current += 2;
+                    break Ok(HaltReason::GaveOutput(output));
                 }
...
                 99 => {
-                    break;
+                    break Ok(HaltReason::NormalHalt);
                 }
                 opcode @ _ => eyre::bail!("Unknown opcode {} at position {}", opcode, self.current),
             }
         }
-        Ok(())
     }
...

+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+pub enum HaltReason {
+    GaveOutput(i32),
+    NeedInput,
+    NormalHalt,
+}

// day_2.rs diff
 pub fn part_1(mut intcode: Intcode) -> eyre::Result<()> {
     intcode.memory[1] = 12;
     intcode.memory[2] = 2;
-    intcode.execute()?;
+    intcode.execute_without_io()?;
     println!("{}", intcode.memory[0]);
     Ok(())
 }
...
             let mut intcode = intcode.clone();
             intcode.memory[1] = noun;
             intcode.memory[2] = verb;
-            intcode.execute()?;
+            intcode.execute_without_io()?;
             if intcode.memory[0] == 19690720 {
                 println!("{}", noun * 100 + verb);

// day_5.rs diff
-use crate::runner::Intcode;
+use crate::runner::{HaltReason, Intcode};
 use color_eyre::eyre;

-pub fn exec(mut intcode: Intcode) -> eyre::Result<()> {
-    println!("Enter 1 for part 1 and 5 for part 2.");
-    intcode.execute()?;
+pub fn part_1(intcode: Intcode) -> eyre::Result<()> {
+    exec(intcode, 1)
+}
+
+pub fn part_2(intcode: Intcode) -> eyre::Result<()> {
+    exec(intcode, 5)
+}
+
+fn exec(mut intcode: Intcode, input: i32) -> eyre::Result<()> {
+    let mut input = Some(input);
+    loop {
+        match intcode.execute(input.take())? {
+            HaltReason::NormalHalt => break,
+            HaltReason::GaveOutput(output) => println!("{}", output),
+            HaltReason::NeedInput => {
+                eyre::bail!("Invalid second request for input; input already given.")
+            }
+        }
+    }
     Ok(())
 }

# Cargo.toml diff
...
 strum = "0.23"
 strum_macros = "0.23"
 argh = "0.1.7"
+itertools = "0.10"

// day_7.rs
use crate::runner::{HaltReason, Intcode};
use color_eyre::eyre;
use itertools::Itertools;

pub fn part_1(intcode: Intcode) -> eyre::Result<()> {
    let mut highest_signal = i32::MIN;
    for phase_setting in (0..=4).permutations(5).map(|vec| match vec[..] {
        [a, b, c, d, e] => [a, b, c, d, e],
        _ => unreachable!(),
    }) {
        highest_signal = highest_signal.max(run_amplifiers(intcode.clone(), phase_setting)?);
    }
    println!("{}", highest_signal);
    Ok(())
}

fn run_amplifiers(intcode: Intcode, phase_setting: [i32; 5]) -> eyre::Result<i32> {
    let mut amplifiers = [(); 5].map(|_| intcode.clone());
    let mut outputs = [i32::MIN; 5];
    for i in 0..5 {
        let mut input = Some(phase_setting[i]);
        loop {
            match amplifiers[i].execute(input.take())? {
                HaltReason::NormalHalt => break,
                HaltReason::GaveOutput(output) => {
                    outputs[i] = output;
                }
                HaltReason::NeedInput => {
                    input = Some(outputs.get(i - 1).copied().unwrap_or(0));
                }
            }
        }
    }
    Ok(outputs[4])
}

> cargo run -- d7p1 inputs/day7
warning: unused import: `std::io`
 --> src/main.rs:9:5
  |
9 | use std::io;
  |     ^^^^^^^
  |
  = note: `#[warn(unused_imports)]` (part of `#[warn(unused)]`) on by default

warning: `intcode` (bin "intcode") generated 1 warning (run `cargo fix --bin "intcode" -p intcode` to apply 1 suggestion)
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.04s
     Running `target/debug/intcode d7p1 inputs/day7`
Reading from "inputs/day7" ...
Successfully read and parsed intcode.
The application panicked (crashed).
Message:  attempt to subtract with overflow
Location: src/day_7.rs:29

Backtrace omitted.
Run with RUST_BACKTRACE=1 environment variable to display it.
Run with RUST_BACKTRACE=full to include source snippets.

                 HaltReason::NeedInput => {
-                    input = Some(outputs.get(i - 1).copied().unwrap_or(0));
+                    input = Some(outputs.get(i.wrapping_sub(1)).copied().unwrap_or(0));
                 }

// day_7.rs
pub fn part_2(intcode: Intcode) -> eyre::Result<()> {
    let mut highest_signal = i32::MIN;
    for phase_setting in (5..=9).permutations(5).map(|vec| match vec[..] {
        [a, b, c, d, e] => [a, b, c, d, e],
        _ => unreachable!(),
    }) {
        highest_signal = highest_signal.max(run_amplifiers_looped(intcode.clone(), phase_setting)?);
    }
    println!("{}", highest_signal);
    Ok(())
}

fn run_amplifiers_looped(intcode: Intcode, mut phase_setting: [i32; 5]) -> eyre::Result<i32> {
    let mut amplifiers = [(); 5].map(|_| intcode.clone());
    phase_setting.rotate_left(1);
    let mut outputs = phase_setting.map(|phase| Some(phase).into_iter().collect::<VecDeque<_>>());
    outputs[4].push_back(0);
    'amp_loop: for i in (0..5).cycle() {
        let _: usize = i;
        loop {
            let previous_amp = i.checked_sub(1).unwrap_or(4);
            let input = outputs[previous_amp].pop_front();
            match amplifiers[i].execute(input)? {
                HaltReason::NormalHalt if i == 4 => break 'amp_loop,
                HaltReason::NormalHalt => break,
                HaltReason::GaveOutput(output) => outputs[i].push_back(output),
                HaltReason::NeedInput if outputs[previous_amp].is_empty() => break,
                HaltReason::NeedInput => {},
            }
        }
    }
    Ok(outputs[4].pop_front().unwrap())
}

// runner.rs diff
...
 #[derive(Debug, Clone)]
 pub struct Intcode {
-    pub memory: Vec<i32>,
+    pub memory: Vec<i64>,
     current: usize,
+    relative_base: i64,
 }

 impl FromStr for Intcode {
...
         Ok(Self {
             memory: vec,
             current: 0,
+            relative_base: 0,
         })
     }
 }
...
         }
         Ok(())
     }
-    pub fn execute(&mut self, mut input: Option<i32>) -> eyre::Result<HaltReason> {
+    pub fn execute(&mut self, mut input: Option<i64>) -> eyre::Result<HaltReason> {
         loop {
-            match get_opcode(self.memory[self.current]) {
+            match get_opcode(self.access_memory(self.current)) {
                 1 => {
                     let [param_1, param_2] = self.get_param_values::<2>();
-                    let out_index = self.memory[self.current + 3] as usize;
-                    self.memory[out_index] = param_1 + param_2;
+                    let out_index = self.get_param_value_as_index(3);
+                    *self.access_memory_mut(out_index) = param_1 + param_2;
                     self.current += 4;
                 }
                 2 => {
                     let [param_1, param_2] = self.get_param_values::<2>();
-                    let out_index = self.memory[self.current + 3] as usize;
-                    self.memory[out_index] = param_1 * param_2;
+                    let out_index = self.get_param_value_as_index(3);
+                    *self.access_memory_mut(out_index) = param_1 * param_2;
                     self.current += 4;
                 }

                 3 => {
                     if let Some(input) = input.take() {
-                        let out_index = self.memory[self.current + 1] as usize;
-                        self.memory[out_index] = input;
+                        let out_index = self.get_param_value_as_index(1);
+                        *self.access_memory_mut(out_index) = input;
                         self.current += 2;
                     } else {
                         break Ok(HaltReason::NeedInput);
...
                 7 => {
                     let [param_1, param_2] = self.get_param_values::<2>();
-                    let out_index = self.memory[self.current + 3] as usize;
-                    self.memory[out_index] = (param_1 < param_2) as i32;
+                    let out_index = self.get_param_value_as_index(3);
+                    *self.access_memory_mut(out_index) = (param_1 < param_2) as i64;
                     self.current += 4;
                 }
                 8 => {
                     let [param_1, param_2] = self.get_param_values::<2>();
-                    let out_index = self.memory[self.current + 3] as usize;
-                    self.memory[out_index] = (param_1 == param_2) as i32;
+                    let out_index = self.get_param_value_as_index(3);
+                    *self.access_memory_mut(out_index) = (param_1 == param_2) as i64;
                     self.current += 4;
                 }

+                9 => {
+                    let [param] = self.get_param_values::<1>();
+                    self.relative_base += param;
+                    self.current += 2;
+                }
+
                 99 => {
                     break Ok(HaltReason::NormalHalt);
                 }
...
         }
     }

-    fn get_param_values<const N: usize>(&self) -> [i32; N] {
+    fn access_memory(&self, index: usize) -> i64 {
+        self.memory.get(index).copied().unwrap_or(0)
+    }
+
+    fn access_memory_mut(&mut self, index: usize) -> &mut i64 {
+        if index >= self.memory.len() {
+            let additional_items = index - self.memory.len() + 1;
+            self.memory
+                .extend(std::iter::repeat(0).take(additional_items));
+        }
+        self.memory.get_mut(index).unwrap()
+    }
+
+    fn get_param_values<const N: usize>(&self) -> [i64; N] {
         let mut param_modes = get_param_modes(self.memory[self.current]);
         let mut i = self.current;
         [(); N]
...
             .map(|i| {
                 let mode = param_modes.next().unwrap();
                 match mode {
-                    0 => self.memory[self.memory[i] as usize],
-                    1 => self.memory[i],
+                    0 => self.access_memory(self.access_memory(i) as usize),
+                    1 => self.access_memory(i),
+                    2 => self.access_memory((self.access_memory(i) + self.relative_base) as usize),
                     other => panic!("Unknown parameter mode {}.", other),
                 }
             })
     }
+
+    fn get_param_value_as_index(&self, offset: usize) -> usize {
+        let param_mode = get_param_modes(self.memory[self.current]).nth(offset - 1).unwrap();
+        let i = self.current + offset;
+        match param_mode {
+            0 => self.access_memory(i) as usize,
+            2 => (self.access_memory(i) + self.relative_base) as usize,
+            1 => panic!("Cannot access index when parameter mode is 1."),
+
+            other => panic!("Unknown parameter mode {}.", other),
+        }
+    }
 }

 #[inline]
-fn get_opcode(num: i32) -> i32 {
+fn get_opcode(num: i64) -> i64 {
     num % 100
 }

-fn get_param_modes(num: i32) -> impl Iterator<Item = i32> {
+fn get_param_modes(num: i64) -> impl Iterator<Item = i64> {
     use std::iter;
     iter::repeat(()).scan(num / 100, |state, _| {
         let out = *state % 10;
...
 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
 pub enum HaltReason {
-    GaveOutput(i32),
+    GaveOutput(i64),
     NeedInput,
     NormalHalt,
 }

// day_5.rs diff
...
-fn exec(mut intcode: Intcode, input: i32) -> eyre::Result<()> {
+fn exec(mut intcode: Intcode, input: i64) -> eyre::Result<()> {
     let mut input = Some(input);
     loop {

// day_7.rs diff
...
 pub fn part_1(intcode: Intcode) -> eyre::Result<()> {
-    let mut highest_signal = i32::MIN;
+    let mut highest_signal = i64::MIN;
     for phase_setting in (0..=4).permutations(5).map(|vec| match vec[..] {
         [a, b, c, d, e] => [a, b, c, d, e],
         _ => unreachable!(),
...
-fn run_amplifiers(intcode: Intcode, phase_setting: [i32; 5]) -> eyre::Result<i32> {
+fn run_amplifiers(intcode: Intcode, phase_setting: [i64; 5]) -> eyre::Result<i64> {
     let mut amplifiers = [(); 5].map(|_| intcode.clone());
-    let mut outputs = [i32::MIN; 5];
+    let mut outputs = [i64::MIN; 5];
     for i in 0..5 {
         let mut input = Some(phase_setting[i]);
         loop {
...
 pub fn part_2(intcode: Intcode) -> eyre::Result<()> {
-    let mut highest_signal = i32::MIN;
+    let mut highest_signal = i64::MIN;
     for phase_setting in (5..=9).permutations(5).map(|vec| match vec[..] {
         [a, b, c, d, e] => [a, b, c, d, e],
...
-fn run_amplifiers_looped(intcode: Intcode, mut phase_setting: [i32; 5]) -> eyre::Result<i32> {
+fn run_amplifiers_looped(intcode: Intcode, mut phase_setting: [i64; 5]) -> eyre::Result<i64> {
     let mut amplifiers = [(); 5].map(|_| intcode.clone());
     phase_setting.rotate_left(1);

// day_9.rs
use crate::runner::{HaltReason, Intcode};
use color_eyre::eyre;

pub fn part_1(mut intcode: Intcode) -> eyre::Result<()> {
    let mut input = Some(1);
    loop {
        match intcode.execute(input.take())? {
            HaltReason::NormalHalt => break,
            HaltReason::GaveOutput(output) => println!("{}", output),
            HaltReason::NeedInput => {
                eyre::bail!("Invalid second request for input; input already given.")
            }
        }
    }
    Ok(())
}

// day_9.rs diff
...
-pub fn part_1(mut intcode: Intcode) -> eyre::Result<()> {
-    let mut input = Some(1);
+pub fn part_1(intcode: Intcode) -> eyre::Result<()> {
+    exec(intcode, 1)
+}
+
+pub fn part_2(intcode: Intcode) -> eyre::Result<()> {
+    exec(intcode, 2)
+}
+
+fn exec(mut intcode: Intcode, input: i64) -> eyre::Result<()> {
+    let mut input = Some(input);
     loop {
         match intcode.execute(input.take())? {
             HaltReason::NormalHalt => break,

// day_11.rs
use crate::runner::{HaltReason, Intcode};
use color_eyre::eyre;
use eyre::bail;
use std::collections::HashSet;

pub fn part_1(mut intcode: Intcode) -> eyre::Result<()> {
    let mut map = HashSet::<(i32, i32)>::new();
    let mut visited_nodes = HashSet::<(i32, i32)>::new();
    let mut current_position = (0, 0);
    visited_nodes.insert(current_position);
    let mut current_orientation = (0, -1);
    let mut input = None;
    loop {
        match intcode.execute(input.take())? {
            HaltReason::NormalHalt => break,
            HaltReason::GaveOutput(color) => {
                if color == 1 {
                    map.insert(current_position);
                } else {
                    map.remove(&current_position);
                }
                visited_nodes.insert(current_position);

                let turn = match intcode.execute(None)? {
                    HaltReason::GaveOutput(output) => output,
                    HaltReason::NormalHalt => bail!("Unexpected halt. Expected to recieve turn."),
                    HaltReason::NeedInput => {
                        bail!("Unexpected request for input. Expected to recieve turn.")
                    }
                };

                if turn == 0 {
                    current_orientation = turn_left(current_orientation);
                } else {
                    current_orientation = turn_right(current_orientation);
                }
                current_position = add(current_orientation, current_position);
            }
            HaltReason::NeedInput => {
                input = Some(if map.contains(&current_position) {
                    1
                } else {
                    0
                });
            }
        }
    }
    println!("{}", visited_nodes.len());
    Ok(())
}

fn add(a: (i32, i32), b: (i32, i32)) -> (i32, i32) {
    (a.0 + b.0, a.1 + b.1)
}

fn turn_left((x, y): (i32, i32)) -> (i32, i32) {
    (y, -x)
}

fn turn_right((x, y): (i32, i32)) -> (i32, i32) {
    (-y, x)
}

// day_11.rs
pub fn part_2(mut intcode: Intcode) -> eyre::Result<()> {
    let mut map = HashSet::<(i32, i32)>::new();
    let mut current_position = (0, 0);
    map.insert(current_position);
    let mut current_orientation = (0, -1);
    let mut input = None;
    loop {
        match intcode.execute(input.take())? {
            HaltReason::NormalHalt => break,
            HaltReason::GaveOutput(color) => {
                if color == 1 {
                    map.insert(current_position);
                } else {
                    map.remove(&current_position);
                }

                let turn = match intcode.execute(None)? {
                    HaltReason::GaveOutput(output) => output,
                    HaltReason::NormalHalt => bail!("Unexpected halt. Expected to recieve turn."),
                    HaltReason::NeedInput => {
                        bail!("Unexpected request for input. Expected to recieve turn.")
                    }
                };

                if turn == 0 {
                    current_orientation = turn_left(current_orientation);
                } else {
                    current_orientation = turn_right(current_orientation);
                }
                current_position = add(current_orientation, current_position);
            }
            HaltReason::NeedInput => {
                input = Some(if map.contains(&current_position) {
                    1
                } else {
                    0
                });
            }
        }
    }
    print_map(&map);
    Ok(())
}

fn print_map(map: &HashSet<(i32, i32)>) {
    let min_x = map.iter().copied().min_by_key(|&(x, _y)| x).unwrap().0;
    let max_x = map.iter().copied().max_by_key(|&(x, _y)| x).unwrap().0;
    let min_y = map.iter().copied().min_by_key(|&(_x, y)| y).unwrap().1;
    let max_y = map.iter().copied().max_by_key(|&(_x, y)| y).unwrap().1;
    for y in min_y..=max_y {
        for x in min_x..=max_x {
            let ch = if map.contains(&(x, y)) { '█' } else { ' ' };
            print!("{}", ch);
        }
        println!()
    }
}

// day_13.rs

pub fn part_1(mut intcode: Intcode) -> eyre::Result<()> {
    let mut block_tiles = HashSet::<(i64, i64)>::new();

    loop {
        match intcode.execute(None)? {
            HaltReason::NormalHalt => break,
            HaltReason::GaveOutput(x) => {
                let y = match intcode.execute(None)? {
                    HaltReason::GaveOutput(output) => output,
                    HaltReason::NormalHalt => {
                        bail!("Unexpected halt. Expected to recieve y coordinate.")
                    }
                    HaltReason::NeedInput => {
                        bail!("Unexpected request for input. Expected to recieve y coordinate.")
                    }
                };

                let tile_id = match intcode.execute(None)? {
                    HaltReason::GaveOutput(output) => output,
                    HaltReason::NormalHalt => {
                        bail!("Unexpected halt. Expected to recieve tile id.")
                    }
                    HaltReason::NeedInput => {
                        bail!("Unexpected request for input. Expected to recieve tile id.")
                    }
                };

                if tile_id == 2 {
                    block_tiles.insert((x, y));
                }
            }
            HaltReason::NeedInput => bail!("Unexpected request for input."),
        }
    }
    println!("{}", block_tiles.len());
    Ok(())
}

// day_13.rs new additions
pub fn part_2(mut intcode: Intcode) -> eyre::Result<()> {
    intcode.memory[0] = 2;

    let mut tiles = HashMap::<(i64, i64), Tile>::new();
    let mut score = i64::MIN;
    let mut input = None;
    let mut last_32_moves: u32 = u32::MAX;
    loop {
        match intcode.execute(input.take())? {
            HaltReason::NormalHalt => break,
            HaltReason::GaveOutput(x) => {
                let y = match intcode.execute(None)? {
                    HaltReason::GaveOutput(output) => output,
                    HaltReason::NormalHalt => {
                        bail!("Unexpected halt. Expected to recieve y coordinate.")
                    }
                    HaltReason::NeedInput => {
                        bail!("Unexpected request for input. Expected to recieve y coordinate.")
                    }
                };

                let tile_id = match intcode.execute(None)? {
                    HaltReason::GaveOutput(output) => output,
                    HaltReason::NormalHalt => {
                        bail!("Unexpected halt. Expected to recieve tile id.")
                    }
                    HaltReason::NeedInput => {
                        bail!("Unexpected request for input. Expected to recieve tile id.")
                    }
                };

                if let (-1, 0) = (x, y) {
                    score = tile_id;
                } else {
                    let tile =
                        Tile::from_id(tile_id).ok_or(eyre!("Invalid tile id {}", tile_id))?;
                    tiles.insert((x, y), tile);
                }
            }
            HaltReason::NeedInput => {
                use std::{thread::sleep, time::Duration};
                display_tiles(&tiles);
                println!("Score: {}", score);
                sleep(Duration::from_millis(
                    (4_u64 * (last_32_moves.count_ones() as u64)).max(8),
                ));

                let paddle_x = tiles
                    .iter()
                    .find(|&(_coord, &tile)| tile == Tile::Paddle)
                    .map(|(&(x, _y), _tile)| x)
                    .unwrap();
                let (ball_x, ball_y) = tiles
                    .iter()
                    .find(|&(_coord, &tile)| tile == Tile::Ball)
                    .map(|(&coord, _tile)| coord)
                    .unwrap();
                last_32_moves <<= 1;
                last_32_moves |= is_near_block(&tiles, (ball_x, ball_y)) as u32;
                input = Some(ball_x - paddle_x);
            }
        }
    }
    display_tiles(&tiles);
    println!("Final score: {}", score);
    Ok(())
}

fn is_near_block(map: &HashMap<(i64, i64), Tile>, (x, y): (i64, i64)) -> bool {
    let neighbors = [
        (x + 1, y + 1),
        (x + 1, y - 1),
        (x - 1, y - 1),
        (x - 1, y + 1),
        (x + 1, y),
        (x, y - 1),
        (x - 1, y),
        (x, y + 1),
    ];
    neighbors
        .iter()
        .filter_map(|coord| map.get(coord))
        .any(|&tile| tile == Tile::Block)
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Tile {
    Empty,
    Wall,
    Block,
    Paddle,
    Ball,
}

impl Default for Tile {
    fn default() -> Self {
        Self::Empty
    }
}

impl Tile {
    fn from_id(id: i64) -> Option<Self> {
        Some(match id {
            0 => Tile::Empty,
            1 => Tile::Wall,
            2 => Tile::Block,
            3 => Tile::Paddle,
            4 => Tile::Ball,
            _ => None?,
        })
    }
    fn to_char(self) -> char {
        use Tile::*;
        match self {
            Empty => '░',
            Wall => '█',
            Block => '▓',
            Paddle => '—',
            Ball => 'o',
        }
    }
}

fn display_tiles(tiles: &HashMap<(i64, i64), Tile>) {
    let min_x = tiles.keys().copied().min_by_key(|&(x, _y)| x).unwrap().0;
    let max_x = tiles.keys().copied().max_by_key(|&(x, _y)| x).unwrap().0;
    let min_y = tiles.keys().copied().min_by_key(|&(_x, y)| y).unwrap().1;
    let max_y = tiles.keys().copied().max_by_key(|&(_x, y)| y).unwrap().1;
    for y in min_y..=max_y {
        for x in min_x..=max_x {
            let tile = tiles.get(&(x, y)).copied().unwrap_or_default();
            print!("{}", tile.to_char());
        }
        println!()
    }
}

// day_15.rs
use crate::runner::{HaltReason, Intcode};
use color_eyre::eyre;
use eyre::bail;
use std::collections::{HashMap, VecDeque};
use std::ops::Not;

pub fn part_1(mut intcode: Intcode) -> eyre::Result<()> {
    let mut map = HashMap::<(i64, i64), bool>::new();
    let mut sources = HashMap::<(i64, i64), Option<((i64, i64), Movement)>>::new();
    let mut costs = HashMap::<(i64, i64), u64>::new();
    let mut frontier = VecDeque::new();
    map.insert((0, 0), false);
    costs.insert((0, 0), 0);
    sources.insert((0, 0), None);
    frontier.push_back((0, 0));
    let mut last_accessed = (0, 0);

    while frontier.is_empty().not() {
        let to_access = frontier.pop_front().unwrap();

        while let Some((source_coord, movement)) = sources[&last_accessed] {
            make_movement(&mut intcode, movement.reverse())?;
            last_accessed = source_coord;
        }

        let mut source_stack = Vec::new();
        let mut to_access_parent = to_access;
        while let Some((source_coord, movement)) = sources[&to_access_parent] {
            source_stack.push(movement);
            to_access_parent = source_coord;
        }
        for movement in source_stack.into_iter().rev() {
            make_movement(&mut intcode, movement)?;
        }
        last_accessed = to_access;

        for movement in Movement::all() {
            let new_coord = add_movement(to_access, movement);
            if let Some(true) = map.get(&new_coord) {
                continue;
            }

            let new_cost = costs[&to_access] + 1;
            match make_movement(&mut intcode, movement)? {
                0 => {
                    map.insert(new_coord, true);
                }
                1 => {
                    if costs.contains_key(&new_coord).not() {
                        costs.insert(new_coord, new_cost);
                        map.insert(new_coord, false);
                        frontier.push_back(new_coord);
                        sources.insert(new_coord, Some((to_access, movement)));
                    }
                    make_movement(&mut intcode, movement.reverse())?;
                }
                2 => {
                    println!("Distance to oxygen system: {}", new_cost);
                    return Ok(());
                }
                other @ _ => bail!("Unexpected status {} given by intcode program", other),
            };
        }
    }
    bail!("Oxygen system not found")
}

fn make_movement(intcode: &mut Intcode, movement: Movement) -> eyre::Result<i64> {
    match intcode.execute(Some(movement.to_int()))? {
        HaltReason::GaveOutput(output) => Ok(output),
        HaltReason::NormalHalt => bail!("Unexpected halt of intcode program."),
        HaltReason::NeedInput => bail!("Invalid request of input, input already given."),
    }
}

fn add_movement((x, y): (i64, i64), movement: Movement) -> (i64, i64) {
    use Movement::*;
    match movement {
        North => (x, y - 1),
        South => (x, y + 1),
        West => (x - 1, y),
        East => (x + 1, y),
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Movement {
    North,
    South,
    East,
    West,
}

impl Movement {
    fn to_int(self) -> i64 {
        use Movement::*;
        match self {
            North => 1,
            South => 2,
            West => 3,
            East => 4,
        }
    }

    fn all() -> [Self; 4] {
        use Movement::*;
        [North, South, East, West]
    }

    fn reverse(self) -> Self {
        use Movement::*;
        match self {
            North => South,
            South => North,
            East => West,
            West => East,
        }
    }
}

     while frontier.is_empty().not() {
         let to_access = frontier.pop_front().unwrap();
-
-        while let Some((source_coord, movement)) = sources[&last_accessed] {
-            make_movement(&mut intcode, movement.reverse())?;
-            last_accessed = source_coord;
-        }
-
-        let mut source_stack = Vec::new();
-        let mut to_access_parent = to_access;
-        while let Some((source_coord, movement)) = sources[&to_access_parent] {
-            source_stack.push(movement);
-            to_access_parent = source_coord;
-        }
-        for movement in source_stack.into_iter().rev() {
-            make_movement(&mut intcode, movement)?;
-        }
+        move_to_new_coord(&mut intcode, &sources, last_accessed, to_access)?;
         last_accessed = to_access;
...
+fn move_to_new_coord(
+    intcode: &mut Intcode,
+    sources: &HashMap<(i64, i64), Option<((i64, i64), Movement)>>,
+    mut last_accessed: (i64, i64),
+    to_access: (i64, i64),
+) -> eyre::Result<()> {
+    while let Some((source_coord, movement)) = sources[&last_accessed] {
+        make_movement(intcode, movement.reverse())?;
+        last_accessed = source_coord;
+    }
+
+    let mut source_stack = Vec::new();
+    let mut to_access_parent = to_access;
+    while let Some((source_coord, movement)) = sources[&to_access_parent] {
+        source_stack.push(movement);
+        to_access_parent = source_coord;
+    }
+    for movement in source_stack.into_iter().rev() {
+        make_movement(intcode, movement)?;
+    }
+    Ok(())
+}
+
 fn make_movement(intcode: &mut Intcode, movement: Movement) -> eyre::Result<i64> {

// day_15.rs new additions
pub fn part_2(mut intcode: Intcode) -> eyre::Result<()> {
    let mut map = HashMap::<(i64, i64), bool>::new();
    let mut sources = HashMap::<(i64, i64), Option<((i64, i64), Movement)>>::new();
    let mut frontier = VecDeque::new();
    let mut oxygen_system_distances = HashMap::<(i64, i64), u64>::new();
    map.insert((0, 0), false);
    sources.insert((0, 0), None);
    frontier.push_back((0, 0));
    let mut last_accessed = (0, 0);
    let mut oxygen_system = None;

    'outer: while frontier.is_empty().not() {
        let to_access = frontier.pop_front().unwrap();
        move_to_new_coord(&mut intcode, &sources, last_accessed, to_access)?;
        last_accessed = to_access;

        for movement in Movement::all() {
            let new_coord = add_movement(to_access, movement);
            if let Some(true) = map.get(&new_coord) {
                continue;
            }

            let status = make_movement(&mut intcode, movement)?;
            match status {
                0 => {
                    map.insert(new_coord, true);
                }
                1 | 2 => {
                    if sources.contains_key(&new_coord).not() {
                        map.insert(new_coord, false);
                        frontier.push_back(new_coord);
                        sources.insert(new_coord, Some((to_access, movement)));
                        if oxygen_system.is_some() {
                            let new_distance = oxygen_system_distances[&to_access] + 1;
                            oxygen_system_distances.insert(new_coord, new_distance);
                        }
                    }
                    make_movement(&mut intcode, movement.reverse())?; // C
                    if status == 2 && oxygen_system.is_none() {
                        oxygen_system = Some(new_coord);
                        frontier.drain(..);
                        sources.drain();
                        map.drain();
                        frontier.push_back(new_coord);
                        oxygen_system_distances.insert(new_coord, 1); // A
                        sources.insert(new_coord, None);
                        map.insert(new_coord, false);
                        last_accessed = new_coord; // B
                        continue 'outer;
                    }
                }
                other @ _ => bail!("Unexpected status {} given by intcode program", other),
            };
        }
    }
    println!(
        "Time taken to fill area with oxygen is {} minutes.",
        oxygen_system_distances.values().copied().max().unwrap()
    );
    Ok(())
}

// day_17.rs (new file)
use crate::runner::{HaltReason, Intcode};
use color_eyre::eyre;
use std::collections::{HashMap, HashSet, VecDeque};
use std::ops::Not;

pub fn part_1(mut intcode: Intcode) -> eyre::Result<()> {
    let mut output = String::new();
    loop {
        match intcode.execute(None)? {
            HaltReason::NormalHalt => break,
            HaltReason::GaveOutput(int) => {
                let ch = char::from(int as u8);
                output.push(ch);
            }
            HaltReason::NeedInput => {
                eyre::bail!("Invalid request for input from intcode program.")
            }
        }
    }
    let width = output.trim().lines().next().unwrap().len();
    let map = output
        .chars()
        .filter(|c| ['.', '#', '^', 'v', '>', '<'].contains(c))
        .enumerate()
        .map(|(i, c)| (((i % width) as i32, (i / width) as i32), c != '.'))
        .collect::<HashMap<_, _>>();
    let mut alignment_parameter_sum = 0;
    for (&(x, y), &c) in map.iter() {
        if c {
            let neighbors = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)];
            if neighbors
                .into_iter()
                .all(|neighbor| map.get(&neighbor) == Some(&true))
            {
                alignment_parameter_sum += x * y;
            }
        }
    }
    println!(
        "The sum of the alignment parameters is {}.",
        alignment_parameter_sum
    );
    Ok(())
}

// day_17.rs new additions
pub fn part_2(mut intcode: Intcode) -> eyre::Result<()> {
    intcode.memory[0] = 2;
    let mut last_character = '\0';
    let mut output = String::new();
    loop {
        match intcode.execute(None)? {
            HaltReason::NormalHalt => eyre::bail!("Unexpected halt of intcode program."),
            HaltReason::NeedInput => eyre::bail!("Invalid request for input."),
            HaltReason::GaveOutput(int) => {
                let ch = char::from(int as u8);
                output.push(ch);
                if ch == '\n' && last_character == '\n' {
                    break;
                }
                last_character = ch;
            }
        }
    }
    let (map, mut robot_coord, mut robot_orientation) = make_map(output);
    let end_coord = map
        .iter()
        .find(|(coord, vec)| vec.len() == 1 && **coord != robot_coord)
        .map(|(coord, _vec)| coord)
        .copied()
        .unwrap();
    let mut instructions = Vec::<Instruction>::new();
    while robot_coord != end_coord {
        if map[&robot_coord].contains(&robot_orientation) {
            robot_coord = add_orientation(robot_coord, robot_orientation);

            if instructions
                .last()
                .map(|instruction| matches!(instruction, Instruction::Forward(_)).not())
                .unwrap_or(false)
            {
                instructions.push(Instruction::Forward(0));
            }
            match instructions.last_mut().unwrap() {
                Instruction::Forward(ref mut x) => {
                    *x += 1;
                }
                _ => unreachable!(),
            }
        } else {
            let final_orientation = map[&robot_coord]
                .iter()
                .find(|&&orientation| orientation != robot_orientation.reverse())
                .copied()
                .unwrap();
            if robot_orientation.left() == final_orientation {
                robot_orientation = final_orientation;
                instructions.push(Instruction::Left);
            } else if robot_orientation.right() == final_orientation {
                robot_orientation = final_orientation;
                instructions.push(Instruction::Right);
            } else {
                eyre::bail!("Broken input.");
            }
        }
    }
    let mut marking = vec![None; instructions.len()];
    let a = mark_common(&instructions, &mut marking, 'A')?;
    let b = mark_common(&instructions, &mut marking, 'B')?;
    let c = mark_common(&instructions, &mut marking, 'C')?;
    eyre::ensure!(
        marking.iter().all(Option::is_some),
        "Could not mark all instructions into movement functions."
    );
    marking.dedup();
    let main_routine = marking
        .iter()
        .copied()
        .map(Option::unwrap)
        .flat_map(|ch| [',', ch])
        .skip(1)
        .chain(Some('\n'))
        .map(|ch| ch as u8);
    let function_a = format_functions(a);
    let function_b = format_functions(b);
    let function_c = format_functions(c);
    let interactive_display = [b'n', b'\n'];
    let mut input_queue = main_routine
        .chain(function_a)
        .chain(function_b)
        .chain(function_c)
        .chain(interactive_display)
        .collect::<VecDeque<_>>();

    let mut last_output = 0;
    let mut input = None;
    loop {
        match intcode.execute(input.take())? {
            HaltReason::NormalHalt => {
                break;
            }
            HaltReason::NeedInput => {
                if input_queue.is_empty() {
                    eyre::bail!("No input left!")
                }
                let first_element = input_queue.pop_front();
                input = first_element.map(i64::from);
                print!("{}", first_element.unwrap() as char);
            }
            HaltReason::GaveOutput(int) => {
                if let Ok(ch) = u8::try_from(int) {
                    print!("{}", ch as char);
                }
                last_output = int;
            }
        }
    }
    println!("Total dust collected by vaccum robot: {}", last_output);
    Ok(())
}

fn format_functions(function: &[Instruction]) -> impl Iterator<Item = u8> + '_ {
    function
        .iter()
        .copied()
        .flat_map(|instruction| match instruction {
            Instruction::Left => [b',', b'L'].to_vec(),
            Instruction::Right => [b',', b'R'].to_vec(),
            Instruction::Forward(n) => format!(",{}", n).as_bytes().to_vec(),
        })
        .skip(1)
        .chain(Some(b'\n'))
}

fn mark_common<'a, 'b>(
    instructions: &'a [Instruction],
    marking: &'b mut [Option<char>],
    marker: char,
) -> eyre::Result<&'a [Instruction]> {
    let start = marking
        .iter()
        .enumerate()
        .find(|(_i, opt)| opt.is_none())
        .map(|(i, _opt)| i)
        .unwrap();
    let empty_len = marking
        .iter()
        .skip_while(|opt| opt.is_some())
        .take_while(|opt| opt.is_none())
        .count();
    for to_consider_len in (6..=10).rev() {
        if to_consider_len > empty_len {
            continue;
        }
        if (empty_len - to_consider_len < 6) && (empty_len != to_consider_len) {
            continue;
        }
        let pattern = &instructions[start..][..to_consider_len];
        let window_starts = instructions[start..]
            .windows(to_consider_len)
            .enumerate()
            .filter(|&(i, window)| {
                marking[start..][i..][..to_consider_len]
                    .iter()
                    .all(Option::is_none)
                    && window == pattern
            })
            .map(|(i, _window)| i)
            .collect::<Vec<usize>>();
        if window_starts.len() > 2 {
            for i in window_starts {
                marking[start..][i..][..to_consider_len].fill(Some(marker));
            }
            return Ok(pattern);
        }
    }
    eyre::bail!("No suitable marking found")
}

fn make_map(
    string: String,
) -> (
    HashMap<(i32, i32), Vec<Orientation>>,
    (i32, i32),
    Orientation,
) {
    let width = string.trim().lines().next().unwrap().len();
    let (robot_coord, robot_orientation) = string
        .chars()
        .filter(|ch| ['.', '#', '^', 'v', '>', '<'].contains(ch))
        .enumerate()
        .map(|(i, ch)| (((i % width) as i32, (i / width) as i32), ch))
        .find(|(_coord, ch)| ['^', 'v', '>', '<'].contains(ch))
        .map(|(coord, ch)| {
            (
                coord,
                match ch {
                    '^' => Orientation::Top,
                    'v' => Orientation::Bottom,
                    '>' => Orientation::Right,
                    '<' => Orientation::Left,
                    _ => unreachable!(),
                },
            )
        })
        .unwrap();
    let coords = string
        .chars()
        .filter(|ch| ['.', '#', '^', 'v', '>', '<'].contains(ch))
        .enumerate()
        .map(|(i, ch)| (((i % width) as i32, (i / width) as i32), ch != '.'))
        .filter(|&(_coord, is_not_space)| is_not_space)
        .map(|(coord, _bool)| coord)
        .collect::<HashSet<_>>();
    let mut map = HashMap::with_capacity(coords.len());
    for coord in coords.iter().copied() {
        let mut vec = Vec::with_capacity(4);
        for orientation in Orientation::all() {
            if coords.contains(&add_orientation(coord, orientation)) {
                vec.push(orientation);
            }
        }
        map.insert(coord, vec);
    }
    (map, robot_coord, robot_orientation)
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
enum Instruction {
    Left,
    Right,
    Forward(u8),
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
enum Orientation {
    Top,
    Bottom,
    Left,
    Right,
}

fn add_orientation((x, y): (i32, i32), orientation: Orientation) -> (i32, i32) {
    use Orientation::*;
    match orientation {
        Top => (x, y - 1),
        Bottom => (x, y + 1),
        Left => (x - 1, y),
        Right => (x + 1, y),
    }
}

impl Orientation {
    fn left(self) -> Self {
        use Orientation::*;
        match self {
            Top => Left,
            Left => Bottom,
            Bottom => Right,
            Right => Top,
        }
    }

    fn right(self) -> Self {
        use Orientation::*;
        match self {
            Top => Right,
            Left => Top,
            Bottom => Left,
            Right => Bottom,
        }
    }

    fn reverse(self) -> Self {
        use Orientation::*;
        match self {
            Top => Bottom,
            Left => Right,
            Bottom => Top,
            Right => Left,
        }
    }

    fn all() -> [Self; 4] {
        use Orientation::*;
        [Top, Left, Bottom, Right]
    }
}