## DEV Community

Ryan Palo

Posted on • Updated on

# Advent of Code 2020 Solution Megathread - Day 5: Binary Boarding

And so closes out the first week. Can you believe we're already 20% of the way through the challenge? How's everybody doing staying on top of it? I was in awe of some of the solutions I saw yesterday. And I believe we had another couple firsts for new languages. Anyways, to the puzzle:

## The Puzzle

In today’s puzzle, we've lost our boarding pass. But, like any tech-savvy holiday traveler, we're writing a program to use binary partitioning to unravel strings like BFBFFFBLRL into seat ID's. So. Yeah. Good luck!

As always, this is the spot where I’ll plug any leaderboard codes shared from the community.

``````Ryan's Leaderboard: 224198-25048a19
``````

If you want to generate your own leaderboard and signal boost it a little bit, send it to me either in a DEV message or in a comment on one of these posts and I'll add it to the list above.

## Yesterday’s Languages

Updated 03:07PM 12/12/2020 PST.

Language Count
JavaScript 4
Ruby 2
C 2
PHP 2
Rust 2
Python 2
C# 1
Go 1
COBOL 1
TypeScript 1
Elixir 1

Merry Coding!

Stephen Gerkin • Edited

Python in 2 lines

``````seats = [(int("".join(map(lambda x: "1" if x in "BR" else "0", s.rstrip())), 2)) for s in open("day5.txt")]
print(f"Highest: {max(seats)}\tYour seat: {next(filter(lambda x: x not in seats, range(min(seats), max(seats))))}")
``````

And a much more legible Kotlin

``````import java.io.File
import java.lang.Exception

const val filepath = "day5.txt"

fun main() {
val seats = File(filepath)
.map { line -> line
.map { ch -> if (ch in "BR") "1" else "0" }
.joinToString("")
.toInt(2) }

val min = seats.minOrNull()
val max = seats.maxOrNull()

val yourSeat = IntRange(min, max).firstOrNull { it !in seats }

println("Highest seat number: \$max\nYour seat number: \$yourSeat")
}
``````

Stephen Gerkin

I was curious to know if Python would let you execute a lambda immediately by wrapping it with parens and giving it the input, such as `(lambda)(input)` and ... sure enough you can. As such, I present this monstrosity in 1 line:

``````(lambda seats: print(f"Highest: {max(seats)}\nYour seat: {next(filter(lambda x: x not in seats, range(min(seats), max(seats))))}"))([(int("".join(map(lambda x: "1" if x in "BR" else "0", s.rstrip())), 2)) for s in open("day5.txt")])
``````

Anna

COBOL (part 2 on my GitHub)

``````   IDENTIFICATION DIVISION.
PROGRAM-ID. AOC-2020-05-1.

ENVIRONMENT DIVISION.
INPUT-OUTPUT SECTION.
FILE-CONTROL.
SELECT INPUTFILE ASSIGN TO "d5.input"
ORGANIZATION IS LINE SEQUENTIAL.

DATA DIVISION.
FILE SECTION.
FD INPUTFILE.
01 INPUTRECORD PIC X(10).
WORKING-STORAGE SECTION.
01 FILE-STATUS PIC 9 VALUE 0.

LOCAL-STORAGE SECTION.
01 I UNSIGNED-INT VALUE 1.
01 SEAT-ID UNSIGNED-INT VALUE 0.
01 ID-MAX UNSIGNED-INT VALUE 0.

PROCEDURE DIVISION.
001-MAIN.
OPEN INPUT INPUTFILE.
PERFORM 002-READ UNTIL FILE-STATUS = 1.
CLOSE INPUTFILE.
DISPLAY ID-MAX.
STOP RUN.

AT END MOVE 1 TO FILE-STATUS
NOT AT END PERFORM 003-PROCESS-RECORD

003-PROCESS-RECORD.
MOVE 0 TO SEAT-ID.
PERFORM VARYING I FROM 1 BY 1 UNTIL I > 10
COMPUTE SEAT-ID = SEAT-ID * 2
IF INPUTRECORD(I:1) = 'B' OR INPUTRECORD(I:1) = 'R' THEN
END-IF
END-PERFORM.

IF SEAT-ID > ID-MAX THEN
MOVE SEAT-ID TO ID-MAX
END-IF.
``````

Paweł Świątkowski

How do you run your COBOL solutions? I tried it in past AoCs but failed on that.

Anna

I'm using GnuCOBOL on Windows:

``````cobc -xj d05b.cob
``````

