Created
December 17, 2019 18:05
-
-
Save 0e4ef622/a66f23da48599e5804e3551aee4e4422 to your computer and use it in GitHub Desktop.
aoc 2019 day 17
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
use std::collections::*; | |
use std::borrow::Cow; | |
use rand::random; | |
pub fn part1(input: &str) -> impl std::fmt::Display { | |
let prog = input.trim().split(",").map(|x| x.parse::<i128>().unwrap()).collect::<Vec<_>>(); | |
let mut vm = ic::Icvm::new(prog); | |
vm.run(); | |
let mut map = vec![vec![]]; | |
for ch in vm.drain_outputs() { | |
if ch == 10 { | |
map.push(vec![]); | |
} else { | |
map.last_mut().unwrap().push(ch as u8); | |
} | |
} | |
map.pop(); | |
map.pop(); | |
let mut sum = 0; | |
for y in 1..map.len()-1 { | |
for x in 1..map[0].len()-1 { | |
if map[y][x] == b'#' && | |
map[y+1][x] == b'#' && | |
map[y-1][x] == b'#' && | |
map[y][x+1] == b'#' && | |
map[y][x-1] == b'#' { | |
sum += x*y; | |
} | |
} | |
} | |
sum | |
} | |
#[derive(Clone, Copy, Debug, PartialEq, Eq)] | |
enum Inst { | |
L, | |
R, | |
F(usize), | |
A, | |
B, | |
C, | |
} | |
impl Inst { | |
fn is_fn(self) -> bool { | |
use Inst::*; | |
match self { | |
L | R | F(_) => false, | |
A | B | C => true, | |
} | |
} | |
} | |
fn serialize_run(run: &[Inst]) -> String { | |
let mut result = String::new(); | |
let mut first = true; | |
for inst in run { | |
let s: Cow<'_, str> = match inst { | |
Inst::L => "L".into(), | |
Inst::R => "R".into(), | |
Inst::A => "A".into(), | |
Inst::B => "B".into(), | |
Inst::C => "C".into(), | |
Inst::F(n) => n.to_string().into(), | |
}; | |
if first { | |
first = false; | |
} else { | |
result.push(','); | |
} | |
result.push_str(&s); | |
} | |
result | |
} | |
fn get_run(map: &[Vec<u8>]) -> Vec<Inst> { | |
let (mut x, mut y) = map | |
.iter() | |
.enumerate() | |
.flat_map(|(y, v)| | |
v.iter() | |
.enumerate() | |
.find(|&(_, &c)| c == b'^') | |
.map(|(x, _)| (x, y))) | |
.next().unwrap(); | |
let mut cd = 0; // 0 = up, 1 = right, 2 = down, 3 = left | |
let mut insts = vec![]; | |
loop { | |
let above = map.get((y as isize-1) as usize).and_then(|v| v.get(x)).unwrap_or(&b'.'); | |
let below = map.get(y+1).and_then(|v| v.get(x)).unwrap_or(&b'.'); | |
let left = map.get(y).and_then(|v| v.get((x as isize-1) as usize)).unwrap_or(&b'.'); | |
let right = map.get(y).and_then(|v| v.get(x+1)).unwrap_or(&b'.'); | |
match (cd, *above, *right, *below, *left) { | |
(0, b'.', b'#', b'#', b'.') => { insts.push(Inst::R); cd = 1; } | |
(0, b'.', b'#', b'.', b'.') => { insts.push(Inst::R); cd = 1; } | |
(0, b'.', b'.', b'#', b'#') => { insts.push(Inst::L); cd = 3; } | |
(0, b'.', b'.', b'.', b'#') => { insts.push(Inst::L); cd = 3; } | |
(2, b'#', b'#', b'.', b'.') => { insts.push(Inst::L); cd = 1; } | |
(2, b'.', b'#', b'.', b'.') => { insts.push(Inst::L); cd = 1; } | |
(2, b'#', b'.', b'.', b'#') => { insts.push(Inst::R); cd = 3; } | |
(2, b'.', b'.', b'.', b'#') => { insts.push(Inst::R); cd = 3; } | |
(1, b'#', b'.', b'.', b'#') => { insts.push(Inst::L); cd = 0; } | |
(1, b'#', b'.', b'.', b'.') => { insts.push(Inst::L); cd = 0; } | |
(1, b'.', b'.', b'#', b'#') => { insts.push(Inst::R); cd = 2; } | |
(1, b'.', b'.', b'#', b'.') => { insts.push(Inst::R); cd = 2; } | |
(3, b'#', b'#', b'.', b'.') => { insts.push(Inst::R); cd = 0; } | |
(3, b'#', b'.', b'.', b'.') => { insts.push(Inst::R); cd = 0; } | |
(3, b'.', b'#', b'#', b'.') => { insts.push(Inst::L); cd = 2; } | |
(3, b'.', b'.', b'#', b'.') => { insts.push(Inst::L); cd = 2; } | |
c => panic!("bad {:?} at {} {}", c, x, y), | |
} | |
let mut count = 0; | |
loop { | |
let (nx, ny) = match cd { | |
0 => (x, (y as isize-1) as usize), | |
1 => (x+1, y), | |
2 => (x, y+1), | |
3 => ((x as isize-1) as usize, y), | |
_ => panic!("ono"), | |
}; | |
if map.get(ny).and_then(|v| v.get(nx)).unwrap_or(&b'.') == &b'#' { | |
count += 1; | |
x = nx; | |
y = ny; | |
} else { | |
break; | |
} | |
} | |
insts.push(Inst::F(count)); | |
let above = map.get((y as isize-1) as usize).and_then(|v| v.get(x)).unwrap_or(&b'.'); | |
let below = map.get(y+1).and_then(|v| v.get(x)).unwrap_or(&b'.'); | |
let left = map.get(y).and_then(|v| v.get((x as isize-1) as usize)).unwrap_or(&b'.'); | |
let right = map.get(y).and_then(|v| v.get(x+1)).unwrap_or(&b'.'); | |
match (cd, *above, *right, *below, *left) { | |
(0, b'.', b'.', b'#', b'.') | |
| (1, b'.', b'.', b'.', b'#') | |
| (2, b'#', b'.', b'.', b'.') | |
| (3, b'.', b'#', b'.', b'.') => break, | |
_ => (), | |
} | |
} | |
insts | |
} | |
fn find_fns(run: &[Inst], fns: Vec<Vec<Inst>>) -> Option<(Vec<Inst>, Vec<Vec<Inst>>)> { | |
if run.iter().all(|i| i.is_fn()) && fns.len() != 3 { return None; } | |
if fns.len() == 3 { | |
if run.iter().all(|i| i.is_fn()) && | |
serialize_run(run).len() <= 20 && | |
fns.iter().all(|v| serialize_run(&v).len() <= 20) { | |
return Some((run.to_vec(), fns)); | |
} else { | |
return None; | |
} | |
} | |
let mut iter = run.iter().enumerate().skip_while(|(_, i)| i.is_fn()).take_while(|(_, i)| !i.is_fn()); | |
let begin = iter.next().unwrap().0; | |
let end = begin + iter.count() + 1; | |
let fn_name = match fns.len() { | |
0 => Inst::A, | |
1 => Inst::B, | |
2 => Inst::C, | |
_ => panic!("baddddd"), | |
}; | |
for i in begin+1..=end { | |
let new_fn = run[begin..i].to_vec(); | |
let mut new_run = vec![]; | |
let mut run_slice = run; | |
while !run_slice.is_empty() { | |
if run_slice.len() >= new_fn.len() && run_slice[..new_fn.len()] == new_fn[..] { | |
new_run.push(fn_name); | |
run_slice = &run_slice[new_fn.len()..]; | |
} else { | |
new_run.push(run_slice[0]); | |
run_slice = &run_slice[1..]; | |
} | |
} | |
let mut new_fns = fns.clone(); | |
new_fns.push(new_fn); | |
if let Some((a, b)) = find_fns(&new_run, new_fns) { | |
return Some((a, b)); | |
} | |
} | |
return None; | |
} | |
pub fn part2(input: &str) -> impl std::fmt::Display { | |
let prog = input.trim().split(",").map(|x| x.parse::<i128>().unwrap()).collect::<Vec<_>>(); | |
let mut vm = ic::Icvm::new(prog); | |
vm.run(); | |
let mut map = vec![vec![]]; | |
for ch in vm.drain_outputs() { | |
if ch == 10 { | |
map.push(vec![]); | |
} else { | |
map.last_mut().unwrap().push(ch as u8); | |
} | |
} | |
map.pop(); | |
map.pop(); | |
let run = get_run(&map); | |
let (main, fns) = find_fns(&run, vec![]).unwrap(); | |
let main = serialize_run(&main); | |
let a = serialize_run(&fns[0]); | |
let b = serialize_run(&fns[1]); | |
let c = serialize_run(&fns[2]); | |
println!("main: {}", main); | |
println!("A: {}", a); | |
println!("B: {}", b); | |
println!("C: {}", c); | |
let mut prog = input.trim().split(",").map(|x| x.parse::<i128>().unwrap()).collect::<Vec<_>>(); | |
prog[0] = 2; | |
vm = ic::Icvm::new(prog); | |
vm.push_inputs(main.bytes().map(Into::into)); | |
vm.push_input(10); | |
vm.push_inputs(a.bytes().map(Into::into)); | |
vm.push_input(10); | |
vm.push_inputs(b.bytes().map(Into::into)); | |
vm.push_input(10); | |
vm.push_inputs(c.bytes().map(Into::into)); | |
vm.push_input(10); | |
vm.push_input(b'n' as i128); | |
vm.push_input(10); | |
vm.run(); | |
let x = vm.drain_outputs().last().unwrap(); | |
x | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment