# Advent of Code 2023 - Day 4

Hello all, hopefully I post this before someone else does and I don’t dupe.

IMO Day 4 was much easier than Day 3 (yay, I can sleep before work!)

My set-up:

``````defmodule Card do
defp to_list_numbers(str) do
str
|> String.split(" ")
|> Enum.filter(fn s -> String.length(s) !== 0 end)
|> Enum.map(fn u ->
{i, _} = Integer.parse(u)
i
end)
end
def parse("Card " <> rest) do
[_, numbers] = rest |> String.split(":")
[winning, player] = numbers |> String.split("|")
[winning |> String.trim() |> to_list_numbers(), player |> String.trim() |> to_list_numbers()]
end
end

cards = for card <- input |> String.split("\n"),
[winning_numbers, our_numbers] = Card.parse(card) do
[winning_numbers, our_numbers]
end

``````

Then part 1 was really simple (10 minutes from start for me to get here):

``````
for [winning_numbers, our_numbers] <- cards
do
case count_winning_cards.(our_numbers, winning_numbers) do
n when n > 0 -> 2**(n-1)
0 -> 0
end
end |> Enum.sum()
``````

Part 2 slightly less so (40 minutes from start to get here):

``````
cards
|> Enum.with_index()
|> Enum.reduce(
List.duplicate(1, cards |> Enum.count()),
fn {[winning, player], idx}, copies ->
self_copies = Enum.at(copies, idx)
won = count_winning_cards.(player, winning)
slice = if won > 0, do: (idx+1)..(idx+won), else: ..
copies |> Enum.with_index() |> Enum.map(
fn {count, idx} ->
if idx in slice, do: count + self_copies, else: count
end
)
end
) |> Enum.sum()
``````

The biggest time sink for me was remembering that `1..1` is a non-empty range in Elixir, so I needed to write the `slice` to be:

``````      slice = if won > 0, do: (idx+1)..(idx+won), else: ..
``````
3 Likes

You don’t have to convert those numeric strings to integers.

Here’s my code:

3 Likes

good point, probably just muscle memory from the previous days

I also found today’s puzzle much easier than yesterday’s.

7 Likes

Wow, today I learned `--`, that’s a really clean way to get the winning numbers!

2 Likes

Part Two really took me a minute, here.

## Input

Processing

A simple map of id to map of mapsets of winners and picks helped me out, meaning that determining the number of winning picks was a `MapSet.intersection/2` away. This is strictly more efficient than `--/2`, but probably doesn’t make a difference at these sizes.

Types
``````@type id :: non_neg_integer()

@type card :: %{winners :: MapSet.t(), picks :: MapSet.t()}

@type input :: {id(), card()}
``````
Example Input
``````%{
1 => %{
picks: MapSet.new([6, 9, 17, 31, 48, 53, 83, 86]),
winners: MapSet.new([17, 41, 48, 83, 86])
},
2 => %{
picks: MapSet.new([17, 19, 24, 30, 32, 61, 68, 82]),
winners: MapSet.new([13, 16, 20, 32, 61])
},
3 => %{
picks: MapSet.new([1, 14, 16, 21, 63, 69, 72, 82]),
winners: MapSet.new([1, 21, 44, 53, 59])
},
4 => %{
picks: MapSet.new([5, 51, 54, 58, 59, 76, 83, 84]),
winners: MapSet.new([41, 69, 73, 84, 92])
},
5 => %{
picks: MapSet.new([12, 22, 30, 36, 70, 82, 88, 93]),
winners: MapSet.new([26, 28, 32, 83, 87])
},
6 => %{
picks: MapSet.new([10, 11, 23, 35, 36, 67, 74, 77]),
winners: MapSet.new([13, 18, 31, 56, 72])
}
}
``````

Source code available here.

``````defmodule AoC.Day.Four.Input do
def parse(input_file \\ System.fetch_env!("INPUT_FILE")) do
input_file
|> String.split("\n")
|> Enum.reject(&(&1 == ""))
|> Enum.map(&parse_card/1)
|> Map.new()
end

def parse_card("Card" <> card) do
card = String.trim(card)
{id, rest} = Integer.parse(card)
<<": ">> <> numbers = rest

[winners, picks] =
String.split(numbers, "|", parts: 2)
|> Enum.map(&String.trim/1)
|> Enum.map(&parse_numbers/1)

{id, %{winners: winners, picks: picks}}
end

def parse_numbers(numbers) do
numbers
|> String.split(~r{\s+})
|> Enum.map(&String.to_integer/1)
|> MapSet.new()
end
end
``````

## Part One

Solution

Scoring a card is counting the number of winning picks, and then doing some `:math.pow`. I’m getting better at breaking calculations in part one apart such that some functions prove useful later in part two.

Source code available here.

