day19_lib.tal

~library/console.lib.tal
~library/string.tal
~library/math.tal
~day19_rotations.tal

%TERMINATOR { #8080 }

%V3SIZE { #0006 } %V3PAD { $6 }

@scanner
  ( get-byte sc* -- count )
  &parse
    [ ;&parse/sc STA2 ]
    [ ;&parse/get-byte-addr STA2 ]

    [ ;&parse/sc LDA2 ] ;&init JSR2

    ;&parse/skip-line JSR2 ,&parse/header-ok JCN
      ( eof while reading header )
      #00
      RTN
    &parse/header-ok

    #00 [ ;&parse/count STA ]

    &parse/line-loop
      ;&parse/number JSR2 NOT ;&parse/done JCN2
      [ ;&parse/count *INC ]

      ;&parse/number JSR2 POP
      ;&parse/number JSR2 POP

      ( x y z )
      ;&parse/insert JSR2

      ;&parse/line-loop JMP2

    &parse/done
    ( 0000 )
    POP2

    [ ;&parse/count LDA ]
    RTN
    [ &parse/sc $2 &parse/count $1 ]

    ( -- b )
    &parse/get-byte
      LIT2 [ &parse/get-byte-addr $2 ] JMP2

    ( -- success )
    &parse/skip-line
      &parse/skip-line/loop
        ;&parse/get-byte JSR2
        DUP #00 EQU ,&parse/skip-line/eof JCN
        #0a NEQ ,&parse/skip-line/loop JCN
      #01
      RTN
      &parse/skip-line/eof
      ( 00 )
      POP #00
      RTN

    ( -- n success )
    &parse/number
      LIT2r 0000 ( : n )
      #00 [ ;&parse/number/started STA ]
      #0001 [ ;&parse/number/sign STA2 ]
      &parse/number/loop
        ;&parse/get-byte JSR2
        DUP LIT '- LTH ,&parse/number/done JCN
        DUP LIT '- NEQ ,&parse/number/positive JCN
          #ffff [ ;&parse/number/sign STA2 ]
          POP
          ,&parse/number/loop JMP
          &parse/number/positive
        LIT '0 SUB #00 SWP ( value : n )
        STH2r #000a MUL2 ADD2 STH2 ( : n*10+value )
        #01 [ ;&parse/number/started STA ]
        ,&parse/number/loop JMP
      &parse/number/done
      ( terminator )
      POP
      STH2r
      [ ;&parse/number/sign LDA2 ] MUL2
      [ ;&parse/number/started LDA ]
      RTN
      [ &parse/number/sign $2 &parse/number/started $1 ]

    ( x y z -- )
    &parse/insert
      ;&parse/v #0004 ADD2 STA2
      ;&parse/v #0002 ADD2 STA2
      ;&parse/v            STA2
      [ ;&parse/sc LDA2 ] ;&parse/v ;&insert JSR2
      RTN
      [ &parse/v V3PAD ]

  ( sc* -- )
  &dump
    ( sc* )
    &dump/loop
      LDA2k TERMINATOR EQU2 ,&dump/done JCN
      DUP2 ;vector3/print JSR2 LF
      V3SIZE ADD2
      ,&dump/loop JMP
    &dump/done
    POP2
    RTN

  ( sc* v* -- )
  &insert
    ( P< "inserting 20 >P DUP2 ;vector3/print JSR2 LF )
    ( sc* v* )
    ;&insert/v SWP2 ;vector3/copy JSR2

    ( find insertion point )
    ( sc* )
    &insert/scan-loop
      LDA2k TERMINATOR EQU2 ,&insert/scan-done JCN
      ;&insert/v OVR2 ;vector3/equal JSR2
      ( if v == *sc, abort )
      ,&insert/done JCN

      ;&insert/v OVR2 ;vector3/less-than JSR2
      ( if v < *sc, we've found our spot )
      ,&insert/scan-done JCN
      ( otherwise advance )
      V3SIZE ADD2
      ,&insert/scan-loop JMP

    &insert/scan-done

    ( make some room )
    DUP2 ;&insert/shift-right JSR2

    ( insert at spot found )
    DUP2 ;&insert/v ;vector3/copy JSR2

    &insert/done
    POP2
    RTN

    [ &insert/v V3PAD &insert/vtmp V3PAD ]

    ( sc* -- )
    &insert/shift-right
      ( scan to end )
      DUP2
      ( sc* sc-end* )
      &insert/shift-right/scan-loop
        LDA2k ( sc* sc-end* word )
        TERMINATOR EQU2 ,&insert/shift-right/at-end JCN
        V3SIZE ADD2
        ,&insert/shift-right/scan-loop JMP

      &insert/shift-right/at-end
      ( sc* sc-end* )
      ( grow list here )
      #0000 OVR2 STA2
      V3SIZE ADD2
      TERMINATOR OVR2 STA2

      ( now copy backwards until sc-end = sc )
      SWP2 STH2
      ( sc-end* : sc* )
      &insert/shift-right/copy-loop
        V3SIZE SUB2
        EQU2k ,&insert/shift-right/copy-done JCN
        ( copy left into right )
        DUP2 DUP2 V3SIZE SUB2
        ( sc-end* sc-end* sc-end-V3SIZE* )
        ;vector3/copy JSR2
        ,&insert/shift-right/copy-loop JMP

      &insert/shift-right/copy-done
      ( sc-end* : sc* )
      POP2r
      POP2
      RTN

  ( scout* scin* rotation -- )
  &rotate
    ;rotations/get JSR2
    ( scout* scin* rotate )
    ;&map JMP2

  ( scout* scin* v* -- )
  &translate
    [ ;&translate/v STA2 ]
    ;&translate/addv
    ( scout* scin* addv )
    ;&stablemap JMP2
    ( vout* vin* -- )
    &translate/addv
      LIT2 [ &translate/v $2 ] ;vector3/add JMP2

  ( sc* -- )
  &init
    TERMINATOR SWP2 STA2
    RTN

  ( scout* scin* [ vout* vin* -- ] -- )
  &map
    [ ;&map/fn STA2 ]

    ( initialize output list )
    OVR2 ;&init JSR2

    SWP2 STH2
    ( scin* : scout* )
    &map/loop
      LDA2k TERMINATOR EQU2 ,&map/done JCN
      ;&map/vout OVR2 LIT2 [ &map/fn $2 ] JSR2
      STH2rk ;&map/vout ;&insert JSR2
      ( scin* : scout* )
      V3SIZE ADD2
      ,&map/loop JMP
    &map/done
    ( scin* : scout* )
    POP2 POP2r
    RTN
    [ &map/vout V3PAD ]

  ( scout* scin* -- )
  &merge
    SWP2 STH2
    ( scin* : scout* )
    &merge/loop
      LDA2k TERMINATOR EQU2 ,&merge/done JCN
      STH2rk OVR2 ;&insert JSR2
      ( scin* : scout* )
      V3SIZE ADD2
      ,&merge/loop JMP
    &merge/done
    ( scin* : scout* )
    POP2 POP2r
    RTN

  ( sc1* sc2* -- count )
  &count-matches
    ( Both lists are sorted, this should be easy:
      - while i<len(A) and j<len(B):
        - if A[i] == B[j], increase match count, increase i, increase j;
        - otherwise if A[i] < B[j], increase i;
        - otherwise, increase j. )
    STH2
    ( sc1* : sc2* )

    #0000 [ ;&count-matches/count STA2 ]

    &count-matches/loop
      ( break if any list has reached its end )
      LDA2k TERMINATOR EQU2 ,&count-matches/done JCN
      STH2rk LDA2 TERMINATOR EQU2 ,&count-matches/done JCN
      ( sc1* : sc2* )
      DUP2 STH2rk ;vector3/equal JSR2 ,&count-matches/v1==v2 JCN

      ( sc1* : sc2* )
      DUP2 STH2rk ;vector3/less-than JSR2 ,&count-matches/v1<v2 JCN
        ( v1>v2: advance sc2* )
        STH2r V3SIZE ADD2 STH2 ( advance sc2* )
        ,&count-matches/loop JMP

      &count-matches/v1<v2
        ( v1<v2: advance sc1* )
        V3SIZE ADD2
        ,&count-matches/loop JMP

      &count-matches/v1==v2
        ( v1 == v2: increase count, advance both )
        [ ;&count-matches/count *INC2 ]
        V3SIZE ADD2            ( advance sc1* )
        STH2r V3SIZE ADD2 STH2 ( advance sc2* )
        ,&count-matches/loop JMP

    &count-matches/done

    ( sc1* : sc2* )
    POP2 POP2r
    [ ;&count-matches/count LDA2 ]
    RTN
    [ &count-matches/count $2 ]

  ( sc* -- count )
  &count
    LIT2r 0000 ( sc* : count )
    &count/loop
      LDA2k TERMINATOR EQU2 ,&count/done JCN
      INC2r
      V3SIZE ADD2
      ,&count/loop JMP
    &count/done
    POP2 STH2r
    RTN

  ( finds a vector that moves sc2 over to sc1 )
  ( sc1* sc2* target -- success )
  &find-alignment
    [ ;&fa/target STA2 ]
    ( generate all pairs )
    [ ;&fa/sc2 STA2 ]
    [ ;&fa/sc1 STA2 ]
    ( try only the first n-target+1 beacons as the first aligned )
    [ ;&fa/sc1 LDA2 ] ;&count JSR2 [ ;&fa/target LDA2 ] DEC2 SUB2 [ ;&fa/sc1count STA2 ]
    [ ;&fa/sc2 LDA2 ] ;&count JSR2 [ ;&fa/target LDA2 ] DEC2 SUB2 [ ;&fa/sc2count STA2 ]
    #0000 [ ;&fa/sc1count LDA2 ] DO
      #0000 [ ;&fa/sc2count LDA2 ] DO
        OVR2 POP2
        ( make offset vector that potentially brings sc2 into alignment with sc1: v1-v2 )
        OVR2 V3SIZE MUL2 [ ;&fa/sc1 LDA2 ] ADD2 [ ;&fa/v1 STA2 ]
        DUP2 V3SIZE MUL2 [ ;&fa/sc2 LDA2 ] ADD2 [ ;&fa/v2 STA2 ]
        ;&find-alignment/offset [ ;&fa/v1 LDA2 ] [ ;&fa/v2 LDA2 ] ;vector3/subtract JSR2

        ;&find-alignment/sc-aligned [ ;&fa/sc2 LDA2 ] ;&find-alignment/offset ;&translate JSR2

        [ ;&fa/sc1 LDA2 ] ;&find-alignment/sc-aligned ;&count-matches JSR2
        ( match-count )
        [ ;&fa/target LDA2 ] LTH2 ,&fa/not-found JCN
          UNLOOP
          UNLOOP
          #01
          RTN
          &fa/not-found
      LOOP
    LOOP
    #00
    RTN
    [ &find-alignment/offset V3PAD
      &fa/target $2
      &fa/sc1 $2
      &fa/sc2 $2
      &fa/v1 $2
      &fa/v2 $2
      &fa/sc1count $2
      &fa/sc2count $2
      &find-alignment/sc-aligned $100 ]

  ( scout* scin* -- )
  &copy
    SWP2 STH2 ( scin* : scout* )
    &copy/loop
      LDA2k TERMINATOR EQU2 ,&copy/done JCN
      LDA2k STH2rk STA2
      2++ 2++r
      ,&copy/loop JMP
    &copy/done
    POP2 POP2r
    RTN

  ( scout* scin* [ vout* vin* -- ] -- )
  &stablemap
    [ ;&stablemap/fn STA2 ]
    SWP2 STH2 ( scin* : scout* )
    &stablemap/loop
      LDA2k TERMINATOR EQU2 ,&stablemap/done JCN
      STH2rk OVR2 ( vout* vin* ) LIT2 [ &stablemap/fn $2 ] JSR2
      V3SIZE ADD2       ( advance scin* )
      V3SIZE STH2 ADD2r ( advance scout* )
      ,&stablemap/loop JMP
    &stablemap/done
    ( terminate scout* )
    LDA2 STH2r STA2
    RTN

@vector3
  ( v* -- )
  &print
    LIT '[ EMIT
    LDA2k ;print-short-decimal/signed JSR2 #0002 ADD2 SP
    LDA2k ;print-short-decimal/signed JSR2 #0002 ADD2 SP
    LDA2  ;print-short-decimal/signed JSR2
    LIT '] EMIT
    RTN

  ( vdest* vsrc* -- )
  &copy
    SWP2 V3SIZE ;memcpy JMP2

  ( vdest* v1* v2* -- )
  &add
    STH2 ( vdest* v1* : v2* )
    OVR2 SWP2 ;&copy JSR2 ( vdest*=v1 : v2* )
    LDA2k STH2rk LDA2 ADD2 OVR2 STA2 2++ 2++r
    LDA2k STH2rk LDA2 ADD2 OVR2 STA2 2++ 2++r
    LDA2k STH2r  LDA2 ADD2 SWP2 STA2
    RTN

  ( vdest* v1* v2* -- )
  &subtract
    STH2 ( vdest* v1* : v2* )
    OVR2 SWP2 ;&copy JSR2 ( vdest*=v1 : v2* )
    LDA2k STH2rk LDA2 SUB2 OVR2 STA2 2++ 2++r
    LDA2k STH2rk LDA2 SUB2 OVR2 STA2 2++ 2++r
    LDA2k STH2r  LDA2 SUB2 SWP2 STA2
    RTN

  ( v1* v2* -- distance )
  &manhattan
    STH2 ( v1* : v2* )
    LDA2k STH2rk LDA2 SUB2 ;&abs JSR2 SWP2 2++ 2++r ( dx v1* : v2* )
    LDA2k STH2rk LDA2 SUB2 ;&abs JSR2 SWP2 2++ 2++r ( dx dy v1* : v2* )
    LDA2  STH2r  LDA2 SUB2 ;&abs JSR2 ( dx dy dz )
    ADD2 ADD2
    RTN

  ( n -- |n| )
  &abs
    DUP2 #8000 LTH2 ,&abs/pos JCN
    NEG2
    &abs/pos
    RTN


  ( v1* v2* -- v1==v2 )
  &equal
    STH2 ( v1* : v2* )

    LDA2k STH2rk LDA2
    NEQ2 ,&equal/not-equal JCN
    2++ 2++r

    LDA2k STH2rk LDA2
    NEQ2 ,&equal/not-equal JCN
    2++ 2++r

    LDA2k STH2rk LDA2
    NEQ2 ,&equal/not-equal JCN
    2++ 2++r

    POP2 POP2r
    #01 RTN

    &equal/not-equal
      POP2 POP2r
      #00 RTN

  ( v1* v2* -- v1<v2 )
  &less-than
    STH2 ( v1* : v2* )
    LDA2k STH2rk LDA2
    ( v1* v1.x v2.x : v2* )
    SGTH2k ,&less-than/not-lesser JCN
      ( v1* v1.x v2.x : v2* )
      EQU2 NOT ,&less-than/lesser JCN
      ( v1.x == v2.x )

    2++ 2++r ( v1+2* : v2+2* )

    LDA2k STH2rk LDA2
    ( v1* v1.y v2.y : v2* )
    SGTH2k ,&less-than/not-lesser JCN
      ( v1* v1.y v2.y : v2* )
      EQU2 NOT ,&less-than/lesser JCN
      ( v1.y == v2.y )

    2++ 2++r ( v1+4* : v2+4* )

    LDA2k STH2rk LDA2
    ( v1* v1.z v2.z : v2* )
    SGTH2k ,&less-than/not-lesser JCN
      ( v1* v1.z v2.z : v2* )
      EQU2 NOT ,&less-than/lesser JCN
      ( v1.z == v2.z )
      POP2 POP2r #00 RTN

    &less-than/not-lesser
    ( v1* v1.? v2.? : v2* )
    POP2 POP2 POP2 POP2r #00 RTN

    &less-than/lesser
    ( v1* : v2* )
    POP2 POP2r #01 RTN


@scanners
  ( get-byte -- )
  &parse
    #0000 [ ;&count STA2 ]
    LIT2r :&scannersbuf
    ( get-byte : scannersbuf* )
    &parse/loop
      DUP2 STH2rk ;scanner/parse JSR2
      ( count )
      DUP NOT ;&parse/done JCN2
      ( count )

      ( store current pointer in scanners array )
      STH2rk ;&list [ ;&count LDA2 ] 2** ADD2 STA2

      ( count )

      ( bump pointer by scanner size )
      #00 SWP V3SIZE MUL2 2++ STH2r ADD2 STH2 ( : scannersbuf+6*count* )

      [ ;&count *INC2 ]
      ;&parse/loop JMP2

    &parse/done
    ( get-byte count : scannersbuf* )
    POP POP2 POP2r
    RTN

  ( -- )
  &dump
    [ ;&count LDA2 ] #0000 NEQ2 ,&dump/not-zero JCN
      RTN
    &dump/not-zero
    #0000 [ ;&count LDA2 ] DO
      DUP2 ;print-short-decimal JSR2 LIT ': EMIT LF
      DUP2 2** ;&list ADD2 LDA2 ;scanner/dump JSR2
    LOOP
    RTN

  ( sourceindex -- )
  &find-matches
    P< "matches_for >P SP DBGSHORTDECn LIT ': EMIT LF
    [ ;&fm/source STA2 ]
    [ ;&fm/source LDA2 ] ;&mark-as-source JSR2
    [ ;&fm/source LDA2 ] ;&get-sc JSR2 [ ;&fm/source-sc STA2 ]
    #0000 [ ;&count LDA2 ] DO
      DUP2 [ ;&fm/candidate STA2 ]
      [ ;&fm/candidate LDA2 ] ;&is-marked JSR2 ;&fm/next-candidate JCN2
      P< "against >P SP DBGSHORTDECn LIT ': EMIT SP

      [ ;&fm/candidate LDA2 ] ;&get-sc JSR2 [ ;&fm/candidate-sc STA2 ]

      ( try all rotations )
      #0000 ROTATIONCOUNT DO
        LIT 'r EMIT DBGSHORTDECn SP
        STH2k
        ;&fm/sctmp [ ;&fm/candidate-sc LDA2 ] STH2r ;scanner/rotate JSR2

        [ ;&fm/source-sc LDA2 ] ;&fm/sctmp #000c ;scanner/find-alignment JSR2
        NOT ,&fm/nomatch JCN
        P< "🎉 >P LF
        ( on success, record and move to next candidate )
        ( overwrite candidate with aligned version )
        [ ;&fm/candidate-sc LDA2 ] ;scanner/find-alignment/sc-aligned ;scanner/copy JSR2

        ( mark candidate as source )
        [ ;&fm/candidate LDA2 ] ;&mark-as-source JSR2

        ( record position )
        [ ;&fm/candidate LDA2 ] V3SIZE MUL2 ;&positions ADD2 ;scanner/find-alignment/offset ;vector3/copy JSR2

        ( stop searching for rotations )
        UNLOOP
        ,&fm/next-candidate JMP

        &fm/nomatch
      LOOP
      LF

      &fm/next-candidate
    LOOP
    ( mark source as done )
    [ ;&fm/source LDA2 ] ;&mark-as-done JSR2
    RTN
    [ &fm/source $2 &fm/source-sc $2 &fm/candidate $2 &fm/candidate-sc $2
      &fm/sctmp $100
      &fm/sctmp2 $100
      &vt 0044 fb22 ffd5 ]

  ( i -- sc* )
  &get-sc
    2** ;&list ADD2 LDA2
    RTN

  ( i -- )
  &mark-as-source
    2** ;&states ADD2 #01 ROT ROT STA
    RTN

  ( i -- )
  &mark-as-done
    2** ;&states ADD2 #02 ROT ROT STA
    RTN

  ( i -- marked )
  &is-marked
    2** ;&states ADD2 LDA #00 NEQ
    RTN

  ( i -- marked )
  &is-marked-as-source
    2** ;&states ADD2 LDA #01 EQU
    RTN

  ( -- )
  &merge-and-count
    ;&finalscanner ;scanner/init JSR2
    #0000 [ ;&count LDA2 ] DO
      P< "merge >P DBGSHORTDEC
      DUP2 ;&get-sc JSR2 ;&finalscanner SWP2 ;scanner/merge JSR2
    LOOP
    ;&finalscanner ;scanner/dump JSR2
    ;&finalscanner ;scanner/count JSR2 DBGSHORTDEC POP2
    RTN

  ( -- )
  &expand-sources
    #00 [ ;&es/found STA ]
    #0000 [ ;&count LDA2 ] DO
      DUP2 ;&is-marked-as-source JSR2 NOT ,&es/not-source JCN
        #01 [ ;&es/found STA ]
        DUP2 ;&find-matches JSR2
      &es/not-source
    LOOP
    [ ;&es/found LDA ]
    RTN
    [ &es/found $1 ]

  [ &count $2 &scannersbuf $4000 &list $100
    &states $100 &finalscanner $4000 
    &positions $100 ]

  ( i -- v* )
  &get-position
    V3SIZE MUL2 ;&positions ADD2
    RTN

  ( -- )
  &print-positions
    #0000 [ ;&pp/maxdist STA2 ]
    #0000 [ ;&count LDA2 ] DO
      DUP2 DBGSHORTDECn LIT ': EMIT ;&get-position JSR2 ;vector3/print JSR2 LF
      DUP2 ;&get-position JSR2
      #0000 [ ;&count LDA2 ] DO
        ( v1* j )
        P< "to 20 >P DBGSHORTDECn LIT ': EMIT

        DUP2 ;&get-position JSR2 STH2 ( v1* j : v2* )

        STH2rk ;vector3/print JSR2

        SP

        OVR2 STH2r ;vector3/manhattan JSR2 DBGSHORTDECn

        ( distance )
        DUP2 [ ;&pp/maxdist LDA2 ] LTH2 ,&pp/not-better JCN
          DUP2 [ ;&pp/maxdist STA2 ]
        &pp/not-better
        POP2

        LF

      LOOP
      POP2
    LOOP
    P< "maxdist= >P [ ;&pp/maxdist LDA2 ] DBGSHORTDEC POP2
    RTN
    [ &pp/vtmp V3PAD &pp/maxdist $2 ]