use grid::Grid;

// # Algorithm outline:
// 1. create grid of distances
// 2. traverse, check each cell from -20,-20 to +20,+20
//      a. check if xy distance is less than 20 picoseconds
//      b. if dist < distance - 100, valid cheat

const  ADJACENTS: [(i32, i32); 4] = [
    (0, -1),
    (1, 0),
    (0, 1),
    (-1, 0),
];

const PICOSECONDS: i32 = 100;

fn main() {
    let time = std::time::Instant::now();
    let input: Vec<_> = include_str!("../input.txt").lines().collect();
    let mut grid: Grid<char> = Grid::new(input.len(), input[0].len());
    let mut end: Option<(i32, i32)> = None;

    for (y, row) in input.into_iter().enumerate() {
        for (x, c) in row.chars().enumerate() {
            grid[(y, x)] = c;

            if c == 'E' {
                end = Some((x as i32, y as i32));
            }
        }
    }

    let end = end.unwrap();
    let mut distances: Grid<Option<i32>> = Grid::new(grid.rows(), grid.cols());
    distances.fill(None);
    let mut cursor: (i32, i32);
    let mut next = end.clone();
    let mut distance = 0;

    'outer: loop {
        cursor = next;

        distances[(cursor.1 as usize, cursor.0 as usize)] = Some(distance);
        distance += 1;

        for (xd, yd) in ADJACENTS {
            let x = cursor.0 + xd;
            let y = cursor.1 + yd;
            if let Some(cell) = grid.get(y, x) {
                match cell {
                    '#' => (),
                    'S' => {
                        distances[(y as usize, x as usize)] = Some(distance);
                        break 'outer;
                    },
                    '.' => {
                        grid[(y as usize, x as usize)] = 'O';
                        next = (x, y);
                    },
                    'O' | 'E' => (),
                    // 'S' => done = true,
                    _ => unimplemented!()
                }
            }
        }
    }

    let width = grid.cols();
    let height = grid.rows();
    let mut cheats = 0;

    for ((y, x), cell) in distances.indexed_iter() {
        if let &Some(from_distance) = cell {
            // No way to find a shortcut that saves more than PICOSECONDS
            if from_distance < PICOSECONDS {
                continue;
            }

            let top    = y.saturating_sub(20);
            let left   = x.saturating_sub(20);
            let bottom = (y + 20).max(height - 1);
            let right  = (x + 20).max(width - 1);

            for ty in top..=bottom {
                for tx in left..=right {
                    let pico = (x.abs_diff(tx) + y.abs_diff(ty)) as i32;
                    if pico > 20 {
                        continue;
                    }

                    if let Some(&Some(to_distance)) = distances.get(ty, tx) {
                        if to_distance <= from_distance - pico - PICOSECONDS {
                            cheats += 1;
                        }
                    }
                }
            }
        }
    }

    println!("Cheats: {}", cheats);
    println!("Time elapsed: {:?}", time.elapsed());

    // let grid_out = grid.iter_rows()
    //     .map(|row| row.into_iter().collect::<String>())
    //     .collect::<Vec<String>>()
    //     .join("\n");
    // println!("Grid:\n{}", grid_out);
}