import 'dart:math';
import 'package:collection/collection.dart';
import 'package:more/more.dart';

typedef PP = (Point, Point);
List<Point<num>> d4 = [Point(1, 0), Point(-1, 0), Point(0, 1), Point(0, -1)];
(num, List<List<(Point, Point)>>) solve(List<String> lines) {
  var grid = {
    for (var r in lines.indexed())
      for (var c in r.value.split('').indexed().where((e) => e.value != '#'))
        Point<num>(c.index, r.index): c.value
  };
  var start = grid.entries.firstWhere((e) => e.value == 'S').key;
  var end = grid.entries.firstWhere((e) => e.value == 'E').key;
  var dir = Point<num>(1, 0);
  int fHeur(PP pd) => 1; // faster than euclidean distance.

  Map<PP, int> fNextAndCost(PP pd) {
    var ret = <PP, int>{};
    for (var n in d4) {
      if (n == pd.last * -1) continue;
      if (!grid.containsKey(pd.first + n)) continue;
      ret[(pd.first + n, n)] = (n == pd.last) ? 1 : 1001;
    }
    return ret;
  }

  bool fAtEnd(PP pd) => pd.first == end;

  return aStarSearch<PP>((start, dir), fNextAndCost, fHeur, fAtEnd);
}

/// Returns cost to destination, plus list of routes to destination.
/// Does Dijkstra/A* search depending on whether heuristic returns 1 or
/// something better.
(num, List<List<T>>) aStarSearch<T>(
    T start,
    Map<T, num> Function(T) fNextAndCost,
    int Function(T) fHeuristic,
    bool Function(T) fAtEnd,
    {lowestCostOnly = true}) {
  var cameFrom = SetMultimap<T, T>();
  cameFrom[start].add(start);

  var ends = <T>{};
  var frontier =
      PriorityQueue<T>((a, b) => fHeuristic(a).compareTo(fHeuristic(b)))
        ..add(start);
  var costSoFar = <T, num>{start: 0};
  while (frontier.isNotEmpty) {
    var here = frontier.removeFirst();
    if (fAtEnd(here)) {
      ends.add(here);
      continue;
    }
    var ns = fNextAndCost(here);
    for (var n in ns.keys) {
      var newCost = costSoFar[here]! + ns[n]!;
      if (!costSoFar.containsKey(n) || newCost < costSoFar[n]!) {
        costSoFar[n] = newCost;
        frontier.add(n);
        cameFrom.removeAll(n);
      }
      if (costSoFar[n] == newCost) cameFrom[n].add(here);
    }
  }
  Iterable<List<T>> routes(T h) sync* {
    if (h == start) {
      yield [h];
      return;
    }
    for (var p in cameFrom[h]) {
      yield* routes(p).map((e) => e + [h]).toList();
    }
  }

  var minCost = ends.map((e) => costSoFar[e]!).min;
  return (
    minCost,
    ends
        .where((e) => costSoFar[e]! == minCost)
        .fold([], (s, t) => s..addAll(routes(t).toList()))
  );
}

part1(List<String> lines) => solve(lines).first;

part2(List<String> lines) => solve(lines)
    .last
    .map((l) => l.map((e) => e.first).toSet())
    .flattenedToSet
    .length;

import Control.Arrow

import Data.Map (Map)
import Data.Set (Set)
import Data.Array.ST (STArray)
import Data.Array (Array)
import Control.Monad.ST (ST, runST)

import qualified Data.Char as Char
import qualified Data.List as List
import qualified Data.Map as Map
import qualified Data.Set as Set
import qualified Data.Array.ST as MutableArray
import qualified Data.Array as Array
import qualified Data.Maybe as Maybe

data Direction = East | West | South | North
        deriving (Show, Eq, Ord)
data MazeTile = Start | End | Wall | Unknown | Explored (Map Direction ExplorationScore)
        deriving Eq

--      instance Show MazeTile where
--              show Wall = "#"
--              show Start = "S"
--              show End = "E"
--              show Unknown = "."
--              show (Explored (East, _))  = ">"
--              show (Explored (South, _)) = "v"
--              show (Explored (West, _))  = "<"
--              show (Explored (North, _)) = "^"

type Position = (Int, Int)
type ExplorationScore = Int

translate '#' = Wall
translate '.' = Unknown
translate 'S' = Start
translate 'E' = End

parse :: String -> Array (Int, Int) MazeTile
parse s = Array.listArray ((1, 1), (height - 1, width)) . map translate . filter (/= '\n') $ s
        where
                width = length . takeWhile (/= '\n') $ s
                height = length . filter (== '\n') $ s

(a1, b1) .+. (a2, b2) = (a1+a2, b1+b2)
(a1, b1) .-. (a2, b2) = (a1-a2, b1-b2)

