aoc-2022

My solutions in postscript to Advent of Code 2022
Log | Files | Refs | README | LICENSE

day17.ps (21366B)


      1 %!PS
      2 %
      3 % Copyright (c) 2022, Natacha Porté
      4 %
      5 % Permission to use, copy, modify, and distribute this software for any
      6 % purpose with or without fee is hereby granted, provided that the above
      7 % copyright notice and this permission notice appear in all copies.
      8 %
      9 % THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
     10 % WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
     11 % MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
     12 % ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
     13 % WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
     14 % ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
     15 % OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
     16 %
     17 % Usage:
     18 % gs -q- -sDEVICE=png16m -o- day17.ps <day17.txt | display
     19 
     20 /datafile (%stdin) (r) file def
     21 /stderr (%stderr) (w) file def
     22 
     23 /data datafile 10100 string readline not { quit } if def
     24 
     25 /width 7 def
     26 
     27 % height -> arena
     28 /new-arena {
     29   % height
     30   width mul dup string exch
     31   % new-arena length
     32   1 sub
     33   % new-arena last-index
     34   0 1 3 2 roll {
     35     % new-arena index
     36     1 index exch 46 put % `.`
     37     % new-arena
     38   } for
     39   % new-arena
     40 } bind def
     41 
     42 % arena ->
     43 /dump-arena {
     44   % arena
     45   dup length width sub
     46   % arena first-index
     47   width neg 0 {
     48     % arena cur-index
     49     1 index exch width getinterval
     50     % arena cur-line
     51     stderr exch writestring
     52     stderr 10 write
     53     % arena
     54   } for
     55   % arena
     56   pop
     57 } bind def
     58 
     59 %%% [dx dy] of cells used by each shape, from the bottom left corner
     60 /shapes [
     61   %%% -
     62   [[0 0] [1 0] [2 0] [3 0]]
     63   %%% +
     64   [[1 0] [0 1] [1 1] [2 1] [1 2]]
     65   %%% J
     66   [[0 0] [1 0] [2 0] [2 1] [2 2]]
     67   %%% I
     68   [[0 0] [0 1] [0 2] [0 3]]
     69   %%% O
     70   [[0 0] [1 0] [0 1] [1 1]]
     71 ] def
     72 
     73 % arena shape-id x y -> bool
     74 /shape-fits? {
     75   % arena shape-id x y
     76   3 2 roll shapes length mod shapes exch get
     77   % arena x y cell-array
     78   true exch
     79   % arena x y result cell-array
     80   {
     81     % arena x y result cur-cell
     82     aload pop
     83     % arena x y result dx dy
     84     3 index add exch 4 index add
     85     % arena x y result cell-y cell-x
     86     dup 0 ge
     87     % arena x y result cell-y cell-x cell-x>=0?
     88     1 index width lt and
     89     % arena x y result cell-y cell-x cell-x-valid?
     90     2 index 0 ge and
     91     % arena x y result cell-y cell-x cell-xy-valid?
     92     { exch width mul add
     93       % arena x y result cell-offset
     94       4 index exch get
     95       % arena x y result cell-char
     96       46 eq
     97       % arena x y result cell-empty?
     98       not { pop false exit } if
     99       % arena x y result
    100     }
    101     { pop pop pop false exit }
    102     ifelse
    103     % arena x y result
    104   } forall
    105   % arena x y result
    106   4 1 roll pop pop pop
    107   % result
    108 } bind def
    109 
    110 % arena shape-id x y char ->
    111 /put-shape {
    112   % arena shape-id x y char
    113   4 3 roll
    114   % arena x y char shape-id
    115   shapes length mod shapes exch get
    116   % arena x y char cell-array
    117   {
    118     % arena x y char cur-cell
    119     aload pop
    120     % arena x y char dx dy
    121     3 index add exch 4 index add exch
    122     % arena x y char cell-x cell-y
    123     width mul add
    124     % arena x y char cell-offset
    125     4 index exch 2 index put
    126     % arena x y char
    127   } forall
    128   % arena x y char
    129   pop pop pop pop
    130   %
    131 } bind def
    132 
    133 % arena -> y
    134 /top-used-line {
    135   % arena
    136   dup length width idiv 1 sub
    137   % arena max-y
    138   {
    139     % arena cur-y
    140     dup 0 lt { exit } if
    141     % arena cur-y
    142     true
    143     % arena cur-y line-empty?
    144     0 1 width 1 sub {
    145       % arena cur-y line-empty? cur-x
    146       2 index width mul add
    147       % arena cur-y line-empty? cur-offset
    148       3 index exch get
    149       % arena cur-y line-empty? cur-cell
    150       46 eq
    151       % arena cur-y line-empty? cur-cell-empty?
    152       not { pop false exit } if
    153       % arena cur-y line-empty?
    154     } for
    155     % arena cur-y line-empty?
    156     not { exit } if
    157     % arena cur-y
    158     1 sub
    159     % arena next-y
    160   } loop
    161   % arena result
    162   exch pop
    163   % result
    164 } bind def
    165 
    166 % arena -> height-array
    167 /column-heights {
    168   % arena
    169   [ exch 0 1 width 1 sub {
    170       % mark prev-heights arena x
    171       1 index length width idiv
    172       % mark prev-heights arena x max-y+1
    173       {
    174         % mark prev-heights arena x prev-y
    175         1 sub
    176         % mark prev-heights arena x y
    177         dup 0 lt { exit } if
    178         % mark prev-heights arena x y
    179         dup width mul 2 index add
    180         % mark prev-heights arena x y offset
    181         3 index exch get 46 eq
    182         % mark prev-heights arena x y cell-empty?
    183         not { exit } if
    184         % mark prev-heights arena x y
    185       } loop
    186       % mark prev-heights arena x y
    187       3 1 roll pop
    188       % mark prev-heights y arena
    189     } for
    190     % mark heights arena
    191     pop
    192   ]
    193   % height-array
    194 } bind def
    195 
    196 % arena -> height-array
    197 /column-reverse-heights {
    198   % arena
    199   column-heights
    200   % height-array
    201   0 1 index {
    202     % height-array prev-max cur-item
    203     2 copy lt { exch } if pop
    204     % height-array cur-max
    205   } forall
    206   % height-array max
    207   exch
    208   % max height-array
    209   [ 3 1 roll
    210     % mark max height-array
    211     {
    212       % mark prev-items max cur-height
    213       1 index exch sub
    214       % mark prev-items max cur-item
    215       exch
    216       % mark prev-items cur-item max
    217     } forall
    218     % mark items max
    219     pop
    220   ]
    221   % reverse-height-array
    222 } bind def
    223 
    224 % array1 array2 -> bool
    225 /deep-eq {
    226   % array1 array2
    227   dup length
    228   % array1 array2 length2
    229   2 index length 1 index eq
    230   { % array1 array2 length
    231     true exch
    232     % array1 array2 cur-result length
    233     1 sub 0 1 3 2 roll {
    234       % array1 array2 prev-result index
    235       3 index 1 index get
    236       % array1 array2 prev-result index item1
    237       3 index 2 index get eq
    238       % array1 array2 prev-result index item1=item2?
    239       exch pop and
    240       % array1 array2 cur-result
    241       dup not { exit } if
    242       % array1 array2 cur-result
    243     } for
    244     % array1 array2 result
    245     3 1 roll pop pop
    246     % result
    247   }
    248   { pop pop pop false }
    249   ifelse
    250 } bind def
    251 
    252 % arena empty-lines-needed -> new-arena
    253 /ensure-lines {
    254   % arena empty-lines-needed
    255   1 index top-used-line 1 add
    256   % arena empty-lines-needed lines-used
    257   add
    258   % arena total-lines-needed
    259   width mul
    260   % arena total-length-needed
    261   1 index length 1 index ge
    262   % arena total-length-needed arena-is-big-enough?
    263   { pop }
    264   { % arena total-length-needed
    265     dup string exch
    266     % old-arena new-arena new-arena-length
    267     2 index length exch
    268     % old-arena new-arena old-arena-length new-arena-length
    269     1 sub 1 exch {
    270       % old-arena new-arena new-index
    271       1 index exch 46 put
    272       % old-arena new-arena
    273     } for
    274     % old-arena new-arena
    275     dup 0 4 3 roll putinterval
    276     % new-arena
    277   }
    278   ifelse
    279   % arena
    280 } bind def
    281 
    282 % arena -> shape-x shape-y
    283 /create-shape {
    284   % arena
    285   top-used-line 4 add
    286   % shape-y
    287   2 exch
    288   % shape-x shape-y
    289 } bind def
    290 
    291 % prev-arena prev-shape-id prev-time -> arena last-shape-id last-time
    292 /simulate-rock {
    293   % prev-arena prev-shape-id prev-time
    294   exch 1 add exch
    295   % prev-arena shape-id prev-time
    296   3 2 roll 7 ensure-lines 3 1 roll
    297   % arena shape-id prev-time
    298   2 index create-shape
    299   % arena shape-id prev-time shape-x shape-y
    300   {
    301     % arena shape-id prev-time shape-x shape-y
    302     3 2 roll 1 add dup 4 1 roll
    303     % arena shape-id time shape-x shape-y time
    304     data length mod
    305     % arena shape-id time shape-x shape-y move-offset
    306     data exch get
    307     % arena shape-id time shape-x shape-y move-char
    308     dup 60 eq
    309     % arena shape-id time shape-x shape-y move-char move-left?
    310     { pop -1 }
    311     { 62 eq
    312       % arena shape-id time shape-x shape-y move-right?
    313       { 1 }
    314       { 1.125 pstack quit }
    315       ifelse
    316     }
    317     ifelse
    318     % arena shape-id time shape-x shape-y dx
    319     2 index add
    320     % arena shape-id time shape-x shape-y new-shape-x
    321     5 index 5 index 2 index 4 index shape-fits?
    322     % arena shape-id time shape-x shape-y new-shape-x x-move-ok?
    323     { exch 3 2 roll pop }
    324     { pop }
    325     ifelse
    326     % arena shape-id time shape-x shape-y
    327     4 index 4 index 3 index 3 index 1 sub shape-fits?
    328     % arena shape-id time shape-x shape-y y-move-ok?
    329     { 1 sub }
    330     { % arena shape-id time shape-x shape-y
    331       4 index 4 index 4 2 roll
    332       % arena shape-id time arena shape-id shape-x shape-y
    333       35 put-shape % `#`
    334       % updated-arena shape-id time
    335       exit
    336     }
    337     ifelse
    338     % arena shape-id time shape-x shape-y
    339   } loop
    340   % updated-arena new-shape-id time
    341 } bind def
    342 
    343 
    344 /Helvetica 20 selectfont
    345 
    346 
    347 (First Puzzle: )
    348 72 700 moveto show
    349 
    350 10 new-arena -1 -1
    351 % arena shape-id time
    352 2022 { simulate-rock } repeat
    353 % arena last-shape-id last-time
    354 pop pop top-used-line 1 add
    355 % tower-height
    356 15 string cvs show
    357 
    358 (Second Puzzle: )
    359 72 664 moveto show
    360 
    361 %%% Let's assume no rock will be tucked below an overhang,
    362 %%% So that the whole floor can be represented by the height difference
    363 %%% of each cell with the tallest one.
    364 %%% We will use the convention of Y positive downwards, and Y=0 for the
    365 %%% highest non-empty row.
    366 %%% The height difference array, rock shape, and wind index describe
    367 %%% completely a state, and will be looking for a cycle
    368 %%%
    369 %%% UPDATE: turns out the reference inputs don't involve such a tuck,
    370 %%% but my input does. So most of the simulation stuff below is not
    371 %%% good enough. Let's try assuming the height difference array is good
    372 %%% enough as a hash of the current state, and use the pedestrian
    373 %%% simulation to derive the state machine.
    374 
    375 /shape-width [
    376   shapes {
    377     % cell-array
    378     0 exch {
    379       % prev-max-dx cell
    380       0 get
    381       % prev-max-dx cur-dx
    382       2 copy lt { exch } if pop
    383       % max-dx
    384     } forall
    385     % max-dx
    386     1 add
    387   } forall
    388 ] def
    389 
    390 % floor-array shape-id any shape-x shape-y -> bool
    391 /shape-fits-2 {
    392   { %%% 1-iteration loop to use `exit` as a short circuit
    393     % floor-array shape-id any shape-x shape-y
    394     1 index 0 lt
    395     % floor-array shape-id any shape-x shape-y shape-x<0
    396     5 index length 5 index shape-width exch get sub
    397     % floor-array shape-id any shape-x shape-y shape-x<0 max-shape-x
    398     3 index lt or
    399     % floor-array shape-id any shape-x shape-y shape-x-oob?
    400     { pop pop pop pop pop false exit } if
    401     % floor-array shape-id any shape-x shape-y
    402     dup 0 lt
    403     { pop pop pop pop pop true exit } if
    404     % floor-array shape-id any shape-x shape-y
    405     true 6 1 roll
    406     % true floor-array shape-id any shape-x shape-y
    407     shapes 4 index get {
    408       % result floor-array shape-id any shape-x shape-y cell
    409       aload pop
    410       % result floor-array shape-id any shape-x shape-y dx dy
    411       2 index exch sub
    412       % result floor-array shape-id any shape-x shape-y dx cell-y
    413       exch 3 index add
    414       % result floor-array shape-id any shape-x shape-y cell-y cell-x
    415       6 index exch get
    416       % result floor-array shape-id any shape-x shape-y cell-y floor-height-at-x
    417       ge {
    418         % result floor-array shape-id any shape-x shape-y
    419         6 5 roll pop false 6 1 roll
    420         % result floor-array shape-id any shape-x shape-y
    421         exit
    422       } if
    423       % result floor-array shape-id any shape-x shape-y
    424     } forall
    425     % result floor-array shape-id any shape-x shape-y
    426     pop pop pop pop pop
    427     % result
    428     exit
    429   } loop
    430 } bind def
    431 
    432 /wind-dx <<
    433  60 -1
    434  62  1
    435 >> def
    436 
    437 % floor-array shape-id wind-id shape-x shape-y
    438 %   -> floor-array shape-id wind-id shape-x shape-y finished?
    439 /time-step {
    440   % floor-array shape-id wind-id shape-x shape-y
    441   5 copy
    442   % save floor-array shape-id wind-id shape-x shape-y
    443   2 index data exch get wind-dx exch get
    444   % save floor-array shape-id wind-id shape-x shape-y wind-dx
    445   3 2 roll add
    446   % save floor-array shape-id wind-id shape-y updated-shape-x
    447   dup 6 1 roll exch
    448   % save updated-shape-x floor-array shape-id wind-id updated-shape-x shape-y
    449   shape-fits-2
    450   % floor-array shape-id wind-id shape-x shape-y updated-shape-x fits?
    451   { 3 1 roll exch } if pop
    452   % floor-array shape-id wind-id new-shape-x shape-y
    453   1 add
    454   % floor-array shape-id wind-id new-shape-x new-shape-y
    455   5 copy shape-fits-2
    456   % floor-array shape-id wind-id new-shape-x new-shape-y fits?
    457   { false }
    458   { 1 sub true }
    459   ifelse
    460 } bind def
    461 
    462 % total-height floor-array shape-id wind-id
    463 %   -> total-height floor-array shape-id wind-id
    464 /rock-step {
    465   % total-height floor-array shape-id wind-id
    466   2 -4
    467   % total-height floor-array shape-id wind-id shape-x shape-y
    468   { time-step
    469     % total-height floor-array shape-id wind-id shape-x shape-y finished?
    470     4 3 roll 1 add data length mod 4 1 roll
    471     % total-height floor-array shape-id next-wind-id shape-x shape-y finished?
    472     { exit } if
    473   } loop
    474   % total-height floor-array shape-id wind-id shape-x shape-y
    475   0 6 1 roll
    476   % total-height floor-min floor-array shape-id wind-id shape-x shape-y
    477   shapes 4 index get {
    478     % total-height floor-min floor-array shape-id wind-id shape-x shape-y cell
    479     aload pop
    480     % total-height floor-min floor-array shape-id wind-id shape-x shape-y dx dy
    481     2 index exch sub exch 3 index add exch
    482     % total-height floor-min floor-array shape-id wind-id shape-x shape-y cell-x cell-y
    483     6 index 2 index get
    484     % total-height floor-min floor-array shape-id wind-id shape-x shape-y cell-x cell-y floor-y
    485     2 copy gt { exch } if pop
    486     % total-height floor-min floor-array shape-id wind-id shape-x shape-y cell-x new-floor-y
    487     dup 8 index lt
    488     { 8 7 roll pop dup 8 1 roll } if
    489     % total-height floor-min floor-array shape-id wind-id shape-x shape-y cell-x new-floor-y
    490     6 index 3 1 roll put
    491     % total-height floor-min floor-array shape-id wind-id shape-x shape-y
    492   } forall
    493   % total-height floor-min floor-array shape-id wind-id shape-x shape-y
    494   pop pop
    495   % total-height floor-min floor-array shape-id wind-id
    496   5 3 roll
    497   % floor-array shape-id wind-id total-height floor-min
    498   exch 1 index sub
    499   % floor-array shape-id wind-id floor-min new-total-height
    500   5 1 roll
    501   % total-height floor-array shape-id wind-id floor-min
    502   0 1 5 index length 1 sub {
    503     % total-height floor-array shape-id wind-id floor-min i
    504     4 index 1 index get
    505     % total-height floor-array shape-id wind-id floor-min i old-y
    506     2 index sub
    507     % total-height floor-array shape-id wind-id floor-min i new-y
    508     5 index 3 1 roll put
    509     % total-height floor-array shape-id wind-id floor-min
    510   } for
    511   % total-height floor-array shape-id wind-id floor-min
    512   pop
    513   % total-height floor-array shape-id wind-id
    514   exch 1 add shapes length mod exch
    515   % total-height floor-array next-shape-id wind-id
    516 } bind def
    517 
    518 % floor-array shape-id wind-id -> key
    519 /state-to-key {
    520   % floor-array shape-id wind-id
    521   2 index length 3 add string
    522   % floor-array shape-id wind-id empty-key
    523   0 1 5 index length 1 sub {
    524     % floor-array shape-id wind-id key index
    525     4 index 1 index get
    526     % floor-array shape-id wind-id key index value
    527     2 index 3 1 roll put
    528     % floor-array shape-id wind-id key
    529   } for
    530   % floor-array shape-id wind-id key
    531   4 3 roll length
    532   % shape-id wind-id key shape-index
    533   1 index 1 index 5 index put
    534   % shape-id wind-id key shape-index
    535   1 add
    536   % shape-id wind-id key MSB-wind-index
    537   1 index 1 index 4 index 256 idiv put
    538   % shape-id wind-id key MSD-wind-index
    539   1 add
    540   % shape-id wind-id key LSD-wind-index
    541   1 index 1 index 4 index 256 mod put
    542   % shape-id wind-id key LSD-wind-index
    543   4 2 roll pop pop pop
    544   % key
    545 } bind def
    546 
    547 % key ->
    548 /dump-key {
    549   stderr ([) writestring
    550   {
    551     % char
    552     15 string cvs
    553     % (element)
    554     dup length 4 exch sub
    555     % (element) pad-count
    556     { stderr 32 write } repeat
    557     stderr exch writestring
    558   } forall
    559   stderr ( ]) writestring
    560 } bind def
    561 
    562 /state-machine 10000 dict def
    563 
    564 %%% 0 0 [ 7 { 0 } repeat ] 0 0
    565 %%% % stone-count total-height floor-array shape-id wind-id
    566 %%% 3 copy state-to-key 5 1 roll
    567 %%% {
    568 %%%   % prev-stone-count prev-key total-height floor-array shape-id wind-id
    569 %%%   6 5 roll 1 add 6 1 roll
    570 %%%   % stone-count prev-key total-height floor-array shape-id wind-id
    571 %%%   rock-step
    572 %%%   % stone-count prev-key total-height floor-array shape-id wind-id
    573 %%%   3 copy state-to-key
    574 %%%   % stone-count prev-key total-height floor-array shape-id wind-id new-key
    575 %%%   state-machine 6 index known
    576 %%%   { % stone-count prev-key total-height floor-array shape-id wind-id new-key
    577 %%%     stderr (Cycle found from stone ) writestring
    578 %%%     state-machine 6 index get 1 get
    579 %%%     stderr exch 15 string cvs writestring
    580 %%%     stderr ( at height ) writestring
    581 %%%     state-machine 6 index get 2 get
    582 %%%     stderr exch 15 string cvs writestring
    583 %%%     stderr ( to stone ) writestring
    584 %%%     6 index stderr exch 15 string cvs writestring
    585 %%%     stderr ( at height ) writestring
    586 %%%     4 index stderr exch 15 string cvs writestring
    587 %%%     stderr 10 write
    588 %%%     exit
    589 %%%   } if
    590 %%%   % stone-count prev-key total-height floor-array shape-id wind-id new-key
    591 %%%   [ 1 index 8 index 7 index ]
    592 %%%   % stone-count prev-key total-height floor-array shape-id wind-id new-key record
    593 %%%   6 index exch state-machine 3 1 roll put
    594 %%%   % stone-count prev-key total-height floor-array shape-id wind-id new-key
    595 %%%   6 1 roll 5 4 roll pop
    596 %%%   % stone-count new-key total-height floor-array shape-id wind-id
    597 %%% } loop
    598 %%% %%% At the end of the first cycle:
    599 %%% % stone-count prev-key total-height floor-array shape-id wind-id begin-key
    600 %%% 4 1 roll pop pop pop
    601 %%% % stone-count prev-key total-height begin-key
    602 %%% state-machine 3 index get aload pop
    603 %%% % stone-count prev-key total-height begin-key next-key begin-count begin-height
    604 %%% 5 4 roll 1 index sub
    605 %%% % stone-count prev-key begin-key next-key begin-count begin-height cycle-height
    606 %%% 7 6 roll 3 index sub
    607 %%% % prev-key begin-key next-key begin-count begin-height cycle-height cycle-count
    608 %%% 6 4 roll pop pop
    609 %%% % prev-key begin-count begin-height cycle-height cycle-count
    610 %%% 2022
    611 %%% % prev-key begin-count begin-height cycle-height cycle-count problem-count
    612 %%% 5 4 roll sub 4 3 roll pop
    613 %%% % prev-key cycle-height cycle-count problem-count-left
    614 %%% dup 2 index idiv
    615 %%% % prev-key cycle-height cycle-count problem-count-left full-cycles-in-problem
    616 %%% stderr (Found ) writestring
    617 %%% stderr 1 index 15 string cvs writestring
    618 %%% stderr ( cycles\012) writestring
    619 %%% % prev-key cycle-height cycle-count problem-count-left full-cycles-in-problem
    620 %%% 3 index mul exch
    621 %%% % prev-key cycle-height cycle-count height-in-full-cycles problem-count-left
    622 %%% 2 index mod
    623 %%% % prev-key cycle-height cycle-count height-in-full-cycles count-in-last-cycle
    624 %%% 4 index exch {
    625 %%%   % ... cur-key
    626 %%%   state-machine exch get 0 get
    627 %%%   % ... next-key
    628 %%% } repeat
    629 %%% % prev-key cycle-height cycle-count height-in-full-cycles last-key
    630 %%% state-machine exch get 2 get
    631 %%% % prev-key cycle-height cycle-count height-in-full-cycles last-height
    632 %%% add
    633 %%% % prev-key cycle-height cycle-count total-height
    634 %%% stderr (Result: ) writestring
    635 %%% stderr exch 15 string cvs writestring
    636 %%% stderr 10 write
    637 
    638 % key -> floor-array
    639 /key-to-column-heights {
    640   [ exch { } forall pop pop pop ]
    641 } bind def
    642 
    643 [ 7 { 0 } repeat ] 0 0
    644 state-to-key
    645 10 new-arena -1 -1
    646 % key arena rock-count time
    647 {
    648   % cur-key arena rock-count time
    649   simulate-rock
    650   % prev-key arena rock-count time
    651   2 index column-reverse-heights
    652   % prev-key arena rock-count time floor-array
    653   2 index shapes length mod
    654   % prev-key arena rock-count time floor-array shape-id
    655   2 index data length mod
    656   % prev-key arena rock-count time floor-array shape-id wind-id
    657   state-to-key
    658   % prev-key arena rock-count time cur-key
    659   state-machine 5 index known { exit } if
    660   % prev-key arena rock-count time cur-key
    661   [ 1 index 4 index 6 index top-used-line 1 add ]
    662   % prev-key arena rock-count time cur-key record
    663   state-machine exch 6 index exch put
    664   % prev-key arena rock-count time cur-key
    665   5 1 roll 4 3 roll pop
    666   % cur-key arena rock-count time
    667 } loop
    668 %%% We found a cycle here:
    669 %%%   prolog ---> last-prolog-key,count1,height1
    670 %%%   last-prolog-key ---> first-cycle-key,count2,height2
    671 %%%   first-cycle-key ---> second-cycle-key,count3,height3
    672 %%%   last-cycle-key  ---> first-cycle-key,count4,height4 ---> current-state
    673 
    674 % first-cycle-key arena rock-count time second-cycle-key
    675 pop
    676 % first-cycle-key arena rock-count time
    677 state-machine 4 index get aload pop 3 2 roll pop
    678 % first-cycle-key arena rock-count time count3 height3
    679 4 index top-used-line 1 add exch sub
    680 % first-cycle-key arena rock-count time count3 cycle-height
    681 3 index 2 index sub
    682 % first-cycle-key arena rock-count time count3 cycle-height cycle-count
    683 stderr (Cycle height: ) writestring
    684 stderr 2 index 15 string cvs writestring
    685 stderr (\012Cycle count: ) writestring
    686 stderr 1 index 15 string cvs writestring
    687 stderr (\012Cycle start: ) writestring
    688 stderr 3 index 15 string cvs writestring
    689 stderr 10 write
    690 % first-cycle-key arena rock-count time count3 cycle-height cycle-count
    691 6 3 roll pop pop pop
    692 % first-cycle-key count3 cycle-height cycle-count
    693 1000000000000
    694 % first-cycle-key count3 cycle-height cycle-count problem-count
    695 3 index sub
    696 % first-cycle-key count3 cycle-height cycle-count problem-count-after-prolog
    697 dup 2 index idiv
    698 % first-cycle-key count3 cycle-height cycle-count problem-count-after-prolog problem-cycles
    699 exch 2 index mod
    700 % first-cycle-key count3 cycle-height cycle-count problem-cycles epilog-count
    701 state-machine 6 index get exch 1 sub {
    702   % prev-state
    703   0 get
    704   % prev-key
    705   state-machine exch get
    706   % cur-state
    707 } repeat
    708 % first-cycle-key count3 cycle-height cycle-count problem-cycles last-state
    709 2 get
    710 % first-cycle-key count3 cycle-height cycle-count problem-cycles epilog-height
    711 exch 3 index mul add
    712 % first-cycle-key count3 cycle-height cycle-count problem-height
    713 15 string cvs show
    714 
    715 showpage
    716 quit