#![allow(dead_code)]

use std::fmt;
use std::io::{self, BufRead};
use std::str;

#[derive(Copy, Clone)]
enum RawOpcode {
    Addr, Addi,
    Mulr, Muli,
    Banr, Bani,
    Borr, Bori,
    Setr, Seti,
    Gtir, Gtri, Gtrr,
    Eqir, Eqri, Eqrr,
}

impl str::FromStr for RawOpcode {
    type Err = io::Error;

    fn from_str(s: &str) -> io::Result<Self> {
        Ok(match s {
            "addr" => RawOpcode::Addr,
            "addi" => RawOpcode::Addi,
            "mulr" => RawOpcode::Mulr,
            "muli" => RawOpcode::Muli,
            "banr" => RawOpcode::Banr,
            "bani" => RawOpcode::Bani,
            "borr" => RawOpcode::Borr,
            "bori" => RawOpcode::Bori,
            "setr" => RawOpcode::Setr,
            "seti" => RawOpcode::Seti,
            "gtir" => RawOpcode::Gtir,
            "gtri" => RawOpcode::Gtri,
            "gtrr" => RawOpcode::Gtrr,
            "eqir" => RawOpcode::Eqir,
            "eqri" => RawOpcode::Eqri,
            "eqrr" => RawOpcode::Eqrr,
            _ => panic!("Invalid raw opcode"),
        })
    }
}

#[derive(Copy, Clone)]
pub enum Oper {
    Reg(usize),
    Num(usize),
}

impl Oper {
    pub fn map_reg<F: Fn(usize) -> Oper>(&mut self, func: F) {
        *self = match *self {
            Oper::Reg(r) => func(r),
            Oper::Num(n) => Oper::Num(n)
        };
    }
}

impl fmt::Display for Oper {
    fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
        match self {
            Oper::Reg(r) => write!(w, "r{}", r),
            Oper::Num(n) => write!(w, "{}", n),
        }
    }
}

struct RawInstr {
    op: RawOpcode,
    a: usize,
    b: usize,
    c: usize,
}

impl fmt::Display for RawInstr {
    fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
        match self.op {
            RawOpcode::Addr => write!(w, "r{} <- {} + {}", self.c, self.a, self.b),
            RawOpcode::Addi => write!(w, "r{} <- {} + {}", self.c, self.a, self.b),
            RawOpcode::Mulr => write!(w, "r{} <- {} * {}", self.c, self.a, self.b),
            RawOpcode::Muli => write!(w, "r{} <- {} * {}", self.c, self.a, self.b),
            RawOpcode::Banr => write!(w, "r{} <- {} & {}", self.c, self.a, self.b),
            RawOpcode::Bani => write!(w, "r{} <- {} & {}", self.c, self.a, self.b),
            RawOpcode::Borr => write!(w, "r{} <- {} | {}", self.c, self.a, self.b),
            RawOpcode::Bori => write!(w, "r{} <- {} | {}", self.c, self.a, self.b),
            RawOpcode::Setr => write!(w, "r{} <- {}", self.c, self.a),
            RawOpcode::Seti => write!(w, "r{} <- {}", self.c, self.a),
            RawOpcode::Gtir => write!(w, "r{} <- {} > {}", self.c, self.a, self.b),
            RawOpcode::Gtri => write!(w, "r{} <- {} > {}", self.c, self.a, self.b),
            RawOpcode::Gtrr => write!(w, "r{} <- {} > {}", self.c, self.a, self.b),
            RawOpcode::Eqir => write!(w, "r{} <- {} == {}", self.c, self.a, self.b),
            RawOpcode::Eqri => write!(w, "r{} <- {} == {}", self.c, self.a, self.b),
            RawOpcode::Eqrr => write!(w, "r{} <- {} == {}", self.c, self.a, self.b),
        }
    }
}

impl str::FromStr for RawInstr {
    type Err = io::Error;

