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
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
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
My solution uses a conventional MapSet
approach.
#!/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()
#!/usr/bin/env elixir
initial_set = MapSet.new(?a..?z)
combine = &MapSet.intersection/2
# The rest is just the same as Part 1
Aha! The way you did the MapSet.new step makes things a lot cleaner.
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 .
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()
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
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
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")
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.