|
| 1 | +#! /usr/bin/env elixir |
| 2 | +defmodule Day05 do |
| 3 | + @moduledoc """ |
| 4 | + --- Day 5: Binary Boarding --- |
| 5 | +
|
| 6 | + You board your plane only to discover a new problem: you dropped your boarding pass! You aren't sure which seat is |
| 7 | + yours, and all of the flight attendants are busy with the flood of people that suddenly made it through passport |
| 8 | + control. |
| 9 | +
|
| 10 | + You write a quick program to use your phone's camera to scan all of the nearby boarding passes (your puzzle input); |
| 11 | + perhaps you can find your seat through process of elimination. |
| 12 | +
|
| 13 | + Instead of zones or groups, this airline uses binary space partitioning to seat people. A seat might be specified like |
| 14 | + FBFBBFFRLR, where F means "front", B means "back", L means "left", and R means "right". |
| 15 | +
|
| 16 | + The first 7 characters will either be F or B; these specify exactly one of the 128 rows on the plane (numbered 0 |
| 17 | + through 127). Each letter tells you which half of a region the given seat is in. Start with the whole list of rows; |
| 18 | + the first letter indicates whether the seat is in the front (0 through 63) or the back (64 through 127). The next |
| 19 | + letter indicates which half of that region the seat is in, and so on until you're left with exactly one row. |
| 20 | +
|
| 21 | + For example, consider just the first seven characters of FBFBBFFRLR: |
| 22 | +
|
| 23 | + Start by considering the whole range, rows 0 through 127. |
| 24 | + F means to take the lower half, keeping rows 0 through 63. |
| 25 | + B means to take the upper half, keeping rows 32 through 63. |
| 26 | + F means to take the lower half, keeping rows 32 through 47. |
| 27 | + B means to take the upper half, keeping rows 40 through 47. |
| 28 | + B keeps rows 44 through 47. |
| 29 | + F keeps rows 44 through 45. |
| 30 | + The final F keeps the lower of the two, row 44. |
| 31 | +
|
| 32 | + The last three characters will be either L or R; these specify exactly one of the 8 columns of seats on the plane |
| 33 | + (numbered 0 through 7). The same process as above proceeds again, this time with only three steps. L means to keep the |
| 34 | + lower half, while R means to keep the upper half. |
| 35 | +
|
| 36 | + For example, consider just the last 3 characters of FBFBBFFRLR: |
| 37 | +
|
| 38 | + Start by considering the whole range, columns 0 through 7. |
| 39 | + R means to take the upper half, keeping columns 4 through 7. |
| 40 | + L means to take the lower half, keeping columns 4 through 5. |
| 41 | + The final R keeps the upper of the two, column 5. |
| 42 | +
|
| 43 | + So, decoding FBFBBFFRLR reveals that it is the seat at row 44, column 5. |
| 44 | +
|
| 45 | + Every seat also has a unique seat ID: multiply the row by 8, then add the column. In this example, the seat has ID |
| 46 | + 44 * 8 + 5 = 357. |
| 47 | +
|
| 48 | + Here are some other boarding passes: |
| 49 | +
|
| 50 | + BFFFBBFRRR: row 70, column 7, seat ID 567. |
| 51 | + FFFBBBFRRR: row 14, column 7, seat ID 119. |
| 52 | + BBFFBBFRLL: row 102, column 4, seat ID 820. |
| 53 | +
|
| 54 | + As a sanity check, look through your list of boarding passes. What is the highest seat ID on a boarding pass? |
| 55 | +
|
| 56 | + --- Part Two --- |
| 57 | +
|
| 58 | + Ding! The "fasten seat belt" signs have turned on. Time to find your seat. |
| 59 | +
|
| 60 | + It's a completely full flight, so your seat should be the only missing boarding pass in your list. However, there's a |
| 61 | + catch: some of the seats at the very front and back of the plane don't exist on this aircraft, so they'll be missing |
| 62 | + from your list as well. |
| 63 | +
|
| 64 | + Your seat wasn't at the very front or back, though; the seats with IDs +1 and -1 from yours will be in your list. |
| 65 | +
|
| 66 | + What is the ID of your seat? |
| 67 | + """ |
| 68 | + |
| 69 | + defp read_input_file() do |
| 70 | + {:ok, boarding_passes_file} = File.read("input.txt") |
| 71 | + |
| 72 | + boarding_passes_file |
| 73 | + |> String.split("\n") |
| 74 | + |> Stream.filter(&(&1 != "")) |
| 75 | + end |
| 76 | + |
| 77 | + defp get_row(boarding_pass), do: get_row(String.slice(boarding_pass, 0..6), 0, 128) |
| 78 | + defp get_row("F", min, _max), do: min |
| 79 | + defp get_row("B", _min, max), do: max |
| 80 | + defp get_row("F" <> rest, min, max), do: get_row(rest, min, div(max+min+1, 2)-1) |
| 81 | + defp get_row("B" <> rest, min, max), do: get_row(rest, div(max+min+1, 2), max) |
| 82 | + |
| 83 | + defp get_column(boarding_pass), do: get_column(String.slice(boarding_pass, 7..9), 0, 7) |
| 84 | + defp get_column("L", min, _max), do: min |
| 85 | + defp get_column("R", _min, max), do: max |
| 86 | + defp get_column("L" <> rest, min, max), do: get_column(rest, min, div(max+min+1, 2)-1) |
| 87 | + defp get_column("R" <> rest, min, max), do: get_column(rest, div(max+min+1, 2), max) |
| 88 | + |
| 89 | + defp get_seat_id(boarding_pass), do: 8 * get_row(boarding_pass) + get_column(boarding_pass) |
| 90 | + |
| 91 | + def part_1() do |
| 92 | + read_input_file() |
| 93 | + |> Stream.map(&get_seat_id/1) |
| 94 | + |> Enum.max() |
| 95 | + end |
| 96 | + |
| 97 | + def part_2() do |
| 98 | + seat_ids = |
| 99 | + read_input_file() |
| 100 | + |> Stream.map(&get_seat_id/1) |
| 101 | + |
| 102 | + 1..Enum.max(seat_ids) |
| 103 | + |> Stream.filter(& &1 not in seat_ids) |
| 104 | + |> Enum.reduce_while(0, fn x, acc -> if x == acc + 1, do: {:cont, x}, else: {:halt, x} end) |
| 105 | + end |
| 106 | + |
| 107 | +end |
| 108 | + |
| 109 | +IO.inspect(Day05.part_1()) |
| 110 | +IO.inspect(Day05.part_2()) |
0 commit comments