    fn from_str(line: &str) -> io::Result<Self> {
        let mut iter = line.split(' ');

        let mut next_string = move || iter.next().ok_or(io::Error::new(io::ErrorKind::Other, "Invalid raw instruction"));
        macro_rules! next_int {
            ( $var:ident ) => {
                let $var = next_string()?.parse()
                    .or(Err(io::Error::new(io::ErrorKind::Other, "Invalid number in raw instruction")))?;
            }
        };

        let op = next_string()?.parse()?;
        next_int!(a);
        next_int!(b);
        next_int!(c);
        Ok(RawInstr { op, a, b, c })
    }
}

pub enum Instr {
    //  src1, src2, dest
    Add(Oper, Oper, usize),
    Mul(Oper, Oper, usize),
    Ban(Oper, Oper, usize),
    Bor(Oper, Oper, usize),
    Grt(Oper, Oper, usize),
    Equ(Oper, Oper, usize),
    Set(Oper,       usize),
}

impl Instr {
    fn from_raw_instr(ins: &RawInstr) -> Self {
        match ins.op {
            RawOpcode::Addr => Instr::Add(Oper::Reg(ins.a), Oper::Reg(ins.b), ins.c),
            RawOpcode::Addi => Instr::Add(Oper::Reg(ins.a), Oper::Num(ins.b), ins.c),
            RawOpcode::Mulr => Instr::Mul(Oper::Reg(ins.a), Oper::Reg(ins.b), ins.c),
            RawOpcode::Muli => Instr::Mul(Oper::Reg(ins.a), Oper::Num(ins.b), ins.c),
            RawOpcode::Banr => Instr::Ban(Oper::Reg(ins.a), Oper::Reg(ins.b), ins.c),
            RawOpcode::Bani => Instr::Ban(Oper::Reg(ins.a), Oper::Num(ins.b), ins.c),
            RawOpcode::Borr => Instr::Bor(Oper::Reg(ins.a), Oper::Reg(ins.b), ins.c),
            RawOpcode::Bori => Instr::Bor(Oper::Reg(ins.a), Oper::Num(ins.b), ins.c),
            RawOpcode::Setr => Instr::Set(Oper::Reg(ins.a),                   ins.c),
            RawOpcode::Seti => Instr::Set(Oper::Num(ins.a),                   ins.c),
            RawOpcode::Gtir => Instr::Grt(Oper::Num(ins.a), Oper::Reg(ins.b), ins.c),
            RawOpcode::Gtri => Instr::Grt(Oper::Reg(ins.a), Oper::Num(ins.b), ins.c),
            RawOpcode::Gtrr => Instr::Grt(Oper::Reg(ins.a), Oper::Reg(ins.b), ins.c),
            RawOpcode::Eqir => Instr::Equ(Oper::Num(ins.a), Oper::Reg(ins.b), ins.c),
            RawOpcode::Eqri => Instr::Equ(Oper::Reg(ins.a), Oper::Num(ins.b), ins.c),
            RawOpcode::Eqrr => Instr::Equ(Oper::Reg(ins.a), Oper::Reg(ins.b), ins.c),
        }
    }

    pub fn map_reads<F: Fn(usize) -> Oper>(&mut self, func: F) {
        match self {
            Instr::Add(a, b, _) => { a.map_reg(&func); b.map_reg(&func); },
            Instr::Mul(a, b, _) => { a.map_reg(&func); b.map_reg(&func); },
            Instr::Ban(a, b, _) => { a.map_reg(&func); b.map_reg(&func); },
            Instr::Bor(a, b, _) => { a.map_reg(&func); b.map_reg(&func); },
            Instr::Grt(a, b, _) => { a.map_reg(&func); b.map_reg(&func); },
            Instr::Equ(a, b, _) => { a.map_reg(&func); b.map_reg(&func); },
            Instr::Set(a, _) => a.map_reg(func),
        };
    }

    pub fn inline_reg(&mut self, reg: usize, value: Oper) {
        self.map_reads(|r| if r == reg { value } else { Oper::Reg(r) });
    }
}

