2023_day12.livemd

Advent of Code - Day 12

Mix.install([
  {:kino_aoc, "~> 0.1"}
  # {:eflambe_live, "~> 0.1.0"}
])

Introduction

--> Content

Puzzle

{:ok, puzzle_input} =
  KinoAOC.download_puzzle("2023", "12", System.fetch_env!("LB_AOC_SESSION"))

Parser

Code - Parser

defmodule Parser do
  def parse(input) do
    String.split(input, "\n", trim: true)
    |> Enum.map(fn row ->
      [col, counts] = String.split(row, " ", trim: true)
      {col, String.split(counts, ",", trim: true) |> Enum.map(&String.to_integer(&1))}
    end)
  end
end

Tests - Parser

ExUnit.start(autorun: false)

defmodule ParserTest do
  use ExUnit.Case, async: true
  import Parser

  @input """
  ???.### 1,1,3
  .??..??...?##. 1,1,3
  ?#?#?#?#?#?#?#? 1,3,1,6
  ????.#...#... 4,1,1
  ????.######..#####. 1,6,5
  ?###???????? 3,2,1
  """

  @expected [
    {"???.###", [1, 1, 3]},
    {".??..??...?##.", [1, 1, 3]},
    {"?#?#?#?#?#?#?#?", [1, 3, 1, 6]},
    {"????.#...#...", [4, 1, 1]},
    {"????.######..#####.", [1, 6, 5]},
    {"?###????????", [3, 2, 1]}
  ]

  describe "parse/1" do
    test "simple example" do
      assert parse(@input) == @expected
    end
  end
end

ExUnit.run()

Part One

Code - Part 1

defmodule PartOne do
  def solve(input) do
    IO.puts("--- Part One ---")
    IO.puts("Result: #{run(input)}")
  end

  def run(input_string) do
    Parser.parse(input_string)
    |> Enum.map(fn input_tuple ->
      # possibilities = possible_arrangements(input_tuple)
      # {_row, counts} = input_tuple
      # if Enum.any?(possibilities, fn poss -> String.length(poss) != String.length(hd(Tuple.to_list(input_tuple))) end) do
      # if Enum.any?(possibilities, fn poss -> 
      #   Regex.scan(~r/(\#+)/, poss) |> Enum.map(fn res -> hd(res) end) |> length() != length(counts)
      # end) do
      #   IO.inspect([input_tuple, possible_arrangements(input_tuple)], label: :input_tuple)    
      # end

      count_of_possible_arrangements(input_tuple)
    end)
    |> Enum.sum()
  end

  def count_of_possible_arrangements({row, counts}) do
    possible_arrangements({row, counts})
    |> length()
  end

  def possible_arrangements({row, counts}, res \\ "") do
    _possible_arrangements({row, counts}, res, hd(counts))
    |> List.flatten()
  end

  defp _possible_arrangements({row, counts}, res, current_count) when is_bitstring(row) do
    _possible_arrangements({String.split(row, "", trim: true), counts}, res, current_count)
  end

  defp _possible_arrangements({row, counts}, res, current_count) do
    # IO.inspect([{row, counts}, res, current_count], label: :_possible_arrangements_input)
    # [{["#", "?"], []}, "#..########.#", nil]
    cond do
      Enum.empty?(row) && !Enum.empty?(counts) ->
        []

      !Enum.empty?(row) && Enum.empty?(counts) && "#" in row ->
        []

      Enum.empty?(row) && Enum.empty?(counts) ->
        res

      Enum.empty?(counts) && "#" not in row ->
        res <> (Enum.join(row) |> String.replace("?", "."))

      # _possible_arrangements_input: [{[".", "?", "?", "?", "#"], [2, 1]}, ".#######.#.#", 1]

      hd(row) == "." && current_count != hd(counts) ->
        []

      hd(row) == "#" && String.last(res) == "#" && current_count == hd(counts) ->
        []

      true ->
        possible_branches =
          cond do
            hd(row) == "#" ->
              [{tl(row), counts, res <> "#", current_count - 1}]

            hd(row) == "?" && String.last(res) == "#" && current_count == hd(counts) ->
              [{tl(row), counts, res <> ".", current_count}]

            hd(row) == "?" && current_count != hd(counts) ->
              [{tl(row), counts, res <> "#", current_count - 1}]

            hd(row) == "?" ->
              [
                {tl(row), counts, res <> "#", current_count - 1},
                {tl(row), counts, res <> ".", current_count}
              ]

            true ->
              [{tl(row), counts, res <> ".", current_count}]
          end

        Enum.map(possible_branches, fn {row_remaining, counts_remaining, res, current_count} ->
          {counts_remaining, current_count} =
            if current_count <= 0 do
              {tl(counts_remaining), List.first(tl(counts_remaining))}
            else
              {counts_remaining, current_count}
            end

          _possible_arrangements({row_remaining, counts_remaining}, res, current_count)
        end)
    end
  end