``````defmodule AoC.Day.Four.Part.One do
def solve(cards) do
cards
|> Enum.map(fn {_id, card} ->
card
|> number_of_wins()
|> score_card()
end)
|> Enum.sum()
end

def winning_numbers(card) do
MapSet.intersection(card.winners, card.picks)
end

def number_of_wins(card) do
card
|> winning_numbers()
|> MapSet.size()
end

def score_card(number_of_wins)

def score_card(0), do: 0

def score_card(number_of_wins) when number_of_wins > 0 do
round(:math.pow(2, number_of_wins - 1))
end
end

``````

## Part Two

Solution

This took a while. The insights that got me over the finish line was that

• the very final cards must always have no/few winners, since there is nothing to copy after them
• earlier cards are always defined by the value of later ones

This means if you start at the end of the cards, you can walk backwards through the card list determining each one’s value without recursive operations or actually generating copies of anything.

First I count how many wins each card has, then I generate a map of `id => [id]` to reference what each card creates a copy of.

Then I generate a map of how many copies each id must create, starting from the `last_id`. `list_id` must always have `Map.get(copies, last_id) == []`, so its count is `1`; `Map.get(copies, last_id -1)` must be either `[]` or `[last_id]`, and can reliably look up the number of copies since `last_id` must have already been computed, etcera.

Source code available here.

``````defmodule AoC.Day.Four.Part.Two do
import AoC.Day.Four.Part.One

def solve(cards) do
wins =
Map.new(cards, fn {id, card} ->
{id, number_of_wins(card)}
end)

copies =
Map.new(wins, fn {id, wins} ->
{id, Range.new(id + 1, id + wins, 1) |> Range.to_list()}
end)

counts =
copies
|> Enum.into([])
|> Enum.sort_by(fn {id, _copies} -> id end)
|> Enum.reverse()
|> Enum.reduce(%{}, fn
{id, []}, counts ->
Map.put(counts, id, 1)

{id, copies}, counts ->
count =
copies
|> Enum.map(&Map.get(counts, &1))
|> Enum.sum()

Map.put(counts, id, count + 1)
end)

counts |> Map.values() |> Enum.sum()
end
end
``````

Once again parsing the input was the biggest challenge. Once I had that both parts went quickly. I kept thinking the card IDs would be necessary in Part 2 but when they weren’t I didn’t bother cleaning them out of the code.

Full code here.

``````defmodule Parser do
alias AocToolbox.Input

def parse_raw_cards(text) do
text
|> Input.lines()
|> Enum.map(&parse_card/1)
end

defp parse_card(<<"Card ", rest::binary>>), do: parse_card(rest)
defp parse_card(<<" ", rest::binary>>), do: parse_card(rest)

defp parse_card(<<d, rest::binary>>) when d > 47 and d < 58 do
{card_id, card} = parse_num(d - 48, rest)

{card_id, parse_card_nums(card, MapSet.new(), MapSet.new(), :winners)}
end

defp parse_num(acc, <<d, rest::binary>>) when d > 47 and d < 58 do
parse_num(acc * 10 + (d - 48), rest)
end

defp parse_num(acc, bin), do: {acc, bin}

defp parse_card_nums("", winners, matches, set), do: {winners, matches}

defp parse_card_nums(<<d, rest::binary>>, winners, matches, set) when d > 47 and d < 58 do
{next_num, card} = parse_num(d - 48, rest)

if set == :winners do
parse_card_nums(card, MapSet.put(winners, next_num), matches, set)
else
parse_card_nums(card, winners, MapSet.put(matches, next_num), set)
end
end

defp parse_card_nums(<<"|", rest::binary>>, winners, matches, _set),
do: parse_card_nums(rest, winners, matches, :matches)

defp parse_card_nums(<<_s, rest::binary>>, winners, matches, set),
do: parse_card_nums(rest, winners, matches, set)
end
``````

I’m sure there’s something really clever to be done with bit shifting for part 1 but I didn’t bother trying.

I must be tired. I can’t seem to figure out how reversing the list helps you here. The thing that made it click for me was that for each copy operation you make as many copies as the number of current cards you have.

My solution skips creating any copies—instead I generate a map of what card ids would get copied. Then I start with the base case of “the last card cannot generate any copies as there is nothing left to copy, it must have the value of `1`” and work backwards, translating each list of “these cards would get copied” to their innate value.

The value of later cards must be computed by the time we get to any given earlier card going backwards. The resulting `counts` map is kind of odd—for the example set,

``````%{
1 => 15,
2 => 7,
3 => 4,
4 => 2,
5 => 1,
6 => 1
}
``````

Later cards like the final `6` is only worth one point, but then the value of earlier cards factor in the repetition of their reference to later ones.

I’m tired as well though, so I can’t tell if it’s clever or not.

