Welcome to another installment in my Advent of Code 2020 series, where I present my solutions to this year’s Advent of Code challenges!
In this installment, I share my Python solution to Day 5 of Advent of Code, titled Binary Boarding.
Spoiler alert!
Please be warned: If you want to try solving the challenge on your own and without any help, stop reading now! The remainder of this post will be all about my solution to both parts of the Day 5 challenge.
The Day 5 challenge, part one
The challenge
Here’s the text from part one of the challenge:
You board your plane only to discover a new problem: you dropped your boarding pass! You aren’t sure which seat is yours, and all of the flight attendants are busy with the flood of people that suddenly made it through passport control.
You write a quick program to use your phone’s camera to scan all of the nearby boarding passes (your puzzle input); perhaps you can find your seat through process of elimination.
Instead of zones or groups, this airline uses binary space partitioning to seat people. A seat might be specified like
FBFBBFFRLR
, whereF
means “front”,B
means “back”,L
means “left”, andR
means “right”.The first 7 characters will either be
F
orB
; these specify exactly one of the 128 rows on the plane (numbered0
through127
). Each letter tells you which half of a region the given seat is in. Start with the whole list of rows; the first letter indicates whether the seat is in the front (0
through63
) or the back (64
through127
). The next letter indicates which half of that region the seat is in, and so on until you’re left with exactly one row.For example, consider just the first seven characters of
FBFBBFFRLR
:
- Start by considering the whole range, rows
0
through127
.F
means to take the lower half, keeping rows0
through63
.B
means to take the upper half, keeping rows32
through63
.F
means to take the lower half, keeping rows32
through47
.B
means to take the upper half, keeping rows40
through47
.B
keeps rows44
through47
.F
keeps rows44
through45
.- The final
F
keeps the lower of the two, row44
.The last three characters will be either
L
orR
; these specify exactly one of the 8 columns of seats on the plane (numbered0
through7
). The same process as above proceeds again, this time with only three steps.L
means to keep the lower half, whileR
means to keep the upper half.For example, consider just the last 3 characters of
FBFBBFFRLR
:
- Start by considering the whole range, columns
0
through7
.R
means to take the upper half, keeping columns4
through7
.L
means to take the lower half, keeping columns4
through5
.- The final
R
keeps the upper of the two, column5
.So, decoding
FBFBBFFRLR
reveals that it is the seat at row44
, column5
.Every seat also has a unique seat ID: multiply the row by 8, then add the column. In this example, the seat has ID
44 * 8 + 5 = 357
.Here are some other boarding passes:
BFFFBBFRRR
: row70
, column7
, seat ID567
.FFFBBBFRRR
: row14
, column7
, seat ID119
.BBFFBBFRLL
: row102
, column4
, seat ID820
.As a sanity check, look through your list of boarding passes. What is the highest seat ID on a boarding pass?
Importing the data
Every Advent of Code participant gets their own set of data. I copied my data and went through my usual process of bringing it into Python. This involves pasting it into a triple-quoted string and assigning it to the variable raw_input
, and then splitting it using the newline character as a delimiter, producing a list named split_input
:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 |
raw_input = """BBFFFFBRLL BFBBBBFLLL FBBBFBFLLR BFBBBFBLRR FBBFFBFLRR FFBFFBFRRR FBFBBBBLLL BFFBFFFRLR BFFBFFFRLL BFBBFBFRRL FBFFFFBLRR BBFFBFBLLR BBFBFFBRLR BFBFBFFRLR FBFFBFBRRL BFFFFBFRLR FFBBBBBRLR BFFFBFBLLR FBBBBBBRLL FBBFBFBRRL FBFBFBFLRL FFBFBBFRLL BFBFFBFRRL FBBBBFBLLR FFBBFBFLRR BFBFBBFRRL FBFFFBBLLR FBBFFBFRRR FFFBFBBLRL FBBBBFBRRL BFBFBBFLRL BBFFBFBLRL BBFFFFFLRL BBFBBFFRLR FFBFBBBRRL FBFFFFFRLR FFFBBFFLRR BFFFBFFLRL BFBFFFBRLR BBFBFBFLRR FBBBBFFRRR FBFFFBFRLL FBFFFFFLRL BFFFFFBLRR FFFBBBFLRL FBFBBBFRLL FFBFBBBLRR FBFFFFFRLL FFBFFFFLRR BBFBFBBRRL FFFBFBBLRR BFFBFBBRRR FFBBFFBLRL BFBBBFFRRL FFBBFFFRLL FBFFBFBLRR FBBFBBBRLL FBBFFFBRLR FBFFBFFLRL FFFBFBBRRR BBFFFBBRLL BFBFBBBRRR BBFFBFFLRR FFBFFBBLLL FFFBBBFLLL FBBFBBBRRL BBFBFBFLLR BFBFFFFRLL BFFBBFFRLR BFBBFFFRLR BBFFFBBRRL BFBFFBFLRR FBBFFFBRRR FFBFFFBLLR BFFFFBBRLR BBFFBBFRRR BFBBBFBLLL FFBBBFBLRR FFBFFBFLRL FFFBBBBRLR BFBFFFBRRR BBFFBFFRRL BFFBBFFLRR FFFBFBBLLL FBBBBBFLLL BFBFFBFLLR BBFBFBBRRR FBFBBFBRLR FBBFFBFRLL BFBBFFBLRL BFBBFFFRRL FBFFBBFRLR FBBFBBBLRL FBFFBFFLLR FFFBBFBRLR FBBFFBBLLR FFFBBBFRRL BBFBBFFRRL FFBBBFFRLR BFFFFBBRRR FBBBBBFRLR BBFBFFBRRR BFFBFBFRLL BFBFFFFLRL FBBBFFBRRR FBBFBBFLLL BFFFFBFLLR BBFFFFBLLR FFBFBFFLRR FBBBFBBRRL BFFFBBFLRL FBFFFBFLLL BBFFFFFRLR FFFBBBFRLL FFBBBFBRLL BFFBFFBRLR BBFFBBFLRR FBBBBFBLRR BFFBFFBLRL FFBFFFFRLR FBBBBBBRRL FBBFFFBLLR FBFFFFFLLR FBBFBBFRLL BFFBFFFRRL FBBFFBFLLR FFBBFFBLLR FBBBFBBRLR BFFBBBFLLR FFBBFBFRRR FFFBFBBRLL FBFFFBBRRL BFFFBBBLRL BBFFBBBLLL FBFBBFBLRL BBFFFBBLRL FBBBBFBLRL BBFFBBFLLL FBFBBFFRRR BFBBFBFLRL FBFFBBFLRL BFBFBFBLRL BFBBFBBLRL FFFBBFBLLR FFFBFBFRRL FBBBFBFRRR FBBBFFBLLR BFFFBBFLRR BFFFBFFLRR BBFFFBFRRR FFFBBFBLRR BFFFFFFRRL FBBFFFFLLR BBFBFFFRRR FBBBFFFRRR BFBFFFFRLR BFBBFFFRLL FFBBBFBLLR BFFBBBFLLL FBFFFBFRRL FFBFFFFRRR FFBBBBFRRL FFBFFFBLRR FBBBBFBRRR BBFFBFFLLL FBBBBFFLLR FBFFBBFLLL BFBBBFBRLL FBBFFFFRLL FBBFBFBRLR BFFBBFBLRR FFBFBFBRLL BBFFBBFRLL FFBFBBFLLL BFFBBFBLLL FBFFFFFRRL FBFFBFBLRL FFBFFBFRLL BFBBBBBRRR FBFFBFBLLR FFBFFFBLRL FFBFFBBLRR BFBFFBBRRL FFBFBFBRLR FFBFBFFLRL BBFBBFFLRL FFBFFBFLLR FFFBBBBLRR BFFBFBBRRL FFBBFBBRLR BFFBFBFLLR FFBBFBBRRR BBFFBBBRRR BFFFBFFLLR BFBBBFFRRR BFBBFBBLLL FFBBFBBLLL FBFBFBBLLR FFBBBFFLRR FFBFFBFLLL BFFBFFBLLL FBFBBBFLLL BBFBFBBRLL FBFFBFBRRR BBFBFFFRLL BBFBFFFRRL BFFFFBBLRL BFBFFFFRRL FFBFFBFRRL FBBFBBFLRR BFFFBBBRRL FFBFFFBLLL FFBBBBBLLR BFBFBFBLRR FFBBFFFLRL FBBBBBBRRR FBFBFFBLLL FBFFBBBRRL BFFBFFFRRR BFBBFFBRRR BBFBBFFLRR BBFBFFBRRL BBFFBBBLLR FBFFFFBRLR BBFFFFFRRR BFBFFBFRLL FBBBFBBRLL FFBBFBFRLR BFBFBFBRLR FFBBBFFLLR FBFFFFFLRR FBFFBFFRLR BFBBBBFRLR FBFBBFBLRR FBBBBFBRLR BFBFFBBRLL FFBBFBFLLL FFBFBFBLLL FFBFBFBRRR BFBFBFBLLR BFBBBBBRRL FBBBBBFRRR BBFBFFBLRL FBBBBFFRLR BBFFFFFLLR FBBFFBBLRR FBFFFFBRRR BFFFBBFRLL FBFBFFBLRR BFBBFBBRRL BFFFFBFRRL FFBFFFBRRR FFBFBBBRLL BBFFFFFRRL BFBBFBBLRR FBBFBFFRRR BFFBFFBLRR BFFFBBFLLL BFBFFFBRLL BBFBBFBLLL BFBFBFFRLL FFFBBBFLLR FBBBFFFRLL BFBFFBFRRR FFBBFFFRRR BBFFFBBRRR BFFFFBFLRR BFFFFFFRRR BBFFBFBLRR FBBBBBBRLR BBFFBFFLLR BFFBBBBLLR FBBBBFFLRR FFBBBFFRRL FBFBBFFLLL BBFFBBBRLL FBFFBFBLLL BFFBFBBRLR FBBFFFBLRL FFBFBFFLLL FBBBFBFLRL FFFBBFFLRL FBBBBFFRRL BFBFBBBRRL BFFFBBBLLR FBFBFBBLRL BFBBFFBLRR BBFBFFFLRR FBFFBBBLRR FFBFFBBRLL BFBFFFFLRR BBFBFFBRLL FBBBFBFRLL BFBBBFFLRL BFFBBBBRRL BFFBBBBLRR FFBBFBFRLL FBFBFFFLLL BFFFFFFLRL BFBBBFBRRL FFFBBBBRRL FBFFFFBLRL FBBBBBFRLL FFBBFFFLRR FBBFBBFLLR BFBFBBFRLL BFBFFFBLLR BFBFBBBLRL FFBFFFBRLR BFFBBBFRRL BFBBBBBLRR FBFFFBBRLL FBFBFBBRRR FFFBFBBRLR BFBFBBFLRR FBFBFBBLLL FFBBFFBRLL FBBFBFBRRR BFFFFFBRRL FBBBFBBLLL BBFBFFBLLL FFBFBFBLLR FFBBBFBRRL FBFBFBFLLL BFBFBBFRLR FBBFBFFRLR FFBFFBBRRR BFFBFFBLLR FBFFFBFLRL FBFFFFFRRR FFBBFBBRLL FBFFBFFRLL BBFFFBFLRR BFBBBFFRLL FBFBBBBLRL FFFBBBBLLL BBFFFFBRRR FBBBBBBLLL FFBFBFBLRL BFFBFFBRRL FFBBFBBLRR BFBFFBFLLL FBBBBFFRLL FFFBBFBRLL BFFFBFBLLL BBFBBFBRLL FFBFFBBLLR BBFFFFBLRL BBFBBBFLLR BFBBFFBRLR BFFFFBFLLL BBFFBBFLLR BBFBFFFLLL FBBBFFFLLL BFBBFBBRRR FFBBBBFRRR BBFBBFBRLR BFBBFFFLLL FFBFFFFLLR FBFBFFBLLR FBBBFFFLLR BFBBBBFLRR FBBFBFFLRR FBFBBFBRRL BFFBFFFLLL FBBFBBFRRR FBFFBBBRLL FBFBBBBRRL FFFBBBFRRR FBFBFFBRRL FFBBFBFLLR BFBFBBBLLL FFBFFBFLRR BFBFBBFRRR FBBBBBBLLR BFFBFBFRRR FBFFFBFRRR BBFFFBFLLL FBBFFBBRRR BFBFBFBLLL BBFFBBBLRR FFBFFFFRRL FFBFBBFLLR FFFBBBFRLR FFFBBFBLLL FBFBBFFLLR FBFBFBFRRR BFBBFFFRRR BFBFFBBRRR FBFBBFFRLR FFBFBBFRLR BFFBBFFRRR BFBFBBFLLL FFFBBFBRRR BFFBBFFRLL FFBFFFFLLL FFBBBFFRLL BBFBBFBRRL BBFBFFBLRR FFBFFBBRRL FBBFBBFRRL BBFFFFBLLL BFBBFFBRLL FFBFBFFRLL BFBBFFFLLR FBBFFBBRLR BFBFFBFLRL BFBBFBBRLL FFBBBFFRRR FBFBBFFLRL BFBBFBFRLR FFBBFFBRRL FBFFBBFLLR FBFBBBFLLR BFFFBBFRRL FFFBBBBRRR BFFFBBBRRR FBBFBFFRRL BBFFFFBRRL BBFFFBBLLR BFBBFBFRRR BFFFFBBRRL FBBFBBFLRL FBBFBBBRLR FBFBFFFLRL BFFBFBFRRL FBFBBBFLRL BFBBBBBLRL FFBFFFBRLL BFFBBFBLRL FBFBFBFRLR BFFBBFFLLL BFBBBBBLLL FFBFBBFLRR BBFBFBFRRR FFFBBFFRRR BFFFBFFRRL BBFBFFFRLR BBFBFFFLLR BFFFFFFLRR FBBFBBFRLR FFBBBFFLRL FBFBFFFRLR FFBFBFFLLR BFBFFBBLRR BFFBBBFRLL FBBFFBBLRL BFBBFFBLLR FBFFBFFRRR BFFBBBFRLR BFBFBBBLLR BFFFFBBLLR BFFBFBFLLL BFBBFFFLRR BFFFFFFRLR BBFFBFFLRL BFBFBFFLLR BBFFFFFLRR FFBFBBFLRL FBFBFFBRRR FFBBBBFRLR BBFBBBFLLL BFFFFBBRLL FBFBBBFRRR BFFBFBFRLR FFFBBFFLLR FBBFBFFLLL FFFBFBBRRL BFBBBBFLRL FFBFFBFRLR FBFFBFBRLL FBBBFBFLRR BBFFBBFRLR FBBBBBFLRR FBFFFFBRLL BFFBFFFLRL BFBFFFFLLL BBFFBFBRLR BFBBBFBLLR FBBFFBBRLL FBFBFBFRLL BBFBFBBLRL BFFBFBBLRL FFBBBFBLRL FFBBFBBLLR BFFBFBFLRR FBBBFBFRRL BFFBBBFLRL BFBBFBBLLR BFBFFFBLRR FBFFBBBLRL FBFFBFFLLL BBFFBFFRRR BFFBFBBRLL BFFFBFFRRR BFFBBBBLRL FBBFFBFRLR FBFFBFFRRL FBFFFBBRRR BBFFFFBLRR FBBBFFFLRL FFBBBBFLRL BFFFBFFLLL BFBBBFFRLR FFBFBBFRRL FBFBBBFLRR FFFBBBFLRR BFFFBFBRLR FBBBFBBLRR FFBBBFFLLL FFFBFBFRLR FBBFFFBRLL FBBFBBBRRR BFBFFFFRRR BFBBBFBLRL BBFFFBBLRR BFBFFBBLLR BFBBFBFLLR BBFFBBBRRL FBBFFFFLLL BBFBFFBLLR BFBBBBBLLR FFBFFBBRLR FFBBBFBRLR FBFBBBBLRR FBBFBFBLRR BBFFBBFRRL BBFFBFFRLL FBBBFFBLRR BFFFBFBRRR BFFBFFFLRR FFBBFBBRRL FBFBBBBRRR BBFBBFFLLL FBFFBBBLLL FBBFFFBLRR BFBBFFBLLL FBFFFFBLLL BFBFBBBLRR BFFFFFBLLR BFFBBFBLLR FBFFBFFLRR FBBFBBBLLR FFBBBBBRLL BFFFBBFLLR FFBFBBBLRL FBFBBBFRRL BFFFFBFLRL FBBFFBFRRL FFFBBFBRRL FFBBBBBRRL BBFFFBFLRL FBBFFFFLRR BFBBBBFRLL BFFBFFBRRR FFBBFFFLLL BFFBBBBRLR BFBBFFFLRL BFBFFBBLRL BBFFFBFRLR FBFBFBFLLR BBFFFBBRLR FBBBFFBLLL FBBBFFFRRL BFFFFFFRLL FFBFBFFRRR BFFFBFBRLL FBBBFFFRLR BFBBBFFLLL FBBFBFBLLL FFBBFFFLLR BFFFBBFRLR BBFFFBFRLL FBBBBBBLRL BFBFBFBRLL FBBBBBFRRL BBFBFFFLRL BFBBBBFRRR BFBFFFBLRL FFBFBFBRRL BFBFBFBRRR FFBFFFFRLL BBFBBFFLLR FFBFBBBLLR BBFBBBFLRL FBFBBBBRLL FFBBBBFLRR FFBFFBBLRL BBFFBBBRLR BFBBFBFLLL FBFBFFBLRL BFFFFFBLLL FBFFBFBRLR FBBBBFBLLL FBBFFBFLRL BFFFBBBLLL FBBFBFFLRL FFFBBFFLLL BFBFBFFRRL BFFFFFBRLL BFFBFBFLRL BFFBBFBRRL BFBBFFBRRL FFFBBBBLRL FFBFBBBRRR FBFBBFBRRR FFBBBBFLLL BBFFBFBRLL FBFFBBFRLL FBFBFFFLLR BFFFFBFRRR FFBBBFBLLL FBBBFFBLRL BFFFBBBLRR FFFBFBFRRR FBFFFBBRLR FBFBFFFLRR FBBBFBBLRL FBBBFBBRRR BBFBFBBLRR BFFBBBFLRR BFFFFFFLLR BBFBFBFRLL BFFBFBBLLL FFBBBBFLLR BFFFFBBLRR FBFBFFFRLL BFBFFFBRRL BBFBFBBLLR FFFBFBBLLR FBFFBBBRRR FBBFBFFLLR FBFBFBBRLL BFFBBBBRRR BFFBFFFLLR BFBFBFBRRL BFBBBBFLLR FBBFBFBLLR BFFFFFBRLR FBFFFBBLLL BBFFFFFLLL FFBBBBBLRR FFBBFBBLRL BBFFFFFRLL FBFBBFFRRL FFBFBBBLLL BFFFBBBRLR FBBBFBFRLR FBBFFFFLRL FFBBFFBRRR FBFBFBFLRR BFBFBBBRLL BFBFBFFLLL FBFFBBBLLR BFFFBFBLRL FBBFFFFRRR FBBBBBFLLR BFFFFBBLLL FBBFBFBLRL BFFFBBFRRR BBFFBFBRRR BBFFBFBRRL FFFBBBBRLL BBFFBBBLRL BFBBFBBRLR BBFBBFBLLR BFBBFBFLRR FBFFFFBRRL BFFBFBBLRR BBFFBFBLLL FBBBFBBLLR FBFBBFBLLL BBFBFBFRLR BFFBBBBLLL BFFBFFBRLL BBFBBFBLRR FBFFBBFLRR BBFFBFFRLR BFFFBFFRLR FBFBBFFRLL BFFBBBFRRR FBBBFBFLLL BBFBBBFLRR FBBFFBFLLL BBFBBFBLRL FBFFFBBLRL FBFBBFBRLL BFBBBBFRRL BFFFBFFRLL BFBFBBBRLR FFBFFFFLRL FFBFFFBRRL FBFFBBFRRR BBFFFFBRLR BFFFBFBLRR BBFFBBFLRL FFBBFFFRRL FBFBFBBRLR FBBFBFFRLL FBBBFFBRLL FBBFBBBLLL FBBFFBBRRL BFBFBBFLLR FFBBFFBLRR FFBBBBBLLL BBFFFBFLLR FBFBBBBRLR BFBFBFFLRL FFBBBBBRRR BFBFFBFRLR FBBBBFBRLL BFBBBBBRLL BFBBBBBRLR FBBBBFFLLL FBBFFFBLLL BBFBFBFLLL BFFFFFBLRL FBBFBFBRLL BBFBFBBRLR BFFBFBBLLR FFBBFBFLRL FBFBBBFRLR FBBBFFBRLR FBFFFBFLRR BFBFBFFLRR BFFFFFBRRR BFFBBFBRLL FBFBFBFRRL BBFBBFFRRR FBBFBBBLRR FBFFBBBRLR BBFBFBBLLL FFBFBBFRRR FBFBBFBLLR BFBFBFFRRR BBFBBFBRRR FFBFBBBRLR FBFBFBBRRL BFBFFFBLLL FBFBFFBRLL FBFFFBFRLR FBFFFBBLRR FBBFFFFRLR BFBBFBFRLL FBFBFBBLRR FFBBBFBRRR FBBFFFFRRL FBFBBFFLRR FBBBFFBRRL FBFFFBFLLR FFBFBFFRLR FBBFFBBLLL FFFBBFFRLR BFFFFFFLLL FFFBBBBLLR FFBFBFFRRL BBFBBFFRLL FFFBBFFRLL BBFFFBFRRL FFBBFFBLLL FBFFBBFRRL BFBBBFBRLR BFBFFBBRLR FBFBFFFRRR BFBBBFFLLR FBFBFFFRRL BFFBBFFLLR FBFBBBBLLR FFBBFFBRLR FBFFFFFLLL BBFBFBFRRL FBBBBFFLRL BFBBBFBRRR BFFBBFFLRL BFFBBFFRRL BBFBFBFLRL FBBFFFBRRL BFFFBFBRRL FBFFFFBLLR FFBBFBFRRL BFFBBBBRLL BFBFFFFLLR FFBBFFFRLR BFBFFBBLLL BFFBBFBRRR BFFFBBBRLL FFFBBFBLRL FFBFBFBLRR FFFBBFFRRL FFBBBBBLRL BFBBBFFLRR FBBBBBFLRL FBBBFFFLRR BFFBBFBRLR BBFFFBBLLL FBBBBBBLRR FBFBFFBRLR FFBBBBFRLL""" split_input = raw_input.split("\n") |
Strategy
They dropped a hint in the title of the challenge: Binary Boarding.
They dropped a hint by saying the airlines seats people using binary space partitioning instead of zones.
They dropped a hint when they said that the row numbers range from 0 to 127, and that a seven-character sequence determined your row. Only two characters could be used in that sequence, F and B.
(Additional hint for those of you who didn’t study binary numbers: The numbers 0 through 127 can be represented using seven bits.)
They dropped a hint when they said that the seat numbers (which they called column numbers) range from 0 to 7, and that a three-character sequence determined your seat. Only two characters could be used in that sequence, L and R.
(Additional hint for those of you who didn’t study binary numbers: The numbers 0 through 7 can be represented using three bits.)
The “FB” and “LR” sequences are just binary numbers in disguise.
Solving this challenge involves:
- Converting the “FB” and “LR” strings into binary strings.
- Converting those binary strings into decimal numbers.
- Doing the math on those numbers to get the seat IDs.
Converting the “FB” and “LR” strings into binary strings and converting those binary strings into decimal numbers
For each “FB” string, I wanted to convert the F
s to 0
s and B
s to 1
s. In order to do this, I used Python’s string.maketrans()
method to build a character translation table and its string.translate()
method to make the translation using that table.
The result was this function:
1 2 3 |
def convert_FB_to_01(string): translation_table = string.maketrans("FB", "01") return string.translate(translation_table) |
The first line in the function uses string.maketrans()
to define a translation table. string.maketrans()
takes two arguments:
- The characters to be translated.
- The corresponding resulting characters.
In this case, I only want F
to be translated into 0
and B
to be translated into 1
. All other characters translated using this table will remain unchanged.
The second line does the actual translating, using the translation table as its guide.
With the function defined, I could then use it to create a list of all the rows, expressed as binary strings:
1 |
binary_rows = [convert_FB_to_01(line[:7]) for line in split_input] |
This line of code creates a new list, binary_rows
, by taking the first seven characters of each line of input data — the “FB” string — and converting it to binary.
Here’s a sample of the result:
1 2 |
['1100001', '1011110', '0111010', '1011101', '0110010', '0010010', '0101111', '1001000', '1001000', '1011010', ...] |
The next step was to convert binary_rows
into a list of its numeric equivalents:
1 |
decimal_rows = [int(binary_row, 2) for binary_row in binary_rows] |
This line of code, creates a new list, decimal_rows
, by converting each binary string into its decimal numeric equivalent. It does this by using the int()
function to convert strings to integers, and the extra argument specifies that value represented in the string is in base 2, a.k.a. binary.
Here’s a sample of the result:
1 2 |
[97, 94, 58, 93, 50, 18, 47, 72, 72, 90, ... |
It was time to do the same thing with the “LR” strings. This was pretty much the same operation as with the “FB” strings.
First, an LR-to-01 converter:
1 2 3 |
def convert_LR_to_01(string): translation_table = string.maketrans("LR", "01") return string.translate(translation_table) |
Then, a list comprehension to use that converter:
1 |
binary_columns = [convert_LR_to_01(line[-3:]) for line in split_input] |
This line of code creates a new list, binary_columns
, by taking the last three characters of each line of input data — the “LR” string — and converting it to binary.
Finally, convert these numbers into decimal:
1 |
decimal_columns = [int(binary_column, 2) for binary_column in binary_columns] |
I now had two lists that I could use to do the math:
decimal_rows
: The “FB” sequences, converted into decimal numbers.decimal_columns
: The “LR” sequences, converted into decimal numbers.
Doing the math to get the seat IDs
As stated in the problem definition, the ID for any given seat is (its row number * 8) + (its seat number). I needed to build a list of seat IDs using decimal_rows
and decimal_columns
.
Here’s the code I used to do it:
1 2 |
decimal_rows_and_columns = zip(decimal_rows, decimal_columns) seat_ids = [item[0] * 8 + item[1] for item in decimal_rows_and_columns] |
The first line uses zip()
to take two lists to make a single list filled with tuples. Each tuple has an item from the first list and a corresponding item from the second list. Here’s an example of zip()
in action:
1 2 |
>>> list(zip(['a', 'b', 'c'], [1, 2, 3])) [('a', 1), ('b', 2), ('c', 3)] |
The second line uses the newly-created decimal_rows_and_columns
as a basis for creating a new list of seat IDs.
Once the seat_ids
list was created, it was a matter of using the max()
function to get the highest ID value, which was the solution for part one. In my case, the value was 883.
The Day 5 challenge, part two
The challenge
Here’s the text of part two:
Ding! The “fasten seat belt” signs have turned on. Time to find your seat.
It’s a completely full flight, so your seat should be the only missing boarding pass in your list. However, there’s a catch: some of the seats at the very front and back of the plane don’t exist on this aircraft, so they’ll be missing from your list as well.
Your seat wasn’t at the very front or back, though; the seats with IDs +1 and -1 from yours will be in your list.
What is the ID of your seat?
Strategy
It’s a full flight, so my seat should be the only one missing from the list. I could find this seat by doing the following:
- Sorting the seats in ascending order.
- Iterating through the seats, while keeping an eye out for a “gap”. That gap is my seat.
Solution
Here’s the code I used to solve part two:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
sorted_seat_ids = sorted(seat_ids) last_seat_ids_index = len(sorted_seat_ids) - 1 current_index = 0 my_seat_id = None while current_index < last_seat_ids_index - 1: if sorted_seat_ids[current_index + 1] - sorted_seat_ids[current_index] == 2: my_seat_id = sorted_seat_ids[current_index] + 1 break current_index += 1 if my_seat_id: print(f"My seat is {my_seat_id}.") else: print("Better check that algorithm!") |
It creates a list of sorted seat IDs, which it then loops through. While looping through it, it checks to see if the ID of the seat immediately after the current one is 2 higher than the current ID. If it is, we’ve found the gap, and the ID of my seat is the ID of the current seat plus one.
In my case, the seat ID was 532. I entered that value and solved part two.
One reply on “My solution to Advent of Code 2020’s Day 5 challenge, in Python”
seats = list(seat_ids)
for seat in seats :
if (seat+2 in seats) and not(seat+1 in seats):
print(seat+1)