end

Tests - Part 1

ExUnit.start(autorun: false)

defmodule PartOneTest do
  use ExUnit.Case, async: true
  import PartOne

  @raw_input """
  ???.### 1,1,3
  .??..??...?##. 1,1,3
  ?#?#?#?#?#?#?#? 1,3,1,6
  ????.#...#... 4,1,1
  ????.######..#####. 1,6,5
  ?###???????? 3,2,1
  """

  # describe "run/1" do
  #   test "main example" do
  #     assert run(@raw_input) == 21
  #   end
  # end

  describe "possible_arrangements/2" do
    test "test 1" do
      actual = possible_arrangements({"???.###", [1, 1, 3]})
      assert actual == ["#.#.###"]
    end

    test "test 2" do
      actual = possible_arrangements({".??..??...?##.", [1, 1, 3]})
      assert actual == [".#...#....###.", ".#....#...###.", "..#..#....###.", "..#...#...###."]
    end

    test "test 3" do
      actual = possible_arrangements({"?#?#?#?#?#?#?#?", [1, 3, 1, 6]})
      assert actual == [".#.###.#.######"]
    end

    test "test 4" do
      actual = possible_arrangements({"????.#...#...", [4, 1, 1]})
      assert actual == ["####.#...#..."]
    end

    test "test 5" do
      actual = possible_arrangements({"????.######..#####.", [1, 6, 5]})

      assert actual == [
               "#....######..#####.",
               ".#...######..#####.",
               "..#..######..#####.",
               "...#.######..#####."
             ]
    end

    test "test 6" do
      actual = possible_arrangements({"?###????????", [3, 2, 1]})

      assert actual == [
               ".###.##.#...",
               ".###.##..#..",
               ".###.##...#.",
               ".###.##....#",
               ".###..##.#..",
               ".###..##..#.",
               ".###..##...#",
               ".###...##.#.",
               ".###...##..#",
               ".###....##.#"
             ]
    end

    test "from example input" do
      actual = possible_arrangements({".?#?#?##??.#.???#", [7, 1, 2, 1]})

      assert actual == [
               ".#######...#.##.#",
               "..#######..#.##.#"
             ]
    end
  end
end

ExUnit.run()

Solution - Part 1

PartOne.solve(puzzle_input)
# Parser.parse(puzzle_input) |> Enum.filter(fn {line, _} -> !String.contains?(line, "#") end)

Part Two

Code - Part 2

defmodule PartTwo do
  require Integer, [:is_odd, :is_even]

  def solve(input) do
    IO.puts("--- Part Two ---")
    IO.puts("Result: #{run(input)}")
  end

  def run(input_string) do
    Parser.parse(input_string)
    |> Enum.with_index()
    |> Enum.map(fn {{row, counts}, index} ->
      IO.inspect(index)
      count = count_of_possible_arrangements_v2(row, counts)
      IO.inspect(count, label: :count)
    end)
    |> Enum.sum()
  end

  def count_of_possible_arrangements_v2(row, counts, loops \\ 5) do
    {row, counts} = unfold(row, counts, loops)
    _count_of_possible_arrangements_v2(row, counts)
  end

  def unfold(row, counts, loops \\ 5) do
    {Enum.map(1..loops, fn _ -> row end) |> Enum.join("?"),
     Enum.map(1..loops, fn _ -> counts end) |> List.flatten()}
  end

  defp _count_of_possible_arrangements_v2(row, counts) when is_bitstring(row) do
    _count_of_possible_arrangements_v2(String.split(row, "", trim: true), counts)
  end

  defp _count_of_possible_arrangements_v2(row, counts) do
    _count_of_possible_arrangements_v2(row, counts, "", "", hd(counts))
  end

  defp _count_of_possible_arrangements_v2([], [], _, _, _), do: 1

  defp _count_of_possible_arrangements_v2(row_remaining, counts_remaining, res, "#", 0),
    do:
      _count_of_possible_arrangements_v2(
        row_remaining,
        tl(counts_remaining),
        res,
        "#",
        List.first(tl(counts_remaining))
      )

  defp _count_of_possible_arrangements_v2([], _, _, _, _), do: 0

  defp _count_of_possible_arrangements_v2(["." | row], [], res, last_res, current_count),
    do: _count_of_possible_arrangements_v2(row, [], res <> ".", last_res, current_count)

  defp _count_of_possible_arrangements_v2(["?" | row], [], res, last_res, current_count),
    do: _count_of_possible_arrangements_v2(row, [], res <> ".", last_res, current_count)

  defp _count_of_possible_arrangements_v2(_, [front_count | _], _, ".", current_count)
       when front_count != current_count,
       do: 0

  defp _count_of_possible_arrangements_v2(["#" | _], [], _, _, _), do: 0

  defp _count_of_possible_arrangements_v2(["#" | _], [count | _], _, "#", current_count)
       when count == current_count,
       do: 0

  defp _count_of_possible_arrangements_v2(row, counts, res, last_res, current_count) do
    if cache_val = Process.get({row, counts, last_res, current_count}) do
      cache_val
    else
      cond do
        hd(row) == "#" ->
          _count_of_possible_arrangements_v2(tl(row), counts, res <> "#", "#", current_count - 1)

        hd(row) == "?" && last_res == "#" && current_count == hd(counts) ->
          _count_of_possible_arrangements_v2(tl(row), counts, res <> ".", ".", current_count)

        hd(row) == "?" && current_count != hd(counts) ->
          _count_of_possible_arrangements_v2(tl(row), counts, res <> "#", "#", current_count - 1)

        hd(row) == "?" ->
          results_to_cache =
            _count_of_possible_arrangements_v2(
              tl(row),
              counts,
              res <> "#",
              "#",
              current_count - 1
            ) +
              _count_of_possible_arrangements_v2(tl(row), counts, res <> ".", ".", current_count)

          Process.put({row, counts, last_res, current_count}, results_to_cache)
          results_to_cache

        true ->
          _count_of_possible_arrangements_v2(tl(row), counts, res <> ".", ".", current_count)
      end
    end
  end
