My code for today’s puzzle:
3 Likes
Just a simple tweak of the Manhattan distance…
import AOC
aoc 2023, 11 do
def calculate(input, multiplier) do
grid = grid(input) |> Map.new()
{rows, cols} = grid |> Enum.unzip() |> elem(0) |> Enum.unzip()
row_max = rows |> Enum.max()
col_max = cols |> Enum.max()
blank_rows = 0..row_max |> Enum.filter(fn row -> Enum.all?(0..col_max, fn col -> grid[{row, col}] == "." end) end)
blank_cols = 0..col_max |> Enum.filter(fn col -> Enum.all?(0..row_max, fn row -> grid[{row, col}] == "." end) end)
galaxies = Enum.filter(grid, fn {_, char} -> char == "#" end) |> Enum.unzip() |> elem(0)
for i <- 1..Enum.count(galaxies), j <- 1..i, j < i do
distance(Enum.at(galaxies, i-1), Enum.at(galaxies, j-1), blank_rows, blank_cols, multiplier)
end |> Enum.sum()
end
def p1(input) do
calculate(input, 2)
end
def p2(input) do
calculate(input, 1_000_000)
end
def distance({a, b}, {c, d}, blank_rows, blank_cols, multiplier) do
[lo_row, hi_row] = [a, c] |> Enum.sort()
[lo_col, hi_col] = [b, d] |> Enum.sort()
[blank_rows |> Enum.count(fn row -> lo_row <= row and row <= hi_row end) |> Kernel.*(multiplier-1),
blank_cols |> Enum.count(fn col -> lo_col <= col and col <= hi_col end) |> Kernel.*(multiplier-1),
hi_row - lo_row,
hi_col - lo_col] |> Enum.sum()
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)
end)
end
end
1 Like
To expand I sort the empty Y coords descending, and for each one I bump each XY in the galaxy list. Same for X.
I have an idea to do it all at once but I’m not chasing milliseconds today 
2 Likes
Solution using dynamic programming (prefix sums): https://github.com/ibarakaiev/advent-of-code-2023/blob/main/lib/advent_of_code/day_11.ex. There are some possible optimizations like recording coordinates at the same time as the vertical prefix sum, but it would take away from readability 
3 Likes
This one seemed like a great opportunity to learn a bit of Nx. I took the naive approach for part 1 and duplicated all of the rows and columns. Obviously that didn’t work out in part 2 
Part 1
sky =
for line <- String.split(input, "\n", trim: true) do
for char <- String.graphemes(line) do
if char == "#", do: 1, else: 0
end
end
sky_tensor = Nx.tensor(sky, type: :u8, names: [:y, :x])
empty_ys = Nx.any(sky_tensor, axes: [:x]) |> Nx.logical_not() |> Nx.to_list()
empty_xs = Nx.any(sky_tensor, axes: [:y]) |> Nx.logical_not() |> Nx.to_list()
pad_ys =
empty_ys
|> Enum.with_index()
|> Enum.flat_map(fn {empty, index} -> List.duplicate(index, empty + 1) end)
|> Nx.tensor(type: :u8)
pad_xs =
empty_xs
|> Enum.with_index()
|> Enum.flat_map(fn {empty, index} -> List.duplicate(index, empty + 1) end)
|> Nx.tensor(type: :u8)
big_sky =
sky_tensor
|> Nx.take(pad_ys, axis: :y)
|> Nx.take(pad_xs, axis: :x)
galaxies =
for {line, y} <- big_sky |> Nx.to_list() |> Enum.with_index(),
{galaxy, x} <- Enum.with_index(line),
reduce: [] do
acc -> if galaxy == 1, do: [{y, x} | acc], else: acc
end
pairs =
for {{y1, x1}, i} <- Enum.with_index(galaxies),
{y2, x2} <- Enum.drop(galaxies, i + 1) do
[[y1, x1], [y2, x2]]
end
|> Nx.tensor(type: :s64)
Nx.abs(Nx.subtract(pairs[[.., 0, 0]], pairs[[.., 1, 0]]))
|> Nx.add(Nx.abs(Nx.subtract(pairs[[.., 0, 1]], pairs[[.., 1, 1]])))
|> Nx.sum()
Part 2
galaxies =
for {line, y} <- sky |> Enum.with_index(),
{galaxy, x} <- Enum.with_index(line),
reduce: [] do
acc -> if galaxy == 1, do: [{y, x} | acc], else: acc
end
y_indexes =
empty_ys
|> Enum.with_index()
|> Enum.flat_map(fn
{1, i} -> [i]
_ -> []
end)
x_indexes =
empty_xs
|> Enum.with_index()
|> Enum.flat_map(fn
{1, i} -> [i]
_ -> []
end)
galaxies =
for {y, x} <- galaxies do
sy = Enum.count(y_indexes, &(&1 < y))
sx = Enum.count(x_indexes, &(&1 < x))
{y + 999_999 * sy, x + 999_999 * sx}
end
pairs =
for {{y1, x1}, i} <- Enum.with_index(galaxies),
{y2, x2} <- Enum.drop(galaxies, i + 1) do
[[y1, x1], [y2, x2]]
end
|> Nx.tensor(type: :s64)
Nx.abs(Nx.subtract(pairs[[.., 0, 0]], pairs[[.., 1, 0]]))
|> Nx.add(Nx.abs(Nx.subtract(pairs[[.., 0, 1]], pairs[[.., 1, 1]])))
|> Nx.sum()
2 Likes
The scale of today’s puzzle is too small. I don’t even bother to optimize my solution.
1 Like
It was easy this one. I was mostly busy adding tags and difficulty markdown page generator for Advent of Code repository, so was too busy checking it out. But here’s my code (pretty similar to lot of y’all)
1 Like
My beginner’s solution, Day 11 part 1. Cosmic Expansion
defmodule Day11 do
def part2(input), do: part1(input, 1_000_000) # :)
def part1(input, e \\ 2) do
parse(input) # [[true, nil, nil], [nil, nil, true]]
|> expand(e)
|> rotate
|> expand(e) # [[true, nil], [nil, nil], [nil, nil], [nil, true]]
|> galaxies # [{0, 0}, {3, 1}]
|> pairs
|> Enum.map(&distance/1)
|> Enum.sum
end
def distance([{r1, c1}, {r2, c2}]), do: abs(r1-r2) + abs(c1-c2)
def pairs(galaxies) do
for n <- galaxies, m <- galaxies do [n, m] end
|> Enum.uniq_by(&Enum.sort/1)
|> Enum.reject(fn [a, b] -> a == b end)
end
def galaxies(image) do
for {row, r} <- Enum.with_index(image) do
for {true, c} <- Enum.with_index(row), do: {r, c}
end |> List.flatten
end
def expand(image, n \\ 2) do
image
|> Enum.reduce([], fn row, acc ->
if not Enum.any?(row) do
acc ++ List.duplicate(row, n)
else
acc ++ [row]
end
end)
end
def rotate(image) do
image
|> List.zip
|> Enum.map(&Tuple.to_list/1)
end
def parse(raw_image) do
raw_image
|> String.split("\n")
|> Enum.map(fn raw_line -> raw_line
|> String.graphemes
|> Enum.map(fn raw_char -> raw_char
|> case do
"#" -> true
"." -> nil
end
end)
end)
end
end
I started with matrix transpose but improved with finding gaps between galaxies:
defmodule AdventOfCode.Day11 do
def part1(input) do
solve(input, 2)
end
def solve(input, size) do
map =
input
|> String.split("\n", trim: true)
|> Enum.map(&String.to_charlist/1)
galaxies = find_galaxies(map)
{x_expansions, y_expansions} = expansions(galaxies)
galaxies
|> expand(x_expansions, y_expansions, size - 1)
|> combinations()
|> Enum.map(fn {{x1, y1}, {x2, y2}} ->
abs(x1 - x2) + abs(y1 - y2)
end)
|> Enum.sum()
end
defp expansions(galaxies) do
xes = Enum.map(galaxies, &elem(&1, 0))
yes = Enum.map(galaxies, &elem(&1, 1))
{cals_expansions(xes), cals_expansions(yes)}
end
defp cals_expansions(vals) do
max = Enum.max(vals)
MapSet.difference(MapSet.new(0..max), MapSet.new(vals))
end
defp expand(galaxies, x_expansions, y_expansions, size) do
Enum.map(galaxies, fn {x, y} ->
x_expansion = Enum.filter(x_expansions, &(&1 < x)) |> length()
y_expansion = Enum.filter(y_expansions, &(&1 < y)) |> length()
{
x + x_expansion * size,
y + y_expansion * size
}
end)
end
defp find_galaxies(map) do
Enum.reduce(map, {0, []}, fn line, {y, galaxies} ->
{_, list} =
Enum.reduce(line, {0, galaxies}, fn ch, {x, g} ->
case ch do
?# -> {x + 1, [{x, y} | g]}
_ -> {x + 1, g}
end
end)
{y + 1, list}
end)
|> elem(1)
end
def combinations(list) do
Enum.flat_map(list, fn g1 ->
Enum.flat_map(list, fn g2 ->
if g1 < g2,
do: [{g1, g2}],
else: []
end)
end)
end
def part2(input) do
solve(input, 1_000_000)
end
end
Added quite a few new helper functions to speed up writing AOC solutions, notably:
load_day_as_gridto automatically parse input as a map of coordinates to pointsdistinct_pairsto generate all distinct pairs of elements within a listlist_set_differenceto calculate the set difference between 2 lists (reducing the need forMapSet.newcalls)
2 Likes
Very similar to everyone else’s approach today. No gratuitous use of :digraph this time. Agree with @Aetherus that scale of the dataset made it easier than expected. My solution has lots of room for optimization but works fast enough for the given dataset.
Like a lot of people for part 1 I just did the naive thing and literally expanded the grid. I knew it was not the ideal approach but did it anyway because I like to see what the point of part 2 is sometimes.
defmodule Day11 do
@moduledoc """
Day11 AoC Solutions
"""
alias AocToolbox.Input
# add sample data here
def input(:test) do
"""
...#......
.......#..
#.........
..........
......#...
.#........
.........#
..........
.......#..
#...#.....
"""
end
def input(:real), do: Input.load(__DIR__ <> "/input.txt")
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) do
input
|> parse()
end
defp parse(input) do
input
|> Input.lines()
|> Input.lines_to_indexed_chars()
|> expand_universe()
|> identify_galaxies()
|> galaxy_pairs()
|> manhattan_distances()
|> Enum.sum()
end
defp expand_universe(map) do
expand_rows = find_blank_rows(map)
expand_cols = find_blank_cols(map)
map |> expand_cols(expand_cols) |> expand_rows(expand_rows)
end
defp find_blank_rows(map) do
map
|> Enum.filter(fn {_r, cs} -> Enum.all?(cs, fn {_c, v} -> v == "." end) end)
|> Enum.map(&elem(&1, 0))
|> Enum.sort(:desc)
end
defp find_blank_cols(map) do
0..map_size(map[0])
|> Enum.filter(fn c -> map |> Enum.all?(fn {_r, cs} -> cs[c] == "." end) end)
end
defp expand_cols(map, blank_cols) do
blank_cols
|> Enum.sort(:desc)
|> Enum.reduce(map, fn b, m ->
m
|> Enum.map(fn {r, cs} ->
{r,
cs
|> Enum.map(fn {c, v} ->
if c > b do
{c + 1, v}
else
{c, v}
end
end)
|> Enum.into(%{})}
end)
end)
|> Enum.into(%{})
|> do_expand_cols(blank_cols)
end
defp do_expand_cols(map, blank_cols) do
blank_cols
|> Enum.sort()
|> Enum.with_index(1)
|> Enum.reverse()
|> Enum.reduce(map, fn {b, i}, m ->
Enum.map(m, fn {r, cs} ->
{r, Map.put(cs, b + i, cs[b + i - 1])}
end)
end)
end
defp expand_rows(map, blank_rows) do
blank_rows
|> Enum.sort(:desc)
|> Enum.reduce(map, fn b, m ->
m
|> Enum.map(fn {r, cs} ->
if r > b do
{r + 1, cs}
else
{r, cs}
end
end)
|> Enum.into(%{})
end)
|> do_expand_rows(blank_rows)
end
defp do_expand_rows(map, blank_rows) do
blank_rows
|> Enum.sort()
|> Enum.with_index(1)
|> Enum.reduce(map, fn {b, i}, m ->
Map.put(m, b + i, m[b + i - 1])
end)
end
defp identify_galaxies(map) do
0..(map_size(map) - 1)
|> Enum.filter(fn i -> map[i][61] == nil end)
map
|> Enum.flat_map(fn {r, cs} ->
cs |> Enum.filter(fn {_c, v} -> v == "#" end) |> Enum.map(fn {c, _} -> {r, c} end)
end)
end
def galaxy_pairs([]), do: []
def galaxy_pairs(galaxies) do
[g | gs] = galaxies
pairs = for h <- gs, do: {g, h}
pairs ++ galaxy_pairs(gs)
end
def manhattan_distances(pairs) do
pairs
|> Enum.map(fn {{a, b}, {c, d}} -> abs(a - c) + abs(b - d) end)
end
end
defmodule Part2 do
def solve(input) do
input
|> parse()
|> identify_galaxies_and_blanks()
|> expand_universe()
|> Day11.Part1.galaxy_pairs()
|> Day11.Part1.manhattan_distances()
|> Enum.sum()
end
defp parse(input) do
input
|> Input.lines()
|> Input.lines_to_indexed_chars()
end
defp identify_galaxies_and_blanks(map) do
blank_rows =
0..(map_size(map) - 1)
|> Enum.filter(fn i -> map[i] |> Enum.all?(fn {_c, v} -> v == "." end) end)
|> Enum.sort()
blank_cols =
0..(map_size(map[0]) - 1)
|> Enum.filter(fn i -> map |> Enum.all?(fn {_r, cs} -> cs[i] == "." end) end)
|> Enum.sort()
galaxies =
map
|> Enum.flat_map(fn {r, cs} ->
cs |> Enum.filter(fn {c, v} -> v == "#" end) |> Enum.map(fn {c, _} -> {r, c} end)
end)
{blank_rows, blank_cols, galaxies}
end
defp expand_universe({blank_rows, blank_cols, galaxies}) do
galaxies
|> Enum.map(fn {r, c} ->
{blank_rows
|> Enum.filter(fn b -> r > b end)
|> Enum.count()
|> Kernel.*(999_999)
|> Kernel.+(r),
blank_cols
|> Enum.filter(fn b -> c > b end)
|> Enum.count()
|> Kernel.*(999_999)
|> Kernel.+(c)}
end)
end
end
end
I’m not sure I understand why you expand the universe twice and then take sum of each expanded universe distances and then divide by two. Why not just expand the universe once and sum the manhattan distances of the galaxies once?
I only expanded the universe once for each part of the puzzle. Dividing by two is because for each pair of the galaxies a and b, I calculated the distance between a and b and the distance between b and a. I know I could calculate the distances only once. I just didn’t bother to do that optimization.
2 Likes
A quick one today:
pairs
|> Enum.map(fn {{x1, y1}, {x2, y2}} ->
# Distance between two points
dx = x2 - x1
dy = y2 - y1
# Count how many empty rows or columns are in between
expanded_count =
Enum.count(state.empty_cols, fn col_idx ->
col_idx in x1..x2
end) +
Enum.count(state.empty_rows, fn row_idx ->
row_idx in y1..y2
end)
# Manhattan distance with the empty rows/columns expanded
abs(dx) + abs(dy) + expanded_count * (expansion_size - 1)
end)
|> Enum.sum()
Full solution here on Github
