day19.ps (19166B)
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- day19.ps <day19.txt | display 19 20 % [ item_1 ... item_n ] item_0 -> [ item_0 item_1 ... item_n ] 21 /apush { 22 % array new_item 23 exch aload length 1 add array astore 24 } bind def 25 26 % [ item_0 ... item_n-1 ] item_n -> [ item_0 item_1 ... item_n ] 27 /aappend { 28 % [ item_0 ... item_n-1 ] item_n 29 1 index length 30 % [ item_0 ... item_n-1 ] item_n n 31 dup 1 add array 32 % [ item_0 ... item_n-1 ] item_n n new-array 33 dup 5 4 roll 34 % item_n n new-array new-array [ item_0 ... item_n-1 ] 35 0 exch putinterval 36 % item_n n [ item_0 ... item_n-1 null ] 37 dup 4 2 roll 38 % [ item_0 ... item_n-1 null ] [ item_0 ... item_n-1 null ] item_n n 39 exch put 40 % [ item_0 ... item_n-1 item_n ] 41 } bind def 42 43 % [ item_0 item_1 ... item_n ] -> [ item_1 ... item_n ] item_0 44 /apop { 45 % [ item_0 item_1 ... item_n ] 46 dup 0 get exch 47 % item_0 [ item_0 item_1 ... item_n ] 48 1 1 index length 1 sub 49 % item_0 [ item_0 item_1 ... item_n ] 1 n 50 getinterval 51 % item_0 [ item_1 ... item_n ] 52 exch 53 % [ item_1 ... item_n ] item_0 54 } bind def 55 56 % [item1a item2a ... itemma] [item1b item2b ... itemmnb] 57 % -> [[item1a item1b] [item2a item2b] ... [item(min(m,n))a item(min(m,n))b]] 58 /azip { 59 % [item1a item2a ... itemma] [item1b item2b ... itemnb] 60 0 1 3 index length 3 index length 61 % [item1a item2a ... itemma] [item1b item2b ... itemnb] 0 1 n m 62 2 copy gt { exch } if pop 63 % [item1a item2a ... itemma] [item1b item2b ... itemnb] 0 1 min(m,n) 64 [ 6 1 roll 65 % mark [item1a item2a ... itemma] [item1b item2b ... itemnb] 0 1 min(m,n) 66 1 sub { 67 % mark prev-items array1 array2 index 68 2 index 1 index get 69 % mark prev-items array1 array2 index val1 70 exch 2 index exch get 71 % mark prev-items array1 array2 val1 val2 72 2 array astore 73 % mark prev-items array1 array2 cur-item 74 3 1 roll 75 % mark prev-items cur-item array1 array2 76 } for 77 % mark items [item1a item2a ... itemma] [item1b item2b ... itemnb] 78 pop pop 79 ] 80 } bind def 81 82 % [item1a item2a ... itemma] [item1b item2b ... itemmnb] 83 % -> [item1a+item1b item2a+item2b ... item(min(m,n))a+item(min(m,n))b] 84 /vec-add { 85 [ 3 1 roll azip { aload pop add } forall ] 86 } bind def 87 88 % [item1a item2a ... itemma] [item1b item2b ... itemmnb] 89 % -> [item1a-item1b item2a-item2b ... item(min(m,n))a-item(min(m,n))b] 90 /vec-sub { 91 [ 3 1 roll azip { aload pop sub } forall ] 92 } bind def 93 94 % [item1a item2a ... itemma] [item1b item2b ... itemmnb] 95 % -> item1a>=item1b & item2a>=item2b & ... & item(min(m,n))a>=item(min(m,n))b 96 /vec-all-ge { 97 true 3 1 roll 98 azip { aload pop ge and } forall 99 } bind def 100 101 /datafile (%stdin) (r) file def 102 /stderr (%stderr) (w) file def 103 104 /data [ 105 { 106 datafile 300 string readline 107 not { pop exit } if 108 % line 109 counttomark exch 110 % expected-rank line 111 (Blueprint ) anchorsearch 112 not { 1.125 pstack quit } if 113 pop 114 % expected-rank suffix 115 (: Each ore robot costs ) search 116 not { 2.125 pstack quit } if 117 exch pop cvi exch 118 % expected-rank rank suffix 119 ( ore. Each clay robot costs ) search 120 not { 3.125 pstack quit } if 121 exch pop cvi exch 122 % expected-rank rank cost0 suffix 123 ( ore. Each obsidian robot costs ) search 124 not { 4.125 pstack quit } if 125 exch pop cvi exch 126 % expected-rank rank cost0 cost1 suffix 127 ( ore and ) search 128 not { 5.125 pstack quit } if 129 exch pop cvi exch 130 % expected-rank rank cost0 cost1 cost2a suffix 131 ( clay. Each geode robot costs ) search 132 not { 6.125 pstack quit } if 133 exch pop cvi exch 134 % expected-rank rank cost0 cost1 cost2a cost2b suffix 135 ( ore and ) search 136 not { 7.125 pstack quit } if 137 exch pop cvi exch 138 % expected-rank rank cost0 cost1 cost2a cost2b cost3a suffix 139 ( obsidian.) search 140 not { 8.125 pstack quit } if 141 exch pop cvi exch 142 % expected-rank rank cost0 cost1 cost2a cost2b cost3a cost3b suffix 143 dup length 0 eq not { 9.125 pstack quit } if pop 144 % expected-rank rank cost0 cost1 cost2a cost2b cost3a cost3b 145 8 6 roll 2 copy eq not { 10.125 pstack quit } if pop pop 146 % cost0 cost1 cost2a cost2b cost3a cost3b 147 0 exch 0 4 array astore 148 % cost0 cost1 cost2a cost2b cost3-array 149 5 1 roll 0 0 4 array astore 150 % cost3-array cost0 cost1 cost2-array 151 4 1 roll 0 0 0 4 array astore 152 % cost2-array cost3-array cost0 cost1-array 153 4 1 roll 0 0 0 4 array astore 154 % cost1-array cost2-array cost3-array cost0-array 155 4 1 roll 4 array astore 156 % cost-array 157 } loop 158 ] def 159 160 /max-cost [ 161 0 0 0 0 data { 162 { 163 % prev-max-cost0 prev-max-cost1 prev-max-cost2 prev-max-cost3 cur-cost 164 dup 0 get 165 % prev-max-cost0 prev-max-cost1 prev-max-cost2 prev-max-cost3 cur-cost cost0 166 6 5 roll 167 % prev-max-cost1 prev-max-cost2 prev-max-cost3 cur-cost cost0 prev-max-cost0 168 2 copy lt { exch } if pop 169 % prev-max-cost0 prev-max-cost1 prev-max-cost2 cur-cost max-cost0 170 1 index 1 get 171 % prev-max-cost1 prev-max-cost2 prev-max-cost3 cur-cost max-cost0 cost1 172 6 5 roll 2 copy lt { exch } if pop 173 % prev-max-cost2 prev-max-cost3 cur-cost max-cost0 max-cost1 174 2 index 2 get 175 % prev-max-cost2 prev-max-cost3 cur-cost max-cost0 max-cost1 cost2 176 6 5 roll 2 copy lt { exch } if pop 177 % prev-max-cost3 cur-cost max-cost0 max-cost1 max-cost2 178 3 index 3 get 179 % prev-max-cost3 cur-cost max-cost0 max-cost1 max-cost2 cost3 180 6 5 roll 2 copy lt { exch } if pop 181 % cur-cost max-cost0 max-cost1 max-cost2 max-cost3 182 5 4 roll pop 183 % max-cost0 max-cost1 max-cost2 max-cost3 184 } forall 185 } forall 186 ] def 187 188 max-cost == 189 190 % blueprint resources flows build -> blueprint next-resources next-flows 191 /simulate-minute { 192 % blueprint resources flows build 193 dup 0 ge 194 % blueprint resources flows build has-build? 195 { % blueprint resources flows build 196 3 index 1 index get 197 % blueprint resources flows build costs 198 4 3 roll exch vec-sub 199 % blueprint flows build updated-resources 200 } 201 { 3 2 roll } 202 ifelse 203 % blueprint flows build resources 204 2 index vec-add 205 % blueprint flows build next-resources 206 3 1 roll 207 % blueprint next-resources flows build 208 dup 0 ge 209 % blueprint next-resources flows build has-build? 210 { % blueprint next-resources flows build 211 2 copy get 1 add 212 % blueprint next-resources flows build next-flow 213 2 index 3 1 roll put 214 % blueprint next-resources next-flows 215 } 216 { pop } 217 ifelse 218 % blueprint next-resources next-flows 219 } bind def 220 221 % blueprint build-list max-time -> score true 222 % -> false 223 /simulate-build-list { 224 % blueprint build-list max-time 225 0 [0 0 0 0] [1 0 0 0] 4 3 roll 226 % blueprint build-list build-index resources flows max-time 227 6 5 roll 4 1 roll 228 % build-list build-index blueprint resources flows max-time 229 { % build-list build-index blueprint resources flows 230 4 index length 4 index gt 231 % build-list build-index blueprint resources flows has-build? 232 { % build-list build-index blueprint resources flows 233 4 index 4 index get 234 % build-list build-index blueprint resources flows build 235 3 index 1 index get 236 % build-list build-index blueprint resources flows build costs 237 3 index exch vec-all-ge 238 % build-list build-index blueprint resources flows build can-build? 239 { 5 4 roll 1 add 5 1 roll } 240 { pop -1 } 241 ifelse 242 % build-list build-index blueprint resources flows build 243 } 244 { -1 } 245 ifelse 246 % build-list build-index blueprint resources flows build 247 simulate-minute 248 % build-list build-index blueprint resources flows 249 } repeat 250 % build-list build-index blueprint resources flows 251 4 index length 4 index le 252 % build-list build-index blueprint resources flows build-list-finished? 253 { pop 3 get 4 1 roll pop pop pop true } 254 { pop pop pop pop pop false } 255 ifelse 256 } bind def 257 258 % build-list -> next-build-list 259 /next-build-list { 260 % build-list 261 dup length 2 sub 262 % build-list index 263 { 264 % build-list index 265 dup 0 lt { pop 0 apush exit } if 266 % build-list index 267 2 copy get 268 % build-list index item 269 1 add 4 mod 270 % build-list index next-item 271 3 copy put 272 % next-build-list index next-item 273 0 eq 274 { 1 sub } 275 { pop exit } 276 ifelse 277 } loop 278 % next-build-list 279 } bind def 280 281 % build-list -> build-list 282 /next-valid-build-list { 283 { 284 % prev-build-list 285 next-build-list 286 % build-list 287 [ 0 0 0 0 ] 1 index { 288 % build-list count-list cur-item 289 2 copy get 290 % build-list count-list cur-item prev-count 291 1 add 292 % build-list count-list cur-item count 293 2 index 3 1 roll put 294 % build-list updated-count-list 295 } forall 296 % build-list count-list 297 dup 3 0 put 298 % build-list fixed-count-list 299 max-cost exch vec-all-ge 300 % build-list is-valid? 301 { exit } if 302 % build-list 303 } loop 304 % valid-build-list 305 } bind def 306 307 % array -> copied-array 308 /copy-array { 309 aload length array astore 310 } bind def 311 312 % blueprint prev-state build -> next-state 313 /update-state { 314 % blueprint prev-state build 315 exch aload pop 316 % blueprint build prev-resources prev-flows prev-build-list 317 3 index 0 ge 318 { 3 index aappend } if 319 % blueprint build prev-resources prev-flows build-list 320 5 1 roll 321 % build-list blueprint build prev-resources prev-flows 322 exch copy-array exch copy-array 323 % build-list blueprint build prev-resources-copy prev-flows-copy 324 3 2 roll 325 % build-list blueprint prev-resources-copy prev-flows-copy build 326 simulate-minute 327 % build-list blueprint resources flows 328 3 2 roll pop 329 % build-list resources flows 330 3 2 roll 331 % resources flows build-list 332 3 array astore 333 % next-state 334 } bind def 335 336 % int-list -> key 337 /list-to-key { 338 % int-list 339 dup length string 340 % int-list empty-key 341 0 1 2 index length 1 sub { 342 % int-list key index 343 2 index 1 index get 344 % int-list key index value 345 2 index 3 1 roll put 346 % int-list updated-key 347 } for 348 % int-list final-key 349 exch pop 350 % final-key 351 } bind def 352 353 % active-dict blueprint prev-state build 354 % -> active-dict blueprint prev-state build is-valid? 355 /update-valid? { 356 % active-dict blueprint prev-state build 357 dup 0 ge 358 { % active-dict blueprint prev-state build 359 1 index 2 get 360 % active-dict blueprint prev-state build prev-build-list 361 1 index aappend 362 % active-dict blueprint prev-state build next-build-list 363 list-to-key 364 % active-dict blueprint prev-state build next-key 365 4 index 1 index known 366 % active-dict blueprint prev-state build next-key already-active? 367 { pop false } 368 { % active-dict blueprint prev-state build next-key 369 2 index 0 get 370 % active-dict blueprint prev-state build next-key resources 371 4 index 3 index get 372 % active-dict blueprint prev-state build next-key resources cost 373 vec-all-ge 374 % active-dict blueprint prev-state build next-key is-possible? 375 3 index 1 get 376 % active-dict blueprint prev-state build next-key is-possible? rates 377 3 index get 378 % active-dict blueprint prev-state build next-key is-possible? rate 379 max-cost 4 index get lt 380 % active-dict blueprint prev-state build next-key is-possible? rate-ok? 381 3 index 3 eq or and 382 % active-dict blueprint prev-state build next-key is-valid? 383 { % active-dict blueprint prev-state build next-key 384 4 index exch 1 put 385 % active-dict blueprint prev-state build 386 true 387 } 388 { pop false } 389 ifelse 390 % active-dict blueprint prev-state build is-valid? 391 } 392 ifelse 393 } 394 { true } 395 ifelse 396 } bind def 397 398 % blueprint max-time -> score 399 /eval-blueprint { 400 % blueprint max-time 401 0 1000 dict [[[0 0 0 0] [1 0 0 0] []]] 4 3 roll 402 % blueprint init-time init-active-dict init-state-list max-time 403 { 404 % blueprint prev-time active-dict state-list 405 3 2 roll 1 add 3 1 roll 406 % blueprint time active-dict state-list 407 [ exch 408 % blueprint time active-dict mark state-list 409 2 index 5 index 3 2 roll 410 % blueprint time active-dict mark active-dict blueprint state-list 411 { 412 %%% Exchaustive search of build-list-space 413 %%% % ... active-dict blueprint prev-state 414 %%% -1 1 3 { 415 %%% % ... active-dict blueprint prev-state build 416 %%% update-valid? 417 %%% { % ... active-dict blueprint prev-state build 418 %%% 3 copy update-state 419 %%% % ... active-dict blueprint prev-state build next-state 420 %%% 5 1 roll pop 421 %%% % ... next-state active-dict blueprint prev-state 422 %%% } 423 %%% { pop } 424 %%% ifelse 425 %%% } for 426 %%% % ... active-dict blueprint prev-state 427 %%% pop 428 %%% % ... active-dict blueprint 429 %%% Greedy search of build-list-space, prioritizing geode over obsidian over 430 %%% everything else. This is a bit of a hack, it doesn't work with the 431 %%% reference input (first blueprint needs to build an obsidian bot when 432 %%% both obsidian and geode are possible), but it works on my input, 433 %%% so let's say it's good enough. 434 % ... active-dict blueprint prev-state 435 3 update-valid? 436 { %%% drop everything to build a geode bot 437 % ... active-dict blueprint prev-state build 438 2 index 3 1 roll 439 % ... active-dict blueprint blueprint prev-state build 440 update-state 441 % ... active-dict blueprint next-state 442 3 1 roll 443 % ... next-state active-dict blueprint 444 } 445 { pop 2 update-valid? 446 { %%% drop everything to build an obsidian bot 447 % ... active-dict blueprint prev-state build 448 2 index 3 1 roll 449 % ... active-dict blueprint blueprint prev-state build 450 update-state 451 % ... active-dict blueprint next-state 452 3 1 roll 453 % ... next-state active-dict blueprint 454 } 455 { pop 456 % ... active-dict blueprint prev-state 457 -1 1 1 { 458 % ... active-dict blueprint prev-state build 459 update-valid? 460 { % ... active-dict blueprint prev-state build 461 3 copy update-state 462 % ... active-dict blueprint prev-state build next-state 463 5 1 roll pop 464 % ... next-state active-dict blueprint prev-state 465 } 466 { pop } 467 ifelse 468 } for 469 % ... active-dict blueprint prev-state 470 pop 471 % ... active-dict blueprint 472 } 473 ifelse 474 } 475 ifelse 476 % ... active-dict blueprint 477 } forall 478 % blueprint time mark new-states active-dict blueprint 479 pop pop 480 ] 481 % blueprint time active-dict new-state-list 482 } repeat 483 % blueprint time active-dict final-state-list 484 exch pop 485 % blueprint time final-state-list 486 stderr (Final list with ) writestring 487 stderr 1 index length 15 string cvs writestring 488 stderr ( states\012) writestring 489 % blueprint time final-state-list 490 exch pop 0 exch { 491 % blueprint best-so-far state 492 0 get 493 % blueprint best-so-far resources 494 3 get 495 % blueprint best-so-far score 496 2 copy lt { exch } if pop 497 % blueprint new-best-so-far 498 } forall 499 % blueprint best-score 500 exch pop 501 % best-score 502 stderr (Score ) writestring 503 stderr 1 index 15 string cvs writestring 504 stderr 10 write 505 } bind def 506 507 /Helvetica 20 selectfont 508 509 510 (First Puzzle: ) 511 72 700 moveto show 512 513 0 0 data { 514 % accumulator prev-rank cur-blueprint 515 exch 1 add exch 516 % accumulator rank cur-blueprint 517 stderr (Running blueprint ) writestring 518 stderr 2 index 15 string cvs writestring 519 stderr ( / ) writestring 520 stderr data length 15 string cvs writestring 521 stderr 10 write 522 stderr flushfile 523 % accumulator rank cur-blueprint 524 24 eval-blueprint 525 % accumulator rank score 526 1 index mul 527 % accumulator rank contribution 528 3 2 roll add exch 529 % updated-accumulator rank 530 } forall 531 % final-accumulator last-rank 532 pop 15 string cvs show 533 534 %%% [ data length { 0 } repeat ] [3] 535 %%% { 536 %%% % best-score-array prev-build-list 537 %%% next-valid-build-list false 538 %%% % best-score-array build-list updated? 539 %%% 0 1 data length 1 sub { 540 %%% % best-score-array build-list updated? index 541 %%% data 1 index get 542 %%% % best-score-array build-list updated? index blueprint 543 %%% 3 index 544 %%% % best-score-array build-list updated? index blueprint build-list 545 %%% 24 simulate-build-list 546 %%% { % best-score-array build-list updated? index score 547 %%% dup 5 index 3 index get gt 548 %%% % best-score-array build-list updated? index score score>prev-max? 549 %%% { 4 index 2 index 2 index put 550 %%% % updated-best-score-array build-list updated? index score 551 %%% pop pop pop true 552 %%% % updated-best-score-array build-list updated? 553 %%% } 554 %%% { pop pop } 555 %%% ifelse 556 %%% % updated-best-score-array build-list updated? 557 %%% } 558 %%% { pop } 559 %%% ifelse 560 %%% % best-score-array build-list updated? 561 %%% } for 562 %%% % best-score-array build-list updated? 563 %%% { 564 %%% % best-score-array build-list 565 %%% stderr (\015Score ) writestring 566 %%% 0 0 3 index { 567 %%% % ... accumulator prev-rank score 568 %%% exch 1 add exch 569 %%% % ... accumulator rank score 570 %%% 1 index mul 571 %%% % ... accumulator rank contribution 572 %%% 3 2 roll add exch 573 %%% % ... accumulator rank 574 %%% } forall 575 %%% % best-score-array build-list accumulator rank 576 %%% 1 index 33 eq { quit } if 577 %%% % best-score-array build-list accumulator rank 578 %%% pop 15 string cvs 579 %%% stderr exch writestring 580 %%% stderr ( at length ) writestring 581 %%% stderr 1 index length 15 string cvs writestring 582 %%% stderr flushfile 583 %%% % best-score-array build-list 584 %%% } if 585 %%% % best-score-array build-list 586 %%% } loop 587 588 (Second Puzzle: ) 589 72 664 moveto show 590 591 1 0 data { 592 % accumulator prev-rank cur-blueprint 593 exch 1 add exch 594 % accumulator rank cur-blueprint 595 1 index 4 ge { pop exit } if 596 % accumulator rank cur-blueprint 597 stderr (Running blueprint ) writestring 598 stderr 2 index 15 string cvs writestring 599 stderr ( / ) writestring 600 stderr data length 15 string cvs writestring 601 stderr 10 write 602 stderr flushfile 603 % accumulator rank cur-blueprint 604 32 eval-blueprint 605 % accumulator rank score 606 3 2 roll mul exch 607 % updated-accumulator rank 608 } forall 609 % final-accumulator last-rank 610 stderr (Result 2: ) writestring 611 stderr 2 index 15 string cvs writestring 612 stderr 10 write 613 pop 15 string cvs show 614 615 616 showpage 617 quit