<!-- livebook:{"persist_outputs":true} -->
# Advent of Code 2023 - Day 11
## Sample
```elixir
sample = """
...#......
.......#..
#.........
..........
......#...
.#........
.........#
..........
.......#..
#...#.....
"""
```
<!-- livebook:{"output":true} -->
```
"...#......\n.......#..\n#.........\n..........\n......#...\n.#........\n.........#\n..........\n.......#..\n#...#.....\n"
```
## Input
```elixir
input = """
......................#..................#................................#............#..........................#.........................
..........#....................................#.................#..........................................................................
................................#......................#..........................#.....................#................#..................
...........................#....................................................................#........................................#..
.....#..........#...................................................................................................................#.......
........................................................................................#...................................................
........................................#............#......................................................................................
.....................#....................................................#...................#.......................#.....................
..............................................................................................................................#...........#.
............................#.......#......................#................................................................................
...........#......................................#..............#............#.............................................................
.........................................................................................#..................................................
....#...............................................................................#.....................................#...........#.....
..................#...........#...............#..............................................#.......#........#.............................
........................................#...........................#.......................................................................
............................................................................................................................................
.........................#..........................#.........................#.........................#...................................
................#...................#..................................................................................#...................#
...#...........................................................#........#.............#..............................................#......
..................................................................................................#.........................................
.............#..............................#...............................................................................................
.....................#.........................................................................................#............................
............................#........................#............#.........................#..................................#............
.......#..............................................................................................................#.....................
........................................................................#........#..................#.......................................
...#......................................#.......#......................................................#........#...............#.........
...........................................................#.............................................................................#..
................................#..................................#........................................................................
.............#.................................#............................................................................................
#.......................#...............#.................................#...........#.........#...................................#.......
...........................................................................................#..................#.............................
........#....................#........................................................................................#......#..............
............................................................#......................................#......................................#.
..#.......................................#.................................................................................................
....................#................................................................#....................................#........#........
.............#......................#................#......................................#...............................................
.......#............................................................#................................................#......................
..............................#.................#.................................................#.........................................
.......................#...................................................................................#................................
..................#..........................................#..................................................#..............#.....#......
...................................................#...............................#.....#.............#....................................
...#..........#.............#........#......................................................................................................
............................................................................#..................#.............#...........................#..
......................................................#..............#......................................................................
#......#....................................................................................................................#...............
..............................................#.............................................................................................
...................#................#...................................#.......................................................#..........#
...........#............#.................................#.................................................#...........#...................
.....................................................................................#.....#........#............#.....................#....
....................................................#..........#............................................................................
............................................................................................................................................
.#.......#..................#..........#.............................#............#............#..........#................#..............#.
...............#.....#...................................................................#..................................................
.................................................#..........................#.........................................#........#.....#......
......#..........................................................#...............................................#..........................
............................................................................................................................................
.............................#................#.......................................#.....................#...............................
..................#..................#.......................#..........#.....................#.............................#...............
............................................................................................................................................
..................................................................................#.................#...................#..........#........
..................................#.....#..............#..........#.....................#...................................................
.....#.................#....................................................................................................................
#......................................................................................................................................#....
..................#..................#........#...........#..................#.................#............................................
.....................................................................#................................#.........#.............#.............
..........#..........................................................................#.....#................................................
............................#.......................#...........#...........................................................................
.#.................................#.............................................................#.................#........................
............................................................................#................................#..........................#...
......#..................................................................................................................#..................
...................#..............................#.................................................#.........................#.............
..............#................#.........................................................#..........................................#.......
............................................#....................#...............#..........................................................
.......................#................................................#.................................#.................................
..................................#.....#...........#...................................................................#...................
.#.....................................................................................#........#...........................................
.......#......................#................................#.......................................#....................................
...............................................#............................................................................................
..........................................................#................#.....................................#..........................
......................#.....................................................................................................................
............................................#.........#.......................................#..................................#..........
.#.........#........................................................#...................................#.....#.............................
.......................................#.............................................#..................................................#...
...............................#............................................................................................................
.............................................................................#..................#................#........#.................
......................#.....................................................................................................................
...#..............................................#.........#.....................#......................#...........................#......
..................................#.........................................................................................................
...........................................................................#...............#...................................#............
..........#..............#....................#.............................................................................................
...............................................................................................................#........................#...
....#.........#...............................................................#.....#.......................................................
.......................................................#..........#.......................................................#.................
..................................#...............#..............................................................................#..........
..............................................................#..........................#................#.........#.......................
........#............................................................#......................................................................
#...............................................................................................#...........................................
......................#....................................................................................................................#
.....#......................#..............................................#...........#..........................#.....#...................
................#.................................................#..............#..........................................................
...........#.........................................#......................................................................................
..#..................................#.............................................................................................#.....#..
..........................................#................................................#.....#........#.................................
..............#...............................................#.................................................#...........................
....................#.............#....................#..............................................#.....................................
.............................#..........................................#...................................................................
...........................................................#................................................................................
.......................#.........................#.....................................#...........#........................................
.................................................................#............................................#.......#.....................
........#.....#............................................................#........................................................#.......
.................................#...........................................................#..............................................
.#.................#......................#.................#.........#..................................#.......#........#................#
...........#................................................................................................................................
........................#..............................#.............................#......................................................
...................................#.....................................#.........................#.................................#......
............................................................................................................................................
....#..................................#.................................................#...............................#..................
.............................#....................#......................................................................................#..
.............................................................................#.........................#....................................
.............#.....#......................#.......................#.................#........................................#..............
......................................................................................................................................#.....
...#.................................................#...........................................#..........................................
......................#.....................................#...............................................................................
................#..........#..................................................................................#..........#..................
..........#.........................#............#.................#..........#............................................................#
............................................................................................................................................
.......................................................#............................................................#.......................
...#.........................................#.....................................#...............#..............................#.........
............#.........................#.....................................................................................................
.......................#...........................#.....................................................#..................................
..............................................................#............................#...............................#..........#.....
.........#......................#..........#.........................................#......................................................
...............#................................................................................#.....#.....................................
....#.......................#..................#....................#......................................#...................#............
..........................................................#.................................................................................
.....................................#.........................#.........................#..................................................
#..........................................................................#................................................................
...........................................#..................................................................#........#...........#........
......................#...........................................................#...................#.....................................
....#...........#................................................................................#..........................................
"""
```
<!-- livebook:{"output":true} -->
```
"......................#..................#................................#............#..........................#.........................\n..........#....................................#.................#..........................................................................\n................................#......................#..........................#.....................#................#..................\n...........................#....................................................................#........................................#..\n.....#..........#...................................................................................................................#.......\n........................................................................................#...................................................\n........................................#............#......................................................................................\n.....................#....................................................#...................#.......................#.....................\n..............................................................................................................................#...........#.\n............................#.......#......................#................................................................................\n...........#......................................#..............#............#.............................................................\n.........................................................................................#..................................................\n....#...............................................................................#.....................................#...........#.....\n..................#...........#...............#..............................................#.......#........#.............................\n........................................#...........................#.......................................................................\n............................................................................................................................................\n.........................#..........................#.........................#.........................#...................................\n................#...................#..................................................................................#...................#\n...#...........................................................#........#.............#..............................................#......\n..................................................................................................#.........................................\n.............#..............................#...............................................................................................\n.....................#.........................................................................................#............................\n............................#........................#............#.........................#..................................#............\n.......#..............................................................................................................#.....................\n........................................................................#........#..................#.......................................\n...#......................................#.......#......................................................#........#...............#.........\n...........................................................#.............................................................................#..\n................................#..................................#........................................................................\n.............#.................................#............................................................................................\n#......" <> ...
```
## Part 1
```elixir
defmodule Part1 do
def parse(text) do
text
|> String.split("\n", trim: true)
|> Enum.with_index()
|> Enum.reduce(%{}, fn {line, y}, acc ->
line
|> String.graphemes()
|> Enum.with_index()
|> Enum.reduce(acc, fn {cell, x}, acc ->
Map.put(acc, {x, y}, cell)
end)
|> Map.merge(acc)
end)
end
def distance({ax, ay}, {bx, by}, rows, cols) do
dist = abs(bx - ax) + abs(by - ay)
empty_cols = ax..bx |> Enum.filter(&(!MapSet.member?(cols, &1))) |> length
empty_rows = ay..by |> Enum.filter(&(!MapSet.member?(rows, &1))) |> length
dist + empty_cols + empty_rows
end
def find_galaxies(map) do
map
|> Map.filter(fn {_, v} -> v == "#" end)
|> Enum.map(&elem(&1, 0))
end
defp populated_n(galaxies, n) do
galaxies
|> Enum.map(&elem(&1, n))
|> MapSet.new()
end
def populated_columns(galaxies) do
populated_n(galaxies, 0)
end
def populated_rows(galaxies) do
populated_n(galaxies, 1)
end
def all_pair_distances(galaxies, rows, cols) do
galaxies
|> Enum.map(fn a ->
galaxies
|> Enum.filter(&(&1 > a))
|> Enum.map(fn b ->
distance(a, b, rows, cols)
end)
|> Enum.sum()
end)
|> Enum.sum()
end
end
map = Part1.parse(input)
galaxies = Part1.find_galaxies(map)
rows = Part1.populated_rows(galaxies)
cols = Part1.populated_columns(galaxies)
Part1.all_pair_distances(galaxies, rows, cols)
```
<!-- livebook:{"output":true} -->
```
10033566
```
## Part 2
```elixir
defmodule Part2 do
def parse(text) do
text
|> String.split("\n", trim: true)
|> Enum.with_index()
|> Enum.reduce(%{}, fn {line, y}, acc ->
line
|> String.graphemes()
|> Enum.with_index()
|> Enum.reduce(acc, fn {cell, x}, acc ->
Map.put(acc, {x, y}, cell)
end)
|> Map.merge(acc)
end)
end
def distance({ax, ay}, {bx, by}, rows, cols) do
dist = abs(bx - ax) + abs(by - ay)
empty_cols = ax..bx |> Enum.filter(&(!MapSet.member?(cols, &1))) |> length
empty_rows = ay..by |> Enum.filter(&(!MapSet.member?(rows, &1))) |> length
dist + empty_cols * 999_999 + empty_rows * 999_999
end
def find_galaxies(map) do
map
|> Map.filter(fn {_, v} -> v == "#" end)
|> Enum.map(&elem(&1, 0))
end
defp populated_n(galaxies, n) do
galaxies
|> Enum.map(&elem(&1, n))
|> MapSet.new()
end
def populated_columns(galaxies) do
populated_n(galaxies, 0)
end
def populated_rows(galaxies) do
populated_n(galaxies, 1)
end
def all_pair_distances(galaxies, rows, cols) do
galaxies
|> Enum.map(fn a ->
galaxies
|> Enum.filter(&(&1 > a))
|> Enum.map(fn b ->
distance(a, b, rows, cols)
end)
|> Enum.sum()
end)
|> Enum.sum()
end
end
map = Part2.parse(input)
galaxies = Part2.find_galaxies(map)
rows = Part2.populated_rows(galaxies)
cols = Part2.populated_columns(galaxies)
Part2.all_pair_distances(galaxies, rows, cols)
```
<!-- livebook:{"output":true} -->
```
560822911938
```
