Advent Of Code 2022 - Day 3

Learning Questions & Discussions Coding Challenges
,
1

Probably not the most efficient implementation, because part 1 took >1 ms and part 2 >4ms, but the code was simple enough.

  def part1(input) do
    input
    # ...
    |> Enum.map(fn {a, b} -> hd(a -- a -- b) end)
    |> Enum.map(&score/1)
    |> Enum.sum()
  end

  defp score(<<lower::utf8>>) when lower in ?a..?z, do: lower - ?a + 1
  defp score(<<upper::utf8>>) when upper in ?A..?Z, do: upper - ?A + 27
2

It was simple, today’s one. Not sure of the performance though. Basically it was a game of sets for me.

3

I went with charlists and MapSets.

...
  |> Enum.map(&to_charlist/1)
  |> Enum.map(&MapSet.new/1)
  |> Enum.reduce(&MapSet.intersection/2)
...
4 Likes
4

Performance on my fingertips

defmodule AOC do

  def priority(x) when x >= ?a, do: x - ?a + 1
  def priority(x), do: x - ?A + 27

  def traverse(string, line \\ [], group \\ [], score \\ 0) do
    case string do
      x when x in ["\n", ""] ->
        score + score_group([line | group])

      <<"\n", tail :: binary()>> ->
        case group do
          [_, _] ->
            traverse(tail, [], [], score_group([line | group]) + score)

          _ ->
            traverse(tail, [], [line | group], score)
        end

      <<char, tail :: binary()>> ->
        traverse(tail, [priority(char) | line], group, score)
    end
  end

  defp score_group([one, two, three]) do
    founds = unquote {:{}, [], List.duplicate(0, 52)}
    founds = score_one(one, founds)
    founds = score_two(two, founds)
    score_three(three, founds)
  end

  defp score_one([head | tail], founds) do
    score_one(tail, :erlang.setelement(head, founds, 1))
  end
  defp score_one([], founds), do: founds

  defp score_two([head | tail], founds) when :erlang.element(head, founds) == 1 do
    score_two(tail, :erlang.setelement(head, founds, 2))
  end
  defp score_two([_ | tail], founds) do
    score_two(tail, founds)
  end
  defp score_two(_, founds), do: founds

  defp score_three([head | tail], founds) when :erlang.element(head, founds) == 2 do
    head
  end
  defp score_three([_ | tail], founds) do
    score_three(tail, founds)
  end

end

IO.inspect AOC.traverse IO.read :eof
1 Like
5

Did the same charlists and MapSets.

6

I started with a MapSet but ended up with a :binary.match/2:

# split the rucksack into two equal compartments
{head, tail} = line |> String.split_at(line |> String.length() |> div(2))

head
|> String.codepoints()
|> Enum.reduce_while(:ok, fn code, _ ->
  case :binary.match(tail, code) do
    {_, 1} -> {:halt, code |> priority()}
    :nomatch -> {:cont, :ok}
  end
end)
4 Likes
7

I outsourced the heavy lifting to MapSet.intersect and charlists as well :slight_smile:

I also realized you could just map all letters to their priority at the start so you only have to deal with integers later.

Function for converting char → priority

item_priority = fn
  item when item >= ?a and item <= ?z -> item - ?a + 1
  item -> item - ?A + 27
end
1 Like
8

I just pipe to the bitter end :sweat_smile:

defmodule Day03 do
  @priorities [?a..?z, ?A..?Z] |> Enum.concat() |> Enum.with_index(1) |> Map.new()

  def part1(input_path) do
    input_path
    |> File.stream!()
    |> Stream.map(&String.trim/1)
    |> Stream.map(&:binary.bin_to_list/1)
    |> Stream.map(&Enum.split(&1, div(length(&1), 2)))
    |> Stream.map(fn {f, r} ->
      Enum.uniq(f -- f -- r)
    end)
    |> Stream.flat_map(fn intersection ->
      Enum.map(intersection, &@priorities[&1])
    end)
    |> Enum.sum()
  end

  def part2(input_path) do
    input_path
    |> File.stream!()
    |> Stream.map(&String.trim/1)
    |> Stream.map(&:binary.bin_to_list/1)
    |> Stream.map(&MapSet.new/1)
    |> Stream.chunk_every(3)
    |> Stream.flat_map(fn group ->
      Enum.reduce(group, &MapSet.intersection/2)
    end)
    |> Stream.map(&@priorities[&1])
    |> Enum.sum()
  end
