Advent of Code 2023 - Day 12

I spent most time to get part 1 to work; I solved part 2 by adding memoization:

https://github.com/bjorng/advent-of-code-2023/blob/main/day12/lib/day12.ex

@Aetherus I love your process dictionary trick. I just set up an ETS for each thread . I wonder though if process dictionaries are O(1) or O(log N) like other maps in Elixir?

My solution (not very happy with how it turned out, feels like way too much code):

https://github.com/ibarakaiev/advent-of-code-2023/blob/main/lib/advent_of_code/day_12.ex

Runs in around 0.2 seconds.

I don’t know whether it’s O(1) or O(log N) either. According to my benchmark (not for this puzzle), process dictionary is faster than ETS, which in turn is faster than a plain map, and Agent is the slowest.

Just tried changing my solution to use process dictionaries instead — besides a much cleaner solution, it seems that this version is indeed around 10% faster than my old ETS-based approach. Never used process dictionaries in this way, thanks for sharing your solution! Learned a new thing today.

Well I split the springs into groups (so ??..??.#? becomes ["??", "??", "#?"], and then I ran my (originally non-memoized) fit-counter, which I then memoized once I encountered part 2 with a dumb Map, that I just send up and down the recursive function

https://github.com/ramuuns/aoc/blob/master/2023/day-12.ex

Today was tricky, I got the naive solution but optimizing for part 2 was not easy:

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

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA…

Ok so after hours and hours failing, I looked a bit online and found some tips to implement a fast solution.

The problem is that is was only in mutable imperative languages, so I had a hard time to find my own thing in Elixir. And it still could be better.

I could not have made it alone, I was too lost.

But anyway, this solutions takes 100ms for part 2 which is satisying. : adventofcode/lib/solutions/2023/day12.ex at main · lud/adventofcode · GitHub

I tried a pure functional approach. Here’s my heavily commented code:

defmodule AoC2023.Day12.FunctionalMemoization do

  # `input` for both parts are things like
  #
  # [
  #   {"#.#.###", [1,1,3]},
  #   {".#...#....###.", [1,1,3]},
  #   ...
  # ]

  @spec part1([{String.t(), [pos_integer()]}]) :: non_neg_integer()
  def part1(input) do
    input
    |> Task.async_stream(fn {springs, counters} ->
      # It does not change the result
      # if we prepend a "." to each line of springs.
      # By adding this "." I do not need to handle the
      # edge case that the line starts with a "?".
      aux(springs, 0, ".", counters, %{})
    end, ordered: false)
    |> Stream.map(&elem(&1, 1))
    |> Stream.map(&elem(&1, 0))
    |> Enum.sum()
  end

  @spec part2([{String.t(), [pos_integer()]}]) :: non_neg_integer()
  def part2(input) do
    input
    |> Enum.map(fn {springs, counters} ->
      {
        List.duplicate(springs, 5) |> Enum.join("?"),
        List.duplicate(counters, 5) |> List.flatten()
      }
    end)
    |> part1()
  end

  @spec aux(
    springs :: String.t(),
    index,
    previous_spring :: String.t(),
    counters,
    memo
  ) :: {total_count, memo}
  when index: non_neg_integer(),
       counters: [non_neg_integer()],
       total_count: non_neg_integer(),
       memo: %{optional({index, counters}) => total_count}

  # When we reached the end of a line,
  # and all counters are consumed,
  # we found a solution.
  defp aux("", _, _, [], memo), do: {1, memo}

  # When we reached the end of a line,
  # and the last counter reaches 0,
  # we found a solution.
  defp aux("", _, _, [0], memo), do: {1, memo}

  # When we reached the end of a line,
  # and there is at least one non-zero counter,
  # that's an invalid situation so no solution.
  defp aux("", _, _, _, memo), do: {0, memo}

  # When the current spring is broken,
  # and there is no counter left,
  # that's an invalid situation so no solution.
  defp aux("#" <> _, _, _, [], memo), do: {0, memo}

  # When the current spring is broken,
  # and the current counter reaches 0,
  # that's an invalid situation so no solution.
  defp aux("#" <> _, _, _, [0 | _], memo), do: {0, memo}

  # When the current spring is broken,
  # and the current counter is not 0,
  # decrement the counter and recursively find solutions.
  defp aux("#" <> rest, i, _, [h | t], memo), do: aux(rest, i + 1, "#", [h - 1 | t], memo)

  # When the current spring is good,
  # and there's no counter left,
  # try rest of the line and see if all the springs left are good.
  defp aux("." <> rest, i, _, [], memo), do: aux(rest, i + 1, ".", [], memo)

  # When the current spring is good,
  # and the previous spring is bad,
  # and the current counter reaches 0,
  # we can discard that 0 and recursively find solutions.
  defp aux("." <> rest, i, "#", [0 | t], memo), do: aux(rest, i + 1, ".", t, memo)

  # When the current spring is good,
  # and the previous spring is bad,
  # and the current counter is not 0,
  # that's an invalid situation so no solution.
  defp aux("." <> _, _, "#", [_ | _], memo), do: {0, memo}

  # When the current spring is good,
  # and the previous spring is also good,
  # and the current counter is not 0,
  # just check the rest of the springs.
  defp aux("." <> rest, i, ".", counters, memo), do: aux(rest, i + 1, ".", counters, memo)

  # When the current spring is unknown,
  # and the previous spring is broken,
  # and there's no counter left,
  # then the current spring has to be good.
  # We still need to check the rest of the springs. 
  defp aux("?" <> rest, i, "#", [], memo), do: aux(rest, i + 1, ".", [], memo)

  # When the current spring is unknown,
  # and the previous spring is broken,
  # and the current counter reaches 0,
  # then the current spring has to be good.
  # We still need to check the rest of the springs.
  # The zero-counter is no longer useful so we discard it.
  defp aux("?" <> rest, i, "#", [0 | t], memo), do: aux(rest, i + 1, ".", t, memo)

  # When the current spring is unknown,
  # and the previous spring is bad,
  # and the current counter is not 0,
  # then the current spring has to be broken.
  # We decrement that counter and check the rest of the springs.
  defp aux("?" <> rest, i, "#", [h | t], memo), do: aux(rest, i + 1, "#", [h - 1 | t], memo)

  # When the current spring is unknown,
  # and the previous spring is good,
  # and there's no counter left,
  # then the current spring has to be good.
  # We still need to check the rest of the springs.
  defp aux("?" <> rest, i, ".", [], memo), do: aux(rest, i + 1, ".", [], memo)

  # When the current spring is unknown,
  # and the previous spring is good,
  # and the current counter reaches 0,
  # then the current spring must be good.
  # Discard the 0 counter as usual,
  # and check the rest of the springs.
  defp aux("?" <> rest, i, ".", [0 | t], memo), do: aux(rest, i + 1, ".", t, memo)

  # When the current spring is unknown,
  # and the previous spring is good,
  # and the current counter is not 0,
  # then the current spring can be either good or bad.
  # Try both possibilities.
  defp aux("?" <> rest, i, ".", [h | t], memo) do
    memoized(memo, {i, [h | t]}, fn ->
      {a, memo} = aux(rest, i + 1, "#", [h - 1 | t], memo)
      {b, memo} = aux(rest, i + 1, ".", [h | t], memo)
      {a + b, memo}
    end)
  end

  defp memoized(memo, key, fun) do
    with nil <- Map.get(memo, key) do
      {result, memo} = fun.()
      memo = Map.put(memo, key, result)
      {result, memo}
    else
      result -> {result, memo}
    end
  end
end

Nice !

So your memo cache is just the current group index and the remaining group counters.

I tried a memoized solution but I could not get it right. I had either no cache hits or wrong results

I think that if you map each possibility at each step, and sum the indentical states counts, then that would be equivalent to my solution.

I still need to try your solution in a debugging way to fully understand it.

Here’s what I think about dynamic programming. It’s just brute force with some sort of caching. When we talk about caching, we know each entry needs a key. I think it doesn’t matter what the key is, as long as it’s consistent. If the keys are continuous non-negative integers or tuples of integers, in imperative languages we usually use an array or a 2D array or a 3D array as our store. But we don’t have to restrict ourselves to that kind of caching mechanism. We can use maps, GenServers, ETS tables, process dictionaries, or even databases as the cache store as long as it provides a fast way of lookup for an exact match, and what the type of the keys are just doesn’t matter.