# Advent of Code 2023 - Day 11

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()

empty_ys
|> Enum.with_index()
|> Enum.flat_map(fn {empty, index} -> List.duplicate(index, empty + 1) end)
|> Nx.tensor(type: :u8)

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

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:

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:

1. load_day_as_grid to automatically parse input as a map of coordinates to points
2. distinct_pairs to generate all distinct pairs of elements within a list
3. list_set_difference to calculate the set difference between 2 lists (reducing the need for MapSet.new calls)
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

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