impl fmt::Display for Instr {
    fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
        match self {
            Instr::Add(a, b, c) => write!(w, "r{} <- {} + {}", c, a, b),
            Instr::Mul(a, b, c) => write!(w, "r{} <- {} * {}", c, a, b),
            Instr::Ban(a, b, c) => write!(w, "r{} <- {} & {}", c, a, b),
            Instr::Bor(a, b, c) => write!(w, "r{} <- {} | {}", c, a, b),
            Instr::Grt(a, b, c) => write!(w, "r{} <- {} > {}", c, a, b),
            Instr::Equ(a, b, c) => write!(w, "r{} <- {} == {}", c, a, b),
            Instr::Set(a, c) => write!(w, "r{} <- {}", c, a),
        }
    }
}

#[derive(PartialEq, Eq, Clone)]
pub struct Machine {
    pub regs: [usize; 6],
}

impl Machine {
    pub fn exec(&mut self, instr: &Instr) {
        match instr {
            &Instr::Add(a, b, c) => self.regs[c] = self.eval_oper(a) + self.eval_oper(b),
            &Instr::Mul(a, b, c) => self.regs[c] = self.eval_oper(a) * self.eval_oper(b),
            &Instr::Ban(a, b, c) => self.regs[c] = self.eval_oper(a) & self.eval_oper(b),
            &Instr::Bor(a, b, c) => self.regs[c] = self.eval_oper(a) | self.eval_oper(b),
            &Instr::Grt(a, b, c) => self.regs[c] = if self.eval_oper(a) > self.eval_oper(b) { 1 } else { 0 },
            &Instr::Equ(a, b, c) => self.regs[c] = if self.eval_oper(a) == self.eval_oper(b) { 1 } else { 0 },
            &Instr::Set(a, c) => self.regs[c] = self.eval_oper(a),
        }
    }

    pub fn exec_program(&mut self, prog: &[Instr], ip_reg: usize) {
        let mut ip = 0;
        while ip < prog.len() {
            self.regs[ip_reg] = ip;
            println!("{} ip={} {}", self, ip, prog[ip]);
            self.exec(&prog[ip]);
            ip = self.regs[ip_reg] + 1;
        }
    }

    pub fn eval_oper(&self, oper: Oper) -> usize {
        match oper {
            Oper::Reg(r) => self.regs[r],
            Oper::Num(n) => n,
        }
    }
}

impl fmt::Display for Machine {
    fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
        write!(w, "{}", self.regs[0])?;
        for i in 1..6 {
            write!(w, " {}", self.regs[i])?;
        }
        Ok(())
    }
}

pub fn parse_program<T: BufRead>(reader: T) -> io::Result<(usize, Vec<Instr>)> {
    let mut lines = reader.lines();
    let ip_reg = match lines.next() {
        Some(line) => {
            let line = line?;
            if line.starts_with("#ip ") && line.len() == 5 {
                (line.as_bytes()[4] - '0' as u8) as usize
            } else {
                return Err(io::Error::new(io::ErrorKind::Other, "Program parse error: initial line not '#ip n'"));
            }
        }
        None => {
            return Err(io::Error::new(io::ErrorKind::Other, "Program parse error: empty file"));
        }
    };

    let instrs = lines.map(|l| {
        Ok(Instr::from_raw_instr(&l?.parse()?))
    }).collect::<io::Result<Vec<Instr>>>()?;

    Ok((ip_reg, instrs))
}

#[derive(Clone, PartialEq, Eq)]
pub enum SymVal {
    Val(usize),
    Add(Box<SymVal>, Box<SymVal>),
    Mul(Box<SymVal>, Box<SymVal>),
    Ban(Box<SymVal>, Box<SymVal>),
    Bor(Box<SymVal>, Box<SymVal>),
    Grt(Box<SymVal>, Box<SymVal>),
    Equ(Box<SymVal>, Box<SymVal>),
    If1(Box<SymVal>, Box<SymVal>, Box<SymVal>),
}

impl Default for SymVal {
    fn default() -> Self {
        SymVal::Val(0)
    }
}