I just woke up so the main obstacle for me was figuring out what it wanted me to do for part 2

I couldn’t think about an efficient “math-y” way to do it for part 2, so I just pre-save the intersections in a map and check them all the time. I thought it was going to be super slow, but it finishes in ~140ms, which is good enough for me.

I heard that when running `a -- b`, the Erlang runtime will first convert `b` to a red-black tree if `b` is long enough (maybe when `length(b) > 32`). If that’s the case, then `a -- a -- b` can be as performant as `MapSet.intersection(set1, set2)`.

3 Likes
``````import AOC

aoc 2023, 4 do
def p1(input) do
input
|> winning_cards()
|> Enum.unzip()
|> elem(1)
|> Enum.map(fn 0 -> 0; n -> 2 ** (n-1) end)
|> Enum.sum()
end

def winning_cards(input) do
process = fn card -> card |> String.split(" ", trim: true) |> Enum.map(&String.to_integer/1) |> MapSet.new end
input
|> String.split("\n", trim: true)
|> Enum.map(
fn line ->
["Card " <> n, cards] = String.split(line, ": ")
card_strs = String.split(cards, "|")
[winning, holding] = card_strs |> Enum.map(process)
{String.to_integer(String.trim(n)), MapSet.intersection(winning, holding) |> Enum.count()}
end
)
end

def p2(input) do
input
|> winning_cards()
|> Enum.map(fn {i, n} -> {i, {1, n}} end)
|> process()
|> Enum.unzip()
|> elem(1)
|> Enum.unzip()
|> elem(0)
|> Enum.sum()
end

def process([]), do: []
def process([{i, {0, n}} = x | xs]), do: [x | process(xs)]
def process([{i, {count, multiplier}} = x | xs]) do
{before, after_} = Enum.split(xs, multiplier)
[x | process(Enum.map(before, fn {i, {c, n}} -> {i, {c + count, n}} end) ++ after_)]
end
end
``````
1 Like

Here it is. It’s fun how we are mostly doing the same thing but nobody writes it the same.

``````defmodule AdventOfCode.Y23.Day4 do
alias AoC.Input, warn: false

Input.stream!(file, trim: true)
end

def parse_input(input, _part) do
input
|> Enum.map(fn "Card " <> rest ->
{card_id, ": " <> rest} = Integer.parse(rest)
[winnings, playings] = String.split(rest, " | ")
winnings = list_of_ints(winnings)
playings = list_of_ints(playings)
{card_id, winnings, playings}
end)
end

defp list_of_ints(str) do
str |> String.split(" ", trim: true) |> Enum.map(&String.to_integer/1)
end

def part_one(problem) do
problem
|> Enum.map(fn {_, winnings, playings} ->
wins = MapSet.new(winnings)
plays = MapSet.new(playings)
pow = MapSet.size(MapSet.intersection(wins, plays))
trunc(:math.pow(2, pow - 1))
end)
|> Enum.sum()
end

def part_two(problem) do
problem
|> Enum.map_reduce(%{}, fn {card_id, winnings, playings}, acc ->
n_cards = 1 + Map.get(acc, card_id, 0)
wins = MapSet.new(winnings)
plays = MapSet.new(playings)

acc =
case MapSet.size(MapSet.intersection(wins, plays)) do
0 ->
acc

n_wins ->
adds = (card_id + 1)..(card_id + n_wins)

Enum.reduce(adds, acc, fn next_card_id, acc ->
Map.update(acc, next_card_id, n_cards, &(&1 + n_cards))
end)
end

{n_cards, acc}
end)
|> elem(0)
|> Enum.sum()
end
end

``````

@Aetherus I just read your post and indeed there is no need to parse as integers. But with my code it is actually faster when I pay the cost to do it. Probably because it speeds up the matching in `Map.get`

2 Likes

My solution :

``````defmodule Scratchcards do
import NimbleParsec

defparsec(
:parse_line,

ignore(string("Card") |> repeat(ignore(string(" "))))
|> integer(min: 1, max: 3)
|> ignore(string(":"))
|> ignore(repeat(ignore(string(" "))))
|> tag(repeat(integer(min: 1, max: 2) |> repeat(ignore(string(" ")))), "numbers")
|> ignore(string("|"))
|> repeat(ignore(string(" ")))
|> tag(repeat(integer(min: 1, max: 2) |> repeat(ignore(string(" ")))), "winning")
)
defp points(0), do: 0

defp points(x), do: 2 ** (x - 1)

defp calculate_score(line) do
{:ok, [_, {"numbers", numbers}, {"winning", winning}], _, _, _, _} = parse_line(line)
MapSet.intersection(MapSet.new(numbers), MapSet.new(winning))
|> MapSet.to_list()
|> length()
end