Neil Gall

I was hoping for a meaty one for a cold wet Saturday but this was straightforward. The insight was realising that "binary space partitioning" is just binary, swapping 1 and 0 for letters. I almost did it using string replace at first.

``````use std::fs::File;
use std::io::prelude::*;

fn read_file(filename: &str) -> std::io::Result<String> {
let mut file = File::open(filename)?;
let mut contents = String::new();
Ok(contents)
}

// --- model

#[derive(Debug, Eq, PartialEq)]
struct BoardingPass {
row: usize,
column: usize
}

impl BoardingPass {
fn seat_id(&self) -> usize {
self.row * 8 + self.column
}
}

fn decode(s: &str, one: char) -> usize {
s.chars().fold(0, |r, c| (r << 1) | (if c == one { 1 } else { 0 }))
}

impl From<&str> for BoardingPass {
fn from(s: &str) -> BoardingPass {
let row = decode(&s[0..7], 'B');
let column = decode(&s[7..10], 'R');
BoardingPass { row, column }
}
}

// --- problems

fn part1(passes: &Vec<BoardingPass>) -> Option<usize> {
passes.iter().map(|bp| bp.seat_id()).max()
}

fn part2(passes: &Vec<BoardingPass>) -> Option<usize> {
let seat_ids: Vec<usize> = passes.iter().map(|bp| bp.seat_id()).collect();

seat_ids.iter().max().and_then(|max_id| {
(1..=*max_id).find(|id_ref| {
let id = *id_ref;
!seat_ids.contains(&id) && seat_ids.contains(&(id-1)) && seat_ids.contains(&(id+1))
})
})
}

fn main() {
let passes: Vec<BoardingPass> = input.lines().map(|line| line.into()).collect();

println!("part1 {}", part1(&passes).unwrap());
println!("part2 {}", part2(&passes).unwrap());
}

#[cfg(test)]
mod tests {
use super::*;

#[test]
fn test_deocde() {
assert_eq!(decode("BFFFBBF", 'B'), 70);
assert_eq!(decode("RRR", 'R'), 7);
assert_eq!(decode("FFFBBBF", 'B'), 14);
assert_eq!(decode("BBFFBBF", 'B'), 102);
}

#[test]
fn test_to_baording_pass() {
assert_eq!(BoardingPass::from("BFFFBBFRRR"), BoardingPass { row: 70, column: 7 });
assert_eq!(BoardingPass::from("FFFBBBFRRR"), BoardingPass { row: 14, column: 7 });
assert_eq!(BoardingPass::from("BBFFBBFRLL"), BoardingPass { row: 102, column: 4 });
}
}
``````

Ryan Palo

Oh man! Swapping letters for numbers is an amazing insight. I'm half-tempted to go back and rewrite mine using even more sneaky binary tricks! I stopped at bit shifting.

tripledonkey

Yep, I noticed this too, I was like "hang on a sec" 🍒

Derk-Jan Karrenbeld

Today I have two implementations in Ruby for ya.

``````require 'benchmark'

class BoardingPass
def self.from_binary(binary_position)
rows = binary_position[0...7].tr("FB", "01")
columns = binary_position[7..].tr("LR", "01")

BoardingPass.new((rows + columns).to_i(2))
end

def initialize(seat)
self.seat = seat
end

def to_i
self.seat
end

private

attr_accessor :seat
end

def find_missing_id(passes)
seat_ids = passes.map(&:to_i).sort
(seat_ids.first..seat_ids.last).to_a.each_with_index do |expected_id, i|
return expected_id if seat_ids[i] != expected_id
end
end

Benchmark.bmbm do |b|
b.report(:to_i_base_2) do
BoardingPass.from_binary(line.chomp)
end

puts find_missing_id(passes)
end

b.report(:binsearch) do

def binary_position_search(l:, r:, position:)
position
.chars
.inject([0, 2 ** position.length - 1]) do |(low, high), half|
mid = low + ((high - low) / 2.0)

if half == l
[low, mid.floor]
elsif half == r
[mid.ceil, high]
else
raise "Position character #{half} not expected. Expected #{l} or #{r}."
end
end
.first
end

binary_position = line.chomp

row = binary_position_search(l: 'F', r: 'B', position: binary_position[0...7])
column = binary_position_search(l: 'L', r: 'R', position: binary_position[7..])

BoardingPass.new(row * 8 + column)
end

puts find_missing_id(passes)
end
end
``````

``````module Main where

