Rust Advent of Code 2019 Day 18

use std::collections::{HashMap, HashSet};
use std::fs;
use std::fmt::{Debug, Display, Error, Formatter};
use std::ops::{Sub, Add, AddAssign};

use queue::Queue;


#[derive(Hash)]
pub struct Point {
    pub x: isize,
    pub y: isize
}

impl Point {
    pub fn new(x: isize, y: isize) -> Self {
        Self { x, y }
    }
}

impl PartialEq for Point {
    fn eq(&self, other: &Self) -> bool {
        self.x.eq(&other.x) && self.y.eq(&other.y)
    }
}

impl Eq for Point {}

impl Sub for Point {
    type Output = Self;

    fn sub(self, rhs: Self) -> Self::Output {
        Self { x: self.x - rhs.x, y: self.y - rhs.y }
    }
}

impl Add for Point {
    type Output = Self;

    fn add(self, rhs: Self) -> Self::Output {
        Self { x: self.x + rhs.x, y: self.y + rhs.y }
    }
}

impl AddAssign for Point {
    fn add_assign(&mut self, rhs: Self) {
        self.x += rhs.x;
        self.y += rhs.y;
    }
}

impl Copy for Point {

}

impl Clone for Point {
    fn clone(&self) -> Self {
        Self { x: self.x.clone(), y: self.y.clone() }
    }
}

impl Debug for Point {
    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
        write!(f, "({}, {})", self.x, self.y)
    }
}

impl Display for Point {
    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
        write!(f, "({}, {})", self.x, self.y)
    }
}

#[derive(Clone, Hash, Debug, Eq, PartialEq)]
struct State {
    at: Vec<char>,
    obtained_keys: Vec<char>,
}

struct Map {
    path: HashSet<Point>,
    doors: HashMap<Point, char>,
}

fn main() {
    let input = fs::read_to_string("input2").unwrap();
    let (distances, num_keys) = load(&input);
    let state = State {
        at: vec![0 as char, 1 as char, 2 as char, 3 as char],
        obtained_keys: Vec::new(),
    };
//    println!("{:?}: {:?}, {:?}, {:?}", distances, num_positions, num_keys, state);
    let mut previous = HashMap::new();
    println!("{:?}", minimum_steps(&state, &distances, num_keys, &mut previous));
}

fn load(input: &String) -> (HashMap<(char, char), (usize, Vec<char>)>, usize) {
    let path: HashSet<Point> = input.split('\n').enumerate()
        .flat_map(|(y, line)| {
            line.chars().enumerate()
                .filter(|(_, character)| *character != '#')
                .map(|(x, _)| {
                    Point::new(x as isize, y as isize)
                })
                .collect::<HashSet<Point>>()
        })
        .collect();
    let no_letter_characters = vec!['#', '.', '@'];
    let keys: HashMap<Point, char> = input.split('\n').enumerate()
        .flat_map(|(y, line)|
            line.chars().enumerate()
                .filter(|(_, character)| !no_letter_characters.contains(character) && character.to_lowercase().next().unwrap() == *character)
                .map(|(x, character)| (Point::new(x as isize, y as isize), character.to_uppercase().next().unwrap()))
                .collect::<Vec<(Point, char)>>())
        .collect();
    let doors = input.split('\n').enumerate()
        .flat_map(|(y, line)|
            line.chars().enumerate()
                .filter(|(_, character)| !no_letter_characters.contains(character) && character.to_uppercase().next().unwrap() == *character)
                .map(|(x, character)| (Point::new(x as isize, y as isize), character))
                .collect::<Vec<(Point, char)>>())
        .collect();
    let positions: Vec<Point> = input.split('\n').enumerate()
        .flat_map(|(y, line)|
            line.chars().enumerate()
                .filter(|(_, character)| *character == '@')
                .map(|(x, _)| Point::new(x as isize, y as isize))
                .collect::<Vec<Point>>())
        .collect();
    let map = Map { path, doors };
    let identified_positions: HashMap<Point, char> = positions
        .iter()
        .enumerate()
        .map(|(i, point)| (point.clone(), i as u8 as char))
        .collect();
    (keys.clone().into_iter()
         .chain(identified_positions)
         .flat_map(|(point_one, key_one)|
             keys.iter().filter_map(|(point_two, key_two)| {
                 match bfs(&map, &point_one, point_two) {
                     Some(result) => Some(((key_one.clone(), key_two.clone()), result)),
                     None => None
                 }
             })
                 .collect::<Vec<((char, char), (usize, Vec<char>))>>())
         .collect(), keys.len())
}

fn get_accessible_neighbors(current_position: &Point, map: &Map) -> Vec<Point> {
    let neighbors = [current_position.clone() - Point::new(1, 0), current_position.clone() + Point::new(1, 0),
        current_position.clone() - Point::new(0, 1), current_position.clone() + Point::new(0, 1)];
    neighbors.iter()
        .filter(|neighbor| map.path.contains(neighbor))
        .map(|neighbor| neighbor.clone())
        .collect()
}

fn bfs(map: &Map, from: &Point, to: &Point) -> Option<(usize, Vec<char>)> {
    let mut queue: Queue<(Point, usize, Vec<char>)> = Queue::new();
    let mut visited: HashSet<Point> = HashSet::new();

    queue.queue((from.clone(), 0, Vec::new())).unwrap();
    visited.insert(from.clone());
    while !queue.is_empty() {
        let (current_pos, steps, necessary) = queue.dequeue().unwrap();
        if &current_pos == to {
            return Some((steps, necessary));
        }
        let mut new_neccessary = necessary.clone();
        if map.doors.contains_key(&current_pos) {
            new_neccessary.push(map.doors.get(&current_pos).unwrap().clone());
        }
        for neighbor in get_accessible_neighbors(&current_pos, map) {
            if !visited.contains(&neighbor) {
                queue.queue((neighbor, steps + 1, new_neccessary.clone())).unwrap();
                visited.insert(neighbor.clone());
            }
        }
    }
    None
}

fn minimum_steps(state: &State, distances: &HashMap<(char, char), (usize, Vec<char>)>, num_keys: usize, previous_states: &mut HashMap<State, usize>) -> usize {
    if num_keys == state.obtained_keys.len() {
        return 0;
    }
    if previous_states.contains_key(state) {
        return previous_states.get(state).unwrap().clone();
    }

    let mut min_steps = std::usize::MAX;
    let next_stops = distances.iter()
        .filter(|((from, to), (_, required_keys))| !state.obtained_keys.contains(to) && state.at.contains(from) && required_keys.iter().find(|key| !state.obtained_keys.contains(key)).is_none())
            .map(|((from, to), (steps, _))| (state.at.iter().position(|i| i == from).unwrap(), to, steps));
    for (robot, next_stop, steps) in next_stops {
        let mut new_obtained_keys: Vec<char> = state.obtained_keys.iter().chain(vec![next_stop]).cloned().collect();
        new_obtained_keys.sort();
        let new_state = State {
            obtained_keys: new_obtained_keys,
            at: state.at.clone().iter().enumerate().map(|(i, at)| if i == robot { next_stop.clone() } else { at.clone() }).collect(),
        };
        min_steps = min_steps.min(minimum_steps(&new_state, distances, num_keys, previous_states) + steps.clone());
    }
    previous_states.insert(state.clone(), min_steps);
    min_steps
}