Shashank Sabniveesu

Advent of code 2020 - Day 5 (Part 1)

Day - 5 of the series surprised me big as I got the program to execute with absolutely no errors right on the first attempt!

Attempt 1: Time Complexity O(n)

Continuing the tradition of modularized programs, here’s my __main__.py used to solve this challenge:

""" Program to determine the highest seat ID from given boarding passes

    Read every line and determine seat ID

    If current seat ID is higher than the existing "highest seat ID", save the current seat ID into "highest seat ID"
"""
from processors import seat_id


highest_seat_id = -1

with open('input-5.txt', 'r') as lines:
    for line in lines:
        highest_seat_id = max(highest_seat_id, seat_id(line))

print(highest_seat_id)

Here’re the processors.py module used:

""" Module to process boarding pass strings specified in "binary space partitioning" notation

    For each character, if 'B', multiply 1 by 2^n (from n=6 to n=0) and sum together
    When n reaches 0, multiply the sum by 8

    Then, for each character, if 'R', multiply 1 by 2^n (from n=2 to n=0) and sum together

    Return the final sum as seat_id
"""


def seat_id(boarding_pass_string):
    """    Processes the boarding pass string from left to right

    Obtains part identifiers.
    Multiplies and sums them to get full seat_id and return
    """

    return partial_id(boarding_pass_string, 0, 7)*8 + partial_id(boarding_pass_string, 7, 10)


def partial_id(boarding_pass_string, startIndex, endIndex):
    """    Processes the boarding pass string read by breaking as per provided indices and performing multiplications as if in a bitmap

    Breaks the string into row and column strings to determine part identifiers.
    """

    string = boarding_pass_string[startIndex:endIndex]
    exponent = endIndex - startIndex - 1

    part_id = 0
    for char in string:
        if char == 'B' or char == 'R':
            part_id += 2**exponent
        exponent -= 1

    return part_id

Here’s the time taken in 3 consecutive runs:

shashank@shashank-HP-ENVY-Notebook:~/Projects/personal/programming-challenges/advent-of-code/2020/day-5$ time python3 part-1-attempt-1
855

real    0m0.033s
user    0m0.029s
sys     0m0.005s
shashank@shashank-HP-ENVY-Notebook:~/Projects/personal/programming-challenges/advent-of-code/2020/day-5$ time python3 part-1-attempt-1
855

real    0m0.029s
user    0m0.029s
sys     0m0.000s
shashank@shashank-HP-ENVY-Notebook:~/Projects/personal/programming-challenges/advent-of-code/2020/day-5$ time python3 part-1-attempt-1
855

real    0m0.031s
user    0m0.027s
sys     0m0.004s
shashank@shashank-HP-ENVY-Notebook:~/Projects/personal/programming-challenges/advent-of-code/2020/day-5$ 

If you are curious about the choices made here or have suggestions to improve this even further, please Tweet your reply or Open an Issue referencing the title.

Lessons Learned

Not one but many!

1. When you see binary in the problem description, not necessarily it is always a Binary Search Tree problem. Sometimes it is just an encoding problem that can be approached with bitmaps etc.
2. While breaking up your Python logic into multiple modules, name the driver program __main__.py. Then invoking the program is just calling the containing folder with Python executable
3. Seeing pydoc in modules is achieved as pydoc3 folder_name.module_name i.e separated by a dot (.)