This topic is about Day 5 of the Advent of Code 2020 .
Thanks to @egze, we have a private leaderboard:
https://adventofcode.com/2020/leaderboard/private/view/39276
The join code is:
39276-eeb74f9a
This topic is about Day 5 of the Advent of Code 2020 .
Thanks to @egze, we have a private leaderboard:
https://adventofcode.com/2020/leaderboard/private/view/39276
The join code is:
39276-eeb74f9a
ARGH, I spent way too much time looking for “the catch,” the reason it couldn’t as easy as it looked.
I guess you’ve found the same solution as mine.
WARNING: Huge Exploits!!
Don’t look at my solution until you find your own.
#!/usr/bin/env elixir
"day5.txt"
|> File.stream!()
|> Enum.map(&String.trim/1)
|> Enum.map(fn s ->
s
|> String.replace(["F", "L"], "0", global: true)
|> String.replace(["B", "R"], "1", global: true)
|> String.to_integer(2)
end)
|> Enum.max()
|> IO.puts()
#!/usr/bin/env elixir
"day5.txt"
|> File.stream!()
|> Enum.map(&String.trim/1)
|> Enum.map(fn s ->
s
|> String.replace(["F", "L"], "0", global: true)
|> String.replace(["B", "R"], "1", global: true)
|> String.to_integer(2)
end)
|> Enum.sort()
|> Enum.chunk_every(2, 1, :discard)
|> Enum.find(&match?([a, b] when a != b - 1, &1))
|> Enum.reduce(&+/2)
|> Kernel.div(2)
|> IO.puts()
I’m still working on the legitimacy of this approach.
Well… same general idea.
There must be a more efficient way to do this, but the meat of it is:
def seat_id(boarding_pass) do
boarding_pass
|> String.graphemes()
|> Enum.map(&char_to_digit/1)
|> Enum.reverse()
|> Enum.with_index()
|> Enum.reduce(0, fn {digit, exp}, acc -> acc + Bitwise.bsl(digit, exp) end)
end
def char_to_digit(str) do
case str do
"B" -> 1
"F" -> 0
"R" -> 1
"L" -> 0
end
end
Then for part 2, I checked the upper and lower bounds real quick, then:
Enum.to_list(89..989) -- Enum.map(parse_input(filename), &seat_id/1)
Kinda miss Ruby’s String#tr
.
Here’s how I attempted it. Followed the boarding pass and walked.
Wow, why didn’t this occur to me! Awesome solve! Thanks for sharing.
For me, the hint is the 8
in
multiply the row by 8, then add the column.
Multiplying by 8 is equivalent to shift 3 bits to the left, and guess how many bits is needed to represent the all the column numbers?
Today imitating Perl “write-only” style:
defmodule Day05PerlLike do
import Enum, only: [map: 2, max: 1, sort: 1]
import String, only: [replace: 3, split: 1, to_integer: 2]
def p1, do: max(map(input(), &seat_id/1))
def p2, do: find(sort(map(input(), &seat_id/1)))
defp input, do: split(File.read!("data/05"))
defp seat_id(bp), do: to_integer(replace(bp, ~r/./, &((&1 in ~w/F L/ && "0") || "1")), 2)
defp find([sp, sn | ss]), do: (sp + 2 == sn && sp + 1) || find([sn | ss])
end
I feel the obfuscatedness (is that even a word?) of Perl code is way beyond the level of your code
Nothing fancy. I’m not happy with my part2.
defmodule Day05 do
def readinput() do
File.read!("5.input.txt")
|> String.split("\n")
|> Enum.map(&String.graphemes/1)
end
def part1(input \\ readinput()) do
input
|> Enum.map(&findseat/1)
|> Enum.max()
end
def part2(input \\ readinput()) do
ids =
input
|> Enum.map(&findseat/1)
|> Enum.sort()
findmissing(MapSet.new(ids), List.first(ids), List.last(ids))
end
def findmissing(_mids, curid, maxid) when curid > maxid, do: :error
def findmissing(mids, curid, maxid) do
if curid not in mids and (curid - 1) in mids and (curid + 1) in mids do
curid
else
findmissing(mids, curid + 1, maxid)
end
end
def findseat(assignment, row \\ 0..127, col \\ 0..7)
def findseat([], row, col), do: row.first * 8 + col.first
# just makes writing the test cases easier
def findseat(assignment, row, col) when is_binary(assignment),
do: findseat(String.graphemes(assignment), row, col)
def findseat([letter | assignment], row, col) do
case letter do
"F" -> findseat(assignment, lower(row), col)
"B" -> findseat(assignment, upper(row), col)
"R" -> findseat(assignment, row, upper(col))
"L" -> findseat(assignment, row, lower(col))
end
end
def lower(range) do
range.first..(range.first + div(range.last - range.first, 2))
end
def upper(range) do
(range.first + div(1 + range.last - range.first, 2))..range.last
end
end
I felt like there was a some “binary hack” one could do here, 127 and 7 is not just random numbers
Anyway, I did this before my daily coffee so my solution is a little longer but I’m still happy with it.
defmodule Aoc2020.Day05 do
def part1(input) do
input
|> Stream.map(&seat_id/1)
|> Enum.max()
end
def part2(input) do
input
|> Stream.map(&seat_id/1)
|> Enum.sort()
|> Enum.drop_while(&(&1 <= 7))
|> find_gap()
end
def find_gap([a, b | rest]) when b - a == 2, do: a + 1
def find_gap([a, b | rest]) when b - a == 1, do: find_gap([b | rest])
def seat_id(spec) when is_binary(spec) do
{rows, cols} = String.split_at(spec, 7)
seat_id({decode(rows, ?F, ?B, {0, 127}), decode(cols, ?L, ?R, {0, 7})})
end
def seat_id({row, col}) do
row * 8 + col
end
def decode(<<lft>>, lft, _rgt, {min, _max}), do: min
def decode(<<rgt>>, _lft, rgt, {_min, max}), do: max
def decode(<<lft, rest::binary()>>, lft, rgt, {min, max}),
do: decode(rest, lft, rgt, {min, max - mid(min, max)})
def decode(<<rgt, rest::binary()>>, lft, rgt, {min, max}),
do: decode(rest, lft, rgt, {min + mid(min, max), max})
defp mid(min, max), do: div(max - min, 2) + 1
def input_stream(path) do
File.stream!(path)
|> Stream.map(&parse/1)
end
defp parse(line), do: String.trim(line)
end
357 = Aoc2020.Day05.seat_id({44, 5})
357 = Aoc2020.Day05.seat_id("FBFBBFFRLR")
567 = Aoc2020.Day05.seat_id({70, 7})
567 = Aoc2020.Day05.seat_id("BFFFBBFRRR")
119 = Aoc2020.Day05.seat_id({14, 7})
119 = Aoc2020.Day05.seat_id("FFFBBBFRRR")
820 = Aoc2020.Day05.seat_id({102, 4})
820 = Aoc2020.Day05.seat_id("BBFFBBFRLL")
input = Aoc2020.Day05.input_stream("input.txt")
Aoc2020.Day05.part1(input)
|> IO.inspect(label: "part1")
Aoc2020.Day05.part2(input)
|> IO.inspect(label: "part2")
Day 5 was pretty fun!
defmodule Day5 do
def one do
File.read!("inputs/five.txt")
|> String.split("\n")
|> Enum.map(&parse/1)
|> Enum.max()
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
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
end
Yes!
Your solution is almost the same as mine, except that I didn’t split the strings into 2 parts. The row * 8
part is tricky.
Same idea as some above, but when I was solving I wanted to see if I could use Bitwise
at all. Ended up using it to “construct” the id by reducing it to the value. Shift left for each character, adding a bit at the end if it’s “B” or “R”. No need to “multiple 8, then add col” since the row/col are already in “position”, bitwise.
reduce_while
and MapSet
to locate pairs like 2SUM (so you can stream and not have to sort). However, I felt the sort + function matches were more compact for the challenge.(apologies if any terminology is wrong, new to Elixir)
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
@spec part_two(passes :: Enumerable.t(String.t())) :: integer | nil
def part_two(passes) do
passes
|> Stream.map(&seat_id/1)
|> Enum.sort()
|> find_middle_seat()
end
defp seat_id(partition) do
partition
|> String.graphemes()
|> Enum.reduce(0, fn
"B", sum -> sum <<< 1 ||| 1
"R", sum -> sum <<< 1 ||| 1
_, sum -> sum <<< 1
end)
end
# Assumes the list is sorted
defp find_middle_seat([a, b | _tail]) when b - a == 2, do: a + 1
defp find_middle_seat([_a, b | tail]), do: find_middle_seat([b | tail])
defp find_middle_seat(_), do: nil
end
I did something unusual for this one: I implemented the bording pass code as a sigil/struct with a custom Inspect
implementation, before solving the problem itself.
Wow, that’s awesome! Finally, we have someone doing metaprogramming!
Not as clever as the folks above, but I like it
defmodule Aoc.Y2020.D5 do
use Aoc.Boilerplate,
transform: fn raw -> raw |> String.split() end
def part1(input \\ processed()) do
input
|> Enum.reduce(0, &max_seat_id_reducer/2)
end
def part2(input \\ processed()) do
input
|> Enum.map(&get_seat_id/1)
|> Enum.sort()
|> Enum.reduce_while(0, fn x, acc ->
cond do
acc == 0 -> {:cont, x}
x - 1 == acc -> {:cont, x}
:else -> {:halt, x - 1}
end
end)
end
defp max_seat_id_reducer(seat, acc) do
seat_id = get_seat_id(seat)
if seat_id >= acc, do: seat_id, else: acc
end
def get_seat_id(seat) do
{row, col, _, _} =
seat
|> String.graphemes()
|> Enum.reduce({0, 0, 0..127, 0..7}, fn char, {row, col, row_range, col_range} ->
case char do
"F" ->
first..last = row_range
new_row_last = floor((first + last) / 2)
{first, col, first..new_row_last, col_range}
"B" ->
first..last = row_range
new_row_first = round((first + last) / 2)
{new_row_first, col, new_row_first..last, col_range}
"R" ->
first..last = col_range
new_col_first = round((first + last) / 2)
{row, new_col_first, row_range, new_col_first..last}
"L" ->
first..last = col_range
new_col_last = floor((first + last) / 2)
{row, first, row_range, first..new_col_last}
end
end)
row * 8 + col
end
end
For Part 2:
Solution without sorting
computed minSeat, maxSeat, seatTotal
Missing Seat = sum(minSeat:maxSeat) - seatTotal
defmodule Day5 do
defp getIndex(_charList, index, index) do
index
end
defp getIndex([headChar | tail], minIdx, maxIdx) when headChar == "F" or headChar == "L" do
getIndex(tail, minIdx, minIdx + div(maxIdx - minIdx + 1, 2) - 1)
end
defp getIndex([headChar | tail], minIdx, maxIdx) when headChar == "B" or headChar == "R" do
getIndex(tail, minIdx + div(maxIdx - minIdx + 1, 2), maxIdx)
end
defp seatFun([], seatIdAcc) do
seatIdAcc
end
defp seatFun([head | tail], seatIdAcc) do
{rowStr, colStr} = String.split_at(head, 7)
row = getIndex(String.graphemes(rowStr), 0, 127)
col = getIndex(String.graphemes(colStr), 0, 7)
seatFun(tail, [row * 8 + col | seatIdAcc])
end
defp sumAtoB(a, b) do
div(b * (b + 1) - (a - 1) * a, 2)
end
defp getMinMaxTotal([], seatAcc) do
seatAcc
end
defp getMinMaxTotal([head | tail], {seatMinAcc, seatMaxAcc, seatTotalAcc}) do
getMinMaxTotal(tail, {min(head, seatMinAcc), max(head, seatMaxAcc), head + seatTotalAcc})
end
def main(part) do
seatList =
File.read!("day5.txt")
|> String.split("\n", trim: true)
|> seatFun([])
case part do
1 ->
Enum.max(seatList)
2 ->
{minSeat, maxSeat, seatTotal} = getMinMaxTotal(seatList, {10_000_000, 0, 0})
sumAtoB(minSeat, maxSeat) - seatTotal
end
end
end