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

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.