Advent of Code 2022 - Day 6

Reasonably pleased with my solution. The bitstring packet problems are so well suited to Erlang/Elixir it’s almost not fair.

defmodule Day6 do
  defmodule Input do
    def sample_data(1), do: "mjqjpqmgbljsphdztnvjfqwrcgsmlb"

    def sample_data(2), do: "bvwbjplbgvbhsrlpgdmjqwftvncz"

    def sample_data(3), do: "nppdvjthqldpwncqszvftbrmjlhg"

    def sample_data(4), do: "nznrnfrfntjfmvfwmzdfjlvtqnbhcprsg"

    def sample_data(5), do: "zcfzfwzzqfrljwzlrfnpqdbhtmscgvjw"

    def load() do
      ReqAOC.fetch!({2022, 06, System.fetch_env!("AOC2022Session")})
    end
  end

  defmodule Solve do
    defp find_packet(input, n, i) do
      <<pkthd, pkttl::binary-size(n - 1), rest::binary>> = input

      if <<pkthd, pkttl::binary>> |> uniq_chars?() do
        i
      else
        find_packet(<<pkttl::binary, rest::binary>>, n, i + 1)
      end
    end

    defp uniq_chars?(<<>>), do: true

    defp uniq_chars?(<<a, rest::binary>>) do
      not String.contains?(rest, <<a>>) and uniq_chars?(rest)
    end

    def part1(input), do: find_packet(input, 4, 4)

    def part2(input), do: find_packet(input, 14, 14)
  end
end

Not an issue for the given data sets, but I did just realize this would crash and burn if there was no packet of unique elements of N length. I could handle it but, getting late.

1 Like

Today’s quiz is easy again. In order to leverage Stream and Enum functions, I just read the file into a charlist.

defmodule Day06 do
  def part1(input_path) do
    solve(input_path, 4)
  end

  def part2(input_path) do
    solve(input_path, 14)
  end

  defp solve(input_path, chunk_size) do
    input_path
    |> File.open!([:read, :charlist], &IO.read(&1, :eof))
    |> Stream.chunk_every(chunk_size, 1, :discard)
    |> Stream.map(&Enum.uniq/1)
    |> Stream.map(&length/1)
    |> Enum.find_index(& &1 == chunk_size)
    |> Kernel.+(chunk_size)
  end
end
6 Likes

After the convoluted puzzle input of day 5 I guess they wanted to give us a rest. Just one line :grinning:

{:ok, datastream} = File.read("input06")
datastream
|> String.graphemes
|> Enum.chunk_every(4, 1, :discard)
|> Enum.reduce_while(0, fn marker, pos ->
  case marker -- Enum.uniq(marker) do
    [] -> {:halt, pos + 4}
    _ -> {:cont, pos + 1}
  end
end)
|> IO.puts

datastream
|> String.graphemes
|> Enum.chunk_every(14, 1, :discard)
|> Enum.reduce_while(0, fn marker, pos ->
  case marker -- Enum.uniq(marker) do
    [] -> {:halt, pos + 14}
    _ -> {:cont, pos + 1}
  end
end)
|> IO.puts

This is standard elixir ? What are pkttl::binary, rest::binary?

1 Like

pkttl::binary and rest::binary are just variables assigned to sub-binaries via pattern matching. The uniq_chars? is just a helper function I made for this problem. I was really just talking about the pattern matching aspect on binaries.

I see, I got confused by the bitstring/binary syntax, thanks!

1 Like

Shortest solution I produced so far… when I solved it I did more explicit pattern matching to get the answer right, then shortened it up, first used take instead of patterns, then moved to binary pattern instead of grapheme pattern… here’s the final one.

defmodule AdventOfCode.Y2022.Day06 do
  alias AdventOfCode.Helpers.InputReader

  def input, do: InputReader.read_from_file(2022, 6)
  def run(data \\ input()), do: {marker(data, 4), marker(data, 14)}
  defp uniq?(xs, len), do: len == Enum.count(MapSet.new(:binary.bin_to_list(xs)))

  defp marker(<<_::bytes-size(1)>> <> xs = data, len, v \\ 0),
    do: (uniq?(:binary.part(data, 0, len), len) && v + len) || marker(xs, len, v + 1)
end

2 Likes

First part is beautiful and perfect for binary matching

defmodule AOC do

  defguard are_different(a, b, c, d) when
    a != b and a != c and a != d and
    b != c and b != d and
    c != d

  def traverse(string, acc \\ 0) do
    case string do
      <<a, b, c, d, _tail :: binary>> when are_different(a, b, c, d) ->
        acc + 4

      <<_, tail :: binary>> ->
        traverse(tail, acc + 1)
    end
  end

end