directions = [East, West, South, North]
directionVector East  = (0,  1)
directionVector West  = (0, -1)
directionVector North = (-1, 0)
directionVector South = ( 1, 0)

turnRight East  = South
turnRight South = West
turnRight West  = North
turnRight North = East

walkableNeighbors a p = do
        let neighbors = List.map ((.+. p) . directionVector) directions
        tiles <- mapM (MutableArray.readArray a) neighbors
        let neighborPosition = List.map fst . List.filter ((/= Wall). snd) . zip neighbors $ tiles
        return $ neighborPosition


findDeadEnds a = Array.assocs
        >>> List.filter (snd >>> (== Unknown))
        >>> List.map (fst)
        >>> List.filter (isDeadEnd a)
        $ a
isDeadEnd a p = List.map directionVector
        >>> List.map (.+. p)
        >>> List.map (a Array.!)
        >>> List.filter (/= Wall)
        >>> List.length
        >>> (== 1)
        $ directions

fillDeadEnds :: Array (Int, Int) MazeTile -> ST s (Array (Int, Int) MazeTile)
fillDeadEnds a = do
        ma <- MutableArray.thaw a
        let deadEnds = findDeadEnds a
        mapM_ (fillDeadEnd ma) deadEnds
        MutableArray.freeze ma

fillDeadEnd :: STArray s (Int, Int) MazeTile -> Position -> ST s ()
fillDeadEnd a p = do
        MutableArray.writeArray a p Wall
        p' <- walkableNeighbors a p >>= return . head
        t <- MutableArray.readArray a p'
        n <- walkableNeighbors a p' >>= return . List.length
        if n == 1 && t == Unknown then fillDeadEnd a p' else return ()

thawArray :: Array (Int, Int) MazeTile -> ST s (STArray s (Int, Int) MazeTile)
thawArray a = do
        a' <- MutableArray.thaw a
        return a'

solveMaze a = do
        a' <- fillDeadEnds a
        a'' <- thawArray a'
        let s = Array.assocs
                >>> List.filter ((== Start) . snd)
                >>> Maybe.listToMaybe
                >>> Maybe.maybe (error "Start not in map") fst
                $ a
        let e = Array.assocs
                >>> List.filter ((== End) . snd)
                >>> Maybe.listToMaybe
                >>> Maybe.maybe (error "End not in map") fst
                $ a
        MutableArray.writeArray a'' s $ Explored (Map.singleton East 0)
        MutableArray.writeArray a'' e $ Unknown
        solveMaze' (s, East) a''
        fa <- MutableArray.freeze a''
        t <- MutableArray.readArray a'' e
        case t of
                Wall  -> error "Unreachable code"
                Start -> error "Unreachable code"
                End   -> error "Unreachable code"
                Unknown -> error "End was not explored yet"
                Explored m -> return (List.minimum . List.map snd . Map.toList $ m, countTiles fa s e)

countTiles a s p = Set.size . countTiles' a s p $ South

