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

[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