Alright guys, couldn’t resist and optimised my solution with the binary trick.
I think nobody yet used Integer.undigits/2
def get_seat_id(seat) do
seat
|> String.graphemes()
|> Enum.map(fn char -> if char in ["F", "R"], do: 1, else: 0 end)
|> Integer.undigits(2)
end
EDIT: hmm, it’s actually not working correctly. Will fix later 
This is great. I’m a bit disappointed in myself that I didn’t work it out. All that halving, 128, 8, multiplying by 8, the encoding being called binary space partitioning. I was like “this sure feels like binary” - it didn’t occur to me though that the 3-bit column was just bitshifted and the whole thing could be parsed directly to an integer. 
Instead I diligently parsed it according to the “rules”:
row =
Enum.reduce(row_spec, {0, 128}, fn
?F, {front, 2} -> front
?B, {front, 2} -> front + 1
?F, {front, count} -> {front, div(count, 2)}
?B, {front, count} -> {front + div(count, 2), div(count, 2)}
end)
And for part 2, I zipped the list of IDs with itself shifted by 1, to find the first non-sequential ID:
def find_seat([_ | next_seats] = seats) do
Stream.zip(seats, next_seats)
|> Enum.find(fn {seat, next} -> next - seat > 1 end)
|> elem(0)
|> Kernel.+(1)
end
Full solution on Github
I also didn’t figure out the trick but still happy with my solution. Nothing fancy just pattern matching and recursion
Yeah, that bitshift by the same number of places as the column storage in retrospect is an obvious thing.
defmodule Day5 do
@input File.stream!("lib/input.txt")
@process_input @input
|> Stream.map(&String.trim(&1))
|> Stream.map(
&String.replace(&1, ["F", "B", "L", "R"], fn c ->
case c do
"F" -> "0"
"B" -> "1"
"L" -> "0"
"R" -> "1"
end
end)
)
|> Stream.map(&String.split_at(&1, 7))
|> Stream.map(fn {a, b} -> {Integer.parse(a, 2), Integer.parse(b, 2)} end)
|> Enum.map(fn {{a, _}, {b, _}} -> a * 8 + b end)
def highest_seat do
@process_input
|> Enum.max()
end
def sort_tickets do
@process_input
|> Enum.sort()
end
def find_gap do
sort_tickets()
|> Stream.chunk_every(2, 1, :discard)
|> Stream.filter(fn [a, b] -> b - a != 1 end)
|> Enum.reduce(1, fn [a, _], acc -> acc + a end)
end
end
IO.inspect(Day5.highest_seat())
IO.inspect(Day5.find_gap())
I can see where find is more efficient than my filter approach since it would be short-circuiting.
How about this for the binary parsing @Aetherus, @aaronnamba @egze (looks like @lud was almost there too)?
def char_to_bit(c) when c in 'FL', do: <<0::1>>
def char_to_bit(c) when c in 'BR', do: <<1::1>>
def seat_id(boarding_pass \\ "FBFBBFFRLR") do
<<id::integer-10>> = for <<char <- boarding_pass>>, into: <<>>, do: char_to_bit(char)
id
end
Really enjoying the puzzles so far this year. Here’s my Day 5:
https://github.com/JEG2/advent_of_code_2020/blob/main/day_05/boarding.exs
The bit manipulation solution is awesome, definitely the most efficient - O(n)
I get a O(n log m) solution
defmodule Advent.Day5 do
@rows 0..128 |> Enum.map(fn o -> o end)
@cols [0,1,2,3,4,5,6,7]
def start(part, file \\ "/tmp/input.txt")
def start(:part1, file), do:
File.stream!(flie)
|> Enum.reduce(0, fn o, acc -> max(acc, find_seat_id(to_charlist(o), @rows, @cols)) end)
def start(:part2, file), do:
File.stream!(file)
|> Enum.map(fn o -> find_seat_id(to_charlist(o), @rows, @cols) end)
|> Enum.sort()
|> Enum.reduce_while(-1, fn o, acc ->
cond do
acc == -1 -> {:cont, o}
o - acc == 1 -> {:cont, o}
true -> {:halt, o - 1}
end
end)
def find_seat_id(_, [rows], [cols]), do: rows * 8 + cols
def find_seat_id([v|t], rows, cols) when v in [?F,?B], do:
find_seat_id(t, split_half(rows) |> elem(v == ?F && 0 || 1), cols)
def find_seat_id([v|t], rows, cols), do:
find_seat_id(t, rows, split_half(cols) |> elem(v == ?L && 0 || 1))
defp split_half(lst), do: Enum.split(lst, div(length(lst), 2))
end
I was inspired by @akagrawal’s solution to find the missing id by taking advantage of the input ids being a sequence. I was curious if there was a way to do so still using just Bitwise operators. Turns out there is! Credit to the source Find the Missing Number - GeeksforGeeks
We can determine the missing value if we XOR the XOR of the entire sequence with the XOR of all the given values, i.e. where a_m is the missing value
full = a_min ^ ... ^ a_m ^ ... ^ a_max
sub = a_min ^ ... ^ a_m-1 ^ a_m+1 ^ ... ^ a_max
a_m = sub ^ full
Here’s my updated solution, just for fun
defmodule Advent.Y2020.D05 do
use Bitwise, only_operators: true
@spec part_one(passes :: Enumerable.t(String.t())) :: integer
def part_one(passes) do
passes
|> Stream.map(&seat_id/1)
|> Enum.max()
end
# NOTE: this strategy assumes there is exactly one missing id within a
# contiguous set of ids (and ids are all positive)
@spec part_two(passes :: Enumerable.t(String.t())) :: integer
def part_two(passes) do
passes
|> Stream.map(&seat_id/1)
|> Enum.reduce({:infinity, -1, 0}, fn id, {min, max, sum} ->
min = if id < min, do: id, else: min
max = if id > max, do: id, else: max
sum = sum ^^^ id
{min, max, sum}
end)
|> (fn {min, max, sum} ->
sum ^^^ Enum.reduce(min..max, 0, &(&1 ^^^ &2))
end).()
end
defp seat_id(partition) do
partition
|> String.graphemes()
|> Enum.reduce(0, fn c, sum ->
sum = sum <<< 1
if c == "B" || c == "R", do: sum ||| 1, else: sum
end)
end
end
Just mixed up the character for 1.
def get_seat_id(seat) do
seat
|> String.graphemes()
|> Enum.map(fn char -> if char in ["B", "R"], do: 1, else: 0 end)
|> Integer.undigits(2)
end