Advent of Code 2023 - Day 11

Sample

sample = """
...#......
.......#..
#.........
..........
......#...
.#........
.........#
..........
.......#..
#...#.....
"""

"...#......\n.......#..\n#.........\n..........\n......#...\n.#........\n.........#\n..........\n.......#..\n#...#.....\n"

Input

input = """
......................#..................#................................#............#..........................#.........................
..........#....................................#.................#..........................................................................
................................#......................#..........................#.....................#................#..................
...........................#....................................................................#........................................#..
.....#..........#...................................................................................................................#.......
........................................................................................#...................................................
........................................#............#......................................................................................
.....................#....................................................#...................#.......................#.....................
..............................................................................................................................#...........#.
............................#.......#......................#................................................................................
...........#......................................#..............#............#.............................................................
.........................................................................................#..................................................
....#...............................................................................#.....................................#...........#.....
..................#...........#...............#..............................................#.......#........#.............................
........................................#...........................#.......................................................................
............................................................................................................................................
.........................#..........................#.........................#.........................#...................................
................#...................#..................................................................................#...................#
...#...........................................................#........#.............#..............................................#......
..................................................................................................#.........................................
.............#..............................#...............................................................................................
.....................#.........................................................................................#............................
............................#........................#............#.........................#..................................#............
.......#..............................................................................................................#.....................
........................................................................#........#..................#.......................................
...#......................................#.......#......................................................#........#...............#.........
...........................................................#.............................................................................#..
................................#..................................#........................................................................
.............#.................................#............................................................................................
#.......................#...............#.................................#...........#.........#...................................#.......
...........................................................................................#..................#.............................
........#....................#........................................................................................#......#..............
............................................................#......................................#......................................#.
..#.......................................#.................................................................................................
....................#................................................................#....................................#........#........
.............#......................#................#......................................#...............................................
.......#............................................................#................................................#......................
..............................#.................#.................................................#.........................................
.......................#...................................................................................#................................
..................#..........................................#..................................................#..............#.....#......
...................................................#...............................#.....#.............#....................................
...#..........#.............#........#......................................................................................................
............................................................................#..................#.............#...........................#..
......................................................#..............#......................................................................
#......#....................................................................................................................#...............
..............................................#.............................................................................................
...................#................#...................................#.......................................................#..........#
...........#............#.................................#.................................................#...........#...................
.....................................................................................#.....#........#............#.....................#....
....................................................#..........#............................................................................
............................................................................................................................................
.#.......#..................#..........#.............................#............#............#..........#................#..............#.
...............#.....#...................................................................#..................................................
.................................................#..........................#.........................................#........#.....#......
......#..........................................................#...............................................#..........................
............................................................................................................................................
.............................#................#.......................................#.....................#...............................
..................#..................#.......................#..........#.....................#.............................#...............
............................................................................................................................................
..................................................................................#.................#...................#..........#........
..................................#.....#..............#..........#.....................#...................................................
.....#.................#....................................................................................................................
#......................................................................................................................................#....
..................#..................#........#...........#..................#.................#............................................
.....................................................................#................................#.........#.............#.............
..........#..........................................................................#.....#................................................
............................#.......................#...........#...........................................................................
.#.................................#.............................................................#.................#........................
............................................................................#................................#..........................#...
......#..................................................................................................................#..................
...................#..............................#.................................................#.........................#.............
..............#................#.........................................................#..........................................#.......
............................................#....................#...............#..........................................................
.......................#................................................#.................................#.................................
..................................#.....#...........#...................................................................#...................
.#.....................................................................................#........#...........................................
.......#......................#................................#.......................................#....................................
...............................................#............................................................................................
..........................................................#................#.....................................#..........................
......................#.....................................................................................................................
............................................#.........#.......................................#..................................#..........
.#.........#........................................................#...................................#.....#.............................
.......................................#.............................................#..................................................#...
...............................#............................................................................................................
.............................................................................#..................#................#........#.................
......................#.....................................................................................................................
...#..............................................#.........#.....................#......................#...........................#......
..................................#.........................................................................................................
...........................................................................#...............#...................................#............
..........#..............#....................#.............................................................................................
...............................................................................................................#........................#...
....#.........#...............................................................#.....#.......................................................
.......................................................#..........#.......................................................#.................
..................................#...............#..............................................................................#..........
..............................................................#..........................#................#.........#.......................
........#............................................................#......................................................................
#...............................................................................................#...........................................
......................#....................................................................................................................#
.....#......................#..............................................#...........#..........................#.....#...................
................#.................................................#..............#..........................................................
...........#.........................................#......................................................................................
..#..................................#.............................................................................................#.....#..
..........................................#................................................#.....#........#.................................
..............#...............................................#.................................................#...........................
....................#.............#....................#..............................................#.....................................
.............................#..........................................#...................................................................
...........................................................#................................................................................
.......................#.........................#.....................................#...........#........................................
.................................................................#............................................#.......#.....................
........#.....#............................................................#........................................................#.......
.................................#...........................................................#..............................................
.#.................#......................#.................#.........#..................................#.......#........#................#
...........#................................................................................................................................
........................#..............................#.............................#......................................................
...................................#.....................................#.........................#.................................#......
............................................................................................................................................
....#..................................#.................................................#...............................#..................
.............................#....................#......................................................................................#..
.............................................................................#.........................#....................................
.............#.....#......................#.......................#.................#........................................#..............
......................................................................................................................................#.....
...#.................................................#...........................................#..........................................
......................#.....................................#...............................................................................
................#..........#..................................................................................#..........#..................
..........#.........................#............#.................#..........#............................................................#
............................................................................................................................................
.......................................................#............................................................#.......................
...#.........................................#.....................................#...............#..............................#.........
............#.........................#.....................................................................................................
.......................#...........................#.....................................................#..................................
..............................................................#............................#...............................#..........#.....
.........#......................#..........#.........................................#......................................................
...............#................................................................................#.....#.....................................
....#.......................#..................#....................#......................................#...................#............
..........................................................#.................................................................................
.....................................#.........................#.........................#..................................................
#..........................................................................#................................................................
...........................................#..................................................................#........#...........#........
......................#...........................................................#...................#.....................................
....#...........#................................................................................#..........................................
"""

"......................#..................#................................#............#..........................#.........................\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

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)

10033566

Part 2

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)

560822911938