Advent of Code 2023 - Day 11

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

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

https://github.com/lud/adventofcode/blob/main/lib/solutions/2023/day11.ex

Solution using dynamic programming (prefix sums): advent-of-code-2023/lib/advent_of_code/day_11.ex at main · ibarakaiev/advent-of-code-2023 · GitHub. There are some possible optimizations like recording coordinates at the same time as the vertical prefix sum, but it would take away from readability

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

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

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

The scale of today’s puzzle is too small. I don’t even bother to optimize my solution.

https://github.com/Aetherus/advent-of-code/blob/master/2023/day-11.livemd

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)

https://github.com/code-shoily/advent_of_code/blob/master/lib/2023/day_11.ex

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:

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)

https://github.com/woojiahao/aoc/blob/main/lib/aoc/2023/day_11.ex

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