Fun day today! Quite straightforward but the key observations are:
import AOC
aoc 2023, 13 do
def p1(input) do
{xs, ys} = input |> grids() |> Enum.map(&calculate/1) |> Enum.unzip()
combine = fn items -> items |> List.flatten() |> Enum.map(fn n -> (1 + n)/2 end) |> Enum.sum() end
100*combine.(xs) + combine.(ys)
end
def p2(input) do
{xs, ys} = input |> grids() |> Enum.map(&calculate_with_smudge/1) |> Enum.unzip()
combine = fn items -> items |> List.flatten() |> Enum.map(fn n -> (1 + n)/2 end) |> Enum.sum() end
100*combine.(xs) + combine.(ys)
end
def calculate(grid) do
grid = grid |> Enum.map(fn {x, y} -> {2*x, 2*y} end) |> MapSet.new
max_x = max_(grid, &get_x/1)
max_y = max_(grid, &get_y/1)
{1..max_x//2 |> Enum.filter(fn i -> x_reflect?(grid, i, max_x) end),
1..max_y//2 |> Enum.filter(fn i -> y_reflect?(grid, i, max_y) end)}
end
@spec calculate_with_smudge(any()) :: {list(), list()}
def calculate_with_smudge(grid) do
{original_xs, original_ys} = calculate(grid)
grid_set = grid |> MapSet.new()
max_x = max_(grid_set , &get_x/1)
max_y = max_(grid_set, &get_y/1)
for x <- 0..max_x, y <- 0..max_y do
calculate(invert(grid_set, {x, y}))
end
|> Enum.reject(fn {[], []} -> true; _ -> false end)
|> Enum.reduce(fn {x, y}, {x2, y2} -> {x ++ x2, y ++ y2} end)
|> then(fn {xs, ys} -> {Enum.uniq(xs) -- original_xs, Enum.uniq(ys) -- original_ys} end)
end
def invert(grid, p) do
if MapSet.member?(grid, p) do
MapSet.delete(grid, p)
else
MapSet.put(grid, p)
end
end
def get_x({x, _}), do: x
def get_y({_, y}), do: y
def max_(grid, f), do: Enum.max_by(grid, f) |> then(f)
def x_reflect?(grid, i, max) do
grid
|> Enum.group_by(&get_y/1)
|> Enum.all?(
fn {_, row} ->
Enum.all?(
row,
fn {x, y} -> x_r = i + i - x; x_r > max || x_r < 0 || Enum.member?(grid, {x_r, y}) end
)
end)
end
def y_reflect?(grid, i, max) do
grid
|> Enum.group_by(&get_x/1)
|> Enum.all?(
fn {_, col} ->
Enum.all?(
col,
fn {x, y} -> y_r = i + i - y; y_r > max || y_r < 0 || Enum.member?(grid, {x, y_r}) end
)
end)
end
def grid(input) do
input
|> String.split("\n", trim: true)
|> Enum.with_index
|> Enum.flat_map(
fn {line, row} ->
line
|> String.split("", trim: true)
|> Enum.with_index
|> Enum.map(fn {char, col} -> {{row, col}, char} end)
|> Enum.filter(fn {_, char} -> char == "#" end)
|> Enum.map(&elem(&1, 0))
end)
end
def grids(input) do
input |> String.split("\n\n") |> Enum.map(&grid/1)
end
end
Easier than yesterday 
Today I learnt that you can match a 0-length binary part in a patter.
Each pattern is a list of string, so to change a smudge I need to update the string at list index Y and change a character in that string at index X. The following code works when X is zero.
defp stream_changes(pattern) do
yo = length(pattern) - 1
xo = (pattern |> hd() |> String.length()) - 1
Stream.resource(
fn -> {0, 0} end,
fn
{_, y} when y > yo -> raise "expleted"
{x, y} when x > xo -> {[], {0, y + 1}}
{x, y} -> {[fix_pattern(pattern, x, y)], {x + 1, y}}
end,
fn _ -> nil end
)
end
defp fix_pattern(pattern, x, y) do
List.update_at(pattern, y, fn <<prev::binary-size(x), c, rest::binary>> ->
new_c =
case c do
?. -> ?#
?# -> ?.
end
<<prev::binary-size(x), new_c, rest::binary>>
end)
end
I used Stream.resource instead of Stream.unfold because it lets you return an empty list, which is convenient to reset the stream state to X=0 and Y+1.
I’m so not proud of my code. Just a pile of junk. Ctrl+C & Ctrl+V everywhere. Anyway, I post it here.
I have optimized the code as much as possible to make it appear more comprehensible. If there are any parts that someone doesn’t understand, I am more than willing to add additional comments.
The approach I took for solving part 1 was not useful for part 1, so I had to rewrite my solver so that it was able to handle part 2.
My solution:
Nice usage of bit strings 
defmodule Day13 do
def find_axes(list) do
reversed = Enum.reverse(list)
len = length(list)
back = dbg(do_find(list, 0))
front = dbg(do_find(reversed, 0))
[
if(back, do: div(len - back, 2) + back),
if(front, do: div(len - front, 2))
]
|> Enum.filter(& &1)
end
defp do_find([_], _), do: nil
defp do_find([_ | a], n) when rem(n, 2) == 0, do: do_find(a, n + 1)
defp do_find(a, n) do
if palindrome?(a) do
n
else
do_find(tl(a), n + 1)
end
end
def palindrome?(list) do
list == Enum.reverse(list)
end
def print_mirror({rows, cols, _, _}) do
width = length(cols)
display =
for row <- rows do
for digit <- Integer.digits(row, 2) do
if digit == 1, do: "#", else: "."
end
|> List.to_string()
|> String.pad_leading(width, ".")
end
IO.puts(Enum.intersperse(display, "\n"))
end
end
mirrors =
puzzle_input
|> String.split("\n\n", trim: true)
|> Enum.map(fn grid ->
mirror =
grid
|> String.split("\n", trim: true)
|> Enum.map(fn line ->
for <<c <- line>>, do: if(c == ?#, do: 1, else: 0)
end)
rows = Enum.map(mirror, &Integer.undigits(&1, 2))
cols = Enum.zip_with(mirror, &Integer.undigits(&1, 2))
row = Day13.find_axes(rows)
col = Day13.find_axes(cols)
{rows, cols, row, col}
end)
Enum.map(mirrors, fn {_, _, row, col} ->
List.first(col, 0) + List.first(row, 0) * 100
end)
|> Enum.sum()
defmodule Day13.Part2 do
import Bitwise
def alternatives(list, a, n) do
l = length(list)
list =
for i <- 0..n,
d = bsl(1, i),
j <- 0..l,
desmudged = List.update_at(list, j, &bxor(&1, d)),
v <- Day13.find_axes(desmudged),
v not in a,
do: v
Enum.dedup(list)
end
end
mirrors
|> Enum.with_index()
|> Enum.map(fn {{rows, cols, row, col}, _idx} ->
row = List.first(Day13.Part2.alternatives(rows, row, length(cols)), 0)
col = List.first(Day13.Part2.alternatives(cols, col, length(rows)), 0)
row * 100 + col
end)
|> Enum.sum()
My beginner’s solution, Day 13 part 1. Point of Incidence
defmodule Day13 do
def part1(input) do
parse(input)
|> Enum.map(fn pattern -> pattern
|> reflection()
|> case do
index when is_number(index) -> 100 * index
list -> Enum.reverse(list) |> List.zip |> Enum.map(&Tuple.to_list/1) |> reflection()
end |> tap(&IO.puts(&1))
end)
|> Enum.sum
end
def reflection(righthand, lefthand \\ [])
def reflection([head | tail], []), do: reflection(tail, [head])
def reflection([head | tail], lefthand) do
length = [[head|tail], lefthand]
|> Enum.map(&length/1)
|> Enum.min
if Enum.take([head|tail], length) == Enum.take(lefthand, length) do
length(lefthand)
else
reflection(tail, [head | lefthand])
end
end
def reflection([], lefthand), do: lefthand # now it's reversed
def parse(raw_note) do
raw_note
|> String.split("\n\n")
|> Enum.map(&parse_pattern/1)
end
def parse_pattern(raw_pattern) do
raw_pattern
|> String.split("\n")
|> Enum.map(&parse_line/1)
end
def parse_line(raw_line) do
raw_line
|> String.graphemes
|> Enum.map(&(case &1 do "." -> :ash; "#" -> :rock; end))
end
end
Went with Nx again for today’s problem.
defmodule Part1 do
def parse(input) do
for pattern <- String.split(input, "\n\n") do
for line <- String.split(pattern, "\n", trim: true) do
String.graphemes(line)
|> Enum.map(fn c -> if c == "#", do: 1, else: 0 end)
end
|> Nx.tensor(type: :u8, names: [:y, :x])
end
end
def summarize(patterns) do
for pattern <- patterns do
{axis, {index, _}} =
reflect(pattern)
left = index + 1
if axis == :x, do: left, else: 100 * left
end
|> Enum.sum()
end
def reflect(pattern) do
[:x, :y]
|> Enum.map(fn axis -> {axis, reflect_along(pattern, axis)} end)
|> Enum.max_by(fn {_, {_, size}} -> size end)
end
def reflect_along(pattern, axis) do
0..Nx.axis_size(pattern, axis)
|> Enum.reduce({-1, -1}, fn index, {_, prev_size} = prev ->
{_, next_size} = next = reflect_at(pattern, axis, index)
if next_size > prev_size, do: next, else: prev
end)
end
def reflect_at(pattern, axis, index), do: reflect_at(pattern, axis, index, index + 1)
def reflect_at(pattern, axis, left, right) do
if left < 0 or right >= Nx.axis_size(pattern, axis) do
reflection(left + 1, right - 1)
else
left_tensor = pattern[Keyword.new([{axis, left}])]
right_tensor = pattern[Keyword.new([{axis, right}])]
if left_tensor != right_tensor do
{-1, -1}
else
reflect_at(pattern, axis, left - 1, right + 1)
end
end
end
def reflection(left, right) when left > right, do: {-1, -1}
def reflection(left, right) do
size = div(right - left, 2)
{left + size, size}
end
end
input
|> Part1.parse()
|> Part1.summarize()
defmodule Part2 do
def summarize(patterns) do
for pattern <- patterns do
{axis, {index, _}} =
reflect(pattern)
left = index + 1
if axis == :x, do: left, else: 100 * left
end
|> Enum.sum()
end
def reflect(pattern) do
[:x, :y]
|> Enum.map(fn axis -> {axis, reflect_along(pattern, axis)} end)
|> Enum.max_by(fn {_, {_, size}} -> size end)
end
def reflect_along(pattern, axis) do
0..Nx.axis_size(pattern, axis)
|> Enum.reduce({-1, -1}, fn index, prev ->
{start, size, smudge} = reflect_at(pattern, axis, index)
if smudge, do: {start, size}, else: prev
end)
end
def reflect_at(pattern, axis, index), do: reflect_at(pattern, axis, index, index + 1, false)
def reflect_at(pattern, axis, left, right, smudge) do
if left < 0 or right >= Nx.axis_size(pattern, axis) do
reflection(left + 1, right - 1, smudge)
else
left_tensor = pattern[Keyword.new([{axis, left}])]
right_tensor = pattern[Keyword.new([{axis, right}])]
if left_tensor != right_tensor do
if smudge or
Nx.equal(left_tensor, right_tensor)
|> Nx.logical_not()
|> Nx.sum() != Nx.tensor(1, type: :u64) do
{-1, -1, false}
else
reflect_at(pattern, axis, left - 1, right + 1, true)
end
else
reflect_at(pattern, axis, left - 1, right + 1, smudge)
end
end
end
def reflection(left, right, _) when left > right, do: {-1, -1, false}
def reflection(left, right, smudge) do
size = div(right - left, 2)
{left + size, size, smudge}
end
end
input
|> Part1.parse()
|> Part2.summarize()
I probably over complicated parsing the input, but it worked really well. One thing that got highlighted (for me again) was that the :ets module is kind of non-ergonomic. Like there’s no update_or_insert or insert_new type of functions. I was feeling pretty clever about how easy it was to add the smudge factor to part 1 and make it reusable.
defmodule Day13 do
@moduledoc """
Day13 AoC Solutions
"""
alias AocToolbox.Input
def solve(1, mode) do
__MODULE__.Part1.solve(input(mode))
end
def solve(2, mode) do
__MODULE__.Part2.solve(input(mode))
end
defmodule Part1 do
def solve(input, smudges \\ 0) do
:ets.new(:grids, [:set, :protected, :named_table])
solution =
input
|> parse()
|> grids_to_ets()
|> find_symmetry(smudges)
:ets.delete(:grids)
solution
end
def parse(input) do
input
|> String.split("\n\n")
|> Enum.map(&Input.lines/1)
|> Enum.with_index()
|> Enum.flat_map(&stream_to_grid/1)
end
defp stream_to_grid({stream, grid}) do
stream
|> Enum.with_index()
|> Enum.flat_map(fn {line, row} ->
line
|> String.graphemes()
|> Enum.with_index()
|> Enum.map(fn {g, col} -> {{grid, row, col}, g} end)
end)
end
defp grids_to_ets(grids) do
for {{g, r, c}, v} <- grids, reduce: 0 do
gg ->
:ets.insert(:grids, {{g, r, c}, v})
[{:max_row, r}, {:max_col, c}]
|> Enum.each(fn {max, i} ->
if :ets.member(:grids, {g, max}) do
:ets.update_element(
:grids,
{g, max},
{2, max(i, :ets.lookup_element(:grids, {g, max}, 2))}
)
else
:ets.insert(:grids, {{g, max}, i})
end
end)
max(g, gg)
end
end
defp find_symmetry(max_grid, smudges) do
0..max_grid
|> Task.async_stream(fn g ->
max_row = :ets.lookup_element(:grids, {g, :max_row}, 2)
max_col = :ets.lookup_element(:grids, {g, :max_col}, 2)
grid = get_grid(g, max_row, max_col)
Enum.find_value([{1, max_row}, {2, max_col}], fn {orientation, max} ->
find_axis(grid, max, orientation, smudges)
end)
end)
|> Enum.reduce({0, 0}, fn {:ok, {axis, n}}, {verts, horizs} ->
case axis do
:vertical -> {verts + n, horizs}
:horizontal -> {verts, horizs + n * 100}
end
end)
|> Tuple.to_list()
|> Enum.sum()
end
defp get_grid(grid, max_row, max_col) do
for r <- 0..max_row,
c <- 0..max_col do
:ets.lookup(:grids, {grid, r, c})
end
end
defp find_axis(grid, max, orientation, smudges) when orientation in [1, 2] do
grid
|> Enum.group_by(fn [{k, _v}] ->
elem(k, orientation)
end)
|> do_find_axis(max, 1, elem({:horizontal, :vertical}, orientation - 1), smudges)
end
defp do_find_axis(rows_or_cols, max, maybe_axis \\ 1, orientation, smudges)
defp do_find_axis(_rows_or_cols, max, maybe_axis, _orientation, _smudges)
when max < maybe_axis,
do: false
defp do_find_axis(rows_or_cols, max, maybe_axis, orientation, smudges) do
case 0..(maybe_axis - 1)
|> Enum.map(fn i -> {i, 2 * maybe_axis - 1 - i} end)
|> Enum.filter(fn {l, r} -> r <= max end)
|> Enum.reduce_while(smudges, fn {l, r}, acc ->
case acc - count_diffs(l, r, rows_or_cols, orientation) do
n when n < 0 -> {:halt, false}
n -> {:cont, n}
end
end) do
0 ->
{orientation, maybe_axis}
_ ->
do_find_axis(rows_or_cols, max, maybe_axis + 1, orientation, smudges)
end
end
defp count_diffs(l, r, groups, orientation) do
[l, r] =
[l, r]
|> Enum.map(fn i ->
groups[i]
|> Enum.map(fn [{k, v}] ->
case orientation do
:horizontal -> {elem(k, 2), v}
:vertical -> {elem(k, 1), v}
end
end)
end)
|> Enum.map(fn elems -> MapSet.new(elems) end)
MapSet.difference(l, r) |> MapSet.size()
end
end
defmodule Part2 do
def solve(input) do
input
|> Part1.solve(1)
end
end
end
One of my favorite things about AoC is seeing the various different approaches. What I’ve learned is that the way the data gets structured really dictates how you are able to approach the logic. Often when I’m trying to understand the solutions from others I find I’m struggling because I set up the data so differently that I can’t shift my head around to the flow of the data through their solution.
For part 1 I checked the two sides for equality. For part 2 I checked for a diff of 1. So I only switched the compare_fun.
© Copyright Elixir Forum | Terms | Privacy & Cookies
