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

   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.

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))))}")

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")
}

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

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
}

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"

# 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]

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))

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}")

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

-- 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 is = let (rs, cs) = splitAt 7 is
              (r,_) = foldl' half (0,127) rs
              (c,_) = foldl' half (0,7) cs
          in (r*8+c) 

main = do xs <- readFile "day5_input" <&> lines
          let seats = map seat xs
          print (maximum seats)
          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

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

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

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

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