IO.inspect AOC.traverse IO.read :eof
5 Likes

I did use Stream.chunk_every as well. Makes this really short and sweet.

Solution
defmodule Day6 do
  def find_marker(text) do
    find_unique_character_string_of_length(text, 4)
  end

  def find_message_marker(text) do
    find_unique_character_string_of_length(text, 14)
  end

  defp find_unique_character_string_of_length(text, length) do
    {_list, index} =
      text
      |> String.to_charlist()
      |> Stream.chunk_every(length, 1, :discard)
      |> Stream.with_index(length)
      |> Enum.find(fn {list, _index} -> list |> Enum.uniq() |> length == length end)

    index
  end
end
4 Likes

A bit of metaprogramming with a help of Formulae.Combinators to build a guard

defmodule Lookup do
  import Formulae.Combinators, only: [combinations: 2]

  @count 14
  @args Enum.map(1..@count, &Macro.var(:"c#{&1}", nil))
  @guard @args
         |> combinations(2)
         |> Enum.map(&{:!=, [], &1})
         |> Enum.reduce(&{:and, [], [&2, &1]})

  def parse(input), do: do_parse(input, @count)

  defp do_parse(<<unquote_splicing(@args), _::binary>>, acc) when unquote(@guard), do: acc
  defp do_parse(<<_, rest::binary>>, acc), do: do_parse(rest, acc + 1)
end
3 Likes

You know you can use Macro.generate_unique_arguments for this

Yes, thanks, but I don’t really care about syntactic sugar which brings literally nothing to the table.

This is not syntactic sugar, this just avoids unnecessary atom generation in compile-time. And I’d suggest using quote instead of building AST from structures. quote preserves metadata and context for operators

Excuse me? elixir/macro.ex at v1.14.2 · elixir-lang/elixir · GitHub

I know. Why would I ever need metadata here?

Debugging

Hahaha, I thought since they had counter in metadata, they wouldn’t generate atoms in this function. My bad, I didn’t even think that this function was so broken

One obviously cannot generate AST for def foo(arg) without having arg atom, because its AST would contain {:arg, [], nil} I am not sure what do you mean under “broken.”

I prefer to write the code that works from scratch.

Did the second part with some metaprogramming

n = 14

defmodule Helper do

  def pairs([head | tail]) do
    pairs_with_head = Enum.map(tail, fn tail_item -> {head, tail_item} end)
    pairs_with_head ++ pairs(tail)
  end
  def pairs([]), do: []

end

defmodule AOC do

  vars = Macro.generate_unique_arguments(n, __MODULE__)
  guard =
    vars
    |> Helper.pairs()
    |> Enum.map(fn {left, right} -> quote do: unquote(left) != unquote(right) end)
    |> Enum.reduce(fn neq, expr -> quote do: unquote(neq) and unquote(expr) end)

  def traverse(string, acc \\ 0) do
    case string do
      <<unquote_splicing(vars), _tail :: binary>> when unquote guard ->
        acc + unquote(n)

      <<_, tail :: binary>> ->
        traverse(tail, acc + 1)
    end
  end

end

IO.inspect AOC.traverse IO.read :eof

Pow-pow, 1000x-developer rockstar ninja in this thread

Nah, I meant that {name, [counter: 1], context} and {name, [counter: 2], context} are different variables and are treated as different variables.

So, instead of generating 1000 atoms for Macro.generate_unique_arguments(1000, __MODULE__), it could just use this :arg as a name atom for each variable and just have different [counter: counter] in metadata

The only problem with this solution is that code inspection will suck, since all variables are named exactly the same. But this is a known issue, since contexts are simply ignored in all AST-to-String functions

Here is my solution of this easy day. As usual I prefer expressive readable code.

defmodule AOCHelpers do
  def find_marker(str, chunk_length) do
    chunks =
      str
      |> String.to_charlist()
      |> Enum.chunk_every(chunk_length, 1, :discard)
      |> Enum.with_index()

    {marker, idx} =
      chunks
      |> Enum.map(fn {chunk, idx} -> {Enum.uniq(chunk), idx} end)
      |> Enum.filter(fn {chunk, _idx} -> length(chunk) == chunk_length end)
      |> Enum.at(0)

    {marker, idx + chunk_length}
  end
end
1 Like

This one was very easy, but I would love to hear what I can improve on

# window_size 4
# window_overlap 1
# index + window_size = answer
input
|> String.to_charlist()
|> Enum.chunk_every(4, 1, :discard)
|> Enum.with_index()
|> Enum.reduce_while(0, fn {window, index}, marker_index ->
  if Enum.uniq(window) |> length() == 4 do
    {:halt, marker_index + index + 4}
  else
    {:cont, marker_index}
  end
end)