day20.ps (4974B)
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- day20.ps <day20.txt | display 19 20 % array value -> index 21 /find-in-array { 22 % array value 23 -1.125 0 1 4 index length 1 sub { 24 % array value result cur-index 25 3 index 1 index get 26 % array value result cur-index cur-value 27 3 index eq 28 { % array value result cur-index 29 exch pop exit } if 30 % array value result cur-index 31 pop 32 % array value result 33 } for 34 % array value result 35 3 1 roll pop pop 36 % result 37 } bind def 38 39 % array orig-index distance -> 40 /move-in-array { 41 % array orig-index unbounded-distance 42 2 index length 43 % array orig-index unbounded-distance length 44 exch 1 index 1 sub mod 45 % array orig-index length distance 46 dup 0 eq 47 { pop pop pop pop } 48 { 49 % array orig-index length distance 50 3 index 3 index get 51 % array orig-index length distance pivot 52 3 index 1 add 3 index lt 53 % array orig-index length distance pivot orig-not-last? 54 { 55 % array orig-index length distance pivot 56 4 index 4 index 1 add 4 index 1 index sub getinterval 57 % array orig-index length distance pivot slice-after-pivot 58 5 index exch 5 index exch putinterval 59 } if 60 % array-without-pivot orig-index length distance pivot 61 exch 4 3 roll add 62 % array-without-pivot length pivot extended-dest-index 63 dup 0 lt { 2 index 1 sub add } if 64 dup 3 index ge { 2 index sub 1 add } if 65 % array-without-pivot length pivot dest-index 66 dup 1 add 3 index lt 67 % array-without-pivot length pivot dest-index dest-not-last? 68 { 69 % array-without-pivot length pivot dest-index 70 3 index 1 index 4 index 1 index sub 1 sub getinterval 71 % array-without-pivot length pivot dest-index slice-after-dest 72 4 index exch 2 index 1 add exch putinterval 73 % array-with-room-for-dest length pivot dest-index 74 } if 75 % array-with-room-for-dest length pivot dest-index 76 exch 3 index 3 1 roll put 77 % final-array length 78 pop pop 79 % 80 } 81 ifelse 82 } bind def 83 84 % index-array factor -> updated-index-array 85 /mix { 86 % init-index-array factor 87 exch 88 % factor init-index-array 89 0 1 data length 1 sub { 90 % factor prev-index-array cur-index 91 data 1 index get 92 % factor prev-index-array cur-index data-entry 93 3 index mul exch 94 % factor prev-index-array distance cur-index 95 2 index exch find-in-array 96 % factor prev-index-array distance index-in-index 97 exch 2 index 3 1 roll 98 % factor prev-index-array prev-index-array index-in-index distance 99 move-in-array 100 % factor index-array 101 } for 102 } bind def 103 104 % index-array -> result 105 /compute-result { 106 % index-array 107 data 0 find-in-array 108 % index-array index-of-0 109 1 index exch find-in-array 110 % index-array index-of-index-of-0 111 1000 add 1 index length mod 112 % index-array index-of-1000th 113 2 copy get 114 % index-array index-of-1000th 1000th 115 data exch get 116 % index-array index-of-1000th value-of-1000th 117 exch 1000 add 2 index length mod 118 % index-array value-of-1000th index-of-2000th 119 2 index 1 index get data exch get exch 120 % index-array value-of-1000th value-of-2000th index-of-2000th 121 1000 add 3 index length mod 122 % index-array value-of-1000th value-of-2000th index-of-3000th 123 3 index exch get data exch get 124 % index-array value-of-1000th value-of-2000th value-of-3000th 125 add add 126 % index-array result 127 exch pop 128 } bind def 129 130 % value-array index-array -> array 131 /dereference-array { 132 [ 3 1 roll 133 % mark value-array index-array 134 { 135 % mark prev-items value-array cur-index 136 1 index exch get 137 % mark prev-items value-array cur-item 138 exch 139 % mark prev-items cur-item value-array 140 } forall 141 % mark items value-array 142 pop 143 ] 144 } bind def 145 146 /datafile (%stdin) (r) file def 147 /stderr (%stderr) (w) file def 148 149 /data [ 150 { 151 datafile 300 string readline 152 not { pop exit } if 153 cvi 154 } loop 155 ] def 156 157 158 /Helvetica 20 selectfont 159 160 161 (First Puzzle: ) 162 72 700 moveto show 163 164 [ 0 1 data length 1 sub { } for ] 165 % init-indices 166 1 mix 167 % final-index-array 168 compute-result 15 string cvs show 169 170 171 (Second Puzzle: ) 172 72 664 moveto show 173 174 [ 0 1 data length 1 sub { } for ] 175 % init-indices 176 10 { 811589153 mix } repeat 177 % final-index-array 178 compute-result 811589153 mul 179 15 string cvs show 180 181 182 showpage 183 quit