1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
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<Self, Self::Err> {
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<Self, Self::Err> {
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<i64> {
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<i64> {
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<Vec<Op>> {
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;
}
}
}
}
}
|