countTiles' :: Array (Int, Int) MazeTile -> Position -> Position -> Direction -> Set Position
countTiles' a s p d
        | p == s    = Set.singleton p
        | otherwise = Set.unions 
                . List.map (Set.insert p) 
                . List.map (uncurry (countTiles' a s)) 
                $ (zip minCostNeighbors minCostDirections)
        where
                minCostNeighbors   = List.map ((p .-.) . directionVector) minCostDirections
                minCostDirections  = List.map fst . List.filter ((== minCost) . snd) . Map.toList $ visits
                visits = case a Array.! p of
                        Explored m -> Map.adjust (+ (-1000)) d m
                minCost = List.minimum . List.map snd . Map.toList $ visits

maybeExplore c p d a = do
        t <- MutableArray.readArray a p
        case t of
                Wall     -> return ()
                Start    -> error "Unreachable code"
                End      -> error "Unreachable code"
                Unknown  -> do
                        MutableArray.writeArray a p $ Explored (Map.singleton d c)
                        solveMaze' (p, d) a
                Explored m -> do
                        let c' = Maybe.maybe c id (m Map.!? d)
                        if c <= c' then do
                                let m' = Map.insert d c m
                                MutableArray.writeArray a p (Explored m')
                                solveMaze' (p, d) a
                        else
                                return ()

solveMaze' :: (Position, Direction) -> STArray s (Int, Int) MazeTile -> ST s ()
solveMaze' s@(p, d) a = do
        t <- MutableArray.readArray a p
        case t of
                Wall -> return ()
                Start -> error "Unreachable code"
                End -> error "Unreachable code"
                Unknown -> error "Starting on unexplored field"
                Explored m -> do
                        let c = m Map.! d
                        maybeExplore (c+1)    (p .+. directionVector d)  d a
                        let d' = turnRight d
                        maybeExplore (c+1001) (p .+. directionVector d') d' a
                        let d'' = turnRight d'
                        maybeExplore (c+1001) (p .+. directionVector d'') d'' a
                        let d''' = turnRight d''
                        maybeExplore (c+1001) (p .+. directionVector d''') d''' a

part1 a = runST (solveMaze a)

main = getContents
        >>= print
        . part1
        . parse

use std::cmp::{Ordering, Reverse};

use euclid::{default::*, vec2};
use priority_queue::PriorityQueue;
use rustc_hash::{FxHashMap, FxHashSet};

const DIRS: [Vector2D<i32>; 4] = [vec2(1, 0), vec2(0, 1), vec2(-1, 0), vec2(0, -1)];

type Node = (Point2D<i32>, u8);

fn parse(input: &str) -> (Vec<Vec<bool>>, Point2D<i32>, Point2D<i32>) {
    let mut start = None;
    let mut end = None;
    let mut field = Vec::new();
    for (y, l) in input.lines().enumerate() {
        let mut row = Vec::new();
        for (x, b) in l.bytes().enumerate() {
            if b == b'S' {
                start = Some(Point2D::new(x, y).to_i32());
            } else if b == b'E' {
                end = Some(Point2D::new(x, y).to_i32());
            }
            row.push(b == b'#');
        }
        field.push(row);
    }
    (field, start.unwrap(), end.unwrap())
}

fn adj(field: &[Vec<bool>], (v, dir): Node) -> Vec<(Node, u32)> {
    let mut adj = Vec::with_capacity(3);
    let next = v + DIRS[dir as usize];
    if !field[next.y as usize][next.x as usize] {
        adj.push(((next, dir), 1));
    }
    adj.push(((v, (dir + 1) % 4), 1000));
    adj.push(((v, (dir + 3) % 4), 1000));
    adj
}

fn shortest_path_length(field: &[Vec<bool>], start: Node, end: Point2D<i32>) -> u32 {
    let mut dist: FxHashMap<Node, u32> = FxHashMap::default();
    dist.insert(start, 0);
    let mut pq: PriorityQueue<Node, Reverse<u32>> = PriorityQueue::new();
    pq.push(start, Reverse(0));
    while let Some((v, _)) = pq.pop() {
        for (w, weight) in adj(field, v) {
            let dist_w = dist.get(&w).copied().unwrap_or(u32::MAX);
            let new_dist = dist[&v] + weight;
            if dist_w > new_dist {
                dist.insert(w, new_dist);
                pq.push_increase(w, Reverse(new_dist));
            }
        }
    }
    // Shortest distance to end, regardless of final direction
    (0..4).map(|dir| dist[&(end, dir)]).min().unwrap()
}

fn part1(input: String) {
    let (field, start, end) = parse(&input);
    let distance = shortest_path_length(&field, (start, 0), end);
    println!("{distance}");
}

fn shortest_path_tiles(field: &[Vec<bool>], start: Node, end: Point2D<i32>) -> u32 {
    let mut parents: FxHashMap<Node, Vec<Node>> = FxHashMap::default();
    let mut dist: FxHashMap<Node, u32> = FxHashMap::default();
    dist.insert(start, 0);
    let mut pq: PriorityQueue<Node, Reverse<u32>> = PriorityQueue::new();
    pq.push(start, Reverse(0));
    while let Some((v, _)) = pq.pop() {
        for (w, weight) in adj(field, v) {
            let dist_w = dist.get(&w).copied().unwrap_or(u32::MAX);
            let new_dist = dist[&v] + weight;
            match dist_w.cmp(&new_dist) {
                Ordering::Greater => {
                    parents.insert(w, vec![v]);
                    dist.insert(w, new_dist);
                    pq.push_increase(w, Reverse(new_dist));
                }
                // Remember both parents if distance is equal
                Ordering::Equal => parents.get_mut(&w).unwrap().push(v),
                Ordering::Less => {}
            }
        }
    }
    let mut path_tiles: FxHashSet<Point2D<i32>> = FxHashSet::default();
    path_tiles.insert(end);

    // Shortest distance to end, regardless of final direction
    let shortest_dist = (0..4).map(|dir| dist[&(end, dir)]).min().unwrap();
    for dir in 0..4 {
        if dist[&(end, dir)] == shortest_dist {
            collect_tiles(&parents, &mut path_tiles, (end, dir));
        }
    }
    path_tiles.len() as u32
}

fn collect_tiles(
    parents: &FxHashMap<Node, Vec<Node>>,
    tiles: &mut FxHashSet<Point2D<i32>>,
    cur: Node,
) {
    if let Some(pars) = parents.get(&cur) {
        for p in pars {
            tiles.insert(p.0);
            collect_tiles(parents, tiles, *p);
        }
    }
}

fn part2(input: String) {
    let (field, start, end) = parse(&input);
    let tiles = shortest_path_tiles(&field, (start, 0), end);
    println!("{tiles}");
}

util::aoc_main!();