-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathday5-puzzle1.txt
67 lines (48 loc) · 2.27 KB
/
day5-puzzle1.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
--- Day 5: Binary Boarding ---
Your puzzle input contains all nearby boarding passes.
You hope to find your seat by elimination.
This airline uses *binary space partitioning* to seat people.
A seat is specified like FBFBBFFRLR (10 characters)
where:
F => "front"
B => "back"
L => "left"
R => "right".
The first 7 characters will each be F or B;
Together these specify exactly one of the *128* rows on the plane (numbered 0 through 127).
Each letter tells you which half of a region the given seat is in.
Start with the whole list of rows;
Letter 1: indicates
if the seat is in the *front* (0 through 63)
or the *back* (64 through 127).
Letter 2: indicates
which half of that region the seat is in,
and so on until you're left with exactly one row.
For example, consider just the first seven characters of FBFBBFFRLR:
Start by considering the whole range, rows 0 through 127.
F means to take the *lower half*, keeping rows 0 through 63.
B means to take the *upper half*, keeping rows 32 through 63.
F means to take the *lower half*, keeping rows 32 through 47.
B means to take the *upper half*, keeping rows 40 through 47.
B keeps rows 44 through 47.
F keeps rows 44 through 45.
The final F keeps the lower of the two, *row 44*.
The last three characters will be either L or R;
these specify exactly one of the *8 columns* of seats on the plane (numbered 0 through 7).
The same process as above proceeds again, this time with only three steps.
L means to keep the *lower half*, while R means to keep the *upper half*.
For example, consider just the last 3 characters of FBFBBFFRLR:
Start by considering the whole range, columns 0 through 7.
R means to take the *upper half*, keeping columns 4 through 7.
L means to take the *lower half*, keeping columns 4 through 5.
The final R keeps the upper of the two, *column 5*.
So, decoding FBFBBFFRLR reveals that it is the seat at *row 44*, *column 5*.
Every seat also has a unique *seat ID*:
multiply the row by 8, then add the column.
In this example, the seat has ID 44 * 8 + 5 = *357*.
Here are some other boarding passes:
BFFFBBFRRR: row 70, column 7, seat ID 567.
FFFBBBFRRR: row 14, column 7, seat ID 119.
BBFFBBFRLL: row 102, column 4, seat ID 820.
As a sanity check, look through your list of boarding passes.
What is the highest seat ID on a boarding pass?