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
126
127
128
129
130
131
132
133
134
135
|
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)]
pub 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 parse(fh: std::fs::File) -> anyhow::Result<Vec<Op>> {
crate::util::parse::lines(fh)
.map(|line| line.parse())
.collect()
}
pub fn part1(opcodes: Vec<Op>) -> anyhow::Result<i64> {
let (acc, success) = run(&opcodes)?;
if success {
return Err(anyhow::anyhow!("unexpectedly succeeded"));
}
Ok(acc)
}
pub fn part2(opcodes: Vec<Op>) -> anyhow::Result<i64> {
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 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;
}
}
}
}
}
#[test]
fn test() {
assert_eq!(
part1(parse(crate::util::data(2020, 8).unwrap()).unwrap()).unwrap(),
1928
);
assert_eq!(
part2(parse(crate::util::data(2020, 8).unwrap()).unwrap()).unwrap(),
1319
);
}
|
