DEV Community

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

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

Ryan Palo on December 05, 2020

And so closes out the first week. Can you believe we're already 20% of the way through the challenge? How's everybody doing staying on top of it?...
Read full post
Collapse
 
scgrk profile image
Stephen Gerkin • • Edited

Python in 2 lines

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))))}")
Enter fullscreen mode Exit fullscreen mode

And a much more legible Kotlin

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")
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
scgrk profile image
Stephen Gerkin •

I was curious to know if Python would let you execute a lambda immediately by wrapping it with parens and giving it the input, such as (lambda)(input) and ... sure enough you can. As such, I present this monstrosity in 1 line:

(lambda seats: print(f"Highest: {max(seats)}\nYour seat: {next(filter(lambda x: x not in seats, range(min(seats), max(seats))))}"))([(int("".join(map(lambda x: "1" if x in "BR" else "0", s.rstrip())), 2)) for s in open("day5.txt")])
Enter fullscreen mode Exit fullscreen mode
Collapse
 
galoisgirl profile image
Anna •

COBOL (part 2 on my GitHub)

   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.
Enter fullscreen mode Exit fullscreen mode
Collapse
 
katafrakt profile image
Paweł Świątkowski •

How do you run your COBOL solutions? I tried it in past AoCs but failed on that.

Collapse
 
galoisgirl profile image
Anna •

I'm using GnuCOBOL on Windows:

cobc -xj d05b.cob
Enter fullscreen mode Exit fullscreen mode
Collapse
 
neilgall profile image
Neil Gall •

I was hoping for a meaty one for a cold wet Saturday but this was straightforward. The insight was realising that "binary space partitioning" is just binary, swapping 1 and 0 for letters. I almost did it using string replace at first.

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 });
    }
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
rpalo profile image
Ryan Palo •

Oh man! Swapping letters for numbers is an amazing insight. I'm half-tempted to go back and rewrite mine using even more sneaky binary tricks! I stopped at bit shifting.

Collapse
 
tripledonkey profile image
tripledonkey •

Yep, I noticed this too, I was like "hang on a sec" 🍒

Collapse
 
sleeplessbyte profile image
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
Enter fullscreen mode Exit fullscreen mode
Collapse
 
erikbackman profile image
Erik Bäckman • • Edited

Haskell:

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"
Enter fullscreen mode Exit fullscreen mode
Collapse
 
harrygibson profile image
Harry Gibson •

My solution in python. Sometimes the challenge is just clicking what the description is actually saying, once it's obvious that these are just binary numbers then it was quite an easy one.

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}")
Enter fullscreen mode Exit fullscreen mode
Collapse
 
patryk profile image
Patryk Woziński • • Edited

Today I had a weird day. I did an advent task in my car waiting for gf Good for me that she was so late packing our cat for the trip. :topkek:

I saw many people did the task in a different way - I've used recurrence and pattern matching and it just works.

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
Enter fullscreen mode Exit fullscreen mode
Collapse
 
bgaster profile image
Benedict Gaster • • Edited

After discussing with my partner I thought I should do the binary version too, so here is a slightly modified version, but rather than using Haskell binary stuff, just used fold to convert the binary string to an int.

-- 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
Enter fullscreen mode Exit fullscreen mode
Collapse
 
katafrakt profile image
Paweł Świątkowski •

I went down an easy path today, implementing it in a most straightforward way:

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);
    }
  }
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
willsmart profile image
willsmart • • Edited

Here's my C implementation. Kind of glad it was a straightforward problem this time. Will do tomorrow's in Python.

#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;
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
particleflux profile image
Stefan Linke •

With a bit of bitshifting:

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
        }
    }
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
particleflux profile image
Stefan Linke •

And an alternative solution in PHP :-D

<?for(;$p=fgets(STDIN);$c++)$i[]=base_convert(strtr($p,'BFRL','1010'),2,10);sort($i);echo$i[--$c].' ';for(;$j++<$c;)if($i[$j+1]-$i[$j]>1)echo$i[$j]+1;
Enter fullscreen mode Exit fullscreen mode
Collapse
 
rpalo profile image
Ryan Palo •

Pretty quick one today! I didn't have much problem, and once I realized that the seat ID was actually the index into a 1-D array of seats, I stopped writing my own custom seatID->index function 😂

Day5.h:

#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
Enter fullscreen mode Exit fullscreen mode

Day5.c:

#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;
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
kais_blog profile image
Kai •

Hey everyone 👋!

I've created a step-by-step tutorial for solving AoC 2020 day 5:

dev.to/kais_blog/step-by-step-tuto...

I'm using TypeScript and I explain how to use the binary representation of the boarding pass data.

Collapse
 
benwtrent profile image
Benjamin Trent •

This one was pretty simple.

Rust as always :D

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
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
derekmwright profile image
Derek Wright • • Edited

Ruby, Late to the party - catching up!

I see lots of complex solutions when binary data packing/unpacking should be relatively compact and optimized. Hopefully this helps give people some ideas!

# 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]
Enter fullscreen mode Exit fullscreen mode
Collapse
 
anvsh profile image
Anvesh Saxena •

Part 2 of the puzzle was really puzzling, though I got the answer using set theory

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))
Enter fullscreen mode Exit fullscreen mode
Collapse
 
bgaster profile image
Benedict Gaster • • Edited

Wanting to continue with the Haskell approach of using just lists, which looks back at one of my favourite books from collage Brid and Wadler's Introduction to Functional Programming, I decided to allow my self one function, from the lens package, that is not in Haskell's standard of functions. At some point I guess it might get much of a performance issue to remain with just lists, but for now we continue.

That being said I could not face working with binary date in Haskell, directly at least, and so took a slightly lazy approach with calulating mid points, rather than going for swapping letters for 0 and 1.

-- 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
Enter fullscreen mode Exit fullscreen mode
Collapse
 
mellen profile image
Matt Ellen-Tsivintzeli • • Edited

I'm sad I couldn't think of a regex solution, just a quick sort and filter. (you get the gist)

Collapse
 
readyready15728 profile image
readyready15728 • • Edited

Ruby, part 2:

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]
Enter fullscreen mode Exit fullscreen mode
Collapse
 
justinh11235 profile image
Justin Hinckley •

My Haskell Solution (I just started learning Haskell so fair warning):

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
Enter fullscreen mode Exit fullscreen mode
Collapse
 
tripledonkey profile image
tripledonkey •

Hi, new to this site, and AOC. I did the last 4 in Python, but I thought I would try shell for this one (i'm not great at shell so this may be not the best):

I solved part 1 with this shell oneliner...

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
Enter fullscreen mode Exit fullscreen mode

for part two, I created the list of passport ids with:

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
Enter fullscreen mode Exit fullscreen mode

then threw this at the ids file:

#!/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
Enter fullscreen mode Exit fullscreen mode
Collapse
 
thibpat profile image
Thibaut Patel •

My JavaScript walkthrough: