Advent of Code 2020 - Day 6

This topic is about Day 6 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

Repo with all of my solutions and notes is here as always:

And the meat of today’s problem:

  def count_uniq(group) do
    group
    |> Enum.join()
    |> String.graphemes()
    |> Enum.uniq()
    |> Enum.count()
  end
  def count_common(group) do
    group = Enum.map(group, &String.graphemes/1)

    Enum.reduce(group, MapSet.new(List.first(group)), fn responses, acc ->
      MapSet.intersection(MapSet.new(responses), acc)
    end)
    |> Enum.count()
  end
2 Likes

Here’s mine: https://github.com/code-shoily/advent_of_code/blob/master/lib/2020/day_6.ex

The important functions for part 1.

  defp answers(group) do
    group
    |> Enum.flat_map(&String.graphemes/1)
    |> Enum.uniq()
    |> Enum.count()
  end

… and part 2

  defp unanimous_answers(group) do
    group
    |> Enum.map(&MapSet.new(String.graphemes(&1)))
    |> Enum.reduce(&MapSet.intersection/2)
    |> Enum.count()
  end
4 Likes

My solution uses a conventional MapSet approach.

Part 1

#!/usr/bin/env elixir

initial_set = MapSet.new()
combine = &MapSet.union/2

"day6.txt"
|> File.stream!()
|> Stream.map(&String.trim/1)
|> Stream.chunk_while(initial_set, fn
  "", acc -> {:cont, acc, initial_set}
  s, acc -> {:cont, s |> String.to_charlist() |> MapSet.new() |> combine.(acc)}
end,
&{:cont, &1, initial_set})
|> Enum.map(&MapSet.size/1)
|> Enum.sum()
|> IO.inspect()

Part 2

#!/usr/bin/env elixir

initial_set = MapSet.new(?a..?z)
combine = &MapSet.intersection/2

# The rest is just the same as Part 1
3 Likes

Aha! The way you did the MapSet.new step makes things a lot cleaner. :slight_smile:

I spent forever trying to figure out what part two wanted me to do, and then once I realized it was a set intersection, it took a whole two minutes to complete. Still pretty fun though, definitely better than last year’s intcode nightmare!

defmodule Day6 do
  def one do
    File.read!("inputs/six.txt")
    |> String.split("\n\n")
    |> Enum.map(&String.replace(&1, "\n", "", global: true))
    |> Enum.map(&String.split(&1, "", trim: true))
    |> Enum.map(&MapSet.new(&1))
    |> Enum.map(&MapSet.size(&1))
    |> Enum.reduce(&(&1 + &2))
  end

  def two do
    File.read!("inputs/six.txt")
    |> String.split("\n\n")
    |> Enum.map(&String.split(&1, "\n", trim: true))
    |> Enum.map(&parse/1)
    |> Enum.map(&MapSet.size/1)
    |> Enum.reduce(&(&1 + &2))
  end

  def parse(input) do
    input
    |> Enum.map(&String.graphemes(&1))
    |> Enum.map(&MapSet.new(&1))
    |> Enum.reduce(&MapSet.intersection/2)
  end
end

I didn’t think about taking the intersection, as always makes complete sense in hindsight. That’s so simple and clean @code-shoily :star_struck:.

I ended up counting how many of each answer was given, and counting those that matched the number of answers. The same thing, but more convoluted.

Probably slightly quirky how I popped \n from the frequency map to count the number of answers.

File.stream!("input")
|> Stream.chunk_by(&(&1 == "\n"))
|> Stream.map(fn group ->
  {count, frequencies} =
    group
    |> Enum.join()
    |> String.to_charlist()
    |> Enum.frequencies()
    |> Map.pop(?\n)

  Enum.count(frequencies, fn {_, v} -> v == count end)
end)
|> Enum.sum()
1 Like

I ended up actually counting answers by using group_by because my brain decided to ignore that there is MapSet in elixir.

defmodule Event6 do
  def run do
    IO.puts("Test part1: #{solver("input/event6/test.txt", &count_answers/1)}")
    IO.puts("Puzzle part1: #{solver("input/event6/puzzle.txt", &count_answers/1)}")
    IO.puts("Test part2: #{solver("input/event6/test.txt", &count_answers2/1)}")
    IO.puts("Puzzle part2: #{solver("input/event6/puzzle.txt", &count_answers2/1)}")
  end

  def solver(path, counter),
    do: input_stream(path) |> Stream.chunk_by(&(&1 == "")) |> Stream.map(counter) |> Enum.sum()

  def input_stream(path), do: path |> File.stream!() |> Stream.map(&String.trim/1)

  def count_answers(group),
    do: group |> Enum.reduce(&<>/2) |> String.graphemes() |> Enum.uniq() |> Enum.count()

  def count_answers2(group) do
    people = length(group)

    group
    |> Enum.flat_map(&(&1 |> String.graphemes() |> Enum.uniq()))
    |> Enum.group_by(& &1)
    |> Enum.flat_map(fn {key, value} -> (length(value) == people && [key]) || [] end)
    |> Enum.count()
  end
end

Love the use of chunk_by @Aetherus, wasn’t so smart though - have instead split groups by String.split("\n\n", trim: true)

#!/usr/bin/env elixir
yes = MapSet.new('abcdefghijklmnopqrstuvwxyz')

File.read!("6.csv")
|> String.split("\n\n", trim: true)
|> Enum.map(fn group ->
  group = String.split(group, "\n", trim: true)
    |> Enum.map(fn person -> MapSet.new(String.to_charlist(person)) end)
    |> Enum.reduce(yes, fn p, all -> MapSet.intersection(all, p) end)

  MapSet.size(yes) - MapSet.size(MapSet.difference(yes, group))
end)
|> Enum.sum()
|> IO.inspect()

MapSet like most folks :smiley:

GitHub

defmodule Aoc.Y2020.D6 do
  use Aoc.Boilerplate,
    transform: fn raw ->
      raw
      |> String.split("\n\n")
      |> Enum.map(fn group ->
        group
        |> String.split("\n")
        |> Enum.map(fn person ->
          person |> String.graphemes()
        end)
      end)
    end

  def part1(input \\ processed()) do
    input
    |> Enum.map(&count_yes_in_group/1)
    |> Enum.sum()
  end

  def part2(input \\ processed()) do
    input
    |> Enum.map(&count_all_yes_in_group/1)
    |> Enum.sum()
  end

  defp count_yes_in_group(group) do
    group
    |> Enum.reduce(MapSet.new(), fn answers, acc ->
      MapSet.union(acc, MapSet.new(answers))
    end)
    |> MapSet.size()
  end

  defp count_all_yes_in_group([first | rest]) do
    rest
    |> Enum.reduce(MapSet.new(first), fn answers, acc ->
      MapSet.intersection(acc, MapSet.new(answers))
    end)
    |> MapSet.size()
  end
end

I didn’t think of sets for part 2, so I ended up iterating all given answers with Enum.all? to figure out if they’re given by each person.

It’ll only work if nobody can answer the same question twice though.

Just had another stab at part 2 and optimized it even beyond the MapSet solution by filtering out invalid answers on aggragation:

a
abcdef
…

After the first line there’s no need to check for anything, but a.

I thought about using intersection but Enum.frequencies seemed to get the job done easily (not sure how efficient this is).

defmodule AdventOfCode.Day06 do
  def part1(input) do
    input
    |> String.trim()
    |> String.split("\n\n")
    |> Enum.map(&String.replace(&1, ~r/\s/, ""))
    |> Enum.map(&String.codepoints/1)
    |> Enum.map(&Enum.uniq/1)
    |> Enum.map(&Enum.count/1)
    |> Enum.reduce(&(&1 + &2))
  end

  def part2(input) do
    input
    |> String.trim()
    |> String.split("\n\n")
    |> Enum.map(&String.codepoints/1)
    |> Enum.map(&find_common_answers/1)
    |> Enum.reduce(&(&1 + &2))
  end

  def find_common_answers(group) do
    frequencies = Enum.frequencies(group)
    lines = Map.get(frequencies, "\n", 0) + 1

    frequencies |> Enum.filter(fn {_k, v} -> v == lines end) |> Enum.count()
  end
end

I immediately reached for a MapSet base solution, but decided that was boring… so I thought this was great time to practice some Bitwise magic :slight_smile:

Here is the gist of it, the following function encode a group members answer into an integer.
So encode("abc") == 0b111 == 7.

def encode(""), do: 0
def encode(<<char, rest::binary()>>), do: 0b1 <<< (char - ?a) ||| encode(rest)

It is then just a matter of using AND or OR (&&&, |||) to get the numbers that was asked for.

defmodule Aoc2020.Day06 do
  use Bitwise

  def part1(input) do
    input
    |> Stream.map(&count_uniq/1)
    |> Enum.sum()
  end

  def part2(input) do
    input
    |> Stream.map(&count_common/1)
    |> Enum.sum()
  end

  defp count_uniq(group) do
    group
    |> Enum.reduce(0, fn member, acc -> acc ||| member end)
    |> count_bits()
  end

  defp count_common(group) do
    group
    |> Enum.reduce(fn member, acc -> acc &&& member end)
    |> count_bits()
  end

  defp count_bits(number) do
    number
    |> Integer.digits(2)
    |> Enum.sum()
  end

  def input_stream(path) do
    chunk_fun = fn
      "", parts -> {:cont, parts, []}
      part, parts -> {:cont, [encode(part) | parts]}
    end

    after_fun = fn
      parts -> {:cont, parts, []}
    end

    File.stream!(path)
    |> Stream.map(&String.trim/1)
    |> Stream.chunk_while([], chunk_fun, after_fun)
  end

  def encode(""), do: 0
  def encode(<<char, rest::binary()>>), do: 0b1 <<< (char - ?a) ||| encode(rest)
