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

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 

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

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 

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

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

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 } 

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