def part1(input) do
input
|> String.split("\n")
|> Enum.map(fn line ->
line
|> calculate_score()
|> points()
end)
|> Enum.sum()
end

defp count(input, pos, total) do

score = Enum.at(input, pos)
if score > 0 do
Enum.reduce((pos + 1)..(pos + score), total, fn(i, total) ->
count(input, i, total + 1)
end)
else
total
end
end

def part2(input) do
scores = input
|> String.split("\n")
|> Enum.map(fn line ->
calculate_score(line)
end)

scores
|> Enum.with_index()
|> Enum.reduce(0, fn({_v, i}, total) ->
total + count(scores, i, 1)
end)
end
end

Scratchcards.part2(input)
``````
2 Likes

## Parsing

``````cards =
puzzle_input
|> String.split("\n", trim: true)
|> Enum.map(fn "Card" <> rest ->
{id, ": " <> rest} = rest |> String.trim() |> Integer.parse()

[wins, inputs] =
rest
|> String.split(" | ")
|> Enum.map(fn part ->
part
|> String.split()
|> Enum.map(&String.to_integer/1)
end)

{id, wins, inputs}
end)
``````

## Part 1

``````cards
|> Enum.map(fn {_, wins, inputs} ->
matches = length(wins) - length(wins -- inputs)

if matches > 0, do: 2**(matches - 1), else: 0
end)
|> dbg()
|> Enum.sum()
``````

## Part 2

``````cards
|> Enum.reduce(%{}, fn {id, wins, inputs}, acc ->
matches = length(wins) - length(wins -- inputs)
{current, acc} = Map.get_and_update(acc, id, fn v ->
v = (v || 0) + 1
{v, v}
end)

Enum.reduce(1..matches//1, acc, &Map.update(&2, id + &1, current, fn a -> a + current end))
end)
|> Map.values()
|> Enum.sum()
``````
2 Likes

Learned `Map.get_and_update`.

3 Likes

My beginner’s solution, Day 4.
I had a lot of fun implementing a function using `[tail | head]` syntax. Is it idiomatic?

``````defmodule Day04 do

def part2(input) do
input
|> String.split("\n")
|> Enum.map(&parse_to_map_of_your_and_winning_numbers/1)
|> Enum.map(&amount_of_winning_numbers/1)
|> Enum.reverse
# [0, 0, 1, 2, 2, 4]
|> total_scratchcards
end

def part1(input) do
input
|> String.split("\n")
|> Enum.map(&parse_to_map_of_your_and_winning_numbers/1)
|> Enum.map(&amount_of_winning_numbers/1)
|> Enum.map(&calculate_worth/1)
|> Enum.sum
end

def parse_to_map_of_your_and_winning_numbers(line) do
# "Card 1: 41 48 83 86 17 | 83 86 6 31 17 9 48 53"
line
|> String.split(": ")
|> List.last
|> String.split(" | ")
|> Enum.map(fn x -> x
|> String.split
|> Enum.map(&String.to_integer/1)
end)
|> then(fn [w, y] -> %{your: y, winning: w} end)
# %{ winning: [41, 48, 83, 86, 17],
#       your: [83, 86, 6, 31, 17, 9, 48, 53] }
end

def amount_of_winning_numbers(card) do
# %{ winning: [41, 48, 83, 86, 17],
#       your: [83, 86, 6, 31, 17, 9, 48, 53] }
Enum.member?(card.winning, your_number)
end
|> Enum.count(&(&1))
end

def calculate_worth(0), do: 0
def calculate_worth(n), do: :math.pow(2, n-1) |> round

def total_scratchcards(how_many_wins_list, scratchcards_amount_list \\ [])
def total_scratchcards([], amount_list), do: Enum.sum(amount_list)
def total_scratchcards([head | tail], amount_list) do
amount = amount_list
|> Enum.sum
|> Kernel.+(1)

total_scratchcards(tail, [amount] ++  amount_list)
end

end
``````

I was proud of my recursive copy function, until I saw @bjorng’s

edit: tidied up enough to share. Both parts under a ms.

``````  def part1(input) do
input
|> Enum.map(fn 0 -> 0; num_winners -> 2 ** (num_winners - 1) end)
|> Enum.sum()
end

def part2(input) do
input
|> Enum.map(fn num_winners -> {_num_copies = 1, num_winners} end)
|> copy()
|> Enum.sum()
end

def copy([]), do: []

def copy([{num_copies, num_winners} | rest]) do
{to_copy, left_alone} = Enum.split(rest, num_winners)

copied =
Enum.map(to_copy, fn {child_num_copies, num_winners} ->
{num_copies + child_num_copies, num_winners}
end)

[num_copies | copy(copied ++ left_alone)]
end
``````
2 Likes

Solved part 2 with a single `for reduce`:

2 Likes

For me it was the easier this year. quite fun to solve.

1 Like