end
3 Likes
9

Nice touch to download the input from the interwebs :slight_smile:

3 Likes
10

Today’s was strangely easy, especially for languages like Elixir with piping and sets. Like others, I also used charlist and MapSet to do everything. Although, I had to learn up on some charlist bits.

Livebook notebook: advent-of-code/advent_of_code_2022.livemd at main · bmitc/advent-of-code · GitHub

defmodule Day3 do
  @moduledoc """
  Solutions for Day 3
  """

  @typedoc """
  Represents a single compartment
  """
  @type compartment() :: charlist()

  @typedoc """
  Represents a rucksack which consists of two equally sized compartments
  """
  @type rucksack() :: {
          first_compartment :: compartment(),
          second_compartment :: compartment()
        }

  @doc """
  Parse a rucksack string into a rucksack 2-tuple for the two
  compartments
  """
  @spec parse_rucksack(String.t()) :: rucksack()
  def parse_rucksack(data) do
    # Note that compartments are specified to be of the same length
    data
    |> String.to_charlist()
    |> Enum.split(div(String.length(data), 2))
  end

  @doc """
  A list of all the rucksacks
  """
  @spec rucksacks() :: [rucksack()]
  def rucksacks() do
    Utilities.readDataStream(3)
    |> Enum.map(&parse_rucksack/1)
  end

  @doc """
  Given a charlist of a single element, calculate its priority according to the
  rubric of a -> z has priority 1 -> 26 and A -> Z has priority 27 -> 52
  """
  @spec assign_item_priority(charlist()) :: pos_integer()
  def assign_item_priority([char] = charlist) do
    # Note that all codepoints after 'a' and 'A' are sequential up to 'z'
    # and 'Z', respectively.
    if Utilities.is_lowercase(to_string(charlist)) do
      # Assigns a -> z the priority 1 -> 26 by normalizing against the codepoint for 'a'
      char - ?a + 1
    else
      # Assigns A -> Z the priority 27 -> 52 by normalizing against the codepoint for 'A'
      char - ?A + 27
    end
  end

  def part_one() do
    rucksacks()
    # Convert each rucksack's compartments into sets and then find their
    # intersection and then assign a priority to that single element in
    # the intersection
    |> Enum.map(fn {first, second} ->
      MapSet.intersection(MapSet.new(first), MapSet.new(second))
      # Strip away the MapSet, leaving a charlist
      |> MapSet.to_list()
      |> assign_item_priority()
    end)
    # Sum up all the priorities, with one priority from each rucksack
    |> Enum.sum()
  end

  def part_two() do
    rucksacks()
    # Chunk every three rucksacks into a group
    |> Enum.chunk(3)
    # Convert all rucksacks in the group to sets and find their intersection
    # and then assign a priority to that single element in the intersection
    |> Enum.map(fn chunk ->
      chunk
      |> Enum.map(fn {first, second} ->
        (first ++ second)
        |> MapSet.new()
      end)
      |> Enum.reduce(&MapSet.intersection/2)
      # Strip away the MapSet, leaving a charlist
      |> MapSet.to_list()
      |> assign_item_priority()
    end)
    # Sum up all the priorities, with one priority from each group
    |> Enum.sum()
  end
end
11

This certainly was a quick one. Having used essentially :binary.bin_to_list + Enum.find for both parts.

Solution 
defmodule Day3 do
  def sum_priorities(text) do
    text
    |> String.split("\n")
    |> Enum.reject(&(&1 == ""))
    |> Enum.map(&rucksack_priority/1)
    |> Enum.sum()
  end

  def sum_group_priorities(text) do
    text
    |> String.split("\n")
    |> Enum.reject(&(&1 == ""))
    |> Enum.chunk_every(3)
    |> Enum.map(&group_priority/1)
    |> Enum.sum()
  end

  defp rucksack_priority(contents) do
    compartments_size = div(byte_size(contents), 2)
    first = :binary.bin_to_list(contents, 0, compartments_size)
    second = :binary.bin_to_list(contents, compartments_size, compartments_size)
    first |> Enum.find(fn char -> char in second end) |> priority()
  end

  defp group_priority([a, b, c]) do
    a = :binary.bin_to_list(a)
    b = :binary.bin_to_list(b)
    c = :binary.bin_to_list(c)
    a |> Enum.find(fn char -> char in b and char in c end) |> priority()
  end

  defp priority(c) when c in ?a..?z, do: c - ?a + 1
  defp priority(c) when c in ?A..?Z, do: c - ?A + 27
