My solution:
https://github.com/bjorng/advent-of-code-2023/blob/main/day03/lib/day03.ex
bjorng
Erlang Core Team
2
christhekeele
I have to admit, my favorite part of these puzzles is
- Seeing if I can parse the input into a structure that is useful for parts one and two
- Seeing if I can break apart part one into functions also useful for part two
Essentially, seeing if I can implement good abstractions upfront. Today was a good day for that!
Input
Processing
The datastructure I chose to use here was {symbols, numbers}, each as maps, with their indexed location in the grid as the keys and the parsed data from the grid as the values. In the case of numbers, their column index is a range representing their span in the grid.
Types
@type index :: non_neg_integer()
@type symbol_index :: {row_num :: index(), col_num :: index()}
@type symbols :: %{
symbol_index() => symbol :: String.t()
}
@type number_index :: {row_num :: index(), col_num :: Range.t()}
@type numbers :: %{
number_index() => number :: non_neg_integer()
}
@type input :: {symbols(), numbers()}
Example Input
{symbols, numbers} = {%{
{1, 3} => "*",
{3, 6} => "#",
{4, 3} => "*",
{5, 5} => "+",
{8, 3} => "$",
{8, 5} => "*"
},
%{
{0, 0..2} => 467,
{0, 5..7} => 114,
{2, 2..3} => 35,
{2, 6..8} => 633,
{4, 0..2} => 617,
{5, 7..8} => 58,
{6, 2..4} => 592,
{7, 6..8} => 755,
{9, 1..3} => 664,
{9, 5..7} => 598
}}
Regex.scan(regex, string, return: :index) carried the day. I never really use it for anything but programming puzzles where I am indexing into a string grid, but boy is it handy here.
Source code available here.
defmodule AoC.Day.Three.Input do
def parse(input_file \\ System.fetch_env!("INPUT_FILE")) do
input_file
|> File.read!()
|> String.split("\n")
|> Enum.with_index()
|> Enum.reduce({%{}, %{}}, fn {row, y}, {symbols, numbers} ->
symbols = scan_symbols({row, y}, symbols)
numbers = scan_numbers({row, y}, numbers)
{symbols, numbers}
end)
end
def scan_symbols({row, y}, symbols) do
Regex.scan(~r{[^\d\.]}, row, return: :index)
|> List.flatten()
|> Enum.reduce(symbols, fn {x, 1}, symbols ->
Map.put(symbols, {y, x}, String.at(row, x))
end)
end
def scan_numbers({row, y}, numbers) do
Regex.scan(~r{\d+}, row, return: :index)
|> List.flatten()
|> Enum.reduce(numbers, fn {x, length}, numbers ->
x_start = x
x_end = x + length - 1
number =
row
|> String.slice(x_start..x_end)
|> String.to_integer()
Map.put(numbers, {y, x_start..x_end}, number)
end)
end
end
Part One
Solution
My adjacency check here is not as inefficient as scanning the whole grid ever time, but still suboptimal. It was easy and fun to implement, thought. It checks every symbol against every number.
A more optimal approach would probably be to generate the indices of every possible symbol location around each number, and do a lookup to see if there was an entry (or vice-versa).
I don’t love the variable names I came up with in the adjacency logic, but readability is less at a premium in these sorts of application as being able to see where the different - 1s and + 1s are, and terseness helps there.
Source code available here.
defmodule AoC.Day.Three.Part.One do
def solve({symbols, numbers}) do
symbols
|> Enum.map(&adjacent_numbers_indices(&1, numbers))
|> List.flatten()
|> Enum.uniq()
|> Enum.map(&Map.get(numbers, &1))
|> Enum.sum()
end
def adjacent_numbers_indices({symbol_index, _symbol}, numbers) do
numbers
|> Map.keys()
|> Enum.filter(&adjacent?(symbol_index, &1))
end
# The geometry of considers 8 neighbours to be adjacent, cardinals and diagonals
# We hardcode these in function heads, going clockwise, starting north
def adjacent?(symbol_index, number_index)
# North
def adjacent?({s_y, s_x}, {n_y, n_xs..n_xe})
when s_y + 1 == n_y and s_x in n_xs..n_xe,
do: true
# North-East
def adjacent?({s_y, s_x}, {n_y, n_xs..n_xe})
when s_y + 1 == n_y and (s_x + 1) in n_xs..n_xe,
do: true
# East
def adjacent?({s_y, s_x}, {n_y, n_xs..n_xe})
when s_y == n_y and (s_x + 1) in n_xs..n_xe,
do: true
# South-East
def adjacent?({s_y, s_x}, {n_y, n_xs..n_xe})
when s_y - 1 == n_y and (s_x + 1) in n_xs..n_xe,
do: true
# South
def adjacent?({s_y, s_x}, {n_y, n_xs..n_xe})
when s_y - 1 == n_y and s_x in n_xs..n_xe,
do: true
# South-West
def adjacent?({s_y, s_x}, {n_y, n_xs..n_xe})
when s_y - 1 == n_y and (s_x - 1) in n_xs..n_xe,
do: true
# West
def adjacent?({s_y, s_x}, {n_y, n_xs..n_xe})
when s_y == n_y and (s_x - 1) in n_xs..n_xe,
do: true
# North-West
def adjacent?({s_y, s_x}, {n_y, n_xs..n_xe})
when s_y + 1 == n_y and (s_x - 1) in n_xs..n_xe,
do: true
def adjacent?(_symbol_index, _number_index), do: false
end
Part Two
Solution
Exactly what you want to see: use the same datastructure you developed for part one, use functions from part one to solve! Source code available here.
defmodule AoC.Day.Three.Part.Two do
@gear "*"
import AoC.Day.Three.Part.One
def solve({symbols, numbers}) do
symbols
|> Enum.filter(fn {_index, symbol} -> symbol == @gear end)
|> Enum.map(&adjacent_numbers_indices(&1, numbers))
|> Enum.filter(&(length(&1) == 2))
|> Enum.reduce(0, fn [gear1, gear2], acc ->
acc + numbers[gear1] * numbers[gear2]
end)
end
end
2
epilgrim
I did something I didn’t see in other solutions. I created an index of positions for all the numbers, but also added a unique id to each number. That way, the number 467 can be indexed as [{{0,0}, {id_1, 467}}, {{0,1}, {id_1, 467}}, {{0,2}, {id_1, 467}}]
That way, adjacency is trivial, and then deduplicating numbers is also trivial (as the same number might be adjacent to a symbol multiple times)
Solution: advent_of_code/2023/day_03.ex at master · juanperi/advent_of_code · GitHub
2
stevensonmt
I have not yet looked at the solutions in this thread but I just wanted to state that for day 3 this was a very difficult challenge relative to previous years. I think there may have been an effort to handicap the AI coders with the difficult input parsing this year.
4
adamu
It could also be because it’s Sunday, and they’re typically more involved.
I skipped part 2 today, not a fan of these grid challenges in Elixir. I did get part 1 running in 3ms using :ets for constant time lookups though. And I wrote a crazy single-pass binary pattern-matching recursive function to parse the input that I’ll spare you all from seeing 
1
stevensonmt
Finally managed to get part 2 correct after completely redoing my parser approach. I still don’t understand the bug my original approach had as it worked for part 1 and the example input for part 2. Still, the second attempt is much cleaner (not CLEAN, but not the mess of spaghetti my first attempt was).
Full code here. Just the parser:
defmodule Parser do
alias AocToolbox.Input
defstruct [
:max_ndx,
line: "",
row: 0,
ndx: 0,
graph: %{},
num_map: %{},
symbol_neighbors_map: %{}
]
def parse_raw_graph(text) do
text
|> Input.lines()
|> Enum.with_index()
|> Enum.map(fn {line, row} ->
parse_lines(%__MODULE__{line: line, row: row, max_ndx: String.length(line)})
end)
|> Enum.reduce(fn row, acc ->
row
|> Enum.map(fn {key, val} ->
{key, Map.merge(val, acc[key], fn _, v1, v2 -> MapSet.union(v1, v2) end)}
end)
end)
end
def parse_lines(%__MODULE__{
ndx: ndx,
max_ndx: max_ndx,
graph: graph,
num_map: num_map,
symbol_neighbors_map: symbol_neighbors_map
})
when ndx > max_ndx,
do: [graph: graph, num_map: num_map, symbol_neighbors_map: symbol_neighbors_map]
def parse_lines(%__MODULE__{
line: <<".", rest::binary>>,
row: row,
ndx: ndx,
max_ndx: max_ndx,
graph: graph,
num_map: num_map,
symbol_neighbors_map: symbol_neighbors_map
}),
do:
parse_lines(%__MODULE__{
line: rest,
row: row,
ndx: ndx + 1,
max_ndx: max_ndx,
graph: Map.put(graph, {row, ndx}, nil),
num_map: num_map,
symbol_neighbors_map: symbol_neighbors_map
})
def parse_lines(%__MODULE__{
line: <<?*, rest::binary>>,
row: row,
ndx: ndx,
max_ndx: max_ndx,
graph: graph,
num_map: num_map,
symbol_neighbors_map: symbol_neighbors_map
}) do
parse_lines(%__MODULE__{
line: rest,
row: row,
ndx: ndx + 1,
max_ndx: max_ndx,
graph: Map.put(graph, {row, ndx}, :gear),
num_map: num_map,
symbol_neighbors_map:
update_symbol_neighbors(symbol_neighbors_map, row, ndx, max_ndx, :gear)
})
end
def parse_lines(%__MODULE__{
line: <<d, rest::binary>>,
row: row,
ndx: ndx,
max_ndx: max_ndx,
graph: graph,
num_map: num_map,
symbol_neighbors_map: symbol_neighbors_map
})
when d > 47 and d < 58 do
{num, rem_line, last_ndx} = parse_nums(d - 48, rest, ndx)
graph =
ndx..last_ndx
|> Enum.reduce(graph, fn n, g -> Map.update(g, {row, n}, num, fn _ -> num end) end)
num_map =
all_associations(ndx, last_ndx, row)
|> Map.merge(num_map, fn _, v1, v2 -> MapSet.union(v1, v2) end)
parse_lines(%__MODULE__{
line: rem_line,
row: row,
ndx: last_ndx + 1,
max_ndx: max_ndx,
graph: graph,
num_map: num_map,
symbol_neighbors_map: symbol_neighbors_map
})
end
def parse_lines(%__MODULE__{
line: "",
graph: graph,
num_map: num_map,
symbol_neighbors_map: symbol_neighbors_map
}),
do: [graph: graph, num_map: num_map, symbol_neighbors_map: symbol_neighbors_map]
def parse_lines(%__MODULE__{
line: <<s, rest::binary>>,
row: row,
ndx: ndx,
max_ndx: max_ndx,
graph: graph,
num_map: num_map,
symbol_neighbors_map: symbol_neighbors_map
}),
do:
parse_lines(%__MODULE__{
line: rest,
row: row,
ndx: ndx + 1,
max_ndx: max_ndx,
graph: Map.put(graph, {row, ndx}, :symbol),
num_map: num_map,
symbol_neighbors_map:
update_symbol_neighbors(symbol_neighbors_map, row, ndx, max_ndx, :symbol)
})
defp parse_nums(acc, <<d, rest::binary>>, ndx) when d > 47 and d < 58 do
parse_nums(acc * 10 + d - 48, rest, ndx + 1)
end
defp parse_nums(acc, bin, ndx), do: {acc, bin, ndx}
defp all_associations(start, stop, row) do
start..stop
|> Enum.to_list()
|> AocToolbox.Math.permutations()
|> Enum.map(fn [a | rest] ->
{{row, a}, MapSet.new(Enum.map(rest, fn b -> {row, b} end))}
end)
|> Enum.into(%{})
end
defp update_symbol_neighbors(symbol_neighbors_map, row, ndx, max_ndx, symbol) do
for i <- -1..1,
j <- -1..1,
not (i == 0 and j == 0),
row + i >= 0,
ndx + j >= 0,
ndx + j <= max_ndx,
reduce: symbol_neighbors_map do
acc ->
Map.update(acc, {symbol, {row, ndx}}, MapSet.new([{row + i, ndx + j}]), fn curr ->
MapSet.put(curr, {row + i, ndx + j})
end)
end
end
1
kip
ex_cldr Core Team
For part 1 I decided to try a “sliding window” approach. After splitting into lines, the code “slides” a window over three adjacent lines simultaneously looking for a number on the second line that is has a symbol somewhere around it. This limits the amount of parsing done and yes, it’s not very reusable for the second part (which I may not finish today).
It’s not super pretty, but it does run in about 3.5ms on my MacBook Pro (M1 Max). And I do think its quite easy to comprehend.
Preprocessing
Just split the lines. To ensure a regular window frame for the sliding window, add a border of one "." one each side. def part_1 do
input = parse_input()
find_parts(input, 0, tl(input))
end
def parse_input do
list = String.split(@input, "\n", trim: true)
length = String.length(hd(list))
header = String.duplicate(".", length)
[header | list] ++ [header]
|> Enum.map(&("." <> &1 <> "."))
end
# Guards used for surrounding symbol detection
defguard are_digits(c1, c2, c3) when
(c1 in ?0..?9 and c2 in ?0..?9 and c3 in ?0..?9)
defguard are_digits(c1, c2) when
(c1 in ?0..?9 and c2 in ?0..?9)
defguard are_digits(c1) when
(c1 in ?0..?9)
defguard is_surrounded_by_symbol(l1c1, l1c2, l1c3, l1c4, l1c5, l3c1, l3c2, l3c3, l3c4, l3c5, l2c1, l2c5) when
(l1c1 != ?. or l1c2 != ?. or l1c3 != ?. or l1c4 != ?. or l1c5 != ?. or
l3c1 != ?. or l3c2 != ?. or l3c3 != ?. or l3c4 != ?. or l3c5 != ?. or
l2c1 != ?. or l2c5 != ?.)
defguard is_surrounded_by_symbol(l1c1, l1c2, l1c3, l1c4, l3c1, l3c2, l3c3, l3c4, l2c1, l2c4) when
(l1c1 != ?. or l1c2 != ?. or l1c3 != ?. or l1c4 != ?. or
l3c1 != ?. or l3c2 != ?. or l3c3 != ?. or l3c4 != ?. or
l2c1 != ?. or l2c4 != ?.)
defguard is_surrounded_by_symbol(l1c1, l1c2, l1c3, l3c1, l3c2, l3c3, l2c1, l2c3) when
(l1c1 != ?. or l1c2 != ?. or l1c3 != ?. or
l3c1 != ?. or l3c2 != ?. or l3c3 != ?. or
l2c1 != ?. or l2c3 != ?.)
Part 1
# Three digit number
def find_parts([<<l1c1, l1c2, l1c3, l1c4, l1c5, l1_rest::binary>>, <<l2c1, l2c2, l2c3, l2c4, l2c5, l2_rest::binary>>, <<l3c1, l3c2, l3c3, l3c4, l3c5, l3_rest::binary>> | rest], acc, tail)
when are_digits(l2c2, l2c3, l2c4) and
is_surrounded_by_symbol(l1c1, l1c2, l1c3, l1c4, l1c5, l3c1, l3c2, l3c3, l3c4, l3c5, l2c1, l2c5) do
acc = ((l2c2 - ?0) * 100) + ((l2c3 - ?0) * 10) + (l2c4 - ?0) + acc
find_parts([<<l1c5, l1_rest::binary>>, <<l2c5, l2_rest::binary>>, <<l3c5, l3_rest::binary>> | rest], acc, tail)
end
# Three digit number but no symbol, skip over the number
def find_parts([<<_, _, _, _, l1c5, l1_rest::binary>>, <<_, l2c2, l2c3, l2c4, l2c5, l2_rest::binary>>, <<_, _, _, _, l3c5, l3_rest::binary>> | rest], acc, tail)
when are_digits(l2c2, l2c3, l2c4) do
find_parts([<<l1c5, l1_rest::binary>>, <<l2c5, l2_rest::binary>>, <<l3c5, l3_rest::binary>> | rest], acc, tail)
end
# Two digit number surrounded by a symbol
def find_parts([<<l1c1, l1c2, l1c3, l1c4, l1_rest::binary>>, <<l2c1, l2c2, l2c3, l2c4, l2_rest::binary>>, <<l3c1, l3c2, l3c3, l3c4, l3_rest::binary>> | rest], acc, tail)
when are_digits(l2c2, l2c3) and
is_surrounded_by_symbol(l1c1, l1c2, l1c3, l1c4, l3c1, l3c2, l3c3, l3c4, l2c1, l2c4) do
acc = ((l2c2 - ?0) * 10) + (l2c3 - ?0) + acc
find_parts([<<l1c4, l1_rest::binary>>, <<l2c4, l2_rest::binary>>, <<l3c4, l3_rest::binary>> | rest], acc, tail)
end
# Two digit number but no symbol, skip over the number
def find_parts([<<_, _, _, l1c4, l1_rest::binary>>, <<_, l2c2, l2c3, l2c4, l2_rest::binary>>, <<_, _, _, l3c4, l3_rest::binary>> | rest], acc, tail)
when are_digits(l2c2, l2c3) do
find_parts([<<l1c4, l1_rest::binary>>, <<l2c4, l2_rest::binary>>, <<l3c4, l3_rest::binary>> | rest], acc, tail)
end
# One digit number surrounded with a symbol
def find_parts([<<l1c1, l1c2, l1c3, l1_rest::binary>>, <<l2c1, l2c2, l2c3, l2_rest::binary>>, <<l3c1, l3c2, l3c3, l3_rest::binary>> | rest], acc, tail)
when are_digits(l2c2) and
is_surrounded_by_symbol(l1c1, l1c2, l1c3, l3c1, l3c2, l3c3, l2c1, l2c3) do
acc = (l2c2 - ?0) + acc
find_parts([<<l1c3, l1_rest::binary>>, <<l2c3, l2_rest::binary>>, <<l3c3, l3_rest::binary>> | rest], acc, tail)
end
# Move the window across one character
def find_parts([<<_, rest_1::binary>>, <<_, rest_2::binary>>, <<_, rest_3::binary>> | rest], acc, tail) do
find_parts([rest_1, rest_2, rest_3 | rest], acc, tail)
end
# Move the window down one line
def find_parts(["", "", "" | _rest], acc, [line_1, line_2, line_3 | tail]) do
find_parts([line_1, line_2, line_3], acc, [line_2, line_3 | tail])
end
# End of input, return the accumulator
def find_parts([_, _, _], acc, _tail) do
acc
end
1
hauleth
epilgrim
oohhhh, completely missed!! nicely done with the Integer.parse(str)… never thought about splitting numbers vs rest this way
0