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!

The Leaderboards

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
Haskell	1

Merry Coding!

Comments

[Stephen Gerkin]

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)
        .readLines()
        .map { line -> line
            .map { ch -> if (ch in "BR") "1" else "0" }
            .joinToString("")
            .toInt(2) }

    val min = seats.minOrNull() 
        ?: throw Exception("Min not found")
    val max = seats.maxOrNull()
        ?: throw Exception("Max not found")

    val yourSeat = IntRange(min, max).firstOrNull { it !in seats } 
        ?: throw Exception("Seat not found")

    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.
   AUTHOR. ANNA KOSIERADZKA.

   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.

   002-READ.
        READ INPUTFILE
            AT END MOVE 1 TO FILE-STATUS
            NOT AT END PERFORM 003-PROCESS-RECORD
        END-READ.

   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 
             ADD 1 TO SEAT-ID
          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::*;

// --- file read

fn read_file(filename: &str) -> std::io::Result<String> {
    let mut file = File::open(filename)?;
    let mut contents = String::new();
    file.read_to_string(&mut contents)?;
    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 input = read_file("./input.txt").unwrap();
    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
    passes = File.readlines('input.txt').map do |line|
      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

    passes = File.readlines('input.txt').map do |line|
      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

[Erik Bäckman]

Haskell:

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]

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
    |> read_boarding_passes()
    |> Enum.max()
  end

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

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

  defp read_boarding_passes(file_path) do
    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]

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]

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;
}