{ lib, utils, ... }:
with lib;
with builtins;
with utils;
let
  grid = map stringToCharacters (readLines ./input);
  rotMat = [ [ 0 1 ] [ (-1) 0 ] ];

  state = let
    r = findFirst (pipe' [ (elemAt grid) (elem "^") ]) 0 (listRange grid);
    c = let row = elemAt grid r;
    in findFirst (pipe' [ (elemAt row) (eq "^") ]) 0 (listRange row);
  in rec {
    pos = [ r c ];
    direction = [ (-1) 0 ];
    path = [ pos ];
    cyclic = false;
    turns = { }; # only turns are relevant to check cycles
  };

  constructPath = state: extraObstruction:
    let
      isBlocked = pos: (matIndex pos grid) == "#" || pos == extraObstruction;

      # batch pathing via "ray cast" to reduce required recursion depth to something the interpretter likes
      pathAddition =
        raycastUntil (pos: !inRangeMatrix pos grid || isBlocked pos)
        state.direction state.pos;

      pos = last pathAddition;
      turnEntry = "${toString pos} ${toString state.direction}";
    in if (inRangeMatrix (vecSum pos state.direction) grid)
    && !state.cyclic then
      (constructPath {
        direction = matVecMul rotMat state.direction;
        inherit pos;
        path = state.path ++ pathAddition;
        cyclic = state.cyclic
          || (hasAttr turnEntry state.turns); # logarithmic lookup
        turns = state.turns // { "${turnEntry}" = null; };
      } extraObstruction)
    else {
      inherit pos;
      inherit (state) direction cyclic turns;
      path = state.path ++ pathAddition;
    };

  uniquePositions = unique (constructPath state null).path;

  obstructionCandidates = remove state.pos uniquePositions;

in {
  part1 = length uniquePositions;
  part2 = count (candidate: (constructPath state candidate).cyclic)
    obstructionCandidates;
}