This topic is about Day 10 of the Advent of Code 2021.
We have a private leaderboard (shared with users of Erlang Forums ):
https://adventofcode.com/2021/leaderboard/private/view/370884
The entry code is:
370884-a6a71927
Here is my solution:
defp process_line(line, needed \\ [])
defp process_line([], needed), do: {:incomplete, needed}
defp process_line([todo | rest], needed) when todo in @openers do
process_line(rest, [@matches[todo] | needed])
end
defp process_line([todo | rest], [match | others]) when todo == match do
process_line(rest, others)
end
defp process_line([todo | _], _), do: {:corrupted, todo}
Full solution here
Not the most concise but good enough. Just happy to be able to get one done night of and still getting some sleep.
Very similar to others, but just wanted to keep posting each day. Love seeing everyone else’s approach
I used a bit of metaprogramming to define the line processor that worked on binaries:
defp process_line(line) do
process_line(line, _stack = [])
end
for <<open, close>> <- ["[]", "()", "{}", "<>"] do
defp process_line(<<unquote(close), rest::bytes>>, [unquote(close) | stack]) do
process_line(rest, stack)
end
defp process_line(<<unquote(open), rest::bytes>>, stack) do
process_line(rest, [unquote(close) | stack])
end
end
defp process_line(<<>>, []), do: :valid
defp process_line(<<>>, stack), do: {:incomplete, stack}
defp process_line(<<char, _rest::bytes>>, _stack), do: {:corrupted, char}
4 Likes
Today’s problem seemed like a good match for Elixir.
defmodule AdventOfCode.Day10 do
@chunks %{
"(" => ")",
"[" => "]",
"{" => "}",
"<" => ">"
}
def part1(input) do
input
|> parse_input()
|> Enum.map(&eval_line/1)
|> Enum.filter(&(elem(&1, 0) == :error))
|> Enum.map(fn {_, v} -> v end)
|> Enum.sum()
end
def part2(input) do
results =
input
|> parse_input()
|> Enum.map(&eval_line/1)
|> Enum.filter(&(elem(&1, 0) == :ok))
|> Enum.map(fn {_, v} -> v end)
|> Enum.sort()
middle = results |> length() |> div(2)
Enum.at(results, middle)
end
def eval_line(line, open \\ [])
def eval_line([head | tail], open) when head in ["(", "[", "{", "<"] do
eval_line(tail, [head | open])
end
def eval_line([head | tail], [open_head | open_tail]) do
if head == @chunks[open_head] do
eval_line(tail, open_tail)
else
{:error, score_error(head)}
end
end
def eval_line(_, open) do
score =
Enum.reduce(open, 0, fn char, acc ->
acc * 5 + score_ac(@chunks[char])
end)
{:ok, score}
end
def score_error(")"), do: 3
def score_error("]"), do: 57
def score_error("}"), do: 1197
def score_error(">"), do: 25137
def score_ac(")"), do: 1
def score_ac("]"), do: 2
def score_ac("}"), do: 3
def score_ac(">"), do: 4
def parse_input(input) do
input
|> String.split("\n", trim: true)
|> Enum.map(&String.codepoints/1)
end
end
1 Like
It got easier again. And I guess not so many different approaches to take… Here’s mine. The nice thing about the reduce_while: it returns the scores for part1 and the remaining stack for part2 - a bit like @mexicat 's eval_line.
@error_scores %{
?) => 3,
?] => 57,
?} => 1197,
?> => 25137,
}
@autocomplete_scores %{
?( => 1,
?[ => 2,
?{ => 3,
?< => 4,
}
def solve(stream, :first) do
stream
|> Stream.map(&String.to_charlist/1)
|> Stream.map(&match_brackets/1)
|> Stream.filter(&is_number/1)
|> Enum.sum()
end
def solve(stream, :second) do
scores =
stream
|> Stream.map(&String.to_charlist/1)
|> Stream.map(&match_brackets/1)
|> Stream.reject(&is_number/1)
|> Stream.map(&calc_autocomplete_tools_score/1)
|> Enum.sort()
Enum.at(scores, div(length(scores),2))
end
defp match_brackets(line) do
Enum.reduce_while(line, [], fn
(bracket, stack) when bracket in [?(, ?{, ?[, ?<] -> {:cont, [bracket | stack]}
(?), [?( | stack]) -> {:cont, stack}
(?], [?[ | stack]) -> {:cont, stack}
(?}, [?{ | stack]) -> {:cont, stack}
(?>, [?< | stack]) -> {:cont, stack}
(illegal, _) -> {:halt, @error_scores[illegal]}
end)
end
defp calc_autocomplete_tools_score(line) do
line
|> Enum.map(&(@autocomplete_scores[&1]))
|> Enum.reduce(&(5 * &2 + &1))
end
I didn’t understand at first that rather than putting openers in the stack you put the complementary closer in the stack. Any reason it is better to match on insertion into the stack rather than on popping off the stack?
This allows you to pattern match directly against the next character in the todo list.
Being easy today’s problem seems that tomorrow Saturday will to be quite hard:)
My solution →
defmodule Day10 do
@moduledoc """
Documentation for `Day10`.
"""
def hello do
:world
end
def part1(input) do
input
|> String.split("\n", trim: true)
|> Enum.map(&String.graphemes/1)
|> Enum.map(&return_points_if_bad/1)
|> Enum.filter(fn nil -> false
_x -> true end)
|> Enum.sum()
end
defp return_points_if_bad(graphemes) do
case couple(graphemes, []) do
[] -> nil
x -> x
end
end
defp couple([], []) do
[]
end
defp couple([], _no_empty) do
[]
end
defp couple([next | list], []) do
couple(list, [next])
end
defp couple([next | list], stack = [prev | rest]) do
case is_open?(next) do
true -> couple(list, [next | stack])
false ->
case is_match?(next, prev) do
true -> couple(list, rest)
false -> points(next)
end
end
end
def part2(input) do
splited = String.split(input, "\n", trim: true)
values = splited
|> Enum.map(&String.graphemes/1)
|> Enum.map(&return_points_if_incomplete/1)
|> Enum.filter(fn nil -> false
_x -> true end)
middle = div(length(values), 2)
values
|> Enum.sort()
|> IO.inspect()
|> Enum.at(middle)
end
defp return_points_if_incomplete(graphemes) do
case eval_sentence(graphemes, []) do
:corrupted -> nil
:right -> nil
x -> x
end
end
defp eval_sentence([], []) do
:right
end
defp eval_sentence([], no_empty) do
compute_completation_points(no_empty)
end
defp eval_sentence([next | list], []) do
eval_sentence(list, [next])
end
defp eval_sentence([next | list], stack = [prev | rest]) do
case is_open?(next) do
true -> eval_sentence(list, [next | stack])
false ->
case is_match?(next, prev) do
true -> eval_sentence(list, rest)
false -> :corrupted
end
end
end
def compute_completation_points(no_empty) do
Enum.reduce(no_empty, 0, fn x, acc -> acc * 5 + oposite_points(x) end)
end
defp oposite_points(symbol) do
case symbol do
"(" -> 1
"[" -> 2
"{" -> 3
"<" -> 4
end
end
defp is_match?(next, prev) do
case {prev, next} do
{"[", "]"} -> true
{"(", ")"} -> true
{"{", "}"} -> true
{"<", ">"} -> true
_ -> false
end
end
defp is_open?(sym) do
case sym do
"(" -> true
"[" -> true
"{" -> true
"<" -> true
_ -> false
end
end
defp points(symbol) do
case symbol do
")" -> 3
"]" -> 57
"}" -> 1197
">" -> 25137
end
end
end
Is it not equivalent this way?
I think it is equivalent except that my implementation for part2 needs to be updated to score openers instead of closers (since stack contains openers for incomplete lines). I rerun the tests with these two changes and they passed.
As for your original question,
Any reason it is better to match on insertion into the stack rather than on popping off the stack?
I don’t think I had any particular reason, at the moment it just made sense to add closers to the stack.
1 Like
I think today’s puzzle was the one I enjoyed the most.
Here’s my solution:
defmodule Day10 do
defguardp is_opening(paren) when paren in [?(, ?[, ?{, ?<]
defguardp matches(opening, closing) when opening == ?( and closing == ?)
defguardp matches(opening, closing) when opening in [?[, ?{, ?<] and closing == opening + 2
@illegal_points %{
?) => 3,
?] => 57,
?} => 1197,
?> => 25137
}
@incomplete_points %{
?) => 1,
?] => 2,
?} => 3,
?> => 4
}
@doc """
iex>Day10.part1(\"""
...>[({(<(())[]>[[{[]{<()<>>
...>[(()[<>])]({[<{<<[]>>(
...>{([(<{}[<>[]}>{[]{[(<()>
...>(((({<>}<{<{<>}{[]{[]{}
...>[[<[([]))<([[{}[[()]]]
...>[{[{({}]{}}([{[{{{}}([]
...>{<[[]]>}<{[{[{[]{()[[[]
...>[<(<(<(<{}))><([]([]()
...><{([([[(<>()){}]>(<<{{
...><{([{{}}[<[[[<>{}]]]>[]]
...>\""")
26397
"""
def part1(input) do
input
|> parse_input()
|> Enum.map(fn subsystem -> visit(subsystem, []) end)
|> Enum.filter(&(elem(&1, 0) == :illegal))
|> Enum.map(fn {_, paren} -> @illegal_points[paren] end)
|> Enum.sum()
end
@doc """
iex>Day10.part2(\"""
...>[({(<(())[]>[[{[]{<()<>>
...>[(()[<>])]({[<{<<[]>>(
...>{([(<{}[<>[]}>{[]{[(<()>
...>(((({<>}<{<{<>}{[]{[]{}
...>[[<[([]))<([[{}[[()]]]
...>[{[{({}]{}}([{[{{{}}([]
...>{<[[]]>}<{[{[{[]{()[[[]
...>[<(<(<(<{}))><([]([]()
...><{([([[(<>()){}]>(<<{{
...><{([{{}}[<[[[<>{}]]]>[]]
...>\""")
288957
"""
def part2(input) do
points =
input
|> parse_input()
|> Enum.map(fn subsystem -> visit(subsystem, []) end)
|> Enum.filter(&(elem(&1, 0) == :incomplete))
|> Enum.map(fn {_, expected} ->
expected
|> Enum.map(&@incomplete_points[&1])
|> Enum.reduce(0, fn points, score ->
score * 5 + points
end)
end)
|> Enum.sort()
Enum.at(points, div(length(points), 2))
end
defp visit([opening, closing | input], expected) when matches(opening, closing) do
visit(input, expected)
end
defp visit([closing | input], [closing | expected]) do
visit(input, expected)
end
defp visit([opening | input], expected) when is_opening(opening) do
visit(input, [pair(opening) | expected])
end
defp visit([illegal | _], _), do: {:illegal, illegal}
defp visit([], expected), do: {:incomplete, expected}
defp pair(?(), do: ?)
defp pair(paren) when paren in [?[, ?{, ?<], do: paren + 2
defp parse_input(input) when is_binary(input) do
input
|> String.split("\n", trim: true)
|> Enum.map(&to_charlist/1)
end
end
1 Like
I used Regex today - which I thought makes for a very concise and nice replacement. Just recursively remove adjacent bracket pairs until the no more adjacent pairs left…
For part 2 - I didn’t use matching brackets, but instead reversed the leftover, and scored directly on that. So an open [( is equivalent to a missing )] - or just score ([ directly - i.e. the reverse of the original.
Hope that makes sense
defmodule Day10 do
@score_map %{")" => 3, "]" => 57, "}" => 1197, ">" => 25137}
@score_map2 %{"(" => 1, "[" => 2, "{" => 3, "<" => 4}
def reg_replace(line) do
regex = ~r/\[\]|\(\)|<>|{}/
Regex.replace(regex, line, "")
end
def clean(line) do
new_line = reg_replace(line)
if new_line == line, do: line, else: clean(new_line)
end
def corrupt?(line) do
line
|> String.graphemes
|> Enum.find(fn x -> x in [")", "}", "]", ">"] end)
end
def part1(input) do
input
|> Enum.map(&clean/1)
|> Enum.reduce(0, fn line, total -> total + Map.get(@score_map, corrupt?(line), 0) end)
end
def remove_corrupt(input) do
input
|> Enum.map(&clean/1)
|> Enum.reject(&corrupt?/1)
end
def score_incomplete(line) do
line
|> String.graphemes
|> Enum.reduce(0, fn char, acc -> (acc * 5) + Map.get(@score_map2, char) end)
end
def part2(input) do
scores =
input
|> remove_corrupt
|> Enum.map(&String.reverse/1)
|> Enum.map(&Day10.score_incomplete/1)
|> Enum.sort
l = div(length(scores), 2)
Enum.at(scores, l)
end
end
Nice use of guards. I always forget about that aspect of Elixir.
1 Like
Thank you! Those are the first ones I’ve ever written! I’m still learning Elixir and I’m so grateful to AoC for giving me the chance to tackle such a diverse and stimulating set of problems!
1 Like
