Debugging Boggle Solver Implemented in Elixir with Trie Structure

Question

I'm working on a Boggle game solver in Elixir that uses a trie to efficiently search for words. My implementation, however, doesn't produce the correct paths for the found words. Instead of showing the actual path traversed on the Boggle board, it repeats the same incorrect path for every word found.

Here's a brief overview of the implementation:

• The game board and a list of words are provided as input.

• Each word is searched on the board using a trie for efficient lookups.

• The expected output should be a map of words to their paths on the board, indicating where each letter of the word can be found.

defmodule Boggle do
  defstruct value: nil, children: %{}

  @moduledoc """
  Implements a boggle solver using a trie for efficient word searching.
  """

  def boggle(board, words) do
    board_lists = Enum.map(Tuple.to_list(board), &Tuple.to_list/1)
    trie = from_list(words)

    Enum.reduce(words, %{}, fn word, acc ->
      paths = find_word(board_lists, word, trie)
      if Enum.any?(paths) do
        # Take the first valid path for simplicity, adjust logic as needed
        Map.put(acc, word, Enum.at(paths, 0))
      else
        acc
      end
    end)
  end

  defp explore(_board, %__MODULE__{value: :word_end}, path, _visited, _), do: [path]
  defp explore(_board, %__MODULE__{children: _}, _path, _visited, []), do: []
  defp explore(board, %__MODULE__{} = trie, path, visited, [{x, y} | rest] = _to_visit) do
    if valid_position?(x, y, board) and {x, y} not in visited do
      letter = Enum.at(Enum.at(board, x), y)
      case Map.get(trie.children, letter) do
        nil ->
          # Letter not in trie, abort this path
          explore(board, trie, path, visited, rest)

        next_trie ->
          # Continue exploring with this letter as part of the path
          new_path = [{x, y} | path]
          new_visited = [{x, y} | visited]
          next_to_visit = rest ++ neighbors(x, y, board, new_visited)

          explore(board, next_trie, new_path, new_visited, next_to_visit) ++
            explore(board, trie, path, visited, rest)
      end
    else
      # Invalid position or already visited, continue with the rest of the to_visit list
      explore(board, trie, path, visited, rest)
    end
  end

  defp neighbors(x, y, board, visited) do
    for dx <- -1..1,
        dy <- -1..1,
        new_x = x + dx,
        new_y = y + dy,
        valid_position?(new_x, new_y, board) and {new_x, new_y} not in visited,
        do: {new_x, new_y}
  end

  defp find_word(board, _word, trie) do
    for x <- 0..(length(board) - 1),
        y <- 0..(length(Enum.at(board, x)) - 1),
        path = explore(board, trie, [], [], [{x, y}]),
        reduce: [] do
      acc -> acc ++ path
    end
    |> Enum.uniq()
  end

  defp valid_position?(x, y, board) do
    x >= 0 and x < length(board) and y >= 0 and y < length(Enum.at(board, x))
  end

  def insert(%__MODULE__{} = trie, word) when is_binary(word) do
    insert_helper(trie, String.graphemes(word))
  end

  defp insert_helper(trie, []) do
    Map.put(trie, :value, :word_end)
  end

  defp insert_helper(%Boggle{children: children} = trie, [head | tail]) do
    child = Map.get(children, head, %Boggle{value: nil, children: %{}})
    updated_child = insert_helper(child, tail)
    Map.put(trie, :children, Map.put(children, head, updated_child))
  end

  def from_list(words) do
    Enum.reduce(words, %Boggle{}, fn word, acc -> insert(acc, word) end)
  end
end

For the board setup {{"e", "a", "r"}, {"s", "t", "p"}, {"b", "c", "o"}} and the words ["east", "eat", "sat", "top", "atop", "spot"], the output is incorrect. All words report the same path {1, 1}, {1, 0}, {0, 1}, {0, 0}, which is clearly not right.

Expected Output:

%{
  "atop" => [{0, 1}, {1, 1}, {2, 2}, {1, 2}],
  "east" => [{0, 0}, {0, 1}, {1, 0}, {1, 1}],
  "eat" => [{0, 0}, {0, 1}, {1, 1}],
  "sat" => [{1, 0}, {0, 1}, {1, 1}],
  "top" => [{1, 1}, {2, 2}, {1, 2}]
}

I suspect the problem might lie in the way paths are constructed or how the trie is traversed, but I've been unable to pinpoint the exact cause. I have been working on this issue for a while, and my head is aching at the moment. Therefore, I decided to seek help on this forum,