day09.ps (11776B)
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- day09.ps <day09.txt | display 19 20 /datafile (%stdin) (r) file def 21 /stderr (%stderr) (w) file def 22 23 % tail-x tail-y head-x head-y dx dy -> tail-x tail-y head-x head-y 24 /move-head { 25 % old-tail-x old-tail-y old-head-x old-head-y dx dy 26 exch 4 1 roll 27 % old-tail-x old-tail-y dx old-head-x old-head-y dy 28 add 3 1 roll 29 % old-tail-x old-tail-y head-y dx old-head-x 30 add exch 31 % old-tail-x old-tail-y head-x head-y 32 4 2 roll 33 % head-x head-y old-tail-x old-tail-y 34 3 index 2 index sub 3 index 2 index sub 35 { %%% 1-iteration loop to use `exit` as a short circuit 36 % head-x head-y old-tail-x old-tail-y TH-x TH-y 37 dup -1 lt { 38 % head-x head-y old-tail-x old-tail-y TH-x -1>TH-y 39 pop pop pop pop 40 % head-x head-y 41 2 copy 1 add 42 % head-x head-y tail-x tail-y 43 exit 44 } if 45 % head-x head-y old-tail-x old-tail-y TH-x -1≤TH-y 46 dup 1 gt { 47 % head-x head-y old-tail-x old-tail-y TH-x 1<TH-y 48 pop pop pop pop 49 % head-x head-y 50 2 copy 1 sub 51 % head-x head-y tail-x tail-y 52 exit 53 } if 54 % head-x head-y old-tail-x old-tail-y TH-x -1≤TH-y≤1 55 pop 56 % head-x head-y old-tail-x old-tail-y TH-x 57 dup -1 lt { 58 % head-x head-y old-tail-x old-tail-y -1>TH-x 59 pop pop pop 60 % head-x head-y 61 2 copy exch 1 add exch 62 % head-x head-y tail-x tail-y 63 exit 64 } if 65 % head-x head-y old-tail-x old-tail-y -1≤TH-x 66 dup 1 gt { 67 % head-x head-y old-tail-x old-tail-y 1<TH-x 68 pop pop pop 69 % head-x head-y 70 2 copy exch 1 sub exch 71 % head-x head-y tail-x tail-y 72 exit 73 } if 74 % head-x head-y old-tail-x old-tail-y -1≤TH-x≤1 75 pop 76 % head-x head-y old-tail-x old-tail-y 77 exit 78 } loop 79 % head-x head-y tail-x tail-y 80 4 2 roll 81 % tail-x tail-y head-x head-y 82 } bind def 83 84 % tail-x tail-y head-x head-y (M) -> tail-x tail-y head-x head-y 85 /exec-step { 86 { %%% 1-iteration loop to use `exit` as a short circuit 87 dup (U) eq { 88 pop 0 -1 move-head exit 89 } if 90 dup (D) eq { 91 pop 0 1 move-head exit 92 } if 93 dup (L) eq { 94 pop -1 0 move-head exit 95 } if 96 dup (R) eq { 97 pop 1 0 move-head exit 98 } if 99 1.125 pstack 100 quit 101 } loop 102 %3 index 15 string cvs stderr exch writestring 103 %stderr 9 write 104 %2 index 15 string cvs stderr exch writestring 105 %stderr 9 write 106 %1 index 15 string cvs stderr exch writestring 107 %stderr 9 write 108 %0 index 15 string cvs stderr exch writestring 109 %stderr 10 write 110 } bind def 111 112 % (string1) (string2) -> (string1string2) 113 /concat { 114 % (string1) (string2) 115 dup length 2 index length add string 116 % (string1) (string2) (blank) 117 dup 0 4 index putinterval 118 % (string1) (string2) (string1blank) 119 3 2 roll length 120 % (string2) (string1blank) string1-length 121 3 2 roll 2 index 4 1 roll putinterval 122 % (string1string2) 123 } bind def 124 125 % x y -> key 126 /xy-key { 127 % x y 128 exch 15 string cvs 129 % y (x) 130 ( ) concat 131 % y (x ) 132 exch 15 string cvs 133 % (x ) (y) 134 concat 135 % (x y) 136 } bind def 137 138 % pos-dict x y -> ø 139 /update-pos-dict { 140 % pos-dict x y 141 xy-key 142 % pos-dict key 143 2 copy known 144 % pos-dict key has-key? 145 { 146 2 copy get 147 % pos-dict key old-value 148 1 add 149 % pos-dict key new-value 150 put 151 } 152 { 153 1 put 154 } 155 ifelse 156 } bind def 157 158 % tail-pos-dict tail-x tail-y head-x head-y (M) 159 % -> tail-pos-dict tail-x tail-y head-x head-y 160 /record-exec-step { 161 exec-step 162 % tail-pos-dict tail-x tail-y head-x head-y 163 5 copy pop pop update-pos-dict 164 } bind def 165 166 % tail-pos-dict tail-x tail-y head-x head-y (M count) 167 % -> tail-pos-dict tail-x tail-y head-x head-y 168 /record-exec-line { 169 ( ) search 170 not { 2.125 pstack quit } if 171 % tail-pos-dict tail-x tail-y head-x head-y (count) ( ) (M) 172 exch pop exch cvi 173 % tail-pos-dict tail-x tail-y head-x head-y (M) count 174 { 175 % tail-pos-dict tail-x tail-y head-x head-y (M) 176 dup 7 1 roll 177 % (M) tail-pos-dict tail-x tail-y head-x head-y (M) 178 record-exec-step 179 % (M) tail-pos-dict tail-x tail-y head-x head-y 180 6 5 roll 181 % tail-pos-dict tail-x tail-y head-x head-y (M) 182 } repeat 183 % tail-pos-dict tail-x tail-y head-x head-y (M) 184 pop 185 } bind def 186 187 188 /rawdata [ 189 { 190 datafile 100 string readline 191 not { pop exit } if 192 } loop 193 ] def 194 195 196 /Helvetica 20 selectfont 197 198 (First Puzzle: ) 199 72 700 moveto show 200 100 dict 0 0 0 0 201 % tail-pos-dict tail-x tail-y head-x head-y 202 rawdata { 203 % tail-pos-dict tail-x tail-y head-x head-y line 204 record-exec-line 205 % tail-pos-dict tail-x tail-y head-x head-y 206 } forall 207 % tail-pos-dict tail-x tail-y head-x head-y 208 4 index length 209 15 string cvs show 210 211 (Second Puzzle: ) 212 72 664 moveto show 213 214 % head-x head-y (M) -> head-x head-y 215 /update-head { 216 { %%% 1-iteration loop to use `exit` as a short circuit 217 dup (U) eq { 218 pop 1 sub exit 219 } if 220 dup (D) eq { 221 pop 1 add exit 222 } if 223 dup (L) eq { 224 pop exch 1 sub exch exit 225 } if 226 dup (R) eq { 227 pop exch 1 add exch exit 228 } if 229 3.125 pstack 230 quit 231 } loop 232 } bind def 233 234 % -infty..-1 -> -1 235 % 0 -> 0 236 % 1..infty -> 1 237 /flatten-delta { 238 dup -1 le 239 { pop -1 } 240 { 1 ge 241 { 1 } { 0 } ifelse 242 } ifelse 243 } bind def 244 245 246 % old-tail-x old-tail-y new-head-x new-head-y 247 % -> new-tail-x new-tail-y new-head-x new-head-y 248 /update-tail { 249 % old-tail-x old-tail-y head-x head-y 250 4 2 roll 251 % head-x head-y old-tail-x old-tail-y 252 3 index 2 index sub 3 index 2 index sub 253 % head-x head-y old-tail-x old-tail-y TH-x TH-y 254 1 index abs 2 ge 255 % head-x head-y old-tail-x old-tail-y TH-x TH-y is-TH-x-large? 256 1 index abs 2 ge or 257 % head-x head-y old-tail-x old-tail-y TH-x TH-y is-TH-large? 258 { 259 % head-x head-y old-tail-x old-tail-y TH-x TH-y 260 flatten-delta 261 % head-x head-y old-tail-x old-tail-y TH-x tail-dy 262 exch flatten-delta 263 % head-x head-y old-tail-x old-tail-y tail-dy tail-dx 264 4 3 roll 265 % head-x head-y old-tail-y tail-dy tail-dx old-tail-x 266 add 267 % head-x head-y old-tail-y tail-dy tail-x 268 3 1 roll add 269 % head-x head-y tail-x tail-y 270 } 271 { pop pop } 272 ifelse 273 % head-x head-y tail-x tail-y 274 4 2 roll 275 % tail-x tail-y head-x head-y 276 } bind def 277 278 % knot-n-x knot-n-y ... knot-2-x knot-2-y knot-1-x knot-1-y n 279 % -> knot-n-x knot-n-y ... knot-2-x knot-2-y knot-1-x knot-1-y n 280 /update-chain { 281 dup 1 sub { 282 % knot-n-x knot-n-y ... knot-2-x knot-2-y knot-1-x knot-1-y n 283 5 1 roll 284 % knot-n-x knot-n-y ... n knot-2-x knot-2-y knot-1-x knot-1-y 285 update-tail 286 % knot-n-x knot-n-y ... n knot-2-x knot-2-y knot-1-x knot-1-y 287 4 index 2 mul 1 add 288 % knot-n-x knot-n-y ... n knot-2-x knot-2-y knot-1-x knot-1-y 2n+1 289 2 roll 290 % knot-1-x knot-1-y knot-n-x knot-n-y ... n knot-2-x knot-2-y 291 3 2 roll 292 % knot-1-x knot-1-y knot-n-x knot-n-y ... knot-2-x knot-2-y n 293 } repeat 294 % knot-(n-1)-x knot-(n-1)-y ... knot-1-x knot-1-y knot-n-x knot-n-y n 295 3 1 roll 296 % knot-(n-1)-x knot-(n-1)-y ... knot-1-x knot-1-y n knot-n-x knot-n-y 297 2 index 2 mul 1 add 2 roll 298 % knot-n-x knot-n-y ... knot-2-x knot-2-y knot-1-x knot-1-y n 299 } bind def 300 301 % tail-pos-dict knot-n-x knot-n-y ... knot-2-x knot-2-y knot-1-x knot-1-y n line 302 % -> tail-pos-dict knot-n-x knot-n-y ... knot-2-x knot-2-y knot-1-x knot-1-y n 303 /move-chain { 304 % tail-pos-dict knots n (M count) 305 ( ) search 306 not { 4.125 pstack quit } if 307 % tail-pos-dict knots n (count) ( ) (M) 308 exch pop 309 % tail-pos-dict knots n (count) (M) 310 2 index 2 mul 3 add 1 roll 311 % tail-pos-dict (M) knots n (count) 312 cvi 313 % tail-pos-dict (M) knots n count 314 { 315 % tail-pos-dict (M) knots n 316 dup 2 mul 1 add index 317 % tail-pos-dict (M) other-knots head-x head-y n (M) 318 exch 4 1 roll 319 % tail-pos-dict (M) other-knots n head-x head-y (M) 320 update-head 321 % tail-pos-dict (M) other-knots n head-x head-y 322 3 2 roll 323 % tail-pos-dict (M) knots n 324 update-chain 325 % tail-pos-dict (M) tail-x tail-y other-knots n 326 dup 2 mul 3 add 327 % tail-pos-dict (M) tail-x tail-y other-knots n 2n+3 328 dup index exch 329 % tail-pos-dict (M) tail-x tail-y other-knots n tail-pos-dict 2n+3 330 1 sub dup index exch 331 % tail-pos-dict (M) tail-x tail-y other-knots n tail-pos-dict tail-x 2n+2 332 1 sub index 333 % tail-pos-dict (M) tail-x tail-y other-knots n tail-pos-dict tail-x tail-y 334 update-pos-dict 335 % tail-pos-dict (M) tail-x tail-y other-knots n 336 } repeat 337 % tail-pos-dict (M) knots n 338 dup 2 mul 2 add dup 1 sub roll 339 % tail-pos-dict knots n (M) 340 pop 341 % tail-pos-dict knots n 342 } bind def 343 344 % knot-n-x knot-n-y ... knot-2-x knot-2-y knot-1-x knot-1-y n min-x min-y max-x max-y 345 % -> knot-n-x knot-n-y ... knot-2-x knot-2-y knot-1-x knot-1-y n 346 /dump-chain { 347 % knots n min-x min-y max-x max-y 348 1 index 4 index sub 1 add 349 % knots n min-x min-y max-x max-y len-x 350 1 index 4 index sub 1 add mul 351 % knots n min-x min-y max-x max-y len-str 352 dup string 353 % knots n min-x min-y max-x max-y len-str (\0\0\0) 354 exch 1 sub 0 exch 1 exch 355 % knots n min-x min-y max-x max-y str 0 1 len-str-1 356 { 357 % str i 358 1 index exch 359 % str str i 360 46 put 361 % updated-str 362 } for 363 % knots n min-x min-y max-x max-y (....) 364 2 index 5 index sub 1 add exch 365 % knots n min-x min-y max-x max-y line-size (....) 366 4 2 roll pop pop 367 % knots n min-x min-y line-size (....) 368 5 4 roll exch 369 % knots min-x min-y line-size n (....) 370 48 2 index 371 % knots min-x min-y line-size n (....) char n 372 { 373 % other-knots cur-x cur-y min-x min-y line-size n (....) char 374 7 index 7 index 375 % other-knots cur-x cur-y min-x min-y line-size n (....) char x y 376 6 index sub 5 index mul add 6 index sub 377 % other-knots cur-x cur-y min-x min-y line-size n (....) char offset 378 2 index 1 index get 46 eq 379 { 3 copy exch put } if 380 % other-knots cur-x cur-y min-x min-y line-size n (..1.) char offset 381 pop 1 add 382 % other-knots cur-x cur-y min-x min-y line-size n (..1.) next-char 383 8 6 roll 384 % other-knots min-x min-y line-size n (..1.) next-char cur-x cur-y 385 4 index 2 mul 6 add 2 roll 386 % cur-x cur-y other-knots min-x min-y line-size n (..1.) next-char 387 } repeat 388 % knots min-x min-y line-size n (..1.) char 389 pop 390 % knots min-x min-y line-size n (..1.) 391 5 2 roll 3 1 roll pop pop exch 392 % knots n line-size (..1.) 393 0 2 index 2 index length 1 sub { 394 % knots n line-size (..1.) offset 395 exch dup 3 2 roll 396 % knots n line-size (..1.) (..1.) offset 397 3 index 398 % knots n line-size (..1.) (..1.) offset line-size 399 getinterval 400 % knots n line-size (..1.) line 401 stderr exch writestring 402 stderr 10 write 403 % knots n line-size (..1.) 404 } for 405 % knots n line-size (..1.) 406 pop pop 407 } bind def 408 409 500 dict 10 { 0 0 } repeat 10 410 % tail-pos-dict knots n 411 rawdata { 412 % tail-pos-dict knots n line 413 %%% stderr 1 index writestring 414 %%% stderr 10 write 415 % tail-pos-dict knots n line 416 move-chain 417 % tail-pos-dict knots n 418 %%% small-example: 0 -4 5 0 dump-chain 419 %%% large-example: -11 -15 14 5 dump-chain 420 % tail-pos-dict knots n 421 } forall 422 % tail-pos-dict knots n 423 dup 2 mul 1 add index 424 % tail-pos-dict knots n tail-pos-dict 425 length 15 string cvs show 426 427 showpage 428 quit