2020 Day 5

Posted on Dec 5, 2020

Part 1

Problem

From a list of seat specifiers, find the seat with the highest ID.

General solution

Read in each line of the file and covert it to an array. For each seat (one seat per line, so one item in the array), split at the seventh character to get the row and column specifiers. Break these down using binary space partitioning (similar to binary searching, as the input is ordered but in this case we do not know what the target number is) to find the row and column number, then calculate the seat ID.

Solution: PHP

A function for binary space partitioning was needed, which is used in both parts.

function binary_space_partition(string $pattern): ?int
{
    $lower_bound = 0;
    $upper_bound = (2 ** strlen($pattern)) - 1;

    for ($c = 0; $c < strlen($pattern); $c++)
    {
        $char = $pattern[$c];
        $mid_point = intval(floor(($lower_bound + $upper_bound) / 2));

        if ($char === 'L')
        {
            $upper_bound = $mid_point;
        }
        elseif ($char === 'R')
        {
            $lower_bound = $mid_point + 1;
        }
    }

    return ($lower_bound === $upper_bound) ? $lower_bound : null;
}

For reading the file and converting it to an array, PHP offers the helpful functions:

file_get_contents(): Read entire file into a string.

preg_split('/\R/', $str): Split string into an array using the \R code, which matches any line break (\r, \n and \r\n).

<?php

declare(strict_types=1);
error_reporting(E_ALL);

$seats_data = file_get_contents('input');
$seats = preg_split('/\R/', $seats_data);
$highest_seat_id = 0;

foreach ($seats as $seat)
{
    if ($seat)
    {
        $row_str = substr($seat, 0, 7);
        $column_str = substr($seat, 7);

        // Rewrite row data to use left/right
        $row_str = str_replace('F', 'L', $row_str);
        $row_str = str_replace('B', 'R', $row_str);

        $row = binary_space_partition($row_str);
        $column = binary_space_partition($column_str);

        $seat_id = ($row * 8) + $column;
        $highest_seat_id = max($highest_seat_id, $seat_id);
    }
}

print("Highest seat ID: $highest_seat_id\n");

Part 2

Problem

Find the ID of the only unoccupied seat.

General solution

Create an array of all possible seats (columns x rows) and mark them as occupied, based on the boarding pass entries.

There are more seats than there are boarding passes, so we cannot just find the first unoccupied seat in the array. However, we know that the seats either side of our seat must be occupied (and therefore must also exist), so we can ignore the first and last columns of seats as by definition they do not have a seat on either side.

<?php

declare(strict_types=1);
error_reporting(E_ALL);

const ROW_COUNT = 128;
const COLUMN_COUNT = 8;

$passes_data = file_get_contents('input');
$passes = preg_split('/\R/', $passes_data);
$seats = [];

// Populate seats
for ($r = 0; $r < ROW_COUNT; $r++)
{
    for ($c = 0; $c < COLUMN_COUNT; $c++)
    {
        $seats[$r][$c] = false;
    }
}

// Occupy seats based on boarding passes
foreach ($passes as $pass)
{
    if ($pass)
    {
        $row_str = substr($pass, 0, 7);
        $column_str = substr($pass, 7);

        // Rewrite row data to use left/right
        $row_str = str_replace('F', 'L', $row_str);
        $row_str = str_replace('B', 'R', $row_str);

        $row = binary_space_partition($row_str);
        $column = binary_space_partition($column_str);

        $seats[$row][$column] = true;
    }
}

// Find the one unoccupied seats
for ($r = 0; $r < ROW_COUNT; $r++)
{
    // Only look between columns 1 and COUNT - 1, because the seats
    // either side of our seat must exist and be occupied
    for ($c = 1; $c < COLUMN_COUNT - 1; $c++)
    {
        if ($seats[$r][$c] === false && $seats[$r][$c - 1] && $seats[$r][$c + 1])
        {
            $seat_id = ($r * 8) + $c;
            print("My seat ID: $seat_id\n");
            exit;
        }
    }
}