9 KiB
9 KiB
AOC2024 Day 12
Mix.install(
[
{:kino_benchee, "0.1.0"}
]
)
Section
defmodule Grid2D do
defstruct width: nil, height: nil
@directions %{
straight: [
{1, 0},
{-1, 0},
{0, 1},
{0, -1}
],
diagonal: [
{1, 1},
{1, -1},
{-1, 1},
{-1, -1}
]
}
def new(width, height) do
%Grid2D{width: width, height: height}
end
@doc """
## Examples
iex> Grid2D.index_to_coord(Grid2D.new(5,5), 0)
{0,0}
iex> Grid2D.index_to_coord(Grid2D.new(5,5), 5)
{0,1}
iex> Grid2D.index_to_coord(Grid2D.new(5,5), 6)
{1,1}
iex> Grid2D.index_to_coord(Grid2D.new(5,5), 3)
{3,0}
iex> Grid2D.index_to_coord(Grid2D.new(5,5), 24)
{4, 4}
"""
def index_to_coord(%Grid2D{width: w}, index) do
{rem(index, w), floor(index / w)}
end
@doc """
## Examples
iex> Grid2D.coord_to_index( Grid2D.new(5,5), {0,0})
0
iex> Grid2D.coord_to_index( Grid2D.new(5,5), {4,4})
24
iex> Grid2D.coord_to_index( Grid2D.new(5,5), {2,2})
12
"""
def coord_to_index(%Grid2D{width: w}, {x, y}) do
y * w + x
end
@doc """
## Examples
iex> Grid2D.neighbors({0, 0}, Grid2D.new(5,5)) |> MapSet.new()
MapSet.new([{0, 1}, {1, 1}, {1,0}])
iex> Grid2D.neighbors({2, 2}, Grid2D.new(5,5)) |> MapSet.new()
[{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 3}, {3, 1}, {3, 2}, {3, 3}] |> MapSet.new()
iex> Grid2D.neighbors({4, 4}, Grid2D.new(5,5)) |> MapSet.new
[{3, 3}, {3, 4}, {4, 3}] |> MapSet.new
"""
def neighbors(p, g, allowed_directions \\ :all) do
directions(allowed_directions)
|> Stream.map(&add(p, &1))
|> Stream.filter(&is_in_grid?(&1, g))
end
@doc """
Distance from two points in a grid
iex> Grid2D.distance(Grid2D.new(5,5), {0,0}, {0,1}, :radial)
1
iex> Grid2D.distance(Grid2D.new(5,5), {0,0}, {1,1}, :radial)
1
iex> Grid2D.distance(Grid2D.new(5,5), {0,0}, {1,2}, :radial)
2
"""
def distance(grid, p1, p2, type)
def distance(_, {x, y}, {a, b}, :radial), do: max(abs(x - a), abs(y - b))
@doc """
Add two points together pairwise
iex> Grid2D.add({0,0}, {0,1})
{0,1}
iex> Grid2D.add({2,3}, {3,2})
{5,5}
"""
def add({x, y}, {j, k}), do: {x + j, y + k}
@doc """
Test if a point is in a grid
iex> Grid2D.is_in_grid?({1, 2}, %Grid2D{width: 3, height: 4})
true
iex> Grid2D.is_in_grid?({2, 2}, %Grid2D{width: 2, height: 4})
false
"""
def is_in_grid?({x, y}, %Grid2D{width: w, height: h}), do: x < w and y < h and x >= 0 and y >= 0
@spec directions(allowed :: :all | :straight | :diagonal) :: any()
def directions(allowed \\ :all)
def directions(:all), do: directions(:straight) ++ directions(:diagonal)
def directions(:straight), do: @directions |> Map.get(:straight)
def directions(:diagonal), do: @directions |> Map.get(:diagonal)
def mul({x, y}, n), do: {n*x, n*y}
end
defmodule EnumUtil do
def pick_n(enum, n)
def pick_n([], _), do: []
def pick_n([a | rest], n) do
pick_n(rest, n, n, []) ++ pick_n(rest, n, n - 1, [a])
end
defp pick_n([], n, _, acc) do
if acc |> Enum.count == n do
[acc]
else
[]
end
end
defp pick_n(_, _, 0, acc), do: [acc]
defp pick_n([a | rest], n, r, acc) do
pick_n(rest, n, r, acc) ++ pick_n(rest, n, r - 1, [a | acc])
end
end
input = """
"""
lines = input |> String.trim() |> String.split("\n")
height = lines |> Enum.count
width = lines |> Enum.at(0) |> String.length()
tiles = lines |> Stream.with_index() |> Stream.flat_map(fn {line, i} -> line |> String.graphemes() |> Stream.with_index() |> Enum.map(fn {c, j} -> {{j, i}, c} end) end) |> Enum.into(%{})
grid = Grid2D.new(width, height)
defmodule Crawl do
def crawl([], _, _, acc), do: acc
def crawl(points, tiles, grid, acc) do
n = points
|> Enum.flat_map(fn p -> Grid2D.neighbors(p, grid, :straight)
|> Enum.reject(&(MapSet.member?(acc, &1) or Map.get(tiles, &1) != Map.get(tiles, p))) end)
|> Enum.uniq()
# IO.puts("#{inspect(n)}")
crawl(n, tiles, grid, points |> Enum.reduce(acc, fn x, s -> MapSet.put(s, x) end))
end
def crawl(tiles, grid) do
for {pt, _} <- tiles, reduce: {MapSet.new([]),[]} do
{seen, list} ->
if !MapSet.member?(seen, pt) do
visited = Crawl.crawl([pt], tiles, grid, MapSet.new([pt]))
{seen |> MapSet.union(visited), [visited | list]}
else
{seen, list}
end
end |> elem(1)
end
def pricep1(regions, tiles, grid) do
for region <- regions, reduce: 0 do
acc ->
area = region |> MapSet.size()
perimeter = region |> MapSet.to_list() |> Enum.map(
fn tile ->
Grid2D.directions(:straight)
|> Enum.reduce(
0,
fn d, acc ->
nb = Grid2D.add(d, tile)
if !Grid2D.is_in_grid?(nb, grid) or Map.get(tiles, nb) != Map.get(tiles, tile) do
acc + 1
else
acc
end
end)
end) |> Enum.sum()
acc + area*perimeter
end
end
def rotate90({a, b}), do: {-b, a}
def pricep2(regions, tiles, grid) do
for region <- regions, reduce: 0 do
acc ->
sides = for direction <- Grid2D.directions(:straight) do
for tile <- region,
neighbor = Grid2D.add(tile, direction),
Map.get(tiles, neighbor) != Map.get(tiles, tile),
reduce: {MapSet.new, 0} do
{used, total} ->
if !MapSet.member?(used, tile) do
scan_dir = rotate90(direction)
line = Stream.iterate(1, &(&1 + 1))
|> Stream.map(fn n ->
if rem(n, 2) == 0 do
{:up, div(n,2)}
else
{:down, div(n+1, 2)*-1}
end
end)
|> Stream.map(&({elem(&1, 0), Grid2D.mul(scan_dir, elem(&1, 1))}))
|> Enum.reduce_while(
%{line: MapSet.new, up: true, down: true},
fn {dir, next}, %{line: line} = acc ->
next = Grid2D.add(next, tile)
is_same? = Map.get(tiles, next) == Map.get(tiles, tile)
next_external? = Map.get(tiles, Grid2D.add(next, direction)) != Map.get(tiles, next)
acc = if acc[dir] and Grid2D.is_in_grid?(next, grid) and is_same? and next_external? do
%{acc | line: MapSet.put(line, next)}
else
acc |> Map.put(dir, false)
end
{(if acc[:up] or acc[:down], do: :cont, else: :halt), acc}
end
) |> Map.get(:line)
{used |> MapSet.union(line), total + 1}
else
{used, total}
end
end |> elem(1)
end |> Enum.sum()
area = region |> MapSet.size()
acc + area*sides
end
end
end
regions = Crawl.crawl(tiles, grid)
Benchee.run(%{
"p1": fn -> Crawl.pricep1(regions, tiles, grid) end,
p2: fn -> Crawl.pricep2(regions, tiles, grid) end
})
warning: found quoted keyword "p1" but the quotes are not required. Note that keywords are always atoms, even when quoted. Similar to atoms, keywords made exclusively of ASCII letters, numbers, and underscores and not beginning with a number do not require quotes
└─ Library/Application Support/livebook/autosaved/2024_12_12/15_42_5s6a/aoc2024_day_12.livemd#cell:fma2uf6b3e4jblnu:2:4
Error trying to determine erlang version enoent, falling back to overall OTP version
Warning: the benchmark p1 is using an evaluated function.
Evaluated functions perform slower than compiled functions.
You can move the Benchee caller to a function in a module and invoke `Mod.fun()` instead.
Alternatively, you can move the benchmark into a benchmark.exs file and run mix run benchmark.exs
Warning: the benchmark p2 is using an evaluated function.
Evaluated functions perform slower than compiled functions.
You can move the Benchee caller to a function in a module and invoke `Mod.fun()` instead.
Alternatively, you can move the benchmark into a benchmark.exs file and run mix run benchmark.exs
Operating System: macOS
CPU Information: Apple M1 Pro
Number of Available Cores: 10
Available memory: 16 GB
Elixir 1.17.2
Erlang 27
JIT enabled: true
Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 0 ns
reduction time: 0 ns
parallel: 1
inputs: none specified
Estimated total run time: 14 s
Benchmarking p1 ...
Benchmarking p2 ...
Calculating statistics...
Formatting results...
Name ips average deviation median 99th %
p1 93.85 10.66 ms ±7.19% 10.61 ms 12.65 ms
p2 45.60 21.93 ms ±4.21% 21.87 ms 24.31 ms
Comparison:
p1 93.85
p2 45.60 - 2.06x slower +11.27 ms