! So umm.. I'm not exactly proud of this, but I also am.
! I've always found pathfinding to be incomprehensible.
! I just broke the problem up into tiny pieces that I could understand.
! It's not the prettiest and uses a lot of mutation, but...
! It solves part1 and part2 in 24 milliseconds somehow, so
! I'm also sort of happy with it.

USING: arrays io.encodings.ascii io.files kernel literals math
math.matrices math.order math.vectors namespaces prettyprint
sequences sequences.extras sequences.generalizations sets ;
FROM: namespaces => set ;
IN: aoc2022.day12

<<

CONSTANT: input
    $[ "vocab:aoc2022/day12/input.txt" ascii file-lines ]

: matrix-index ( obj matrix -- loc )
    f spin '[ nip [ _ = ] find ] find drop swap 2array ;

>>

<< CONSTANT: start-loc $[ CHAR: S input matrix-index ] >>
CONSTANT: end-loc $[ CHAR: E input matrix-index ]
CONSTANT: visited $[ input dimension first2 f <matrix> ]
CONSTANT: forefront $[ start-loc V{ } 1sequence ]
CONSTANT: adjacent { { 1 0 } { -1 0 } { 0 1 } { 0 -1 } }
SYMBOL: steps
: end ( -- n ) end-loc visited matrix-nth ;
: visit ( -- ) steps get forefront visited matrix-set-nths ;
: (neighbors) ( loc -- seq ) adjacent [ v+ ] with map ;
: vbetween? ( u vmin wmax -- ? ) [ between? ] 3 nall? ;

: inside ( seq matrix -- newseq )
    dimension 1 v-n { 0 0 } swap [ vbetween? ] 2curry filter ;

: neighbors ( matrix loc -- seq ) (neighbors) swap inside ;
: neighbors* ( matrix loc -- seq )
    neighbors [ visited matrix-nth ] reject ;

: traversable? ( current new -- ? )
    [ CHAR: a = swap CHAR: S = and ]
    [ CHAR: E = swap CHAR: z = and ]
    [ dup CHAR: E = not -rot - -1 >= and ] 2tri or or ;

: neighbors** ( matrix loc -- seq )
    [ swap matrix-nth ] [ neighbors* ] 2bi
    [ input matrix-nth traversable? ] with filter ;

: new-forefront ( -- seq )
    forefront [ input swap neighbors** ] map-concat ;

: step ( -- )
    visit new-forefront members forefront delete-all
    forefront push-all steps inc ;

: pathfind ( -- ) 0 steps set [ end ] [ step ] until ;

: part1 ( -- ) pathfind end . ;

: reset ( -- )
    visited [ [ drop f ] map! ] map! drop forefront delete-all ;

: part2 ( -- )
    reset input dimension <coordinate-matrix> concat
    [ input matrix-nth { CHAR: S CHAR: a } member? ] filter
    forefront push-all pathfind end . ;

: day12 ( -- ) part1 part2 ;

MAIN: day12