Day 5. Binary Boarding
Problem statement
https://adventofcode.com/2020/day/5 (mirror)My solution
Another very simple problem.
We need a method that will parse the boarding pass ID from a string to a correspoding integer. But if we look closely at the format of the string, it is just a binary number, where instead of ones we have characters B or R, and instead of zeroes we have characters F or L.
So for example, consider boarding pass BFFFFFFLLR:
- first character is
B, so the most significant bit is 1, - second character is
F, so the next bit is 0, - […]
- final chacater is
R, so the least significant bit is 1.
So BFFFFFFLLR is equivalent to 1000000001 in binary, or 2^9 + 2^0 = 513 in decimal.
Solving Part A is trivial, we just need to store the maximal boarding pass number seen so far, compare it to current boarding pass and overwrite the memory if current ID is greater.
To solve Part B, i.e. to find a missing number, we will use the fact that the sum of all consecutive numbers from min to max can be calculated with formula:
sum = (how many numbers there are) * (value of an average number) = (max - min + 1) * (max + min) / 2.
So in a single for loop over all boarding passes:
- we find the maximal and minimal boarding pass ID,
- we also calculate the sum of all present IDs.
If we subtract the actual sum of all present IDs from the expected sum (based on the minimal and maximal ID), we will find the missing value.