end
1 Like
12

Thanks! I made a thing in case anyone else wants to use it:

Mix.install([
  {:req_aoc, github: "mcrumm/req_aoc", ref: "28e3813"}
])

ReqAOC.fetch!({2022, 03, System.fetch_env!("LB_AOC_SESSION")})
# ==> "..."
4 Likes
13

That’s a fantastic tool! Thanks for sharing. I’m definitely using that to speed up my setup for each day.

14

I just want to add that for someone being new to Elixir, it’s so cool to do the Advent Of Code riddles, then compare my implementation with yours. Had some funny “AHA!” moments when I’ve discovered stuff like :binary.bin_to_list.

So keep sharing your solutions, even if they seem trivial. I surely appreciate them :slight_smile:

3 Likes
15

Didn’t reach for MapSet until the second part. Everyone’s use of codepoints to handle priorities is impressive!

16

TIL :binary.bin_to_list - There is a ton of cool stuff in the Erlang stdlib it feels like I’m always discovering something new!

I usually don’t do AoC because I convince myself that writing code for work is more important or something, but so far it’s been a nice exercise, I am only optimizing for fun, and I am learning new things!

3 Likes
17

Same idea as others: MapSets and intersections. I ended up transforming part 1 into the same problem as part 2, just with a different group size. So they shared the same solving function

18

Same solution as many for part one and two, using String.codepoints and MapSet.intersection!

19

Some ideas from @Aetherus solution.

part 1

start = System.monotonic_time(:microsecond)

File.stream!("input.txt")
|> Stream.map(&String.trim/1)
|> Stream.map(&:binary.bin_to_list/1)
|> Stream.map(&Enum.split(&1, div(length(&1), 2)))
|> Stream.map(fn {f, r} -> hd(f -- f -- r) end)
|> Stream.map(fn
  x when x >= ?a and x <= ?z -> x - ?a + 1
  x when x >= ?A and x <= ?Z -> x - ?A + 27
end)
|> Enum.sum()
|> tap(fn sum -> IO.puts "Sum of priorities: #{sum}" end)

elapsed = System.monotonic_time(:microsecond) - start
IO.puts "Job done in #{elapsed} µs"

part 2

start = System.monotonic_time(:microsecond)

File.stream!("input.txt")
|> Stream.map(&String.trim/1)
|> Stream.map(&:binary.bin_to_list/1)
|> Stream.chunk_every(3)
|> Stream.map(fn [r1, r2, r3] ->
  r = r1 -- (r1 -- r2)
  hd(r3 -- (r3 -- r))
end)
|> Stream.map(fn
  x when x >= ?a and x <= ?z -> x - ?a + 1
  x when x >= ?A and x <= ?Z -> x - ?A + 27
end)
|> Enum.sum()
|> tap(fn sum -> IO.puts "Sum of priorities: #{sum}" end)

elapsed = System.monotonic_time(:microsecond) - start
IO.puts "Job done in #{elapsed} µs"

I then decided to benchmark it with benchee. I guess that reading the file many times puts it in some sort of cache and thus the execution times are well below the one with a single execution dominated by I/O. Part 1 without benchee gives ± 7 ms but with benchee an average of 0.86 ms :thinking:

Mix.install([
  {:benchee, "~> 1.1.0"},
])

Benchee.run(%{"run" => fn ->
  File.stream!("input.txt")
  |> Stream.map(&String.trim/1)
  |> Stream.map(&:binary.bin_to_list/1)
  |> Stream.map(&Enum.split(&1, div(length(&1), 2)))
  |> Stream.map(fn {f, r} -> hd(f -- f -- r) end)
  |> Stream.map(fn
    x when x >= ?a and x <= ?z -> x - ?a + 1
    x when x >= ?A and x <= ?Z -> x - ?A + 27
  end)
  |> Enum.sum()
end})
1 Like
20

Amazing! :exploding_head: I’ve learned a lot from this, thanks for sharing…