import Data.List (sort)
import Data.Maybe (listToMaybe)
import Data.Bool (bool)
import Control.Arrow ((&&&))

decode :: String -> Int
decode = foldl (\n a -> (bool 0 1 . (`elem` "BR") \$ a) + 2*n) 0

parseInput :: String -> [Int]
parseInput = fmap decode . lines

distanceOf :: (Ord a, Num a) => a -> [a] -> [(a, a)]
distanceOf n l = [ (x, y) | (x,y) <- (zip <*> tail) . sort \$ l, abs (x - y) == n ]

solveP1 :: [Int] -> Int
solveP1 = maximum

solveP2 :: [Int] -> Maybe Int
solveP2 = fmap (succ . fst) . listToMaybe . distanceOf 2

main :: IO ()
main = print . (solveP1 &&& solveP2) . parseInput =<< readFile "./day5inp.txt"
``````

Harry Gibson

My solution in python. Sometimes the challenge is just clicking what the description is actually saying, once it's obvious that these are just binary numbers then it was quite an easy one.

``````all_seats = [int(
(l.replace('B','1').replace('F','0')
.replace('R','1').replace('L','0'))
,2) for l in open('input.txt')]

print(f"Part 1: Highest seat is {max(all_seats)}")

your_seat = [s for s in range(min(all_seats), max(all_seats))
if s not in all_seats][0]
print(f"Part 2: Your seat is {your_seat}")
``````

Patryk Woziński • Edited

Today I had a weird day. I did an advent task in my car waiting for gf Good for me that she was so late packing our cat for the trip. :topkek:

I saw many people did the task in a different way - I've used recurrence and pattern matching and it just works.

``````defmodule AdventOfCode.Day5 do
def part1(file_path) do
file_path
|> Enum.max()
end

def part2(file_path) do
reserved =
file_path
|> Enum.to_list()

0..Enum.max(reserved)
|> Enum.to_list()
|> Enum.filter(&reserved?(&1, reserved))
|> List.first()
end

file_path
|> File.stream!()
|> Stream.map(&String.replace(&1, "\n", ""))
|> Stream.map(fn bp ->
bp
|> String.graphemes()
|> seat_id({0, 127}, {0, 7})
end)
end

defp seat_id(["F" | rest], {row_start, row_end}, column) do
row_end = get_between(row_start, row_end) |> floor()
seat_id(rest, {row_start, row_end}, column)
end

defp seat_id(["B" | rest], {row_start, row_end}, column) do
row_start = get_between(row_start, row_end) |> round()
seat_id(rest, {row_start, row_end}, column)
end

defp seat_id(["L" | rest], row, {column_start, column_end}) do
column_end = get_between(column_start, column_end) |> floor()
seat_id(rest, row, {column_start, column_end})
end

defp seat_id(["R" | rest], row, {column_start, column_end}) do
column_start = get_between(column_start, column_end) |> round()
seat_id(rest, row, {column_start, column_end})
end

defp seat_id([], {row, _}, {column, _}) do
{row, column}

row * 8 + column
end

defp get_between(lower, higher) do
(higher - lower) / 2 + lower
end

defp reserved?(current, reserved) do
(current - 1) in reserved and (current + 1) in reserved and current not in reserved
end
end
``````

Benedict Gaster • Edited

After discussing with my partner I thought I should do the binary version too, so here is a slightly modified version, but rather than using Haskell binary stuff, just used fold to convert the binary string to an int.

``````-- we need to accumulate, rather than simply fold
foldl' f z []     = z
foldl' f z (x:xs) = let z' = z `f` x
in seq z' \$ foldl' f z' xs

-- calculate our half way range
half = (\ranges m ->  if m == 'F' || m == 'L'
then fst ranges
else snd ranges) . ranges
where
ranges (min, max) = let mp = (min + max) `div` 2
in ((min, mp), (mp+1, max))

-- calculate a seat number
seat = toDec . map (\x -> if x == 'F' || x == 'L'
then '0'
else '1')
where
toDec = foldl' (\acc x -> acc * 2 + digitToInt x) 0

main = do xs <- readFile "day5_input" <&> lines
let seats = map seat xs
print (maximum (map seat xs))
print \$ fst \$ head \$ dropWhile snd
\$ dropWhile (not . snd)
\$ zip [0..] (foldr update emptySeats seats)
where
emptySeats = map (const False) [0..1023]
update s = element s .~ True
``````

Paweł Świątkowski

I went down an easy path today, implementing it in a most straightforward way:

