/ SynacorChallenge / synacor.ipynb
synacor.ipynb
1 { 2 "cells": [ 3 { 4 "cell_type": "markdown", 5 "metadata": {}, 6 "source": [ 7 "# [Synacor Challenge](https://challenge.synacor.com/)" 8 ] 9 }, 10 { 11 "cell_type": "markdown", 12 "metadata": {}, 13 "source": [ 14 "- [Flag #1](#Flag-#1:-rpDoKABnNSke): `rpDoKABnNSke`\n", 15 "- [Flag #2](#Flag-#2:-rLQUQJFVGCub): `rLQUQJFVGCub`\n", 16 "- [Flag #3](#Flag-#3:-sjrxYAWdZvmK): `sjrxYAWdZvmK`\n", 17 "- [Flag #4](#Flag-#4:-JUnaJIfmRkrG): `JUnaJIfmRkrG`\n", 18 "- [Flag #5](#Flag-#5:-iPZHgewRDJWo): `iPZHgewRDJWo`\n", 19 "- [Flag #6](#Flag-#6:-GiCpBBEkozTb): `GiCpBBEkozTb`\n", 20 "- [Flag #7](#Flag-#7:-SySPnzQQARtl): `SySPnzQQARtl`\n", 21 "- [Flag #8](#Flag-#8:-TdoXluXivuiU): `TdoXluXivuiU`" 22 ] 23 }, 24 { 25 "cell_type": "markdown", 26 "metadata": {}, 27 "source": [ 28 "### Flag #1: `rpDoKABnNSke`\n", 29 "\n", 30 "[arch-spec.txt](arch-spec.txt) (line 30)" 31 ] 32 }, 33 { 34 "cell_type": "markdown", 35 "metadata": {}, 36 "source": [ 37 "### Flag #2: `rLQUQJFVGCub`\n", 38 "\n", 39 "Implement `out` and `noop` and run the virtual machine ([synacor.py](synacor.py)).\n", 40 "\n", 41 "```\n", 42 "Welcome to the Synacor Challenge!\n", 43 "Please record your progress by putting codes like\n", 44 "this one into the challenge website: rLQUQJFVGCub\n", 45 "```" 46 ] 47 }, 48 { 49 "cell_type": "markdown", 50 "metadata": {}, 51 "source": [ 52 "### Flag #3: `sjrxYAWdZvmK`\n", 53 "\n", 54 "Finish the [vm implementation](synacor.py) and pass the self-test.\n", 55 "\n", 56 "```\n", 57 "Executing self-test...\n", 58 "\n", 59 "self-test complete, all tests pass\n", 60 "The self-test completion code is: sjrxYAWdZvmK\n", 61 "```" 62 ] 63 }, 64 { 65 "cell_type": "markdown", 66 "metadata": {}, 67 "source": [ 68 "### Flag #4: `JUnaJIfmRkrG`\n", 69 "\n", 70 "Take and use the tablet in the first room.\n", 71 "\n", 72 "```\n", 73 "== Foothills ==\n", 74 "You find yourself standing at the base of an enormous mountain. At its base to the north, there is a massive doorway. A sign nearby reads \"Keep out! Definitely no treasure within!\"\n", 75 "\n", 76 "Things of interest here:\n", 77 "- tablet\n", 78 "\n", 79 "There are 2 exits:\n", 80 "- doorway\n", 81 "- south\n", 82 "\n", 83 "What do you do?\n", 84 "> take tablet\n", 85 "\n", 86 "\n", 87 "Taken.\n", 88 "\n", 89 "What do you do?\n", 90 "> use tablet\n", 91 "\n", 92 "\n", 93 "You find yourself writing \"JUnaJIfmRkrG\" on the tablet. Perhaps it's some kind of code?\n", 94 "```" 95 ] 96 }, 97 { 98 "cell_type": "markdown", 99 "metadata": {}, 100 "source": [ 101 "### Flag #5: `iPZHgewRDJWo`\n", 102 "\n", 103 "Find and take the empty lantern, navigate through the maze and use the oil can.\n", 104 "\n", 105 "```\n", 106 "== Foothills ==\n", 107 "You find yourself standing at the base of an enormous mountain. At its base to the north, there is a massive doorway. A sign nearby reads \"Keep out! Definitely no treasure within!\"\n", 108 "\n", 109 "Things of interest here:\n", 110 "- tablet\n", 111 "\n", 112 "There are 2 exits:\n", 113 "- doorway\n", 114 "- south\n", 115 "\n", 116 "What do you do?\n", 117 "> doorway\n", 118 "\n", 119 "\n", 120 "== Dark cave ==\n", 121 "This seems to be the mouth of a deep cave. As you peer north into the darkness, you think you hear the echoes of bats deeper within.\n", 122 "\n", 123 "There are 2 exits:\n", 124 "- north\n", 125 "- south\n", 126 "\n", 127 "What do you do?\n", 128 "> n\n", 129 "\n", 130 "\n", 131 "== Dark cave ==\n", 132 "The cave is somewhat narrow here, and the light from the doorway to the south is quite dim.\n", 133 "\n", 134 "There are 2 exits:\n", 135 "- north\n", 136 "- south\n", 137 "\n", 138 "What do you do?\n", 139 "> n\n", 140 "\n", 141 "\n", 142 "== Dark cave ==\n", 143 "The cave acoustics dramatically change as you find yourself at a legde above a large chasm. There is barely enough light here to notice a rope bridge leading out into the dark emptiness.\n", 144 "\n", 145 "There are 2 exits:\n", 146 "- bridge\n", 147 "- south\n", 148 "\n", 149 "What do you do?\n", 150 "> bridge\n", 151 "\n", 152 "\n", 153 "== Rope bridge ==\n", 154 "This rope bridge creaks as you walk along it. You aren't sure how old it is, or whether it can even support your weight.\n", 155 "\n", 156 "There are 2 exits:\n", 157 "- continue\n", 158 "- back\n", 159 "\n", 160 "What do you do?\n", 161 "> continue\n", 162 "\n", 163 "\n", 164 "== Falling through the air! ==\n", 165 "As you continue along the bridge, it snaps! You try to grab the bridge, but it evades your grasp in the darkness. You are plummeting quickly downward into the chasm...\n", 166 "\n", 167 "There is 1 exit:\n", 168 "- down\n", 169 "\n", 170 "What do you do?\n", 171 "> d\n", 172 "\n", 173 "\n", 174 "== Moss cavern ==\n", 175 "You are standing in a large cavern full of bioluminescent moss. It must have broken your fall! The cavern extends to the east and west; at the west end, you think you see a passage leading out of the cavern.\n", 176 "\n", 177 "There are 2 exits:\n", 178 "- west\n", 179 "- east\n", 180 "\n", 181 "What do you do?\n", 182 "> e\n", 183 "\n", 184 "\n", 185 "== Moss cavern ==\n", 186 "You are standing in a large cavern full of bioluminescent moss. The cavern extends to the west.\n", 187 "\n", 188 "Things of interest here:\n", 189 "- empty lantern\n", 190 "\n", 191 "There is 1 exit:\n", 192 "- west\n", 193 "\n", 194 "What do you do?\n", 195 "> take empty lantern\n", 196 "\n", 197 "\n", 198 "Taken.\n", 199 "\n", 200 "What do you do?\n", 201 "> w\n", 202 "\n", 203 "\n", 204 "== Moss cavern ==\n", 205 "You are standing in a large cavern full of bioluminescent moss. It must have broken your fall! The cavern extends to the east and west; at the west end, you think you see a passage leading out of the cavern.\n", 206 "\n", 207 "There are 2 exits:\n", 208 "- west\n", 209 "- east\n", 210 "\n", 211 "What do you do?\n", 212 "> w\n", 213 "\n", 214 "\n", 215 "== Moss cavern ==\n", 216 "You are standing in a large cavern full of bioluminescent moss. The cavern extends to the east. There is a crevise in the rocks which opens into a passage.\n", 217 "\n", 218 "There are 2 exits:\n", 219 "- east\n", 220 "- passage\n", 221 "\n", 222 "What do you do?\n", 223 "> passage\n", 224 "\n", 225 "\n", 226 "== Passage ==\n", 227 "You are in a crevise on the west wall of the moss cavern. A dark passage leads further west. There is a ladder here which leads down into a smaller, moss-filled cavern below.\n", 228 "\n", 229 "There are 3 exits:\n", 230 "- cavern\n", 231 "- ladder\n", 232 "- darkness\n", 233 "\n", 234 "What do you do?\n", 235 "> ladder\n", 236 "\n", 237 "\n", 238 "== Twisty passages ==\n", 239 "You are in a maze of twisty little passages, all dimly lit by more bioluminescent moss. There is a ladder here leading up.\n", 240 "\n", 241 "There are 5 exits:\n", 242 "- ladder\n", 243 "- north\n", 244 "- south\n", 245 "- east\n", 246 "- west\n", 247 "\n", 248 "What do you do?\n", 249 "> w\n", 250 "\n", 251 "\n", 252 "== Twisty passages ==\n", 253 "You are in a little maze of twisty passages, all alike.\n", 254 "\n", 255 "There are 3 exits:\n", 256 "- north\n", 257 "- south\n", 258 "- east\n", 259 "\n", 260 "What do you do?\n", 261 "> s\n", 262 "\n", 263 "\n", 264 "== Twisty passages ==\n", 265 "You are in a twisty alike of little passages, all maze.\n", 266 "\n", 267 "The east passage appears very dark; you feel likely to be eaten by a Grue.\n", 268 "\n", 269 "There are 4 exits:\n", 270 "- north\n", 271 "- south\n", 272 "- west\n", 273 "- east\n", 274 "\n", 275 "What do you do?\n", 276 "> n\n", 277 "\n", 278 "\n", 279 "Chiseled on the wall of one of the passageways, you see:\n", 280 "\n", 281 " iPZHgewRDJWo\n", 282 "\n", 283 "You take note of this and keep walking.\n", 284 "\n", 285 "== Twisty passages ==\n", 286 "You are in a maze of twisty little passages, all alike.\n", 287 "\n", 288 "Things of interest here:\n", 289 "- can\n", 290 "\n", 291 "There is 1 exit:\n", 292 "- west\n", 293 "\n", 294 "What do you do?\n", 295 "> take can\n", 296 "\n", 297 "\n", 298 "Taken.\n", 299 "\n", 300 "What do you do?\n", 301 "> use can\n", 302 "\n", 303 "\n", 304 "You fill your lantern with oil. It seems to cheer up!\n", 305 "\n", 306 "\n", 307 "What do you do?\n", 308 "> use lantern\n", 309 "\n", 310 "\n", 311 "You light your lantern.\n", 312 "```" 313 ] 314 }, 315 { 316 "cell_type": "markdown", 317 "metadata": {}, 318 "source": [ 319 "### Flag #6: `GiCpBBEkozTb`\n", 320 "\n", 321 "Use your lantern to navigate the darkness and find the coin puzzle.\n", 322 "\n", 323 "```\n", 324 "== Twisty passages ==\n", 325 "You are in a maze of twisty little passages, all alike.\n", 326 "\n", 327 "There is 1 exit:\n", 328 "- west\n", 329 "\n", 330 "What do you do?\n", 331 "> w\n", 332 "\n", 333 "\n", 334 "== Twisty passages ==\n", 335 "You are in a maze of twisty little passages, all dimly lit by more bioluminescent moss. There is a ladder here leading up.\n", 336 "\n", 337 "There are 5 exits:\n", 338 "- ladder\n", 339 "- north\n", 340 "- south\n", 341 "- east\n", 342 "- west\n", 343 "\n", 344 "What do you do?\n", 345 "> ladder\n", 346 "\n", 347 "\n", 348 "== Passage ==\n", 349 "You are in a crevise on the west wall of the moss cavern. A dark passage leads further west. There is a ladder here which leads down into a smaller, moss-filled cavern below.\n", 350 "\n", 351 "There are 3 exits:\n", 352 "- cavern\n", 353 "- ladder\n", 354 "- darkness\n", 355 "\n", 356 "What do you do?\n", 357 "> darkness\n", 358 "\n", 359 "\n", 360 "== Passage ==\n", 361 "You feel that your light source is more than sufficient to keep grues away.\n", 362 "\n", 363 "There are 2 exits:\n", 364 "- continue\n", 365 "- back\n", 366 "\n", 367 "What do you do?\n", 368 "> continue\n", 369 "\n", 370 "\n", 371 "== Dark passage ==\n", 372 "You are in a narrow passage. There is darkness to the west, but you can barely see a glowing opening to the east.\n", 373 "\n", 374 "There are 2 exits:\n", 375 "- west\n", 376 "- east\n", 377 "\n", 378 "What do you do?\n", 379 "> w\n", 380 "\n", 381 "\n", 382 "== Dark passage ==\n", 383 "You are in a dark, narrow passage.\n", 384 "\n", 385 "There are 2 exits:\n", 386 "- east\n", 387 "- west\n", 388 "\n", 389 "What do you do?\n", 390 "> w\n", 391 "\n", 392 "\n", 393 "== Dark passage ==\n", 394 "You are in a dark, narrow passage.\n", 395 "\n", 396 "There are 2 exits:\n", 397 "- east\n", 398 "- west\n", 399 "\n", 400 "What do you do?\n", 401 "> w\n", 402 "\n", 403 "\n", 404 "== Dark passage ==\n", 405 "You are in a dark, narrow passage. To the west, you spot some vegetation where the passage expands.\n", 406 "\n", 407 "There are 2 exits:\n", 408 "- east\n", 409 "- west\n", 410 "\n", 411 "What do you do?\n", 412 "> w\n", 413 "\n", 414 "\n", 415 "== Ruins ==\n", 416 "You stand in a large cavern with a huge ruin to the north, overgrown by plant life. There is a large stone archway to the north acting as the doorway to the ruined complex. A crevice in the rock to the east leads to an alarmingly dark passageway.\n", 417 "\n", 418 "There are 2 exits:\n", 419 "- east\n", 420 "- north\n", 421 "\n", 422 "What do you do?\n", 423 "> n\n", 424 "\n", 425 "\n", 426 "== Ruins ==\n", 427 "You are in the once-opulent foyer of a massive ruined complex. There is a door to the south leading to the overgrowth outside and stairs to the north which lead into a larger hall.\n", 428 "\n", 429 "Things of interest here:\n", 430 "- red coin\n", 431 "\n", 432 "There are 2 exits:\n", 433 "- north\n", 434 "- south\n", 435 "\n", 436 "What do you do?\n", 437 "> look red coin\n", 438 "\n", 439 "\n", 440 "This coin is made of a red metal. It has two dots on one side.\n", 441 "\n", 442 "What do you do?\n", 443 "> take red coin\n", 444 "\n", 445 "\n", 446 "Taken.\n", 447 "\n", 448 "What do you do?\n", 449 "> n\n", 450 "\n", 451 "\n", 452 "== Ruins ==\n", 453 "You stand in the massive central hall of these ruins. The walls are crumbling, and vegetation has clearly taken over. Rooms are attached in all directions. There is a strange monument in the center of the hall with circular slots and unusual symbols. It reads:\n", 454 "\n", 455 "_ + _ * _^2 + _^3 - _ = 399\n", 456 "\n", 457 "There are 4 exits:\n", 458 "- north\n", 459 "- south\n", 460 "- east\n", 461 "- west\n", 462 "\n", 463 "What do you do?\n", 464 "> e\n", 465 "\n", 466 "\n", 467 "== Ruins ==\n", 468 "You stand in what seems to have once been a dining hall; broken tables and pottery are scattered everywhere. A staircase here leads down.\n", 469 "\n", 470 "Things of interest here:\n", 471 "- concave coin\n", 472 "\n", 473 "There are 2 exits:\n", 474 "- down\n", 475 "- west\n", 476 "\n", 477 "What do you do?\n", 478 "> look concave coin\n", 479 "\n", 480 "\n", 481 "This coin is slightly rounded, almost like a tiny bowl. It has seven dots on one side.\n", 482 "\n", 483 "What do you do?\n", 484 "> take concave coin\n", 485 "\n", 486 "\n", 487 "Taken.\n", 488 "\n", 489 "What do you do?\n", 490 "> d\n", 491 "\n", 492 "\n", 493 "== Ruins ==\n", 494 "This seems to be a kitchen; there are brick stoves and shelves along the wall. Everything here has fallen into disrepair.\n", 495 "\n", 496 "Things of interest here:\n", 497 "- corroded coin\n", 498 "\n", 499 "There is 1 exit:\n", 500 "- up\n", 501 "\n", 502 "What do you do?\n", 503 "> look corroded coin\n", 504 "\n", 505 "\n", 506 "This coin is somewhat corroded. It has a triangle on one side.\n", 507 "\n", 508 "What do you do?\n", 509 "> take corroded coin\n", 510 "\n", 511 "\n", 512 "Taken.\n", 513 "\n", 514 "What do you do?\n", 515 "> u\n", 516 "\n", 517 "\n", 518 "== Ruins ==\n", 519 "You stand in what seems to have once been a dining hall; broken tables and pottery are scattered everywhere. A staircase here leads down.\n", 520 "\n", 521 "There are 2 exits:\n", 522 "- down\n", 523 "- west\n", 524 "\n", 525 "What do you do?\n", 526 "> w\n", 527 "\n", 528 "\n", 529 "== Ruins ==\n", 530 "You stand in the massive central hall of these ruins. The walls are crumbling, and vegetation has clearly taken over. Rooms are attached in all directions. There is a strange monument in the center of the hall with circular slots and unusual symbols. It reads:\n", 531 "\n", 532 "_ + _ * _^2 + _^3 - _ = 399\n", 533 "\n", 534 "There are 4 exits:\n", 535 "- north\n", 536 "- south\n", 537 "- east\n", 538 "- west\n", 539 "\n", 540 "What do you do?\n", 541 "> w\n", 542 "\n", 543 "\n", 544 "== Ruins ==\n", 545 "You find yourself in what was once the living quarters for the complex. Many smaller rooms which once had walls to divide them now lay in disarray. There is a staircase up here.\n", 546 "\n", 547 "Things of interest here:\n", 548 "- blue coin\n", 549 "\n", 550 "There are 2 exits:\n", 551 "- up\n", 552 "- east\n", 553 "\n", 554 "What do you do?\n", 555 "> look blue coin\n", 556 "\n", 557 "\n", 558 "This coin is made of a blue metal. It has nine dots on one side.\n", 559 "\n", 560 "What do you do?\n", 561 "> take blue coin\n", 562 "\n", 563 "\n", 564 "Taken.\n", 565 "\n", 566 "What do you do?\n", 567 "> u\n", 568 "\n", 569 "\n", 570 "== Ruins ==\n", 571 "This was long ago a lavish throne room. Dried-up fountains and crumbling statues line the walls, and the carved stone throne in the center of the room is falling apart.\n", 572 "\n", 573 "Things of interest here:\n", 574 "- shiny coin\n", 575 "\n", 576 "There is 1 exit:\n", 577 "- down\n", 578 "\n", 579 "What do you do?\n", 580 "> look shiny coin\n", 581 "\n", 582 "\n", 583 "This coin is somehow still quite shiny. It has a pentagon on one side.\n", 584 "\n", 585 "What do you do?\n", 586 "> take shiny coin\n", 587 "\n", 588 "\n", 589 "Taken.\n", 590 "\n", 591 "What do you do?\n", 592 "> d\n", 593 "\n", 594 "\n", 595 "== Ruins ==\n", 596 "You find yourself in what was once the living quarters for the complex. Many smaller rooms which once had walls to divide them now lay in disarray. There is a staircase up here.\n", 597 "\n", 598 "There are 2 exits:\n", 599 "- up\n", 600 "- east\n", 601 "\n", 602 "What do you do?\n", 603 "> e\n", 604 "\n", 605 "\n", 606 "== Ruins ==\n", 607 "You stand in the massive central hall of these ruins. The walls are crumbling, and vegetation has clearly taken over. Rooms are attached in all directions. There is a strange monument in the center of the hall with circular slots and unusual symbols. It reads:\n", 608 "\n", 609 "_ + _ * _^2 + _^3 - _ = 399\n", 610 "\n", 611 "There are 4 exits:\n", 612 "- north\n", 613 "- south\n", 614 "- east\n", 615 "- west\n", 616 "\n", 617 "What do you do?\n", 618 "> \n", 619 "```" 620 ] 621 }, 622 { 623 "cell_type": "code", 624 "execution_count": 1, 625 "metadata": {}, 626 "outputs": [ 627 { 628 "name": "stdout", 629 "output_type": "stream", 630 "text": [ 631 "blue red shiny concave corroded\n" 632 ] 633 } 634 ], 635 "source": [ 636 "import itertools\n", 637 "\n", 638 "coins = {\n", 639 " 2: \"red\",\n", 640 " 3: \"corroded\",\n", 641 " 5: \"shiny\",\n", 642 " 7: \"concave\",\n", 643 " 9: \"blue\",\n", 644 "}\n", 645 "\n", 646 "for a, b, c, d, e in itertools.permutations(coins):\n", 647 " if a + b * c**2 + d**3 - e == 399:\n", 648 " print(*map(coins.get, (a, b, c, d, e)))" 649 ] 650 }, 651 { 652 "cell_type": "markdown", 653 "metadata": {}, 654 "source": [ 655 "Now place the coins in this order and use the teleporter.\n", 656 "\n", 657 "```\n", 658 "== Ruins ==\n", 659 "You stand in the massive central hall of these ruins. The walls are crumbling, and vegetation has clearly taken over. Rooms are attached in all directions. There is a strange monument in the center of the hall with circular slots and unusual symbols. It reads:\n", 660 "\n", 661 "_ + _ * _^2 + _^3 - _ = 399\n", 662 "\n", 663 "There are 4 exits:\n", 664 "- north\n", 665 "- south\n", 666 "- east\n", 667 "- west\n", 668 "\n", 669 "What do you do?\n", 670 "> use blue coin\n", 671 "\n", 672 "\n", 673 "You place the blue coin into the leftmost open slot.\n", 674 "\n", 675 "What do you do?\n", 676 "> use red coin\n", 677 "\n", 678 "\n", 679 "You place the red coin into the leftmost open slot.\n", 680 "\n", 681 "What do you do?\n", 682 "> use shiny coin\n", 683 "\n", 684 "\n", 685 "You place the shiny coin into the leftmost open slot.\n", 686 "\n", 687 "What do you do?\n", 688 "> use concave coin\n", 689 "\n", 690 "\n", 691 "You place the concave coin into the leftmost open slot.\n", 692 "\n", 693 "What do you do?\n", 694 "> use corroded coin\n", 695 "\n", 696 "\n", 697 "You place the corroded coin into the leftmost open slot.\n", 698 "As you place the last coin, you hear a click from the north door.\n", 699 "\n", 700 "What do you do?\n", 701 "> n\n", 702 "\n", 703 "\n", 704 "== Ruins ==\n", 705 "Because it has been so well-protected, this room hardly shows signs of decay. The walls are covered in elaborate murals and decorated with precious metals and stones.\n", 706 "\n", 707 "Things of interest here:\n", 708 "- teleporter\n", 709 "\n", 710 "There is 1 exit:\n", 711 "- south\n", 712 "\n", 713 "What do you do?\n", 714 "> take teleporter\n", 715 "\n", 716 "\n", 717 "Taken.\n", 718 "\n", 719 "What do you do?\n", 720 "> use teleporter\n", 721 "\n", 722 "\n", 723 "You activate the teleporter! As you spiral through time and space, you think you see a pattern in the stars...\n", 724 "\n", 725 " GiCpBBEkozTb\n", 726 "\n", 727 "After a few moments, you find yourself back on solid ground and a little disoriented.\n", 728 "```" 729 ] 730 }, 731 { 732 "cell_type": "markdown", 733 "metadata": {}, 734 "source": [ 735 "### Flag #7: `SySPnzQQARtl`\n", 736 "\n", 737 "Assembly:\n", 738 "\n", 739 "```\n", 740 "5483| set r1 4\n", 741 "5486| set r2 1\n", 742 "5489| call 6027\n", 743 "5491| eq r2 r1 6\n", 744 "5495| jf r2 5579\n", 745 "\n", 746 "\n", 747 "6027| jt r1 6035\n", 748 "6030| add r1 r2 1\n", 749 "6034| ret\n", 750 "\n", 751 "6035| jt r2 6048\n", 752 "6038| add r1 r1 32767\n", 753 "6042| set r2 r8\n", 754 "6045| call 6027\n", 755 "6047| ret\n", 756 "\n", 757 "6048| push r1\n", 758 "6050| add r2 r2 32767\n", 759 "6054| call 6027\n", 760 "6056| set r2 r1\n", 761 "6059| pop r1\n", 762 "6061| add r1 r1 32767\n", 763 "6065| call 6027\n", 764 "6067| ret\n", 765 "```\n", 766 "\n", 767 "C++ ([teleporter.cpp](teleporter.cpp)):\n", 768 "```c++\n", 769 "const int MOD = 1<<15;\n", 770 "map<tuple<int, int>, int> dp;\n", 771 "int c;\n", 772 "\n", 773 "int ackermann(int a, int b) {\n", 774 " a %= MOD;\n", 775 " b %= MOD;\n", 776 " if (!a) return (b+1)%MOD;\n", 777 " tuple<int, int> key = make_tuple(a, b);\n", 778 " if (dp.count(key)) return dp[key];\n", 779 " \n", 780 " if (!b) return dp[key] = ackermann(a - 1, c);\n", 781 " return dp[key] = ackermann(a - 1, ackermann(a, b - 1));\n", 782 "}\n", 783 "\n", 784 "int main() {\n", 785 " for (c = 1; c < MOD; c++) {\n", 786 " dp.clear();\n", 787 " if (ackermann(4, 1) == 6) {\n", 788 " // RESULT: 25734\n", 789 " cout << \"RESULT: \" << i << endl;\n", 790 " break;\n", 791 " }\n", 792 " }\n", 793 "}\n", 794 "```\n", 795 "\n", 796 "Now set r8 to `25734` and bypass the confirmation process by patching the program:\n", 797 "```\n", 798 "5483| set r1 6\n", 799 "5486| set r8 25734\n", 800 "5489| noop\n", 801 "5490| noop\n", 802 "5491| eq r2 r1 6\n", 803 "5495| jf r2 5579\n", 804 "```\n", 805 "\n", 806 "Then use the teleporter:\n", 807 "```\n", 808 "== Synacor Headquarters ==\n", 809 "You stand in the lobby of what appears to be a really fun place to work! Sadly, there doesn't seem to be anyone around at the moment, so you make a note to call them later. The bookshelf here looks like it might have something interesting in it, though.\n", 810 "\n", 811 "Things of interest here:\n", 812 "- business card\n", 813 "- strange book\n", 814 "\n", 815 "There is 1 exit:\n", 816 "- outside\n", 817 "\n", 818 "What do you do?\n", 819 "> .rs 8 25734\n", 820 "> use teleporter\n", 821 "\n", 822 "\n", 823 "A strange, electronic voice is projected into your mind:\n", 824 "\n", 825 " \"Unusual setting detected! Starting confirmation process! Estimated time to completion: 1 billion years.\"\n", 826 "\n", 827 "You wake up on a sandy beach with a slight headache. The last thing you remember is activating that teleporter... but now you can't find it anywhere in your pack. Someone seems to have drawn a message in the sand here:\n", 828 "\n", 829 " SySPnzQQARtl\n", 830 "\n", 831 "It begins to rain. The message washes away. You take a deep breath and feel firmly grounded in reality as the effects of the teleportation wear off.\n", 832 "```" 833 ] 834 }, 835 { 836 "cell_type": "markdown", 837 "metadata": {}, 838 "source": [ 839 "### Flag #8: `TdoXluXivuiU`\n", 840 "\n", 841 "Navigate the grid to find out the numbers and symbols. Then use [breadth first search](https://en.wikipedia.org/wiki/Breadth-first_search) to find the shortest path." 842 ] 843 }, 844 { 845 "cell_type": "code", 846 "execution_count": 2, 847 "metadata": {}, 848 "outputs": [ 849 { 850 "name": "stdout", 851 "output_type": "stream", 852 "text": [ 853 "neenwseewnne\n" 854 ] 855 } 856 ], 857 "source": [ 858 "TARGET = 30\n", 859 "graph = [*map(str.split, [\n", 860 " \" * 8 - 1 \",\n", 861 " \" 4 * 11 * \",\n", 862 " \" + 4 - 18 \",\n", 863 " \" 22 - 9 * \",\n", 864 "])]\n", 865 "\n", 866 "queue = [(int(graph[3][0]), 3, 0, \"\")]\n", 867 "visited = set()\n", 868 "while queue:\n", 869 " n, y, x, path = queue.pop(0)\n", 870 " \n", 871 " if (n, y, x) in visited:\n", 872 " continue\n", 873 " visited.add((n, y, x))\n", 874 " \n", 875 " if (y, x) == (0, 3):\n", 876 " if n == TARGET:\n", 877 " print(path)\n", 878 " break\n", 879 " continue\n", 880 " \n", 881 " for r, (ay, ax) in zip(\"nswe\", [(y-1,x),(y+1,x),(y,x-1),(y,x+1)]):\n", 882 " if ay not in range(4) or ax not in range(4):\n", 883 " continue\n", 884 " for s, (by, bx) in zip(\"nswe\", [(ay-1,ax),(ay+1,ax),(ay,ax-1),(ay,ax+1)]):\n", 885 " if by not in range(4) or bx not in range(4) or (by, bx) == (3, 0):\n", 886 " continue\n", 887 " \n", 888 " v = eval(str(n) + graph[ay][ax] + graph[by][bx])\n", 889 " queue.append((v, by, bx, path + r+s))" 890 ] 891 }, 892 { 893 "cell_type": "markdown", 894 "metadata": {}, 895 "source": [ 896 "```\n", 897 "== Beach ==\n", 898 "This is a sandy beach in a cove on some tropical island. It is raining. The ocean is to your south, and heavy foliage is to your north; the beach extends west and east.\n", 899 "\n", 900 "There are 3 exits:\n", 901 "- west\n", 902 "- east\n", 903 "- north\n", 904 "\n", 905 "What do you do?\n", 906 "> n\n", 907 "\n", 908 "\n", 909 "== Tropical Island ==\n", 910 "The large trees here seem to be protecting you from the rain. As you push through the undergrowth, you can hear birds chirping overhead. There is a steep rock face to your west blocking your path.\n", 911 "\n", 912 "There are 3 exits:\n", 913 "- north\n", 914 "- south\n", 915 "- east\n", 916 "\n", 917 "What do you do?\n", 918 "> n\n", 919 "\n", 920 "\n", 921 "== Tropical Island ==\n", 922 "The embankment of the cove come toegher here to your east and west. Between these tall rock faces, there is a narrow, overgrown path leading north. You hear waves lapping up on a beach through the dense vegetation to your south.\n", 923 "\n", 924 "There are 2 exits:\n", 925 "- north\n", 926 "- south\n", 927 "\n", 928 "What do you do?\n", 929 "> n\n", 930 "\n", 931 "\n", 932 "== Tropical Island ==\n", 933 "You are on a narrow path between two steep rock faces which look like they have been here for thousands of years. Rain trickles down through the vegetation and moss, and through the leaves you can occasionally see a sliver of light hundreds of feet above you where the rock walls end.\n", 934 "\n", 935 "There are 2 exits:\n", 936 "- north\n", 937 "- south\n", 938 "\n", 939 "What do you do?\n", 940 "> n\n", 941 "\n", 942 "\n", 943 "== Tropical Island ==\n", 944 "The narrow path slopes downward to the north and leads to the mouth of a small cave. A sign nearby reads \"Treasure Vault Access\", but different handwriting has crossed this out and written \"Lair of Horrible Monster! All non-pirates keep out!\".\n", 945 "\n", 946 "There are 2 exits:\n", 947 "- north\n", 948 "- south\n", 949 "\n", 950 "What do you do?\n", 951 "> n\n", 952 "\n", 953 "\n", 954 "== Tropical Cave ==\n", 955 "You stand at the entrance to a natural cave which looks like it hasn't been visited in quite some time. Light pours in through the opening to the south, while fireflies light the path further into the cave to the north.\n", 956 "\n", 957 "There are 2 exits:\n", 958 "- north\n", 959 "- south\n", 960 "\n", 961 "What do you do?\n", 962 "> n\n", 963 "\n", 964 "\n", 965 "== Tropical Cave ==\n", 966 "Fireflies slowly drift around you and light the tunnel, which seems to get brighter to the south, but dimmer to the north.\n", 967 "\n", 968 "There are 2 exits:\n", 969 "- north\n", 970 "- south\n", 971 "\n", 972 "What do you do?\n", 973 "> n\n", 974 "\n", 975 "\n", 976 "== Tropical Cave ==\n", 977 "The cave is a little wider here. You find the cobweb-encrusted remains of a small camp, and although you don't suspect the broken pieces of tables and chairs will prove useful to your quest, the fireflies seem to like using the debris as a shelter. A passageway leads north and south, and there is an alcove to the east.\n", 978 "\n", 979 "There are 3 exits:\n", 980 "- north\n", 981 "- south\n", 982 "- east\n", 983 "\n", 984 "What do you do?\n", 985 "> n\n", 986 "\n", 987 "\n", 988 "== Tropical Cave ==\n", 989 "This tunnel slopes deeper underground to the north, but the fireflies are all around to light your path.\n", 990 "\n", 991 "There are 2 exits:\n", 992 "- north\n", 993 "- south\n", 994 "\n", 995 "What do you do?\n", 996 "> n\n", 997 "\n", 998 "\n", 999 "== Vault Antechamber ==\n", 1000 "You are in the antechamber to a grid of rooms that control the door to the vault. You notice the number '22' is carved into the orb's pedestal.\n", 1001 "\n", 1002 "Things of interest here:\n", 1003 "- orb\n", 1004 "\n", 1005 "There are 3 exits:\n", 1006 "- north\n", 1007 "- east\n", 1008 "- south\n", 1009 "\n", 1010 "What do you do?\n", 1011 "> take orb\n", 1012 "\n", 1013 "\n", 1014 "Taken.\n", 1015 "\n", 1016 "What do you do?\n", 1017 "> n\n", 1018 "\n", 1019 "\n", 1020 "As you enter the room, the symbol on the floor briefly flashes green. The orb begins subtly glowing green.\n", 1021 "\n", 1022 "== Vault Lock ==\n", 1023 "You are in a grid of rooms that control the door to the vault.\n", 1024 "\n", 1025 "The floor of this room is a large mosaic depicting a '+' symbol.\n", 1026 "\n", 1027 "There are 3 exits:\n", 1028 "- north\n", 1029 "- east\n", 1030 "- south\n", 1031 "\n", 1032 "What do you do?\n", 1033 "> e\n", 1034 "\n", 1035 "\n", 1036 "As you enter the room, the orb briefly flashes green. The number on the floor vibrates strangely beneath your feet. The orb seems to get heavier.\n", 1037 "\n", 1038 "== Vault Lock ==\n", 1039 "You are in a grid of rooms that control the door to the vault.\n", 1040 "\n", 1041 "The floor of this room is a large mosaic depicting the number '4'.\n", 1042 "\n", 1043 "There are 4 exits:\n", 1044 "- north\n", 1045 "- east\n", 1046 "- south\n", 1047 "- west\n", 1048 "\n", 1049 "What do you do?\n", 1050 "> e\n", 1051 "\n", 1052 "\n", 1053 "As you enter the room, the symbol on the floor briefly flashes red. The orb begins subtly glowing red.\n", 1054 "\n", 1055 "== Vault Lock ==\n", 1056 "You are in a grid of rooms that control the door to the vault.\n", 1057 "\n", 1058 "The floor of this room is a large mosaic depicting a '-' symbol.\n", 1059 "\n", 1060 "There are 4 exits:\n", 1061 "- north\n", 1062 "- east\n", 1063 "- south\n", 1064 "- west\n", 1065 "\n", 1066 "What do you do?\n", 1067 "> n\n", 1068 "\n", 1069 "\n", 1070 "As you enter the room, the orb briefly flashes red. The number on the floor vibrates strangely beneath your feet. The orb seems to get lighter.\n", 1071 "\n", 1072 "== Vault Lock ==\n", 1073 "You are in a grid of rooms that control the door to the vault.\n", 1074 "\n", 1075 "The floor of this room is a large mosaic depicting the number '11'.\n", 1076 "\n", 1077 "There are 4 exits:\n", 1078 "- north\n", 1079 "- east\n", 1080 "- south\n", 1081 "- west\n", 1082 "\n", 1083 "What do you do?\n", 1084 "> w\n", 1085 "\n", 1086 "\n", 1087 "As you enter the room, the symbol on the floor briefly flashes yellow. The orb begins subtly glowing yellow.\n", 1088 "\n", 1089 "== Vault Lock ==\n", 1090 "You are in a grid of rooms that control the door to the vault.\n", 1091 "\n", 1092 "The floor of this room is a large mosaic depicting a '*' symbol.\n", 1093 "\n", 1094 "There are 4 exits:\n", 1095 "- north\n", 1096 "- east\n", 1097 "- south\n", 1098 "- west\n", 1099 "\n", 1100 "What do you do?\n", 1101 "> s\n", 1102 "\n", 1103 "\n", 1104 "As you enter the room, the orb briefly flashes yellow. The number on the floor vibrates strangely beneath your feet. The orb seems to get heavier.\n", 1105 "\n", 1106 "== Vault Lock ==\n", 1107 "You are in a grid of rooms that control the door to the vault.\n", 1108 "\n", 1109 "The floor of this room is a large mosaic depicting the number '4'.\n", 1110 "\n", 1111 "There are 4 exits:\n", 1112 "- north\n", 1113 "- east\n", 1114 "- south\n", 1115 "- west\n", 1116 "\n", 1117 "What do you do?\n", 1118 "> e\n", 1119 "\n", 1120 "\n", 1121 "As you enter the room, the symbol on the floor briefly flashes red. The orb begins subtly glowing red.\n", 1122 "\n", 1123 "== Vault Lock ==\n", 1124 "You are in a grid of rooms that control the door to the vault.\n", 1125 "\n", 1126 "The floor of this room is a large mosaic depicting a '-' symbol.\n", 1127 "\n", 1128 "There are 4 exits:\n", 1129 "- north\n", 1130 "- east\n", 1131 "- south\n", 1132 "- west\n", 1133 "\n", 1134 "What do you do?\n", 1135 "> e\n", 1136 "\n", 1137 "\n", 1138 "As you enter the room, the orb briefly flashes red. The number on the floor vibrates strangely beneath your feet. The orb seems to get lighter.\n", 1139 "\n", 1140 "== Vault Lock ==\n", 1141 "You are in a grid of rooms that control the door to the vault.\n", 1142 "\n", 1143 "The floor of this room is a large mosaic depicting the number '18'.\n", 1144 "\n", 1145 "There are 3 exits:\n", 1146 "- north\n", 1147 "- south\n", 1148 "- west\n", 1149 "\n", 1150 "What do you do?\n", 1151 "> w\n", 1152 "\n", 1153 "\n", 1154 "As you enter the room, the symbol on the floor briefly flashes red. The orb begins subtly glowing red.\n", 1155 "\n", 1156 "== Vault Lock ==\n", 1157 "You are in a grid of rooms that control the door to the vault.\n", 1158 "\n", 1159 "The floor of this room is a large mosaic depicting a '-' symbol.\n", 1160 "\n", 1161 "There are 4 exits:\n", 1162 "- north\n", 1163 "- east\n", 1164 "- south\n", 1165 "- west\n", 1166 "\n", 1167 "What do you do?\n", 1168 "> n\n", 1169 "\n", 1170 "\n", 1171 "As you enter the room, the orb briefly flashes red. The number on the floor vibrates strangely beneath your feet. The orb seems to get lighter.\n", 1172 "\n", 1173 "== Vault Lock ==\n", 1174 "You are in a grid of rooms that control the door to the vault.\n", 1175 "\n", 1176 "The floor of this room is a large mosaic depicting the number '11'.\n", 1177 "\n", 1178 "There are 4 exits:\n", 1179 "- north\n", 1180 "- east\n", 1181 "- south\n", 1182 "- west\n", 1183 "\n", 1184 "What do you do?\n", 1185 "> n\n", 1186 "\n", 1187 "\n", 1188 "As you enter the room, the symbol on the floor briefly flashes red. The orb begins subtly glowing red.\n", 1189 "\n", 1190 "== Vault Lock ==\n", 1191 "You are in a grid of rooms that control the door to the vault.\n", 1192 "\n", 1193 "The floor of this room is a large mosaic depicting a '-' symbol.\n", 1194 "\n", 1195 "There are 3 exits:\n", 1196 "- east\n", 1197 "- south\n", 1198 "- west\n", 1199 "\n", 1200 "What do you do?\n", 1201 "> e\n", 1202 "\n", 1203 "\n", 1204 "As you enter the room, the orb briefly flashes red. The number on the floor vibrates strangely beneath your feet. The orb seems to get lighter.\n", 1205 "\n", 1206 "As you approach the vault door, the number on the vault door flashes white! The hourglass is still running! It flashes white! You hear a click from the vault door. The orb evaporates out of hour hands.\n", 1207 "\n", 1208 "== Vault Door ==\n", 1209 "You stand before the door to the vault; it has a large '30' carved into it. Affixed to the wall near the door, there is a running hourglass which never seems to run out of sand.\n", 1210 "\n", 1211 "The floor of this room is a large mosaic depicting the number '1'.\n", 1212 "\n", 1213 "There are 3 exits:\n", 1214 "- south\n", 1215 "- west\n", 1216 "- vault\n", 1217 "\n", 1218 "What do you do?\n", 1219 "> vault\n", 1220 "\n", 1221 "\n", 1222 "== Vault ==\n", 1223 "This vault contains incredible riches! Piles of gold and platinum coins surround you, and the walls are adorned with topazes, rubies, sapphires, emeralds, opals, dilithium crystals, elerium-115, and unobtainium.\n", 1224 "\n", 1225 "Things of interest here:\n", 1226 "- mirror\n", 1227 "\n", 1228 "There is 1 exit:\n", 1229 "- leave\n", 1230 "\n", 1231 "What do you do?\n", 1232 "> take mirror\n", 1233 "\n", 1234 "\n", 1235 "Taken.\n", 1236 "\n", 1237 "What do you do?\n", 1238 "> use mirror\n", 1239 "\n", 1240 "\n", 1241 "You gaze into the mirror, and you see yourself gazing back. But wait! It looks like someone wrote on your face while you were unconscious on the beach! Through the mirror, you see \"UiuviXulXobT\" scrawled in charcoal on your forehead.\n", 1242 "\n", 1243 "Congratulations; you have reached the end of the challenge!\n", 1244 "```\n", 1245 "\n", 1246 "As we are looking into mirror, we need to mirror the flag itself:" 1247 ] 1248 }, 1249 { 1250 "cell_type": "code", 1251 "execution_count": 3, 1252 "metadata": {}, 1253 "outputs": [ 1254 { 1255 "name": "stdout", 1256 "output_type": "stream", 1257 "text": [ 1258 "TdoXluXivuiU\n" 1259 ] 1260 } 1261 ], 1262 "source": [ 1263 "print(\"UiuviXulXobT\"[::-1].replace(\"b\", \"d\"))" 1264 ] 1265 } 1266 ], 1267 "metadata": { 1268 "kernelspec": { 1269 "display_name": "Python 3", 1270 "language": "python", 1271 "name": "python3" 1272 }, 1273 "language_info": { 1274 "codemirror_mode": { 1275 "name": "ipython", 1276 "version": 3 1277 }, 1278 "file_extension": ".py", 1279 "mimetype": "text/x-python", 1280 "name": "python", 1281 "nbconvert_exporter": "python", 1282 "pygments_lexer": "ipython3", 1283 "version": "3.8.6" 1284 } 1285 }, 1286 "nbformat": 4, 1287 "nbformat_minor": 4 1288 }