extern crate crypto;

use std::collections::VecDeque;
use std::io::{self, Read};

use crypto::digest::Digest;
use crypto::md5::Md5;

#[derive(Clone, Copy)]
enum Direction {
    Up,
    Down,
    Left,
    Right,
}

const DIRECTIONS: &'static [Direction] = &[
    Direction::Up,
    Direction::Down,
    Direction::Left,
    Direction::Right,
];

impl From<Direction> for char {
    fn from(direction: Direction) -> Self {
        match direction {
            Direction::Up => 'U',
            Direction::Down => 'D',
            Direction::Left => 'L',
            Direction::Right => 'R',
        }
    }
}

#[derive(Default, Clone, Copy)]
struct Room {
    x: u8,
    y: u8,
}

impl Room {
    fn neighbor(self, direction: Direction) -> Option<Room> {
        match direction {
            Direction::Up    if self.y != 0 => Some(Room { x: self.x, y: self.y - 1 }),
            Direction::Down  if self.y != 3 => Some(Room { x: self.x, y: self.y + 1 }),
            Direction::Left  if self.x != 0 => Some(Room { x: self.x - 1, y: self.y }),
            Direction::Right if self.x != 3 => Some(Room { x: self.x + 1, y: self.y }),
            _ => None,
        }
    }

    fn is_vault(self) -> bool {
        self.x == 3 && self.y == 3
    }
}

#[derive(Default, Clone)]
struct State {
    room: Room,
    path: Vec<Direction>,
}

impl<'a> From<&'a State> for String {
    fn from(state: &'a State) -> String {
        state.path.iter().cloned().map(char::from).collect()
    }
}

impl State {
    fn is_vault(&self) -> bool {
        self.room.is_vault()
    }

    fn generate_states(&self, states: &mut VecDeque<State>, passcode: &str) {
        let mut md5 = Md5::new();
        md5.input_str(passcode);
        md5.input_str(&String::from(self));
        let hash = md5.result_str();

        for (direction, ch) in DIRECTIONS.iter().cloned().zip(hash.chars()) {
            if ch < 'b' || ch > 'f' { continue }

            let room = match self.room.neighbor(direction) {
                Some(r) => r,
                None => continue,
            };

            let mut path = self.path.clone();
            path.push(direction);

            states.push_back(State { room: room, path: path });
        }
    }
}

fn solve1(passcode: &str) -> String {
    let mut states = VecDeque::new();
    states.push_back(State::default());

    while let Some(state) = states.pop_front() {
        if state.is_vault() {
            return String::from(&state);
        }
        state.generate_states(&mut states, passcode);
    }

    panic!("no path to vault")
}

fn solve2(passcode: &str) -> usize {
    let mut states = VecDeque::new();
    states.push_back(State::default());

    let mut longest = None;

    while let Some(state) = states.pop_front() {
        if state.is_vault() {
            longest = Some(state.clone());
        } else {
            state.generate_states(&mut states, passcode);
        }
    }

    longest.unwrap().path.len()
}

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();

    println!("Part 1: {}", solve1(input.trim()));
    println!("Part 2: {}", solve2(input.trim()));
}

#[test]
fn part1() {
    assert_eq!("DDRRRD", solve1("ihgpwlah"));
    assert_eq!("DDUDRLRRUDRD", solve1("kglvqrro"));
    assert_eq!("DRURDRUDDLLDLUURRDULRLDUUDDDRR", solve1("ulqzkmiv"));
}

#[test]
#[ignore]
fn part2() {
    assert_eq!(370, solve2("ihgpwlah"));
    assert_eq!(492, solve2("kglvqrro"));
    assert_eq!(830, solve2("ulqzkmiv"));
}