``````import std.algorithm, std.stdio, std.string, std.container.rbtree;

void main() {
auto file = File("input");
auto passes = file.byLine().map!(s => cast(char[])s);
auto max_id = 0;
auto ids = redBlackTree!int([]);

foreach(pass; passes) {
auto front = 0;
auto back = 127;
auto left = 0;
auto right = 7;

foreach(x; pass) {
switch(x) {
case('F'):
back = (front + back+1)/2 - 1;
break;
case('B'):
front = (front + back+1)/2;
break;
case('R'):
left = (left+right+1)/2;
break;
case('L'):
right = (left+right+1)/2 - 1;
break;
default:
break;
}
}
assert(front == back);
assert(left == right);
auto seat_id = (front * 8) + left;
ids.insert(seat_id);
if(seat_id > max_id) max_id = seat_id;
}
writeln(max_id);

for(int i=1;i<127;i++) {
for(int j=0;j<8;j++) {
const seat_id = i * 8 + j;
if ((seat_id + 1 in ids) && (seat_id - 1 in ids) && !(seat_id in ids)) writeln(seat_id);
}
}
}
``````

willsmart • Edited

Here's my C implementation. Kind of glad it was a straightforward problem this time. Will do tomorrow's in Python.

``````#include <stdio.h>
#include <string.h>

int getSeatId(const char *seatDesc)
{
int ret = 0;
for (int bi = 9; bi >= 0; bi--, seatDesc++)
ret |= (*seatDesc == 'B' || *seatDesc == 'R') << bi;
return ret;
}

int part1()
{
char seatDesc[100];
int maxId = -1, seatId;
while (scanf("%s", seatDesc) == 1) {
if ((seatId = getSeatId(seatDesc)) > maxId) maxId = seatId;
printf("%s -> %d (%d)\n", seatDesc, seatId, maxId);
}
}

int part2()
{
char seatDesc[100];
char filled[1 << 10];
memset(filled, 0, 1 << 10);

while (scanf("%s", seatDesc) == 1) filled[getSeatId(seatDesc)] = 1;

int seatId = 0;
while (!filled[seatId]) seatId++;
while (filled[seatId]) seatId++;
printf("%d\n", seatId);
}

int main(int argc, const char *argv[])
{
if (argc < 2 || argv[1][0] == '1') part1();
else part2();
return 0;
}
``````

With a bit of bitshifting:

``````package main

import (
"bufio"
"fmt"
"os"
"sort"
"strings"
)

func getNumber(id string) int {
num := 0
l := len(id)
for i := l - 1; i >= 0; i-- {
if id[i] == 'B' || id[i] == 'R' {
num |= 1 << (l - i - 1)
}
}
return num
}

func getId(row, col int) int {
return (row << 3) + col
}

func main() {

ids := make([]int, 0)
for {
var line string
if err != nil {
break
}

line = strings.TrimSpace(line)
ids = append(ids, getId(getNumber(line[:7]), getNumber(line[7:])))
}

sort.Ints(ids)
fmt.Println(ids[len(ids) - 1])

for i := 0; i < len(ids)-1; i++ {
if ids[i+1]-ids[i] == 2 {
fmt.Println(ids[i] + 1)
break
}
}
}
``````

And an alternative solution in PHP :-D

``````<?for(;\$p=fgets(STDIN);\$c++)\$i[]=base_convert(strtr(\$p,'BFRL','1010'),2,10);sort(\$i);echo\$i[--\$c].' ';for(;\$j++<\$c;)if(\$i[\$j+1]-\$i[\$j]>1)echo\$i[\$j]+1;
``````

Ryan Palo

Pretty quick one today! I didn't have much problem, and once I realized that the seat ID was actually the index into a 1-D array of seats, I stopped writing my own custom seatID->index function 😂

Day5.h:

``````#ifndef AOC2020_DAY5_H
#define AOC2020_DAY5_H

/// Day 5: Binary Boarding
///
/// Calculate Seat ID's from a binary division process.

#include <stdlib.h>

/// Calculate the seat ID by parsing a 10-char FFBBFFBLRL seat string
/// to a seat row/column.  The seat ID is not only row * 8 + col, but
/// also the index into a linearized array of seats which is nice.
int seat_ID(const char* seat);

/// Run both parts for the day.
int day5(void);
#endif
``````

Day5.c:

``````#include "Day5.h"

#include <stdio.h>
#include <stdbool.h>

