For Part 1, I was lazy and didn’t want to maintain variables and pass them down to each function (which would also involve merging two different histories after each split), so I used the process dictionary trick I learned about in earlier days from @Aetherus to represent state and have the functions produce side effects (which I thought was ugly). For Part 2, though, I was quite happy with this approach because then I just wrapped this code in Task.async_stream/2 and found the max 
2 Likes
Pretty straightforward.
A MapSet to prevent loops and brute force.
import AOC
aoc 2023, 16 do
def p1(input) do
input
|> Grid.parse()
|> then(fn {max, grid} -> {max, Map.new(grid)} end)
|> compute({{0, 0}, :east})
end
def compute(grid, start) do
grid
|> recurse([start], MapSet.new(), MapSet.new())
|> Enum.count()
end
def p2(input) do
{{rows, cols}, points} = input |> Grid.parse()
grid = {{rows, cols}, Map.new(points)}
(for row <- 0..(rows-1), do: [{{row, 0}, :east}, {{row, cols-1}, :west}] ++
for col <- 0..(cols-1), do: [{{0, col}, :south}, {{rows-1, col}, :north}])
|> List.flatten()
|> Enum.map(&compute(grid, &1))
|> Enum.max()
end
def recurse(_, [], energized, _), do: energized
def recurse({_, map} = grid, [active | actives], energized, seen) do
{active_pos, active_dir} = active
if not MapSet.member?(seen, active) and Grid.in?(grid, active_pos) do
energized_new = MapSet.put(energized, active_pos)
seen_new = MapSet.put(seen, active)
f = fn candidates -> candidates |> Kernel.++(actives) |> then(&recurse(grid, &1, energized_new, seen_new)) end
item = map[active_pos]
cond do
item == "." or
(item == "|" and active_dir in [:north, :south]) or
(item == "-" and active_dir in [:east, :west]) -> f.([next(active)])
item == "|" -> f.([next({active_pos, :north}), next({active_pos, :south})])
item == "-" -> f.([next({active_pos, :west}), next({active_pos, :east})])
item == "/" -> f.([next({active_pos, flip_sw(active_dir)})])
item == "\\" -> f.([next({active_pos, flip_se(active_dir)})])
end
else
recurse(grid, actives, energized, seen)
end
end
def flip_sw(dir), do: %{north: :east, south: :west, west: :south, east: :north}[dir]
def flip_se(dir), do: %{north: :west, south: :east, west: :north, east: :south}[dir]
def next({{row, col}, :west}), do: {{row, col-1}, :west}
def next({{row, col}, :east}), do: {{row, col+1}, :east}
def next({{row, col}, :north}), do: {{row-1, col}, :north}
def next({{row, col}, :south}), do: {{row+1, col}, :south}
end
1 Like
TIL of ~w()a to generate a list of atoms instead of words, pretty cool!
1 Like
My solution:
Not that interested in today’s puzzles.
Parsing input
grid =
for {row, i} <- puzzle_input |> String.split() |> Stream.with_index(),
{val, j} <- row |> String.to_charlist() |> Stream.with_index(),
into: %{},
do: {{i, j}, val}
Solutions for both parts
defmodule AoC2023.Day16 do
def part1(grid) do
shoot(grid, {0, 0}, {0, 1}, MapSet.new())
|> count_energized()
end
def part2(grid) do
{max_i, max_j} = grid |> Map.keys() |> Enum.max()
count =
0..max_i
|> Enum.map(&{&1, 0})
|> Task.async_stream(&count_energized(shoot(grid, &1, {0, 1}, MapSet.new())), ordered: false)
|> Enum.max()
count =
0..max_i
|> Enum.map(&{&1, max_j})
|> Task.async_stream(&count_energized(shoot(grid, &1, {0, -1}, MapSet.new())), ordered: false)
|> Enum.reduce(count, &max/2)
count =
0..max_j
|> Enum.map(&{0, &1})
|> Task.async_stream(&count_energized(shoot(grid, &1, {1, 0}, MapSet.new())), ordered: false)
|> Enum.reduce(count, &max/2)
count =
0..max_j
|> Enum.map(&{max_i, &1})
|> Task.async_stream(&count_energized(shoot(grid, &1, {-1, 0}, MapSet.new())), ordered: false)
|> Enum.reduce(count, &max/2)
elem(count, 1)
end
defp count_energized(set) do
set
|> Enum.map(&elem(&1, 0))
|> Enum.uniq()
|> length()
end
defp shoot(grid, {i, j} = position, {di, dj} = direction, acc) do
if {position, direction} in acc do
acc
else
case grid[position] do
nil ->
acc
?. ->
shoot(grid, {i + di, j + dj}, direction, MapSet.put(acc, {position, direction}))
?\\ ->
shoot(grid, {i + dj, j + di}, {dj, di}, MapSet.put(acc, {position, direction}))
?/ ->
shoot(grid, {i - dj, j - di}, {-dj, -di}, MapSet.put(acc, {position, direction}))
?- when di == 0 ->
shoot(grid, {i + di, j + dj}, direction, MapSet.put(acc, {position, direction}))
?| when dj == 0 ->
shoot(grid, {i + di, j + dj}, direction, MapSet.put(acc, {position, direction}))
?- ->
acc = shoot(grid, {i, j - 1}, {0, -1}, MapSet.put(acc, {position, direction}))
shoot(grid, {i, j + 1}, {0, 1}, MapSet.put(acc, {position, direction}))
?| ->
acc = shoot(grid, {i - 1, j}, {-1, 0}, MapSet.put(acc, {position, direction}))
shoot(grid, {i + 1, j}, {1, 0}, MapSet.put(acc, {position, direction}))
end
end
end
end
Hello,
I was afraid that the second part would ask to rotate mirrors to create the maximum energy but thanks it was much easier.
I have no idea how to optimize that so I just simulate all the beams for part 2, and it takes more than one second. Any idea?
1 Like
I did the same. It also took me more than 1 second to run, so I just parallelized them 
Ah yes I generally do not use task async stream because I like to debug the outputs but now that it works, i’ll try it 
Edit: yeah, 500ms, good enough, thanks!
Also ordered: false comes in handy
1 Like
I believe it’s possible to memoize the paths given (row, column, direction). Since you’re just choosing a different starting position, but if the beam traveling left reaches \, it should still be the same path throughout. Though, I did not try this out so it could be false
2 Likes
Bruteforced part 2 without memoization… takes around 16 seconds in LiveBook on my M2 Pro. 
Not sure if this is the right place to post this (and also probably a silly question), but how are y’all parsing the example input? It seems like the escape character is messing up the rows. I’m just doing a simple String.split(input, "\n"), but the lists/rows are not equal length.
I thought the same… with me it turned out they were the same length, but when I printed them (as charlists) the backslashes got quoted - ie. printed as \\ rather than \ - and so visually they looked as if they’d have different length.
For this problem I made an exception to how I usually provide input and instead read the input from a file, because I suspected the backsplashes would mess up the input within IEx.
This was it. I usually write tests asserting on the example outputs by throwing the sample inputs in a multi-line string. I’m just having this day’s tests read from a text file instead, and now I’m seeing the correct row lengths. Cheers!
Okay, sorted it out. I was making it more complex by considering the “next” space rather than the current space and I was not using the correct origin point for rays emanating from a reflection object. Changed the origin to {0,0} and
?/ ->
trace(
new(
Nx.add(ray.origin, Nx.multiply(ray.dir, ray.len)),
update_dir(ray.dir, :reflect270)
),
scene
)
?\\ ->
trace(
new(
Nx.add(ray.origin, Nx.multiply(ray.dir, ray.len)),
update_dir(ray.dir, :reflect90)
),
scene
)
needed to be
?/ ->
dir = update_dir(ray.dir, :reflect270)
origin = Nx.add(ray.origin, Nx.multiply(ray.dir, ray.len)) |> Nx.add(dir)
trace(new(origin, dir), scene)
?\\ ->
dir = update_dir(ray.dir, :reflect90)
origin = Nx.add(ray.origin, Nx.multiply(ray.dir, ray.len)) |> Nx.add(dir)
trace(new(origin, dir), scene)
It’s still a lot slower than I’d like, probably b/c of all the calls to :ets.lookup_element and :ets.insert.
============================================================================
I’m driving myself crazy on this one. I’m blind to the error I’m making at this point though. I’m getting the right output for the test input. The real input must have some edge cases that cause an inappropriate early return because I’m getting an answer that’s too low.
@origin Nx.tensor([-1, 0])
@initial_dir Nx.tensor([1, 0])
@north Nx.tensor([0, -1])
@south Nx.tensor([0, 1])
@west Nx.tensor([-1, 0])
@east Nx.tensor([1, 0])
@horizontal [@east, @west]
@vertical [@north, @south]
defstruct origin: @origin, dir: @initial_dir, len: 0
@type t() :: %__MODULE__{dir: dir(), origin: coord(), len: integer}
@doc "Create new ray at origin {0,0} traveling east, initiate ray path at origin as initial node in path"
@spec new :: t()
def new() do
maybe_start_cache()
%__MODULE__{}
end
@doc "Create new ray at specified oring, with specified direction."
@spec new(coord(), dir()) :: t()
def new(origin, dir) do
maybe_start_cache()
%__MODULE__{origin: origin, dir: dir}
end
@spec maybe_start_cache() :: :ets.table() | atom
defp maybe_start_cache() do
if :ets.whereis(:ray_cache) == :undefined do
:ets.new(:ray_cache, [:named_table])
:ets.insert(:ray_cache, {:seen, MapSet.new()})
else
:cache_already_started
end
end
@doc "At end of ray (OOB, or reflecting/refracting), therefore update the cache with all points travelled by the ray."
@spec update_cache(t()) :: boolean
def update_cache(%__MODULE__{dir: dir, origin: origin, len: len} = _ray) do
seen = :ets.lookup_element(:ray_cache, :seen, 2)
0..len
|> Enum.reduce(seen, fn i, acc ->
MapSet.put(acc, {Nx.add(origin, Nx.multiply(dir, i)), dir})
end)
|> do_update_cache()
end
@spec do_update_cache(MapSet.t(path_el())) :: boolean
defp do_update_cache(seen) do
:ets.insert(:ray_cache, {:seen, seen})
end
@doc "Change direction the ray is traveling but not the location of end of ray."
@spec update_dir(dir(), interaction()) :: t()
def update_dir(dir, :reflect270),
do: Nx.multiply(Nx.reverse(dir), -1)
def update_dir(dir, :reflect90),
do: Nx.reverse(dir)
def update_dir(dir, _), do: dir
@doc """
Track the ray through the scene. A ray ends when it runs off the edge of the scene, refracts, or is reflected. In the
first case the cache is updated but no new ray created. In the second case the cache is updated and two rays are created,
each orthogonal to the direction of the original ray and opposite and colinear to each other. In the case of reflection,
a single new ray is created at 90° or 270° to the original ray. Note that future work could potentiall make it possible
to have objects with defined interactions that reflect or refract with customized angles but this is not currently available.
"""
@spec trace(t(), scene()) :: status()
def trace(ray, scene) do
next = Nx.add(ray.origin, Nx.multiply(ray.dir, ray.len + 1))
next_obj = Map.get(scene, List.to_tuple(Nx.to_list(next)))
cond do
next_obj == nil ->
update_cache(ray)
{:complete, :oob}
found?({next, ray.dir}) ->
ray = %__MODULE__{ray | len: ray.len + 1}
update_cache(ray)
{:complete, :loop}
true ->
ray = %__MODULE__{ray | len: ray.len + 1}
update_cache(ray)
do_trace(ray, next_obj, scene)
end
end
@spec found?(path_el()) :: boolean
defp found?({coord, dir}) do
seen = :ets.lookup_element(:ray_cache, :seen, 2)
MapSet.member?(seen, {coord, dir})
end
@spec do_trace(t(), obj(), scene()) :: status()
def do_trace(ray, obj, scene) do
case obj do
nil ->
{:complete, :oob}
?. ->
trace(ray, scene)
?- when ray.dir in @horizontal ->
trace(ray, scene)
?| when ray.dir in @vertical ->
trace(ray, scene)
?/ ->
trace(
new(
Nx.add(ray.origin, Nx.multiply(ray.dir, ray.len)),
update_dir(ray.dir, :reflect270)
),
scene
)
?\\ ->
trace(
new(
Nx.add(ray.origin, Nx.multiply(ray.dir, ray.len)),
update_dir(ray.dir, :reflect90)
),
scene
)
?- ->
refract_h(ray, scene)
?| ->
refract_v(ray, scene)
end
end
@spec refract_h(t(), scene()) :: status()
def refract_h(ray, scene) do
origin = Nx.add(ray.origin, Nx.multiply(ray.dir, ray.len))
trace(new(origin, @east), scene)
trace(new(origin, @west), scene)
end
@spec refract_v(t(), scene()) :: status()
def refract_v(ray, scene) do
origin = Nx.add(ray.origin, Nx.multiply(ray.dir, ray.len))
trace(new(origin, @north), scene)
trace(new(origin, @south), scene)
end
I’m parsing the input into a map of %{{col, row} => char} and getting the count from
:ets.lookup_element(:ray_cache, :seen, 2)
|> Enum.map(&elem(&1, 0))
|> Enum.map(&Nx.to_list/1)
|> Enum.reject(fn n -> n == {-1, 0} end)
|> Enum.uniq()
|> Enum.count()
My beginner’s solution, Day 16 part 1.
I decided this was a good opportunity to learn elixir processes.
For each tile, a process is spawned that “knows” it’s type and pids of it’s neighbors.
When a process receives a message, it sends a message(s), depending on tile type and source location. First time it happens, it also sends a message to :energized which counts towards the result.
It was tricky to get my head around it and get it right, but I’m pretty proud I succeeded.
I can still see many ways to improve, but I will take those lessons with me for Advent of Code 2024.
Cheers
defmodule Day16 do
def part1(input) do
{border_pid,
top_left_tile_pid} = initialize(input)
Process.register spawn(fn -> energized() end), :energized
send(top_left_tile_pid, border_pid) # the beam enters
end
def energized(count \\ 0) do
receive do
_ -> energized(count+1)
after # 1000ms without a message
1000 -> IO.puts "No. energized tiles: #{count} "
end
end
def init(tile), do: (receive do {l, u, r, d} -> tile_cold(l, u, r, d, tile) end)
def tile_cold(left, up, right, down, tile) do
reflect(left, up, right, down, tile)
send(:energized, self())
tile_hot(left, up, right, down, tile)
end
def tile_hot(left, up, right, down, tile) do
reflect(left, up, right, down, tile)
tile_hot(left, up, right, down, tile)
end
def reflect(left, up, right, down, tile) do
case tile do
#dot
:. -> receive do
^left -> right
^up -> down
^right -> left
^down -> up
end |> send(self())
#slash
:/ -> receive do
^left -> up
^up -> left
^right -> down
^down -> right
end |> send(self())
#backslash
:"\\" -> receive do
^left -> down
^up -> right
^right -> up
^down -> left
end |> send(self())
#pipe
:| -> receive do
^left -> [up, down]
^up -> [down]
^right -> [up, down]
^down -> [up]
end |> Enum.map(&send(&1, self()))
#dash
:- -> receive do
^left -> [right]
^up -> [left, right]
^right -> [left]
^down -> [left, right]
end |> Enum.map(&send(&1, self()))
end
end
def loop(), do: loop()
def initialize(raw_layout) do
border = spawn(fn -> loop() end)
border_row = raw_layout
|> String.split("\n")
|> List.first
|> String.length
|> then(&List.duplicate(border, (&1)+2))
grid = raw_layout
|> String.split("\n")
|> Enum.map(fn raw_line -> raw_line
|> String.graphemes
|> Enum.map(&String.to_atom/1)
|> Enum.map(&spawn(__MODULE__, :init, [&1]))
|> then(&([border] ++ &1 ++ [border]))
end)
|> then(&([border_row] ++ &1 ++ [border_row]))
for {row, r} <- Enum.with_index(grid) |> Enum.slice(1..-2) do
for {pid, c} <- Enum.with_index(row) |> Enum.slice(1..-2) do
left = grid |> Enum.at(r) |> Enum.at(c-1)
up = grid |> Enum.at(r-1) |> Enum.at(c)
right = grid |> Enum.at(r) |> Enum.at(c+1)
down = grid |> Enum.at(r+1) |> Enum.at(c)
send(pid, {left, up, right, down})
end
end
{
border,
grid |> Enum.at(1) |> Enum.at(1)
}
end
end
PS. Check this out (not me):
Milada (@miladamilli): "#AdventOfCode Day 16 (part 1) in #GodotEngine" | nitter
