defmodule Day19 do
  def run do
    {patterns, designs} = parse_file("data.txt")

    {possibles, _c} =
      Enum.reduce(designs, {[], %{}}, fn d, {list, cache} ->
        {total, c} = possible_designs(d, patterns, cache)
        {[total | list], c}
      end)

    part1 = Enum.filter(possibles, fn el -> el != 0 end) |> length
    dbg(part1)

    part2 = Enum.sum(possibles)
    dbg(part2)
  end

  # if the design is empty list, we got to the end successfully
  defp possible_designs([], _, cache), do: {1, cache}

  defp possible_designs(design, patterns, cache) do
    # look in the cache for this design
    if Map.has_key?(cache, design) do
      # if it's there, just return it
      {Map.get(cache, design), cache}
    else
      # find all the patterns that match the beginning of the design
      matching_patterns = Enum.filter(patterns, &List.starts_with?(design, &1))

      {new_total, new_cache} =
        if length(matching_patterns) == 0 do
          # if there are none, we've failed
          {0, cache}
        else
          # recurse on rest of the list
          Enum.reduce(matching_patterns, {0, cache}, fn pattern, {total, new_cache} ->
            rest = Enum.drop(design, length(pattern))
            {t, c} = possible_designs(rest, patterns, new_cache)
            {t + total, c}
          end)
        end

      # add this new total to the cache & return it
      new_cache2 = Map.put(new_cache, design, new_total)
      {new_total, new_cache2}
    end
  end

  defp parse_file(file) do
    [top, bottom] = File.read!(file) |> String.trim() |> String.split("\n\n")
    patterns = String.split(top, ", ") |> Enum.map(&String.graphemes/1)
    designs = String.split(bottom, "\n") |> Enum.map(&String.graphemes/1)
    {patterns, designs}
  end
end

Day19.run()