Day 12

Solution

defmodule D12 do
  def parse_input(input) do
    input
    |> String.split("\n", trim: true)
    |> Enum.map(fn line ->
      [states, damaged] = String.split(line)

      damaged =
        damaged
        |> String.split(",")
        |> Enum.map(&String.to_integer/1)

      {states, damaged}
    end)
  end

  def solve(states, damaged, memo \\ %{}), do: solve(states, damaged, 0, memo) |> elem(0)

  def solve("", [], _, memo), do: {1, memo}
  def solve("", _, _, memo), do: {0, memo}
  def solve("#", [1], _, memo), do: {1, memo}
  def solve("#", damaged, _, memo) when length(damaged) > 0, do: {0, memo}

  def solve(<<"?", rest::binary>>, [springs | damaged], continuing, memo) do
    if continuing > 0 do
      if springs > 0 do
        solve_with_memo("#" <> rest, [springs | damaged], continuing, memo)
      else
        {dot_ans, _} = solve_with_memo("." <> rest, [continuing | damaged], 0, memo)
        {hash_ans, _} = solve_with_memo("#" <> rest, damaged, continuing, memo)
        {hash_ans + dot_ans, memo}
      end
    else
      {hash_ans, memo} = solve_with_memo("#" <> rest, [springs | damaged], 0, memo)
      {dot_ans, memo} = solve_with_memo("." <> rest, [springs | damaged], 0, memo)
      {hash_ans + dot_ans, memo}
    end
  end

  def solve(<<"?", rest::binary>>, [], _continuing, memo) do
    solve_with_memo("." <> rest, [], 0, memo)
  end

  def solve(<<".", rest::binary>>, damaged, _continuing, memo) do
    solve_with_memo(rest, damaged, 0, memo)
  end

  def solve(
        <>,
        [springs | damaged],
        continuing,
        memo
      ) do
    case {a, b, springs} do
      {"#", ".", 1} ->
        solve_with_memo(b <> rest, damaged, 0, memo)

      {"#", ".", _} ->
        {0, memo}

      {"#", "#", springs} when springs < 2 ->
        {0, memo}

      {"#", "#", springs} when springs >= 2 ->
        solve(b <> rest, [springs - 1 | damaged], continuing + 1, memo)

      {"#", "?", 1} ->
        solve_with_memo("." <> rest, damaged, 0, memo)

      {"#", "?", springs} when springs > 1 ->
        solve(b <> rest, [springs - 1 | damaged], continuing + 1, memo)

      {"#", "?", _} ->
        {0, memo}

      {".", b, springs} ->
        if continuing > 0 do
          solve_with_memo(b <> rest, [continuing | springs], 0, memo)
        else
          solve_with_memo(b <> rest, springs, 0, memo)
        end
    end
  end

  def solve(<<"#", _rest::binary>>, [], _, memo), do: {0, memo}

  def solve_with_memo(states, damaged, continuing, memo) do
    case Map.get(memo, {states, damaged}) do
      nil ->
        {answer, memo} = solve(states, damaged, continuing, memo)
        memo = if continuing == 0, do: Map.put(memo, {states, damaged}, answer), else: memo
        {answer, memo}

      answer ->
        {answer, memo}
    end
  end

  def p1(input) do
    input
    |> Enum.map(fn {states, damaged} -> solve(states, damaged) end)
    |> Enum.sum()
  end

  def p2(input) do
    input
    |> Task.async_stream(
      fn {states, damaged} ->
        states = List.duplicate(states, 5) |> Enum.intersperse("?") |> Enum.join()
        damaged = List.duplicate(damaged, 5) |> List.flatten()

        solve(states, damaged)
      end,
      timeout: :infinity
    )
    |> Enum.map(&amp;elem(&amp;1, 1))
    |> Enum.sum()
  end
end

{:module, D12, <<70, 79, 82, 49, 0, 0, 27, ...>>, {:p2, 1}}

Tests

ExUnit.start(autorun: false)

defmodule D12Test do
  use ExUnit.Case, async: true

  @test_input D12.parse_input("""
              ???.### 1,1,3
              .??..??...?##. 1,1,3
              ?#?#?#?#?#?#?#? 1,3,1,6
              ????.#...#... 4,1,1
              ????.######..#####. 1,6,5
              ?###???????? 3,2,1
              """)

  @input Path.join(__DIR__, "inputs/d12") |> File.read!() |> D12.parse_input()

  test "part 1 works" do
    assert D12.p1(@test_input) == 21
    assert D12.p1(@input) == 7236
  end

  test "part 2 works" do
    assert D12.p2(@test_input) == 525_152
    assert D12.p2(@input) == 11_607_695_322_318
  end
end

ExUnit.run()

..
Finished in 0.1 seconds (0.1s async, 0.00s sync)
2 tests, 0 failures

Randomized with seed 543087

%{excluded: 0, failures: 0, skipped: 0, total: 2}