#define ROWS 128
#define COLS 8
#define NUM_ROW_CHARS 7
#define NUM_COL_CHARS 3

int seat_ID(const char* seat) {
int front = 0, left = 0;
int depth = ROWS;
int width = COLS;

for (int i = 0; i < NUM_ROW_CHARS; i++) {
depth >>= 1;
if (seat[i] == 'B') front += depth;
}

for (int i = NUM_ROW_CHARS; i < NUM_ROW_CHARS + NUM_COL_CHARS; i++) {
width >>= 1;
if (seat[i] == 'R') left += width;
}
return front * 8 + left;
}

/// Part 1: Calculate the highest seat ID in the list.
static int part1(void) {
FILE* fp;
fp = fopen("data/day5.txt", "r");
if (fp == NULL) {
printf("Couldn't open file.\n");
exit(EXIT_FAILURE);
}

int max_ID = 0;
char seat[11];

while (fgets(seat, 11, fp)) {
int this_ID = seat_ID(seat);
if (this_ID > max_ID) max_ID = this_ID;
}
fclose(fp);
return max_ID;
}

/// Part 2: Find the only empty seat on the plane.  Note: some seats
/// are missing from the front and back of the grid.
static int part2(void) {
bool seats[ROWS*COLS] = {0};

FILE* fp;
fp = fopen("data/day5.txt", "r");
if (fp == NULL) {
printf("Couldn't open file.\n");
exit(EXIT_FAILURE);
}

// Load all seats in as present.
char seat[11];
while (fgets(seat, 11, fp)) {
seats[seat_ID(seat)] = true;
}
fclose(fp);

// Run through non-present seats.  Once we're into seats on the plane,
// the first empty one is mine!
bool inside_plane = false;
for (int i = 0; i < ROWS*COLS; i++) {
if (!inside_plane && seats[i]) inside_plane = true;
if (inside_plane && !seats[i]) return i;
}

return -1;
}

int day5(void) {
printf("====== Day 5 ======\n");
printf("Part 1: %d\n", part1());
printf("Part 2: %d\n", part2());
return EXIT_SUCCESS;
}
``````

Kai

Hey everyone 👋!

I've created a step-by-step tutorial for solving AoC 2020 day 5:

dev.to/kais_blog/step-by-step-tuto...

I'm using TypeScript and I explain how to use the binary representation of the boarding pass data.

Benjamin Trent

This one was pretty simple.

Rust as always :D

``````fn is_lower(input: &str) -> bool {
&input[0..1] == "F" || &input[0..1] == "L"
}

fn calculate_pos(input: &str, lower: usize, upper: usize) -> usize {
if input.len() == 1 {
if is_lower(input) {
lower
} else {
upper
}
} else {
let (lower, upper) = if is_lower(input) {
(lower, (upper + lower) / 2)
} else {
((upper + lower) / 2 + 1, upper)
};
calculate_pos(&input[1..], lower, upper)
}
}

fn calc_boarding_pass(input: &str) -> usize {
calculate_pos(&input[0..7], 0, 127) * 8 + calculate_pos(&input[input.len() - 3..], 0, 7)
}

#[aoc(day5, part1)]
fn max_boarding_pass(input: &str) -> usize {
input
.lines()
.map(|s| calc_boarding_pass(s))
.max()
.unwrap_or(0)
}

#[aoc(day5, part2)]
fn boarding_passes(input: &str) -> usize {
let mut v: Vec<usize> = input.lines().map(|s| calc_boarding_pass(s)).collect();
v.sort();
for (l, r) in v.iter().zip(v[0]..v[v.len() - 1]) {
if *l != r {
return r;
}
}
0
}
``````

Derek Wright • Edited

Ruby, Late to the party - catching up!

I see lots of complex solutions when binary data packing/unpacking should be relatively compact and optimized. Hopefully this helps give people some ideas!

``````# Read a line and parse it w/ convert
def parse(data)
(convert(data[0..6], 'F', 'B') * 8) +
convert(data[7..9], 'L', 'R')
end

# Converts data into a binary 0/1 string and then gets the dec value
def convert(data, off_char, on_char)
data.scan(/[#{off_char}|#{on_char}]/).map { |c| c == off_char ? 0 : 1 }.join('').to_i(2)
end

# Part One
seats = File.readlines('input.txt').map { |s| parse(s) }.sort
p seats.last

# Part Two
parted_seats = seats.slice_when {|i, j| i+1 != j }.to_a
p (parted_seats.first.last..parted_seats.last.first).to_a[1]
``````