use std::fs;
use std::path::Path;
use std::collections::BinaryHeap;

struct Cave {
    width: usize,
    layout: Vec<u32>
}

impl Cave {
    fn astar(&self, start: usize, goal: usize) -> u32 {
        let mut heap = BinaryHeap::new();
        heap.push(start);
        let mut prec = vec![0;self.layout.len()];
        let mut cost = vec![u32::MAX;self.layout.len()];
        cost[start] = 0;

        while let Some(curr) = heap.pop() {
            for neighbor in self.neighbors(curr) {
                let newcost = cost[curr] + self.layout[neighbor];
                if newcost < cost[neighbor] {
                    prec[neighbor] = curr;
                    cost[neighbor] = newcost;
                    if heap.iter().find(|&&n| n == neighbor).is_none() {
                        heap.push(neighbor);
                    }
                }
            }
        }
        cost[goal]
    }

    fn neighbors(&self, pos: usize) -> Vec<usize> {
        let mut nbs = vec![];
        if (pos+1) % self.width > 0 {
            nbs.push(pos+1);
        }
        if pos % self.width > 0 {
            nbs.push(pos-1);
        }
        if (pos+self.width) < self.layout.len() {
            nbs.push(pos+self.width);
        }
        if pos >= self.width {
            nbs.push(pos-self.width);
        }
        nbs
    }
}

fn main() {
    let input = Path::new("resources").join("input.txt");
    let content = fs::read_to_string(input).expect("Unable to read input file");
    let cave = parse_input(&content);
    println!("Ex1: the result is {}", cave.astar(0,cave.layout.len()-1))
}

fn parse_input(input: &str) -> Cave {
    let width = input.lines().next().unwrap().len();
    let layout = input.lines().flat_map(|l| l.bytes().map(|b| (b-b'0') as u32)).collect();
    Cave { width, layout }
}

#[cfg(test)]
mod tests {
    use super::*;
    
    const INPUT: &str = "1163751742
1381373672
2136511328
3694931569
7463417111
1319128137
1359912421
3125421639
1293138521
2311944581";

    #[test]
    fn example() {
        let cave = parse_input(INPUT);
        assert_eq!(40, cave.astar(0,cave.layout.len()-1));
    }
}