day17.rs

use crate::intcode::{IntCode, Word};
use failure::{bail, format_err, Error};
use pathfinding::prelude::Grid;
use std::collections::VecDeque;
use std::fmt;

type Point = (usize, usize);
type Dir = (isize, isize);

#[derive(Clone, Debug, Eq, PartialEq)]
enum Op {
    Advance(usize),
    Left,
    Right,
    A,
    B,
    C,
}

impl Op {
    fn is_abc(&self) -> bool {
        self == &Op::A || self == &Op::B || self == &Op::C
    }
}

impl fmt::Display for Op {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match *self {
            Op::Advance(n) => write!(f, "{}", n),
            Op::Left => write!(f, "L"),
            Op::Right => write!(f, "R"),
            Op::A => write!(f, "A"),
            Op::B => write!(f, "B"),
            Op::C => write!(f, "C"),
        }
    }
}

#[aoc_generator(day17)]
fn input_generator(input: &str) -> Result<Vec<Word>, std::num::ParseIntError> {
    input.split(',').map(|s| s.parse::<Word>()).collect()
}

#[aoc(day17, part1)]
fn part1(numbers: &[Word]) -> Result<usize, Error> {
    let (maze, _, _) = build_maze(numbers)?;
    Ok(intersections(&maze).into_iter().map(|(x, y)| x * y).sum())
}

#[aoc(day17, part2)]
fn part2(numbers: &[Word]) -> Result<Word, Error> {
    let (maze, start, dir) = build_maze(numbers)?;
    let segments = segments(&maze, &start);
    let ops = ops(&segments, &dir);
    let (funcs, program) = can_compress(&ops, &[Op::A, Op::B, Op::C]).unwrap();
    let input = format!(
        "{}\n{}\nn\n",
        ops_to_str(&program),
        funcs
            .into_iter()
            .map(|f| ops_to_str(&f))
            .collect::<Vec<_>>()
            .join("\n")
    );
    let mut intcode = IntCode::new(numbers);
    intcode.wmem(0, 2)?;
    let mut input = input
        .chars()
        .map(|c| c as u8 as Word)
        .collect::<VecDeque<_>>();
    let mut output = Vec::new();
    intcode.run(
        || {
            input
                .pop_front()
                .ok_or_else(|| format_err!("exhausted input"))
        },
        |o| Ok(output.push(o)),
    )?;
    Ok(output[output.len() - 1])
}

fn intersections(maze: &Grid) -> Vec<(usize, usize)> {
    maze.iter()
        .filter(|c| maze.neighbours(c).len() == 4)
        .collect()
}

fn build_maze(numbers: &[Word]) -> Result<(Grid, Point, Dir), Error> {
    let mut sky = String::new();
    IntCode::new(numbers).run_until_input(|d| Ok(sky.push(d as u8 as char)))?;
    let sky = sky.lines().collect::<Vec<_>>();
    let mut maze = Grid::new(sky[0].len(), sky.len());
    let (mut start, mut start_dir) = (None, None);
    for (y, l) in sky.into_iter().enumerate() {
        for (x, c) in l.chars().enumerate() {
            if c != '.' {
                maze.add_vertex((x, y));
                if c != '#' {
                    start = Some((x, y));
                    start_dir = match c {
                        '^' => Some((0, -1)),
                        '>' => Some((1, 0)),
                        'v' => Some((0, 1)),
                        '<' => Some((-1, 0)),
                        _ => bail!("unknown character {}", c),
                    }
                }
            }
        }
    }
    Ok((maze, start.unwrap(), start_dir.unwrap()))
}

fn segments(maze: &Grid, start: &Point) -> Vec<(Dir, usize)> {
    let mut segments = Vec::new();
    let mut start = *start;
    let mut prev_horizontal = maze.neighbours(&start)[0].1 != start.1;
    loop {
        let dir;
        let neighbours = maze.neighbours(&start);
        if prev_horizontal {
            if neighbours.contains(&(start.0, start.1 - 1)) {
                dir = (0, -1);
            } else if neighbours.contains(&(start.0, start.1 + 1)) {
                dir = (0, 1);
            } else {
                break;
            }
        } else {
            if neighbours.contains(&(start.0 - 1, start.1)) {
                dir = (-1, 0);
            } else if neighbours.contains(&(start.0 + 1, start.1)) {
                dir = (1, 0);
            } else {
                break;
            }
        }
        let mut len = 0;
        loop {
            let next = (
                (start.0 as isize + dir.0) as usize,
                (start.1 as isize + dir.1) as usize,
            );
            if !maze.neighbours(&start).contains(&next) {
                break;
            }
            start = next;
            len += 1;
        }
        segments.push((dir, len));
        prev_horizontal = !prev_horizontal;
    }
    segments
}

fn ops(segments: &[(Dir, usize)], dir: &Dir) -> Vec<Op> {
    let mut ops = Vec::new();
    let mut dir = *dir;
    for &(d, l) in segments {
        if d != dir {
            ops.push(if dir.0 * d.1 - dir.1 * d.0 < 0 {
                Op::Left
            } else {
                Op::Right
            });
            dir = d;
        }
        ops.push(Op::Advance(l));
    }
    ops
}

fn ops_to_str(ops: &[Op]) -> String {
    ops.iter()
        .map(|o| o.to_string())
        .collect::<Vec<_>>()
        .join(",")
}

fn can_compress(ops: &[Op], rest: &[Op]) -> Option<(VecDeque<Vec<Op>>, Vec<Op>)> {
    if rest.is_empty() {
        return if ops.iter().all(|o| o.is_abc()) {
            Some((VecDeque::new(), ops.to_vec()))
        } else {
            None
        };
    }
    let skip = ops
        .iter()
        .enumerate()
        .find(|(_, o)| !o.is_abc())
        .map(|(i, _)| i)?; // Refuse to have only A, B or C is some functions are undefined
    for prefix_len in (1..=10.min(ops.len() - skip)).rev() {
        let prefix = ops[skip..skip + prefix_len].to_vec();
        let s = ops_to_str(&prefix);
        if s.len() > 20 || prefix.iter().any(|o| o.is_abc()) {
            continue;
        }
        let mut compressed = Vec::new();
        let mut idx = 0;
        while idx < ops.len() {
            if idx + prefix.len() <= ops.len() && ops[idx..idx + prefix.len()] == prefix[..] {
                compressed.push(rest[0].clone());
                idx += prefix.len();
            } else {
                compressed.push(ops[idx].clone());
                idx += 1;
            }
        }
        if let Some((mut funcs, s)) = can_compress(&compressed, &rest[1..]) {
            funcs.push_front(prefix);
            return Some((funcs, s));
        }
    }
    None
}