day23.ps (12281B)
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- day23.ps <day23.txt | display 19 20 /datafile (%stdin) (r) file def 21 /stderr (%stderr) (w) file def 22 23 /data [ 24 { 25 datafile 300 string readline 26 not { pop exit } if 27 } loop 28 ] def 29 30 /init-coords [ 31 0 data { 32 % ... y line 33 0 exch { 34 % ... y x char 35 35 eq 36 { % ... y x 37 2 copy exch 2 array astore 38 % ... y x new-item 39 3 1 roll 40 % ... new-item y x 41 } if 42 % y x 43 1 add 44 } forall 45 % y last-x 46 pop 1 add 47 } forall 48 % last-y 49 pop 50 ] def 51 52 /dir-vect << 53 0 [ 0 -1] 54 1 [ 0 1] 55 2 [-1 0] 56 3 [ 1 0] 57 >> def 58 59 /check-vect-list << 60 0 [[-1 -1] [0 -1] [1 -1]] 61 1 [[-1 1] [0 1] [1 1]] 62 2 [[-1 -1] [-1 0] [-1 1]] 63 3 [[1 -1] [1 0] [1 1]] 64 >> def 65 66 % coord-array -> min-x min-y max-x max-y 67 /minmax { 68 % coord-array 69 dup 0 get aload pop 70 % coord-array x0 y0 71 2 copy 72 % coord-array x0 y0 x0 y0 73 5 4 roll { 74 % prev-min-x prev-min-y prev-max-x prev-max-y item 75 aload pop 76 % prev-min-x prev-min-y prev-max-x prev-max-y x y 77 6 5 roll 78 % prev-min-y prev-max-x prev-max-y x y prev-min-x 79 dup 3 index gt { pop 1 index } if 80 % prev-min-y prev-max-x prev-max-y x y min-x 81 6 5 roll 82 % prev-max-x prev-max-y x y min-x prev-min-y 83 dup 3 index gt { pop 1 index } if 84 % prev-max-x prev-max-y x y min-x min-y 85 6 5 roll 86 % prev-max-y x y min-x min-y prev-max-x 87 dup 5 index lt { pop 3 index } if 88 % prev-max-y x y min-x min-y max-x 89 6 5 roll 90 % x y min-x min-y max-x prev-max-y 91 dup 5 index lt { pop 3 index } if 92 % x y min-x min-y max-x max-y 93 6 4 roll pop pop 94 % min-x min-y max-x max-y 95 } forall 96 % min-x min-y max-x max-y 97 } bind def 98 99 % coord-array -> coord-dict width 100 /to-coord-dict { 101 % coord-array 102 dup minmax 103 % coord-array min-x min-y max-x max-y 104 pop 2 index sub 3 add 105 % coord-array min-x min-y width 106 3 2 roll 1 sub 107 % coord-array min-y width orig-x 108 3 2 roll 1 sub 109 % coord-array width orig-x orig-y 110 4 3 roll 111 % width orig-x orig-y coord-array 112 << 4 1 roll 113 % width mark orig-x orig-y coord-array 114 4 index exch 115 % width mark orig-x orig-y width coord-array 116 { 117 aload pop 118 % ... orig-x orig-y width x y 119 3 index sub 2 index mul 4 index sub add 120 % ... orig-x orig-y width key 121 1 122 % ... orig-x orig-y width key value 123 5 2 roll 124 % ... key value orig-x orig-y width 125 } forall 126 % width mark items orig-x orig-y width 127 pop pop pop 128 % width mark items 129 >> 130 % width coord-dict 131 exch 132 } bind def 133 134 % coord-dict width -> 135 /dump-coord-dict { 136 % coord-dict width 137 0 138 % coord-dict width height 139 2 index { 140 pop 141 % coord-dict width prev-height key 142 2 index idiv 143 % coord-dict width prev-height y 144 2 copy lt { exch } if pop 145 % coord-dict width cur-height 146 } forall 147 % coord-dict width height 148 2 add 1 index mul dup string 149 % coord-dict width size repr 150 0 1 3 index 1 sub { 151 % coord-dict width size repr index 152 1 index exch 46 put 153 % coord-dict width size repr 154 } for 155 % coord-dict width size repr 156 exch pop 157 % coord-dict width repr 158 3 2 roll { 159 pop 160 % width repr key 161 1 index exch 35 put 162 % width repr 163 } forall 164 % width repr 165 0 2 index 166 % width repr 0 width 167 2 index length 1 sub { 168 % width repr offset 169 1 index exch 170 % width repr repr offset 171 3 index getinterval 172 % width repr line 173 stderr exch writestring 174 stderr 10 write 175 } for 176 % width repr 177 pop pop 178 } bind def 179 180 % coord-dict width time key -> next-key true 181 % -> false 182 /move-next-coord { 183 % coord-dict width time key 184 false 5 1 roll 185 % result coord-dict width time key 186 exch 1 1 index 3 add 187 % result coord-dict width key time 1 time+3 188 { 189 % result coord-dict width key cur-time 190 true 191 % result coord-dict width key cur-time is-valid? 192 1 index 4 mod check-vect-list exch get { 193 aload pop 194 % result coord-dict width key cur-time prev-is-valid? dx dy 195 5 index mul add 196 % result coord-dict width key cur-time prev-is-valid? dkey 197 3 index add 198 % result coord-dict width key cur-time prev-is-valid? key-to-check 199 5 index exch known not and 200 % result coord-dict width key cur-time is-valid? 201 dup not { exit } if 202 } forall 203 % result coord-dict width key cur-time is-valid? 204 { 205 % false coord-dict width key cur-time 206 dup 4 mod dir-vect exch get aload pop 207 % false coord-dict width key cur-time dx dy 208 4 index mul add 209 % false coord-dict width key cur-time dkey 210 2 index add true 211 % false coord-dict width key cur-time next-key true 212 7 2 roll 5 4 roll pop pop 213 % next-key true coord-dict width key 214 exit 215 } if 216 % result coord-dict width key cur-time 217 pop 218 % result coord-dict width key 219 } for 220 % result coord-dict width key 221 pop pop pop 222 % result 223 } bind def 224 225 /neighbor-list [ 226 [-1 -1] [0 -1] [1 -1] 227 [-1 0] [1 0] 228 [-1 1] [0 1] [1 1] 229 ] def 230 231 % coord-dict width time key -> next-key true 232 % -> false 233 /single-next-coord { 234 false 235 % coord-dict width time key has-neighbor? 236 neighbor-list { 237 aload pop 238 % coord-dict width time key prev-has-neighbor? dx dy 239 5 index mul add 240 % coord-dict width time key prev-has-neighbor? dkey 241 2 index add 242 % coord-dict width time key prev-has-neighbor? neighbor-key 243 5 index exch known or 244 % coord-dict width time key has-neighbor? 245 dup { exit } if 246 } forall 247 % coord-dict width time key has-neighbor? 248 { move-next-coord } 249 { pop pop pop pop false } 250 ifelse 251 } bind def 252 253 % coord-dict width time -> next-coord-dict changed? 254 /next-coord-dict { 255 % coord-dict width time 256 2 index length dict 257 % coord-dict width time next-coord-counts 258 3 index { 259 pop 260 % coord-dict width time next-coord-counts key 261 4 index 4 index 4 index 4 3 roll single-next-coord 262 { 263 % coord-dict width time next-coord-counts next-key 264 2 copy known 265 { 2 copy get 1 add 266 % coord-dict width time next-coord-counts next-key updated-count 267 2 index 3 1 roll put 268 % coord-dict width time updated-next-coord-counts 269 } 270 { % coord-dict width time next-coord-counts next-key 271 1 index exch 1 put 272 % coord-dict width time updated-next-coord-counts 273 } 274 ifelse 275 } if 276 % coord-dict width time next-coord-counts 277 } forall 278 % coord-dict width time next-coord-counts 279 3 index length dict false 6 2 roll 280 % next-coord-dict changed? coord-dict width time next-coord-counts 281 3 index { 282 pop 283 % next-coord-dict changed? coord-dict width time next-coord-counts key 284 4 index 4 index 4 index 3 index single-next-coord 285 { 286 % next-coord-dict changed? coord-dict width time next-coord-counts key next-key 287 2 index 1 index get 288 1 le { 289 exch pop 290 % next-coord-dict changed? coord-dict width time next-coord-counts next-key 291 6 5 roll pop true 6 1 roll 292 % next-coord-dict true coord-dict width time next-coord-counts next-key 293 } 294 { pop 295 % next-coord-dict changed? coord-dict width time next-coord-counts key 296 } 297 ifelse 298 % next-coord-dict changed? coord-dict width time next-coord-counts final-key 299 } if 300 % next-coord-dict changed? coord-dict width time next-coord-counts final-key 301 6 index exch 1 put 302 % next-coord-dict changed? coord-dict width time next-coord-counts 303 } forall 304 % next-coord-dict changed? coord-dict width time next-coord-counts 305 pop pop pop pop 306 % next-coord-dict changed? 307 } bind def 308 309 % coord-dict width -> coord-dict width 310 /fix-coord-dict { 311 % coord-dict width 312 false false false 313 % coord-dict width has-x0? has-y0? has-xmax? 314 4 index { 315 pop 316 % coord-dict width prev-has-x0? prev-has-y0? prev-has-xmax? key 317 dup 5 index mod exch 318 % coord-dict width prev-has-x0? prev-has-y0? prev-has-xmax? x key 319 5 index idiv 320 % coord-dict width prev-has-x0? prev-has-y0? prev-has-xmax? x y 321 0 eq 4 3 roll or 322 % coord-dict width prev-has-x0? prev-has-xmax? x has-y0? 323 4 1 roll 324 % coord-dict width has-y0? prev-has-x0? prev-has-xmax? x 325 dup 0 eq 4 3 roll or 326 % coord-dict width has-y0? prev-has-xmax? x has-x0? 327 4 1 roll 328 % coord-dict width has-x0? has-y0? prev-has-xmax? x 329 4 index 1 sub eq or 330 % coord-dict width has-x0? has-y0? has-xmax? 331 } forall 332 % coord-dict width has-x0? has-y0? has-xmax? 333 exch { 1 } { 0 } ifelse 334 % coord-dict width has-x0? has-xmax? dy 335 2 index { 1 } { 0 } ifelse exch 336 % coord-dict width has-x0? has-xmax? dx dy 337 4 index 5 4 roll { 1 add } if 4 3 roll { 1 add } if 338 % coord-dict width dx dy new-width 339 dup 6 1 roll 5 4 roll 340 % new-width width dx dy new-width coord-dict 341 << 6 1 roll 342 % new-width mark width dx dy new-width coord-dict 343 { pop 344 % ... width dx dy new-width key 345 dup 5 index mod exch 346 % ... width dx dy new-width old-x key 347 5 index idiv 348 % ... width dx dy new-width old-x old-y 349 exch 4 index add exch 3 index add 350 % ... width dx dy new-width new-x new-y 351 2 index mul add 1 352 % ... width dx dy new-width new-key 1 353 6 2 roll 354 % ... new-item width dx dy new-width 355 } forall 356 % new-width mark items width dx dy new-width 357 pop pop pop pop 358 >> 359 % new-width new-coord-dict 360 exch 361 } bind def 362 363 % coord-dict width -> score 364 /coord-dict-score { 365 % coord-dict width 366 0 (placeholder) 4 2 roll exch 367 % occupied-count placeholder width coord-dict 368 { pop 369 % occupied-count maybe-minimax width key 370 dup 2 index mod exch 2 index idiv 371 % occupied-count maybe-minimax width x y 372 3 index type /integertype eq 373 { % occupied-count min-x min-y max-x max-y width x y 374 7 6 roll dup 3 index gt { pop 1 index } if 375 % occupied-count min-y max-x max-y width x y min-x 376 7 6 roll dup 3 index gt { pop 1 index } if 377 % occupied-count max-x max-y width x y min-x min-y 378 7 6 roll dup 5 index lt { pop 3 index } if 379 % occupied-count max-y width x y min-x min-y max-x 380 7 6 roll dup 5 index lt { pop 3 index } if 381 % occupied-count width x y min-x min-y max-x max-y 382 7 4 roll pop pop 383 % occupied-count min-x min-y max-x max-y width 384 } 385 { % occupied-count (placeholder) width x y 386 4 3 roll pop 387 % occupied-count width x y 388 2 copy 5 4 roll 389 % occupied-count x y x y width 390 } 391 ifelse 392 % prev-occupied-count min-x min-y max-x max-y width 393 6 5 roll 1 add 6 1 roll 394 % occupied-count min-x min-y max-x max-y width 395 } forall 396 % occupied-count min-x min-y max-x max-y width 397 pop exch 4 1 roll exch 398 % occupied-count max-x min-x max-y min-y 399 sub 1 add 3 1 roll sub 1 add 400 % occupied-count used-width used-height 401 mul exch sub 402 % score 403 } bind def 404 405 -1 init-coords to-coord-dict 406 % prev-time init-coord-dict width 407 { 408 % prev-time prev-coord-dict width 409 3 2 roll 1 add 410 % prev-coord-dict width time 411 dup 10 eq { 412 3 copy pop coord-dict-score 413 % prev-coord-dict width time score 414 4 1 roll 415 } if 416 % prev-coord-dict width time 417 3 2 roll 2 index 2 index 418 % width time prev-coord-dict width time 419 next-coord-dict 420 % width time cur-coord-dict changed? 421 not { pop 1 add exch pop exit } if 422 % width time cur-coord-dict 423 3 2 roll 424 % time cur-coord-dict width 425 fix-coord-dict 426 % time next-coord-dict next-width 427 } loop 428 % answer1 answer2 429 exch 430 % answer2 answer1 431 432 433 /Helvetica 20 selectfont 434 435 436 (First Puzzle: ) 437 72 700 moveto show 438 15 string cvs show 439 440 441 (Second Puzzle: ) 442 72 664 moveto show 443 15 string cvs show 444 445 446 showpage 447 quit