end

input = Aoc2020.Day06.input_stream("input.txt")

Aoc2020.Day06.part1(input)
|> IO.inspect(label: "part1")

Aoc2020.Day06.part2(input)
|> IO.inspect(label: "part2")
3 Likes

I used MapSet.new where I could’ve used Enum.uniq and my own function instead of Enum.frequencies. My part 2 didn’t feel right, all because I missed Enum.frequencies.

defmodule Day06 do
  def readinput() do
    File.read!("6.test.txt")
    |> String.split("\n\n")
    |> Enum.map(&String.split/1)
  end

  def part1(input \\ readinput()) do
    input
    |> Enum.map(&Enum.join/1)
    |> Enum.map(&String.graphemes/1)
    |> Enum.map(&MapSet.new/1)
    |> Enum.map(&Enum.count/1)
    |> Enum.sum()
  end

  def part2b(input \\ readinput()) do
    input
    |> Enum.map(fn group -> {length(group), Enum.join(group) |> String.graphemes()} end)
    |> Enum.map(fn {len, group} ->
      {len,
       # replace this bit with Enum.frequencies
       Enum.reduce(group, %{}, fn a, acc -> Map.update(acc, a, 1, fn cur -> cur + 1 end) end)}
    end)
    |> Enum.map(fn {len, group} -> Enum.count(Map.values(group), fn v -> v == len end) end)
    |> Enum.sum()
  end
end

Found a neater way of “counting bits” (thanks internet!):

def count_bits(num), do: count_bits(num, 0)
defp count_bits(0, sum), do: sum
defp count_bits(num, sum), do: count_bits(num &&& num - 1, sum + 1)

part1

defmodule Advent.Day6 do

  def start(file \\ "/tmp/input.txt"), do:
    File.read!(file)
    |> to_charlist()
    |> Kernel.++([10, 10])
    |> Enum.reduce({%{}, 0, 0}, fn letter, acc -> process(acc, letter) end)
    |> elem(2)

  defp process({letters, 1, total}, 10), do: {%{}, 0, total + (Map.keys(letters) |> Enum.count())}
  defp process({letters, _, total}, 10), do: {letters, 1, total}
  defp process({letters, _, total}, letter), do: {letters |> Map.put(letter, 1), 0, total}

end

part2

defmodule Advent.Day6b do

  def start(file \\ "/tmp/input.txt"), do:
    File.read!(file)
    |> to_charlist()
    |> Kernel.++([10, 10])
    |> Enum.reduce({%{}, 0, 0, 0}, fn letter, acc -> process(acc, letter) end)
    |> elem(2)

  defp process({letters, 1, total, members}, 10), do: {%{}, 0, total + ((:maps.filter fn _, v -> v == members end, letters) |> Enum.count()), 0}
  defp process({letters, _, total, members}, 10), do: {letters, 1, total, members + 1}
  defp process({letters, _, total, members}, letter), do: {letters |> Map.update(letter, 1, &(&1 + 1)), 0, total, members}

end

Another MapSet solution. I kept getting part 2 wrong by 1 because splitting the groups without trimming screwed up the count.

defmodule Day6 do
  @input File.read!("lib/input.txt") |> String.split("\n\n")

  def total_affirmative_answers() do
    @input
    |> Stream.map(&unique_affirmatives(&1))
    |> Stream.map(&MapSet.size(&1))
    |> Enum.sum()
  end

  defp unique_affirmatives(lines) do
    lines
    |> String.split("\n", trim: true)
    |> Enum.map(&String.codepoints(&1))
    |> Enum.map(&MapSet.new(&1))
    |> Enum.reduce(MapSet.new(), fn set, acc -> MapSet.union(acc, set) end)
  end

  defp inclusive_affirmatives() do
    @input
    |> Enum.map(&get_set_for_group(&1))
  end

  defp get_set_for_group(group) do
    group =
      group
      |> String.split("\n", trim: true)
      |> Enum.map(&String.codepoints(&1))
      |> Enum.map(&MapSet.new(&1))

    group
    |> Enum.reduce(List.first(group), fn individual, acc ->
      MapSet.intersection(acc, individual)
    end)
  end

  def total_inclusive_affirmatives() do
    inclusive_affirmatives()
    |> Enum.map(&MapSet.size(&1))
    |> Enum.sum()
  end
end

IO.inspect(Day6.total_affirmative_answers())
IO.inspect(Day6.total_inclusive_affirmatives())

I wonder of it’s worth optimizing part 2 by length of individual responses. Find the shortest line and search the other lines for those characters. Probably only efficient for groups with a wide variance in answer lengths.

Today’s exercise made me glad I’d extracted “split the input stream on blank lines” into a reusable part back on day 4.