DEV Community

Cover image for Advent of Code 2020 Solution Megathread - Day 5: Binary Boarding
Ryan Palo
Ryan Palo

Posted on • Edited on

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

#adventofcode #challenge

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
Enter fullscreen mode Exit fullscreen mode

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!

Latest comments (28)

Collapse
 
justinh11235 profile image
Justin Hinckley •

My Haskell Solution (I just started learning Haskell so fair warning):

import Data.Bool (bool)

toDecimalList :: [String] -> [Int]
toDecimalList = map (foldl1 ((+) . (2*)) . map (bool 0 1 . (`elem` "BR")))

ans1 :: [String] -> Int
ans1 = maximum . toDecimalList

findMissing :: [Int] -> Int
findMissing nums = (minimum nums + maximum nums) * (length nums + 1) `div` 2 - sum nums

ans2 :: [String] -> Int
ans2 = findMissing . toDecimalList

main :: IO ()
main = do
    contents <- readFile "adventofcode5input"
    print $ ans1 $ lines contents -- Part 1
    print $ ans2 $ lines contents -- Part 2
Enter fullscreen mode Exit fullscreen mode
Collapse
 
erikbackman profile image
Erik Bäckman • • Edited

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"
Enter fullscreen mode Exit fullscreen mode
Collapse
 
harrygibson profile image
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}")
Enter fullscreen mode Exit fullscreen mode
Collapse
 
tripledonkey profile image
tripledonkey •

Hi, new to this site, and AOC. I did the last 4 in Python, but I thought I would try shell for this one (i'm not great at shell so this may be not the best):

I solved part 1 with this shell oneliner...

echo ibase=2 $(sed -e 's/F/0/g' -e 's/B/1/g' -e 's/L/0/g' -e 's/R/1/g' < passes) | sed 's/ /;/g' | bc | sort -n | tail -n1
Enter fullscreen mode Exit fullscreen mode

for part two, I created the list of passport ids with:

echo ibase=2 $(sed -e 's/F/0/g' -e 's/B/1/g' -e 's/L/0/g' -e 's/R/1/g' < passes) | sed 's/ /;/g' | bc > ids
Enter fullscreen mode Exit fullscreen mode

then threw this at the ids file:

#!/bin/bash
i=0; 
for seat in $(cat ids)
do
    ((i=i+1))
    ((prev=i-1))
    ((next=i+1)) 
    if grep --silent ^${prev}$ ids
    then
        if grep --silent ^${next}$ ids
        then
            if ! grep --silent ^${i}$ ids
            then
                echo "${i}"
            fi
        fi
    fi
done
Enter fullscreen mode Exit fullscreen mode
Collapse
 
thibpat profile image
Thibaut Patel •

My JavaScript walkthrough:

Collapse
 
derekmwright profile image
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]
Enter fullscreen mode Exit fullscreen mode
Collapse
 
anvsh profile image
Anvesh Saxena •

Part 2 of the puzzle was really puzzling, though I got the answer using set theory

import sys
import math #for ceil and floor functions

def row_search(seat):
    upper = 127
    lower = 0
    for character in seat[0:7]:
        if character == "F":
            upper = math.floor((lower + upper)/2)
        elif character == "B":
            lower = math.ceil((lower+upper)/2)
        #print("Character {} Lower {} Upper {}".format(character, lower, upper))
    return upper

def column_search(seat):
    right = 7
    left = 0
    #print(seat[-3:])
    for character in seat[-3:]:
        if character == "R":
            left = math.ceil((right+left)/2)
        elif character == "L":
            right = math.floor((right+left)/2)
        #print("Character {} left {} right {}".format(character, left, right))
    return right

highest = 0
seat_list = []
full_seats = range(0,1023)
for boarding_pass in sys.stdin:
        #print(row_search(boarding_pass.rstrip("\n")))
        #print(column_search(boarding_pass.rstrip("\n")))
        #print(row_search(boarding_pass.rstrip("\n")) * 8 + column_search(boarding_pass.rstrip("\n")))
        seat_list.append(row_search(boarding_pass.rstrip("\n")) * 8 + column_search(boarding_pass.rstrip("\n")))
        if highest < row_search(boarding_pass.rstrip("\n")) * 8 + column_search(boarding_pass.rstrip("\n")):
            highest = row_search(boarding_pass.rstrip("\n")) * 8 + column_search(boarding_pass.rstrip("\n"))

print(highest)
print(len(seat_list))
print(set(full_seats) - set(seat_list))
Enter fullscreen mode Exit fullscreen mode
Collapse
 
readyready15728 profile image
readyready15728 • • Edited

Ruby, part 2:

require 'set'

codes = File.readlines('05.txt')
seat_ids = []

codes.each do |code|
  row_code = code[0..6]
  column_code = code[7..9]
  row = 0
  column = 0

  row_code.each_char.each_with_index do |c, i|
    if c == 'B'
      row += 2**(6 - i)
    end
  end

  column_code.each_char.each_with_index do |c, i|
    if c == 'R'
      column += 2**(2 - i)
    end
  end

  seat_ids.push 8 * row + column
end

all_possible_fields = Set.new(seat_ids.min..seat_ids.max)
puts (all_possible_fields - Set.new(seat_ids)).to_a[0]
Enter fullscreen mode Exit fullscreen mode
Collapse
 
sleeplessbyte profile image
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
Enter fullscreen mode Exit fullscreen mode
Collapse
 
willsmart profile image
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;
}
Enter fullscreen mode Exit fullscreen mode
View full discussion (28 comments)