Advent of Code 2020 - Day 5

lud · December 5, 2020, 12:35pm

Today I wanted to play with bit syntax and bitstrings, it was fun

  def read_file!(file, _part) do
    Input.stream_file_lines(file, trim: true)
  end

  def parse_input!(input, _part) do
    input
  end

  def part_one(problem) do
    problem
    |> Stream.map(&seat_id/1)
    |> Enum.max()
  end

  def part_two(problem) do
    problem
    |> Stream.map(&seat_id/1)
    |> Enum.sort()
    |> find_self_seat
  end

  def seat_id(letters) do
    partial = for <<char::8 <- letters>>, into: <<>>, do: cast_bit(char)
    :binary.decode_unsigned(<<0::6, partial::bitstring>>)
  end

  def cast_bit(?F), do: <<0::1>>
  def cast_bit(?L), do: <<0::1>>
  def cast_bit(?B), do: <<1::1>>
  def cast_bit(?R), do: <<1::1>>

  def find_self_seat([prev, next | _]) when next - prev == 2 do
    next - 1
  end

  def find_self_seat([_ | next]) do
    find_self_seat(next)
  end

egze · December 5, 2020, 1:10pm

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

Full code

EDIT: hmm, it’s actually not working correctly. Will fix later

adamu · December 5, 2020, 1:58pm

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

bodgix · December 5, 2020, 2:18pm

I also didn’t figure out the trick but still happy with my solution. Nothing fancy just pattern matching and recursion

github.com

bodgix/aoc2020/blob/main/day5.exs

defmodule Aoc2020.Day5 do
  @moduledoc """
  Module with helpers for the day5
  """

  @rows 0..127
  @cols 0..7
  @data "day5.txt"

  def part1() do
    input_stream()
    |> Enum.max()
    |> IO.inspect(label: "Part1")
  end

  def part2() do
    input_stream()
    |> Enum.sort()
    |> Enum.chunk_every(2)
    |> Enum.find(fn

This file has been truncated. show original

stevensonmt · December 5, 2020, 4:35pm

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.

adamu · December 5, 2020, 4:37pm

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

JEG2 · December 5, 2020, 8:07pm

Really enjoying the puzzles so far this year. Here’s my Day 5:

github.com

JEG2/advent_of_code_2020/blob/main/day_05/boarding.exs

defmodule Boarding do
  def run(args) do
    {opts, [path]} = OptionParser.parse!(args, strict: [part_2: :boolean])

    if Keyword.get(opts, :part_2) do
      find_seat(path)
    else
      find_highest_id(path)
    end
  end

  def find_seat(path) do
    path
    |> read_boarding_passes
    |> locate_seats
    |> find_missing
  end

  def find_highest_id(path) do
    path

This file has been truncated. show original

ricardo-h · December 5, 2020, 10:07pm

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

Aetherus · December 6, 2020, 1:01am

Great trick! 1-bit binary!

deadbeef · December 6, 2020, 4:10am

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 https://www.geeksforgeeks.org/find-the-missing-number/
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

egze · December 6, 2020, 9:20am

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

adamu · December 7, 2020, 2:33am

Saw a Raku implementation, it’s pretty nice:

github.com

gugod/advent-of-code/blob/master/2020/5/solve.raku

my @seats = "input".IO.lines.map(
    -> $line is copy {
        $line ~~ tr/FBLR/0101/;
        $line.parse-base(2);
    }
);

# Part 1
say @seats.max;

# Part 2
my $seats = @seats.Set;
say (@seats.min..@seats.max).first(-> $id { $id ∉ $seats });

code-shoily · December 7, 2020, 2:39am

I learned very recently about Raku, along with its relationship with Perl. From a brief look, I realized seasoned Raku users would be quite swift at solving AoC puzzles