end

Tests - Part 2

ExUnit.start(autorun: false)

defmodule PartTwoTest do
  use ExUnit.Case, async: true
  import PartTwo

  @raw_input """
  ???.### 1,1,3
  .??..??...?##. 1,1,3
  ?#?#?#?#?#?#?#? 1,3,1,6
  ????.#...#... 4,1,1
  ????.######..#####. 1,6,5
  ?###???????? 3,2,1
  """

  describe "run/1" do
    test "main example" do
      assert run(@raw_input) == 525_152
    end
  end

  describe "unfold/1" do
    test "simple example" do
      actual = unfold(".#", [1])
      assert actual == {".#?.#?.#?.#?.#", [1, 1, 1, 1, 1]}
    end
  end

  describe "count_of_possible_arrangements/2" do
    test "test 1" do
      actual = count_of_possible_arrangements_v2("???.###", [1, 1, 3], 2)
      assert actual == 1
    end

    test "test 2" do
      actual = count_of_possible_arrangements_v2(".??..??...?##.", [1, 1, 3])
      assert actual == 16384
    end

    test "test 3" do
      actual = count_of_possible_arrangements_v2("?#?#?#?#?#?#?#?", [1, 3, 1, 6])
      assert actual == 1
    end

    test "test 4" do
      actual = count_of_possible_arrangements_v2("????.#...#...", [4, 1, 1])
      assert actual == 16
    end

    test "test 5" do
      actual = count_of_possible_arrangements_v2("????.######..#####.", [1, 6, 5])
      assert actual == 2500
    end

    test "test 6" do
      actual = count_of_possible_arrangements_v2("?###????????", [3, 2, 1])
      assert actual == 506_250
    end

    test "from example input - one that gets stuck" do
      count_of_possible_arrangements_v2("??#??#????????", [1, 5, 1], 5)
    end

    test "from example input - last loop takes a few seconds (9.5, 11.9, 10.0)" do
      count_of_possible_arrangements_v2("???????????.", [2, 2], 5)
    end

    test "from example input - last loop takes a few seconds (6.3, 5.9, 6.0)" do
      count_of_possible_arrangements_v2("?#?.??.????????", [2, 1, 1, 2], 5)
    end

    test "from example input 226 - can't even finish" do
      count_of_possible_arrangements_v2("?.?.???????.????????", [1, 1], 5)
    end
  end

  describe "possible_arrangements considering only a single loop" do
    test "test 1" do
      actual = count_of_possible_arrangements_v2("???.###", [1, 1, 3], 1)
      assert actual == 1
    end

    test "test 2" do
      actual = count_of_possible_arrangements_v2(".??..??...?##.", [1, 1, 3], 1)
      assert actual == 4
    end

    test "test 3" do
      actual = count_of_possible_arrangements_v2("?#?#?#?#?#?#?#?", [1, 3, 1, 6], 1)
      assert actual == 1
    end

    test "test 4" do
      actual = count_of_possible_arrangements_v2("????.#...#...", [4, 1, 1], 1)
      assert actual == 1
    end

    test "test 5" do
      actual = count_of_possible_arrangements_v2("????.######..#####.", [1, 6, 5], 1)
      assert actual == 4
    end

    test "test 6" do
      actual = count_of_possible_arrangements_v2("?###????????", [3, 2, 1], 1)
      assert actual == 10
    end

    test "from example input" do
      actual = count_of_possible_arrangements_v2(".?#?#?##??.#.???#", [7, 1, 2, 1], 1)
      assert actual == 2
    end
  end
end

ExUnit.run()

Solution - Part 2

PartTwo.solve(puzzle_input)