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
}

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

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() {
    reader := bufio.NewReader(os.Stdin)

    ids := make([]int, 0)
    for {
        var line string
        line, err := reader.ReadString('\n')
        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
        }
    }
}

#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

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

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

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

   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.

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

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

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]

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

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

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

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

#!/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

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

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"

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