13 votes

Day 5: Binary Boarding

Today's problem description: https://adventofcode.com/2020/day/5


Join the Tildes private leaderboard! You can do that on this page, by entering join code 730956-de85ce0c.

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace python with any of the "short names" listed in this page of supported languages):

<details>
<summary>Part 1</summary>

```python
Your code here.
```

</details>

27 comments

  1. [6]
    PapaNachos
    (edited )
    Link
    This one was fun! There are some neat tricks you can do to dramatically reduce the complexity of this one. I could probably cut my code in half pretty easily if I took advantage of math. Day 5...

    This one was fun! There are some neat tricks you can do to dramatically reduce the complexity of this one. I could probably cut my code in half pretty easily if I took advantage of math.

    Day 5 Part A - Python

    I recognized this was just fancy binary, so I split it into sections and then did a find and replace to turn them from fancy binary into regular binary. From there I just did a base-2 int cast to get the numbers I needed.

    boarding_passes = input_data.split('\n')
    
    highest_seat = 0
    
    for boarding_pass in boarding_passes:
        row_data = boarding_pass[:7]
        column_data = boarding_pass[7:]
        
        row_binary = row_data.replace('F', '0')
        row_binary = row_binary.replace('B', '1')
        column_binary = column_data.replace('R', '1')
        column_binary = column_binary.replace('L', '0')
        
        row = int(row_binary,2)
        column = int(column_binary,2)
        
        seat_id = (row * 8) + column
        
        if seat_id > highest_seat:
            highest_seat = seat_id
            
    print(highest_seat)
    
    Day 5 Part B - Python I thought about a couple of different ways I could do this, but I ended up just making a quick list of all the seats, finding the min and max, and then iterating between them until I found which seat wasn't there.
    boarding_passes = input_data.split('\n')
    
    seat_list = []
    
    for boarding_pass in boarding_passes:
        row_data = boarding_pass[:7]
        column_data = boarding_pass[7:]
        
        row_binary = row_data.replace('F', '0')
        row_binary = row_binary.replace('B', '1')
        column_binary = column_data.replace('R', '1')
        column_binary = column_binary.replace('L', '0')
        
        row = int(row_binary,2)
        column = int(column_binary,2)
        
        seat_id = (row * 8) + column
        
        seat_list.append(seat_id)
    
    for i in range(min(seat_list), max(seat_list)):
        if i in seat_list:
            pass
        else:
            print(f'Your seat is {i}')
    
    Tips For Beginners
    • There's a hint in the title: You can use binary for this one to make the math much less of a pain

    • If you're feeling tricky, you don't even need to separate out rows and columns. You can just directly compute the seat id (But it's good to walk through the process if you're having trouble figuring it out)

    • I really took advantage of the built in functions in Python. Find and replace and casting from a base 2 string to a base 10 int saved me a lot of headaches. I didn't know you could cast between bases like I used for this, but some quick googling taught me about it

    • Having a good grounding in math will really help you on this one. Try to remember how base 2 works, if you learned that in school. If you never covered it or don't remember, it might be a good topic to read up a bit on

    6 votes
    1. [2]
      blitz
      Link Parent
      Damn, I was super happy with how clever my solution was but I'm a little upset I didn't think of your way! Brilliant!

      Damn, I was super happy with how clever my solution was but I'm a little upset I didn't think of your way! Brilliant!

      4 votes
      1. PapaNachos
        Link Parent
        Thanks! If you want to get really fancy: Spoilers You don't even have to split out the rows and columns, you can just take the whole thing straight to binary and directly calculate the seat_id

        Thanks! If you want to get really fancy:

        Spoilers You don't even have to split out the rows and columns, you can just take the whole thing straight to binary and directly calculate the seat_id

        3 votes
    2. [3]
      blitz
      Link Parent
      Spoilers Since you know it's not at the beginning or the end and you know the seats IDs are contiguous, you don't even need to find the min and the max, just one side and go up or down until you...

      I ended up just making a quick list of all the seats, finding the min and max, and then iterating between them until I found which seat wasn't there

      Spoilers Since you know it's not at the beginning or the end and you know the seats IDs are contiguous, you don't even need to find the min and the max, just one side and go up or down until you find the first one that's not there!
      4 votes
      1. [2]
        PapaNachos
        Link Parent
        Oh damn, good point! My first idea was way too complicated. I almost Spoilers Sorted the whole list, checked the 'slope' at each point numerically by subtracting it from the next value, and looked...

        Oh damn, good point! My first idea was way too complicated. I almost

        Spoilers Sorted the whole list, checked the 'slope' at each point numerically by subtracting it from the next value, and looked for the peak in that janky numerical first derivative

        That would have been WAY more work than was necessary

        3 votes
        1. thorondir
          Link Parent
          I did something of the sort. Spoiler I just stopped as soon as I found the missing seat-id, I didn't go through it all: Sort the list, find the spot where the difference between seat-ids is bigger...

          I did something of the sort.

          Spoiler I just stopped as soon as I found the missing seat-id, I didn't go through it all:

          Sort the list, find the spot where the difference between seat-ids is bigger than one.
          My seat-id is the missing one.

          1 vote
  2. Lynx
    Link
    Started with haskell this time because it seemed like a good tool for the job; it was, but the whole parser business made it a bit more complicated than I would've liked. day5.hs import Data.List...

    Started with haskell this time because it seemed like a good tool for the job; it was, but the whole parser business made it a bit more complicated than I would've liked.

    day5.hs
    import Data.List (sort)
    import Data.Maybe (fromJust)
    import Numeric (readInt)
    import Text.ParserCombinators.ReadP
    
    -- utils
    
    oneCompleteResult :: ReadP a -> String -> Maybe a
    oneCompleteResult p s = case readP_to_S (p <* eof) s of
                              [(x, "")] -> Just x
                              _ -> Nothing
    
    runAoC :: (Show r1, Show r2) => (String -> i) -> (i -> r1) -> (i -> r2) -> IO ()
    runAoC inputTransform part1 part2 = do
        contents <- inputTransform <$> getContents
        print $ part1 contents
        print $ part2 contents
    
    -- end utils
    
    binarify :: String -> Maybe Int
    binarify = oneCompleteResult . readS_to_P $ readInt 2 (`elem` "BFLR") digitValue
        where digitValue 'F' = 0
              digitValue 'B' = 1
              digitValue 'L' = 0
              digitValue 'R' = 1
    
    findHole :: (Enum a, Eq a) => [a] -> Maybe a
    findHole (x:y:ys) | y == next = findHole $ y:ys
                      | otherwise = Just next
                      where next = succ x
    findHole _ = Nothing
    
    main = runAoC (fmap (fromJust . binarify) <$> lines) part1 part2
        where part1 = foldr1 max
              part2 = fromJust . findHole . sort
    
    5 votes
  3. 3d12
    Link
    I'll also join the chorus in saying that I thought this one would be harder. Specifically, I was expecting part 2 to change the whole parameters, like applying the same evaluation to a...

    I'll also join the chorus in saying that I thought this one would be harder. Specifically, I was expecting part 2 to change the whole parameters, like applying the same evaluation to a differently-sized airplane. So, I kind of over-engineered part 1 in anticipation of that. In any case, I didn't do the binary-cast-trick like some others here, which is super clever! I did mine the silly, slow way. But I was really happy that I was able to successfully use Array.map and Array.reduce to avoid a few loops in the final solutions for both parts!

    Part 1
    const fs = require('fs');
    const readline = require('readline');
    
    let passArray = []
    
    async function openFileForReading(file) {
    	const fileStream = fs.createReadStream(file);
    
    	const rl = readline.createInterface({
    		input: fileStream,
    		crlfDelay: Infinity
    	});
    
    	for await (const line of rl) {
    		passArray.push(line);
    	}
    }
    
    class BinaryDirectionError extends Error {}
    
    function binarySplit(direction, begin, end) {
    	let total = (end+1) - begin;
    	let midpoint = begin + (total / 2) - 1;
    	if (direction == "F" || direction == "L") {
    		return [ begin, midpoint ];
    	}
    	if (direction == "B" || direction == "R") {
    		return [ midpoint+1, end ];
    	}
    	return new BinaryDirectionError("Invalid direction: " + direction);
    }
    
    function calculateSeatID(seat) {
    	return (seat.row * 8) + seat.col;
    }
    
    function parseBoardingPass(line) {
    	let minRow = 0;
    	let maxRow = 127;
    	let minCol = 0;
    	let maxCol = 7;
    	let readIndex = 0;
    	for (const direction of line) {
    		if (readIndex < 7) {
    			[minRow, maxRow] = binarySplit(direction, minRow, maxRow);
    		}
    		if (readIndex >= 7) {
    			[minCol, maxCol] = binarySplit(direction, minCol, maxCol);
    		}
    		readIndex++;
    	}
    	return { row: minRow, col: minCol };
    }
    
    (async function mainExecution() {
    	await openFileForReading('input.txt');
    	let idMap = passArray.map((pass) => {
    		return calculateSeatID(parseBoardingPass(pass));
    	});
    	console.log("The highest seat ID is: " + idMap.reduce((a,b) => {
    		return Math.max(a,b);
    	}));
    })();
    
    Part 2
    const fs = require('fs');
    const readline = require('readline');
    
    let passArray = []
    
    async function openFileForReading(file) {
    	const fileStream = fs.createReadStream(file);
    
    	const rl = readline.createInterface({
    		input: fileStream,
    		crlfDelay: Infinity
    	});
    
    	for await (const line of rl) {
    		passArray.push(line);
    	}
    }
    
    class BinaryDirectionError extends Error {}
    
    function binarySplit(direction, begin, end) {
    	let total = (end+1) - begin;
    	let midpoint = begin + (total / 2) - 1;
    	if (direction == "F" || direction == "L") {
    		return [ begin, midpoint ];
    	}
    	if (direction == "B" || direction == "R") {
    		return [ midpoint+1, end ];
    	}
    	return new BinaryDirectionError("Invalid direction: " + direction);
    }
    
    function calculateSeatID(seat) {
    	return (seat.row * 8) + seat.col;
    }
    
    function parseBoardingPass(line) {
    	let minRow = 0;
    	let maxRow = 127;
    	let minCol = 0;
    	let maxCol = 7;
    	let readIndex = 0;
    	for (const direction of line) {
    		if (readIndex < 7) {
    			[minRow, maxRow] = binarySplit(direction, minRow, maxRow);
    		}
    		if (readIndex >= 7) {
    			[minCol, maxCol] = binarySplit(direction, minCol, maxCol);
    		}
    		readIndex++;
    	}
    	return { row: minRow, col: minCol };
    }
    
    (async function mainExecution() {
    	await openFileForReading('input.txt');
    	let idMap = passArray.map((pass) => {
    		return calculateSeatID(parseBoardingPass(pass));
    	});
    	let maxID = idMap.reduce((a,b) => {
    		return Math.max(a,b);
    	});
    	let minID = idMap.reduce((a,b) => {
    		return Math.min(a,b);
    	});
    	for (let i=minID; i<maxID; i++) {
    		if (idMap.indexOf(i) == -1) {
    			console.log("Your seat is ID: " + i);
    			break;
    		}
    	}
    })();
    
    5 votes
  4. Crespyl
    (edited )
    Link
    Ruby Part 1 #!/usr/bin/env ruby def bstep(path, low, high) steps = path.chars while ! steps.empty? c = steps.shift case c when /F|L/ high -= (high - low)/2 when /B|R/ low += (high - low)/2 end end...

    Ruby

    Part 1
    #!/usr/bin/env ruby
    
    def bstep(path, low, high)
      steps = path.chars
      while ! steps.empty?
        c = steps.shift
        case c
        when /F|L/
          high -= (high - low)/2
        when /B|R/
          low += (high - low)/2
        end
      end
      return low
    end
    
    def find_seat_score(pass)
      row = bstep(pass[0...7], 0, 128)
      col = bstep(pass[7...], 0, 8)
      return (row * 8) + col
    end
    
    input = File.read(ARGV[0] || "test.txt")
    
    puts "Part 1"
    puts input.lines.map { |line| find_seat_score(line) }.max
    
    Part 2
    puts "Part 2"
    seats = input.lines.map { |line| find_seat_score(line) }.sort
    seats[1..].reduce(seats.first) do |prev, cur|
      if prev+1 != cur
        puts prev+1
        break
      else
        cur
      end
    end
    

    Edit
    Hah, I didn't pick up on the binary trick, I tend to think too literally when reading the specs. This serves me well in some puzzles, and not so much in others :P. It's simple enough that I went back and did it that way too:

    Alternate
    def pass_to_number(pass)
      Integer(pass.gsub(/F|L/, '0').gsub(/B|R/, '1'), 2)
    end
    puts "Part 1 (again)"
    puts input.lines.map { |l| pass_to_number(l) }.max
    
    4 votes
  5. clone1
    Link
    MIT scheme solution. Part 1 & 2 Pretty simple if you can find the trick. I wonder if scheme has a better way to do part b. (define (get-lines parse-line) (with-input-from-file "input" (lambda ()...

    MIT scheme solution.

    Part 1 & 2 Pretty simple if you can find the trick. I wonder if scheme has a better way to do part b.
    (define (get-lines parse-line)
      (with-input-from-file "input"
        (lambda ()
          (let loop ((line (read-line))
                     (lines '()))
            (if (eof-object? line)
                (reverse lines)
                (loop (read-line)
                      (cons (parse-line line) lines)))))))
    
    (define (string-replace-all str pairs)
      (fold (lambda (pair str)
              (string-replace str (car pair) (cdr pair)))
            str pairs))
    
    (define (parse-seat-id str)
      (let* ((str (string-replace-all str
                                      '((#\B . #\1)
                                        (#\F . #\0)
                                        (#\R . #\1)
                                        (#\L . #\0))))
             (row (string->number (substring str 0 7)
                                  2))
             (col (string->number (substring str 7)
                                  2)))
        (+ (* row 8)
           col)))
    
    (define (one lines)
      (apply max lines))
    
    (define (two lines)
      (let loop ((ids (sort lines <))
                 (last-id '()))
        (if (null? ids) #f
            (let ((id (car ids))
                  (ids (cdr ids)))
              (if (or (null? last-id)
                      (= (- id last-id)
                         1))
                  (loop ids id)
                  (+ last-id 1))))))
    
    (define (run lines)
      (display "One: ")
      (display (one lines))
      (newline)
      (display "Two: ")
      (display (two lines))
      (newline))
    
    (run (get-lines parse-seat-id))
    
    4 votes
  6. [2]
    tomf
    (edited )
    Link
    Sheets! This one was fairly straightforward for a spreadsheet, actually. Part 2 was longer than it needs to be, simply because I'm trying to do each part with a single formula. I really liked that...

    Sheets!

    This one was fairly straightforward for a spreadsheet, actually. Part 2 was longer than it needs to be, simply because I'm trying to do each part with a single formula.

    I really liked that the seating accounted for double-rows for safety exits. A nice addition since the average passenger is over 7' tall.

    Part 1
    =ARRAYFORMULA(
      MAX(
       IF(ISBLANK(A1:A),,
        BIN2DEC(
         REGEXREPLACE(
          REGEXREPLACE(
           LEFT(A1:A,7),
           "B","1"),
          "F","0"))*8+
        BIN2DEC(
         REGEXREPLACE(
          REGEXREPLACE(
           RIGHT(A1:A,3),
           "R","1"),
          "L","0")))))
    
    
    Part 2
    =ARRAYFORMULA(
     INDEX(
      QUERY(
       {IF(ISBLANK(A1:A),,
         BIN2DEC(
          REGEXREPLACE(
           REGEXREPLACE(
            LEFT(A1:A,7),
            "B","1"),
           "F","0"))*8+
         BIN2DEC(
          REGEXREPLACE(
           REGEXREPLACE(
            RIGHT(A1:A,3),
            "R","1"),
           "L","0")));
        TRANSPOSE(
         SEQUENCE(
          1,
          COUNTA(
           IF(ISBLANK(A1:A),,
            BIN2DEC(
             REGEXREPLACE(
              REGEXREPLACE(
               LEFT(A1:A,7),
               "B","1"),
              "F","0"))*8+
            BIN2DEC(
             REGEXREPLACE(
              REGEXREPLACE(
               RIGHT(A1:A,3),
               "R","1"),
              "L","0"))))+1,
          MIN(
           IF(ISBLANK(A1:A),,
            BIN2DEC(
             REGEXREPLACE(
              REGEXREPLACE(
               LEFT(A1:A,7),
               "B","1"),
              "F","0"))*8+
            BIN2DEC(
             REGEXREPLACE(
              REGEXREPLACE(
               RIGHT(A1:A,3),
               "R","1"),
              "L","0"))))))},
       "select Col1, Count(Col1) 
        where Col1 is not null 
        group by Col1 
        order by Count(Col1) asc 
        limit 1",0),
      2,1))
    
    

    My sheet

    4 votes
    1. 3d12
      Link Parent
      I hadn't even noticed! Points to you for attention to detail :)

      A nice addition since the average passenger is over 7' tall.

      I hadn't even noticed! Points to you for attention to detail :)

      3 votes
  7. markh
    Link
    Day 5! This one was fun, although I had to figure out how to slide an array in Elixir. Elixir defmodule Day5 do def one do File.read!("inputs/five.txt") |> String.split("\n") |> Enum.map(&parse/1)...

    Day 5! This one was fun, although I had to figure out how to slide an array in Elixir.

    Elixir
        defmodule Day5 do
          def one do
            File.read!("inputs/five.txt")
            |> String.split("\n")
            |> Enum.map(&parse/1)
            |> Enum.max()
          end
    
          def parse(input) do
            [[r, s]] = Regex.scan(~r/([F|B]{7})([R|L]{3})/, input, capture: :all_but_first)
    
            row = r
            |> String.replace("F", "0")
            |> String.replace("B", "1")
            |> String.to_integer(2)
    
            seat = s
            |> String.replace("L", "0")
            |> String.replace("R", "1")
            |> String.to_integer(2)
    
            row * 8 + seat
          end
    
          def two do
            [[x, _]] = File.read!("inputs/five.txt")
            |> String.split("\n")
            |> Enum.map(&parse/1)
            |> Enum.sort()
            |> Enum.chunk_every(2, 1, :discard)
            |> Enum.filter(fn [x, y] -> y - x == 2 end)
    
            x + 1
          end
        end
    
    4 votes
  8. Crestwave
    Link
    I'm sure there's a better way to do this, but I started it late and wasted some time figuring out incompatibilities with BWK AWK. Part 1 #!/usr/bin/awk -f { split("0,127", row, ",") split("0,7",...

    I'm sure there's a better way to do this, but I started it late and wasted some time figuring out incompatibilities with BWK AWK.

    Part 1
    #!/usr/bin/awk -f
    {
    	split("0,127", row, ",")
    	split("0,7", col, ",")
    	chars = split($0, char, "")
    	for (i = 1; i <= chars; ++i) {
    		c = char[i]
    		if (c == "F")
    			row[2] -= int((row[2] - row[1] + 1) / 2)
    		else if (c == "B")
    			row[1] += int((row[2] - row[1] + 1) / 2)
    		else if (c == "L")
    			col[2] -= int((col[2] - col[1] + 1) / 2)
    		else if (c == "R")
    			col[1] += int((col[2] - col[1] + 1) / 2)
    	}
    
    	id = row[1] * 8 + col[1]
    	if (id > highest)
    		highest = id
    }
    
    END { print highest }
    
    Part 2
    #!/usr/bin/awk -f
    {
    	split("0,127", row, ",")
    	split("0,7", col, ",")
    	chars = split($0, char, "")
    	for (i = 1; i <= chars; ++i) {
    		c = char[i]
    		if (c == "F")
    			row[2] -= int((row[2] - row[1] + 1) / 2)
    		else if (c == "B")
    			row[1] += int((row[2] - row[1] + 1) / 2)
    		else if (c == "L")
    			col[2] -= int((col[2] - col[1] + 1) / 2)
    		else if (c == "R")
    			col[1] += int((col[2] - col[1] + 1) / 2)
    	}
    
    	id = row[1] * 8 + col[1]
    	seats[id] = 1
    	if (id > highest)
    		highest = id
    	if (id < lowest || !lowest)
    		lowest = id
    }
    
    END {
    	for (i = lowest; i < highest; ++i)
    		if (! seats[i])
    			print i
    }
    
    4 votes
  9. blitz
    (edited )
    Link
    I was expecting something much harder since tomorrow is a weekend! Also, I have joined the private leaderboard as (anonymous user #573549). :) Rust main.rs use std::io; use std::io::prelude::*;...

    I was expecting something much harder since tomorrow is a weekend!

    Also, I have joined the private leaderboard as (anonymous user #573549). :)

    Rust

    main.rs
    use std::io;
    use std::io::prelude::*;
    use std::collections::HashSet;
    
    use std::cmp;
    
    fn row_partition(input: &str) -> usize{
        let mut row_acc = 0;
    
        for (i, c) in input.chars().enumerate() {
            if c == 'B' {
                row_acc += 64 / (2 as usize).pow(i as u32);
            }
        }
    
        row_acc
    }
    
    fn col_partition(input: &str) -> usize {
        let mut col_acc = 0;
    
        for (i, c) in input.chars().enumerate() {
            if c == 'R' {
                col_acc += 4 / (2 as usize).pow(i as u32);
            }
        }
    
        col_acc
    }
    
    fn get_coord(input: &str) -> (usize, usize) {
        let (row, col) = input.split_at(7);
    
        (row_partition(row), col_partition(col))
    }
    
    fn get_seat_id(input: &str) -> usize {
        let (row, col) = get_coord(input);
    
        (row * 8) + col
    }
    
    fn part1(lines: &Vec<String>) -> usize {
        let mut max_seat_id = 0;
    
        for l in lines.iter() {
            max_seat_id = cmp::max(max_seat_id, get_seat_id(l));
        }
    
        max_seat_id
    }
    
    fn part2(lines: &Vec<String>, max_seat_id: usize) -> usize {
        let mut existing_seats = HashSet::new();
    
        for l in lines.iter() {
            existing_seats.insert(get_seat_id(l));
        }
    
        for x in (0..max_seat_id).rev() {
            if !existing_seats.contains(&x) {
                return x;
            }
        }
    
        panic!();
    }
    
    fn main() {
        let stdin = io::stdin();
        let lines: Vec<String> = stdin.lock().lines().collect::<Result<_, _>>().unwrap();
    
        let part1_ans = part1(&lines);
        let part2_ans = part2(&lines, part1_ans);
    
        println!("Part 1: {}", part1_ans);
        println!("Part 2: {}", part2_ans);
    }
    
    3 votes
  10. OrangeBacon
    Link
    My solution in rust: Was fun to do, was expecting something much harder given that it is Saturday. Link to the repository, including test runner main.rs use std::cmp::{max}; pub fn day05(input:...

    My solution in rust:
    Was fun to do, was expecting something much harder given that it is Saturday.

    Link to the repository, including test runner

    main.rs
    use std::cmp::{max};
    
    pub fn day05(input: String) {
        let lines : Vec<_> = input.lines().collect();
    
        let mut highest = 0;
    
        let mut seats = [[(false, 0); 8]; 128];
    
        for line in lines {
            let mut row = 0;
            let mut col = 0;
            let mut row_size = 128;
            let mut col_size = 8;
            for c in line.chars() {
                match c {
                    'F' => row_size /= 2,
                    'B' => { // upper
                        row += row_size;
                        row_size /= 2;
                    }
                    'R' => { // upper
                        col += col_size;
                        col_size /= 2;
                    }
                    'L' => col_size /= 2,
                    _ => panic!()
                }
            }
            seats[row/2][col/2] = (true, row/2 * 8 + col/2);
            highest = max(highest, row/2 * 8 + col/2);
        }
    
        let mut found = false;
        let mut id = 0;
        'out: for (y, row) in seats.iter().enumerate() {
            if !found {
                for seat in row.iter() {
                    if (*seat).0 {
                        found = true;
                    }
                }
            } else {
                for (x, seat) in row.iter().enumerate() {
                    if !(*seat).0 {
                        id = y * 8 + x;
                        break 'out;
                    }
                }
            }
        }
    
        println!("{}", highest);
        println!("{}", id);
    }
    
    3 votes
  11. archevel
    (edited )
    Link
    This time the solution was very straight forward so didn't do anything fancy, just pure python. (edit: realised I could use translate in one go instead of using replace multiple times) Part 1 in...

    This time the solution was very straight forward so didn't do anything fancy, just pure python.

    (edit: realised I could use translate in one go instead of using replace multiple times)

    Part 1 in Python
    import sys
    
    def seatId(p):
        return int(p.translate(str.maketrans("FLBR", "0011")), 2)
    
    seatids = [seatId(x[:-1]) for x in sys.stdin.readlines()]
    print(max(seatids))
    
    Part 2 in Python
    import sys
    
    def seatId(p):
        return int(p.translate(str.maketrans("FLBR", "0011")), 2)
    
    seatids = [seatId(x[:-1]) for x in sys.stdin.readlines()]
    seatids.sort()
    before, after = list(filter(lambda e: e[0] + 2 == e[1], zip(seatids, seatids[1:]))).pop()
    print(before + 1)
    
    3 votes
  12. Bauke
    Link
    Language: Rust. Repository. Main function (run harness). Took me a bit to figure out the math for calculating the row and column, but got there in the end. Could have probably also done this in a...

    Took me a bit to figure out the math for calculating the row and column, but got there in the end. Could have probably also done this in a binary way (which I think the puzzle's title is referring to) but I figured I'd just do it the mathy way.

    I could have probably also factored out the math to generalized functions since the row and column stuff is just the same code with different variable names, but I'm not here to make it look pretty. If it works, it's good enough. :P

    Solution
    use crate::DayResult;
    
    pub(crate) fn solve(data: String) -> DayResult {
      let seat_ids = data
        .lines()
        .map(calculate_row_and_column)
        .map(calculate_seat_id)
        .collect::<Vec<i32>>();
    
      // Result one also functions as the max seat ID.
      let result_one = seat_ids.iter().max().unwrap();
      let min_seat_id = seat_ids.iter().min().unwrap();
    
      let result_two = (*min_seat_id..*result_one)
        .find(|index| !seat_ids.contains(&index))
        .map(|id| id.to_string());
    
      Ok((Some(result_one.to_string()), result_two))
    }
    
    const MAX_ROW_RANGE: i32 = 128;
    const MAX_COLUMN_RANGE: i32 = 8;
    
    fn calculate_row_and_column(data: &str) -> (i32, i32) {
      let mut row_range = 0..MAX_ROW_RANGE;
      let mut column_range = 0..MAX_COLUMN_RANGE;
    
      for character in data.chars() {
        let row_min = row_range.start;
        let row_max = row_range.end;
        let row_difference = (row_max - row_min) / 2;
    
        let column_min = column_range.start;
        let column_max = column_range.end;
        let column_difference = (column_max - column_min) / 2;
    
        match character {
          'F' => {
            row_range = row_min..(row_max - row_difference);
          }
          'B' => {
            row_range = (row_min + row_difference)..row_max;
          }
          'L' => {
            column_range = column_min..(column_max - column_difference);
          }
          'R' => {
            column_range = (column_min + column_difference)..column_max;
          }
          _ => unreachable!(character),
        }
      }
    
      (row_range.start, column_range.start)
    }
    
    fn calculate_seat_id((row, column): (i32, i32)) -> i32 {
      (row * 8) + column
    }
    
    #[test]
    fn test_samples() {
      let samples = vec![
        ("FBFBBFFRLR", 44, 5, 357),
        ("BFFFBBFRRR", 70, 7, 567),
        ("FFFBBBFRRR", 14, 7, 119),
        ("BBFFBBFRLL", 102, 4, 820),
      ];
    
      for (data, row, column, id) in samples {
        let (_row, _column) = calculate_row_and_column(data);
        assert_eq!(row, _row);
        assert_eq!(column, _column);
        assert_eq!(id, calculate_seat_id((_row, _column)));
      }
    }
    
    Output
    🌟 Day 05  |
    🎆 Part 1  | 850
    🎇 Part 2  | 599
    🌠 Runtime | 0.006777296 seconds
    
    3 votes
  13. wycy
    (edited )
    Link
    Rust Not particularly proud of this one. I didn't pick up on the binary implementation at all. When I was doing this last night I couldn't figure out how to sort my vector of seatIDs, so I ended...

    Rust

    Not particularly proud of this one. I didn't pick up on the binary implementation at all. When I was doing this last night I couldn't figure out how to sort my vector of seatIDs, so I ended up printing out all seatIDs, pasting into Sheets, sorting, and then finding the part2 answer that way.

    I've since figured out how to sort.

    Rust
    use std::env;
    use std::io::{self, prelude::*, BufReader};
    use std::fs::File;
    
    struct Seat {
        seat: String,
        row: i64,
        col: i64,
    }
    impl Seat {
        pub fn new(s: &str) -> Seat {
            
            // Get row
            let fb = &s[0..7];
            let mut rows: Vec<i64> = (0..=127).collect();
            for (i,c) in fb.chars().enumerate() {
                let l = rows.len();
                match c.to_string().as_ref() {
                    "F" => for _ in 0..l/2 { rows.pop(); },
                    "B" => for _ in 0..l/2 { rows.remove(0); },
                    other => panic!("Unknown character: {}", other),
                }
            }
            
            // Get column
            let lr = &s[7..10];
            let mut cols: Vec<i64> = (0..=7).collect();
            for (i,c) in lr.chars().enumerate() {
                let l = cols.len();
                match c.to_string().as_ref() {
                    "L" => for _ in 0..l/2 { cols.pop(); },
                    "R" => for _ in 0..l/2 { cols.remove(0); },
                    other => panic!("Unknown character: {}", other),
                }
            }
    
            Seat {
                seat: s.to_string(),
                row: rows[0],
                col: cols[0],
            }
        }
        pub fn seat_id(&self) -> i64 {
            self.row * 8 + self.col
        }
    }
    
    fn day05(input: &str) -> io::Result<()> {
        let file = File::open(input).expect("Input file not found.");
        let reader = BufReader::new(file);
    
        let input: Vec<String> = match reader.lines().collect() {
            Err(err) => panic!("Unknown error reading input: {}", err),
            Ok(result) => result,
        };
    
        let seats = input
            .iter()
            .map(|x| Seat::new(x))
            .collect::<Vec<Seat>>();
    
        // Part 1
        let part1 = seats.iter().map(Seat::seat_id).max().unwrap();
        println!("Part 1: {}", part1); // 826
    
        // Part 2
        let mut seats_sorted: Vec<i64> = seats
            .iter()
            .map(Seat::seat_id)
            .collect::<Vec<i64>>();
        seats_sorted.sort();
    
        let part2 = seats_sorted
            .windows(2)
            .filter(|x| x[1] - x[0] == 2)
            .map(|x| x[0]+1)
            .next()
            .unwrap();
        println!("Part 2: {}", part2); // 678
    
        Ok(())
    }
    
    fn main() {
        let args: Vec<String> = env::args().collect();
        let filename = &args[1];
        day05(&filename).unwrap();
    }
    
    3 votes
  14. Gyrfalcon
    Link
    Language: Julia Repository Like many others, I didn't pick up on the binary hint in the title. In fact, I wrongly assumed it referred to a binary search, which the process they outlined for...

    Like many others, I didn't pick up on the binary hint in the title. In fact, I wrongly assumed it referred to a binary search, which the process they outlined for determining the numbers seemed to be. Oh well, it still wasn't bad, and Julia has some fun tools that made part 2 easy even though I didn't have some elegant way of doing it.

    Part 1
    function main()
    
        # Read input
        lines = []
        open("Day05/input.txt") do fp
            lines = readlines(fp)
        end
    
        # Apply our function using list comprehensions to get our numbers
        rows = [bin_range(code[1:7], 'F', 127) for code in lines]
        columns = [bin_range(code[8:end], 'L', 7) for code in lines]
        ids = [coord[1] * 8 + coord[2] for coord in zip(rows, columns)]
    
        println("Part 1 result is ", maximum(ids))
    
    end
    
    # Little function to generally loop through and binary search
    function bin_range(code, lower, range_max)
        max = range_max
        min = 0
        for letter in code
            if letter == lower
                max -= Int(floor((max - min) / 2))
            else
                min += Int(ceil((max - min) / 2))
            end
        end
        return min
    end
            
    main()
    
    Part 2 diff
    @@ -9,9 +9,14 @@ function main()
         # Apply our function using list comprehensions to get our numbers
         rows = [bin_range(code[1:7], 'F', 127) for code in lines]
         columns = [bin_range(code[8:end], 'L', 7) for code in lines]
    -    ids = [coord[1] * 8 + coord[2] for coord in zip(rows, columns)]
    +    ids = sort([coord[1] * 8 + coord[2] for coord in zip(rows, columns)])
     
    -    println("Part 1 result is ", maximum(ids))
    +    println("Part 1 result is ", ids[end])
    +
    +    # Thanks to added sort on line 12, just look for a big diff
    +    my_seat = ids[argmax(ids[2:end] .- ids[1:end-1])] + 1
    +
    +    println("Part 2 result is ", my_seat)
     
     end
    

    I may try to do some of the future challenges running on a Raspberry Pi, since I am interested to see how it performs with Julia, not sure if that interests anyone here to see.

    2 votes
  15. sal
    (edited )
    Link
    My simple solution in Python Part 1 f = open('day5_input.txt') boardingPasses = f.read().rstrip('\n').split('\n') def getSeat(bp): return ( int(bp[:7].replace('F', '0').replace('B', '1'), 2),...

    My simple solution in Python

    Part 1
    f = open('day5_input.txt')
    boardingPasses = f.read().rstrip('\n').split('\n')
    
    def getSeat(bp):
        return (
            int(bp[:7].replace('F', '0').replace('B', '1'), 2),
            int(bp[7:].replace('R', '1').replace('L', '0'), 2)
        )
    
    def seatID(seat):
        return seat[0] * 8 + seat[1]
    
    seatIDs = [ seatID(getSeat(bp)) for bp in boardingPasses ]
    
    print( "The highest seatID is", max(seatIDs))
    
    Part 2 addition
    for seat in seatIDs:
        if seat + 1 not in seatIDs and seat + 2 in seatIDs:
            print("Your seatID is", seat + 1)
            break
    
    2 votes
  16. nothis
    Link
    Today was pleasant. Took me about 20 mins, which seems appropriate. I just checked the global leaderboards and someone did it in 00:02:55, lol. It reminds me of how hard these can get towards the...

    Today was pleasant. Took me about 20 mins, which seems appropriate. I just checked the global leaderboards and someone did it in 00:02:55, lol. It reminds me of how hard these can get towards the end and this year I'm not sure I'll do the later ones that take a normal person like... hours.

    Part 1+2
    with open("05/input.txt") as inputFile:
        boardingPasses = inputFile.read().split("\n")
    
    
    def bsp(input, depth, lowest, highest):
    
        if lowest == highest or depth > len(input)-1:
            return lowest
    
        if input[depth] == "F" or input[depth] == "L":
            highest = int(lowest + (highest - lowest) / 2)
        else:
            lowest = int(lowest + (highest - lowest) / 2) + 1
    
        return bsp(input, depth + 1, lowest, highest)
    
    
    def seatID(boardingPass):
        row = bsp(boardingPass[0:7], 0, 0, 127)
        column = bsp(boardingPass[7:10], 0, 0, 7)
        return row * 8 + column
    
    
    seats = []
    highest = -1
    for boardingPass in boardingPasses:
        id = seatID(boardingPass)
        seats.append(id)
        if id > highest:
            highest = id
    print("Highest seatID: ", highest)
    
    for seat in range(highest):
        if seat not in seats and seat - 1 in seats and seat + 1 in seats:
            print("Your seatID: ", seat)
            break
    
    2 votes
  17. spit-evil-olive-tips
    Link
    Part 1 def parse_seat(line): row, col = line[:7], line[7:10] row = row.replace('F', '0').replace('B', '1') col = col.replace('L', '0').replace('R', '1') row, col = int(row, base=2), int(col,...
    Part 1
    def parse_seat(line):
        row, col = line[:7], line[7:10]
        row = row.replace('F', '0').replace('B', '1')
        col = col.replace('L', '0').replace('R', '1')
        row, col = int(row, base=2), int(col, base=2)
        print(f'{line.strip()} -> {row}, {col}')
        return row, col
    
    
    def main():
        with open('005.txt') as input_file:
            lines = input_file.readlines()
            seats = [parse_seat(line) for line in lines]
            ids = [(row * 8) + col for row, col in seats]
            print(max(ids))
    
    
    if __name__ == '__main__':
        main()
    

    Neat Python trick I used here of zip(ids, ids[1:]) to walk through the list of IDs one pair at a time.

    Part 2
    def parse_seat(line):
        row, col = line[:7], line[7:10]
        row = row.replace('F', '0').replace('B', '1')
        col = col.replace('L', '0').replace('R', '1')
        row, col = int(row, base=2), int(col, base=2)
        print(f'{line.strip()} -> {row}, {col}')
        return row, col
    
    
    def main():
        with open('005.txt') as input_file:
            lines = input_file.readlines()
            seats = [parse_seat(line) for line in lines]
            ids = sorted([(row * 8) + col for row, col in seats])
    
            for left, right in zip(ids, ids[1:]):
                if left + 2 == right:
                    print(left + 1)
    
    
    if __name__ == '__main__':
        main()
    
    2 votes
  18. andre
    Link
    JavaScript My initial implementation was a typical binary search and then straightforward id calculation. After reading some of the answers here and realizing it's just a binary number, here's a...

    JavaScript

    My initial implementation was a typical binary search and then straightforward id calculation. After reading some of the answers here and realizing it's just a binary number, here's a more interesting solution:

    Parts 1 + 2
    export function solvePart1(input) {
      input = input.split('\n')
      return _.max(
        input.map(seat => {
          return parseInt(seat.replace(/(F|L)/g, 0).replace(/(B|R)/g, 1), 2)
        }),
      )
    }
    
    export function solvePart2(input) {
      input = input.split('\n')
    
      const ids = input
        .map(seat => {
          return parseInt(seat.replace(/(F|L)/g, 0).replace(/(B|R)/g, 1), 2)
        })
        .sort((a, b) => a - b) // Array.sort() is lexicographical in JS, lol
    
      for (let i = 0; i < ids.length; i++) {
        if (ids[i] !== ids[0] + i) {
          return ids[0] + i
        }
      }
    }
    
    1 vote
  19. heady
    Link
    oops I dropped my boarding pass, lemme just scan 850 other boarding passes to avoid bending my knees before sitting for hours Parts 1&2 rawinput = open("day5input", 'r') seats = [] i = 0 for line...

    oops I dropped my boarding pass, lemme just scan 850 other boarding passes to avoid bending my knees before sitting for hours

    Parts 1&2
    rawinput = open("day5input", 'r')
    
    seats = []
    i = 0
    for line in rawinput:
        i += 1
        row = [0, 127]
        isle = [0, 7]
    
        for letter in line:
    
            if letter == 'F':
                row[1] = row[1] - ((row[1] - row[0]) // 2) - 1
            if letter == 'B':
              row[0] = row[0] + ((row[1] - row[0]) // 2) + 1
    
            if letter == 'L':
                isle[1] = isle[1] - ((isle[1] - isle[0]) // 2) - 1
            if letter == 'R':
                isle[0] = isle[0] + ((isle[1] - isle[0]) // 2) + 1
    
        if (row[0] == row[1]) and (isle[0] == isle[1]):
            seats.append((row[0]*8) + isle[0])
    
    print(max(seats))
    
    seats.sort()
    my_seat = 54
    for seat in seats:
        if seat - my_seat > 1:
            my_seat = seat -1
            break
        else:
            my_seat = seat
    print(my_seat)
    
    1 vote
  20. jzimbel
    (edited )
    Link
    Like a lot of other people, I figured out that partial solution spoiler the characters in the partitions could just be mapped to 0's and 1's, and then parsed as binary numbers. Elixir's nice...

    Like a lot of other people, I figured out that

    partial solution spoiler the characters in the partitions could just be mapped to 0's and 1's, and then parsed as binary numbers.
    Elixir's nice built-ins for converting between strings and char lists made this a pleasant experience. Shout out to the `?` operator for easily getting the codepoint of a given character.

    I like @markh's part 2 solution using Enum.chunk_every/3, but my uglier solution using Enum.reduce_while/3 might be slightly faster ;)

    Part 1 and 2
    defmodule AdventOfCode.Day05 do
      def part1(args) do
        args
        |> get_seat_ids()
        |> Enum.max()
      end
    
      def part2(args) do
        args
        |> get_seat_ids()
        |> find_my_seat_id()
      end
    
      defp get_seat_ids(input) do
        input
        |> String.split()
        |> Enum.map(&String.split_at(&1, 7))
        |> Enum.map(fn {row, col} ->
          {parse_partition(row), parse_partition(col)}
        end)
        |> Enum.map(&seat_id/1)
      end
    
      defp parse_partition(partition) do
        partition
        |> String.to_charlist()
        |> Enum.map(&char_mapper/1)
        |> List.to_string()
        |> String.to_integer(2)
      end
    
      defp char_mapper(?F), do: ?0
      defp char_mapper(?B), do: ?1
      defp char_mapper(?L), do: ?0
      defp char_mapper(?R), do: ?1
    
      defp seat_id({row_num, col_num}), do: row_num * 8 + col_num
    
      defp find_my_seat_id(seat_ids) do
        [first_id | rest] = Enum.sort(seat_ids)
    
        Enum.reduce_while(rest, first_id, fn
          seat_id, prev_seat_id when seat_id - prev_seat_id == 2 ->
            {:halt, seat_id - 1}
    
          seat_id, _ ->
            {:cont, seat_id}
        end)
      end
    end
    
    1 vote
  21. bilbodwyer
    Link
    Didn't do any over the weekend, so I was playing catch up today, and beating my head against the brick wall that was part B for day 4. I'm pleased to say that I nailed both parts for day 5 quite...

    Didn't do any over the weekend, so I was playing catch up today, and beating my head against the brick wall that was part B for day 4. I'm pleased to say that I nailed both parts for day 5 quite quickly though!

    Parts A and B in python
    #!/usr/bin/env python3
    
    # Advent of Code
    # Day 5
    # bill@billodwyer.xyz
    
    boarding_passes = []
    
    with open("input","r") as input:
        boarding_passes = input.read().splitlines()
        
    highest_seat_id = 0
    seat_id_list = []
    
    for string in boarding_passes:
        row = string[:-3]
        col = string[-3:]
    
        row_bin = row.replace("F", "0")
        row_bin = row_bin.replace("B", "1")
        col_bin = col.replace("L", "0")
        col_bin = col_bin.replace("R", "1")
    
        row_num = int(row_bin, 2)
        col_num = int(col_bin, 2)
    
        id_calc = (row_num * 8) + col_num
        if id_calc > highest_seat_id:
            highest_seat_id = id_calc
        seat_id_list.append(id_calc)
    
    
    total_seats = len(seat_id_list)
    
    for i in range(0,total_seats):
        if i not in seat_id_list:
            if i+1 in seat_id_list and i-1 in seat_id_list:
                your_seat = i
                
    print(f"Highest seat ID is {highest_seat_id}")
    print(f"Your seat ID is {your_seat}")
    
    1 vote