56 lines
1.7 KiB
Nix
56 lines
1.7 KiB
Nix
{ 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;
|
|
}
|