impl SymVal {
    pub fn simplify(&mut self) {
        let optres = match self {
            SymVal::Val(n) => Some(SymVal::Val(*n)),
            SymVal::Add(a, b) => { a.simplify(); b.simplify(); SymVal::eval_vals(&*a, &*b, |x, y| x + y) }
            SymVal::Mul(a, b) => { a.simplify(); b.simplify(); SymVal::eval_vals(&*a, &*b, |x, y| x * y) }
            SymVal::Ban(a, b) => { a.simplify(); b.simplify(); SymVal::eval_vals(&*a, &*b, |x, y| x & y) }
            SymVal::Bor(a, b) => { a.simplify(); b.simplify(); SymVal::eval_vals(&*a, &*b, |x, y| x | y) }
            SymVal::Grt(a, b) => { a.simplify(); b.simplify(); SymVal::eval_vals(&*a, &*b, |x, y| (x > y) as usize) }
            SymVal::Equ(a, b) => { a.simplify(); b.simplify(); SymVal::eval_vals(&*a, &*b, |x, y| (x == y) as usize) }
            SymVal::If1(c, t, e) => {
                c.simplify(); t.simplify(); e.simplify();
                match **c {
                    SymVal::Val(1) => Some((**t).clone()),
                    SymVal::Val(_) => Some((**e).clone()),
                    _ => None,
                }
            }
        };
        if let Some(res) = optres {
            *self = res;
        }
    }

    pub fn eval_vals<F: Fn(usize, usize) -> usize>(a: &SymVal, b: &SymVal, func: F) -> Option<SymVal> {
        match (a, b) {
            (&SymVal::Val(x), &SymVal::Val(y)) => Some(SymVal::Val(func(x, y))),
            _ => None,
        }
    }
}

pub struct SymbolicMachine {
    pub regs: [SymVal; 6],
}

impl SymbolicMachine {
    pub fn from(m: &Machine) -> Self {
        let mut sm = SymbolicMachine { regs: Default::default() };
        for i in 0..6 {
            sm.regs[i] = SymVal::Val(m.regs[i]);
        }
        sm
    }

    pub fn exec_oper(&self, oper: Oper) -> SymVal {
        match oper {
            Oper::Reg(r) => self.regs[r].clone(),
            Oper::Num(n) => SymVal::Val(n),
        }
    }

    pub fn exec(&mut self, instr: &Instr) {
        let (c, mut val) = match instr {
            &Instr::Add(a, b, c) => (c, SymVal::Add(Box::new(self.exec_oper(a)), Box::new(self.exec_oper(b)))),
            &Instr::Mul(a, b, c) => (c, SymVal::Mul(Box::new(self.exec_oper(a)), Box::new(self.exec_oper(b)))),
            &Instr::Ban(a, b, c) => (c, SymVal::Ban(Box::new(self.exec_oper(a)), Box::new(self.exec_oper(b)))),
            &Instr::Bor(a, b, c) => (c, SymVal::Bor(Box::new(self.exec_oper(a)), Box::new(self.exec_oper(b)))),
            &Instr::Grt(a, b, c) => (c, SymVal::Grt(Box::new(self.exec_oper(a)), Box::new(self.exec_oper(b)))),
            &Instr::Equ(a, b, c) => (c, SymVal::Equ(Box::new(self.exec_oper(a)), Box::new(self.exec_oper(b)))),
            &Instr::Set(a, c) => (c, self.exec_oper(a)),
        };

        val.simplify();
        self.regs[c] = val;
    }

    fn exec_find_loop(&mut self, prog: &[Instr], start_ip: usize, ip_reg: usize) -> bool {
        let mut ip = start_ip;
        while ip != start_ip {
            self.regs[ip_reg] = SymVal::Val(ip);
            // println!("{} ip={} {}", self, ip, prog[ip]);
            self.exec(&prog[ip]);
            self.regs[ip_reg].simplify();
            ip = match self.regs[ip_reg] {
                SymVal::Val(v) => v,
                _ => return false,
            };
        }

        false
    }
}