Backtracking in Elixir

Questions / Help
1

How does Backtracking actually work in Elixir? I’m currently working on this leetcode problem where we have been given a string of digits and we have to find all possible letter combinations that the number can represent. However, I can’t seem to understand how backtracking will work here due to immutability of Elixir.

I tried writing my solution based on this C++ code (Solution - II) given below:

defmodule Solution do
    def letter_combinations(digits) do
        ans = []
        mappings = %{
          "2" => "abc", 
          "3" => "def", 
          "4" => "ghi", 
          "5" => "jkl", 
          "6" => "mno", 
          "7" => "pqrs", 
          "8" => "tuv", 
          "9" => "wxyz"
        }
        
        cond do
            String.equivalent?(digits, "") -> ans
            true -> 
                combination = ""
                helper(digits, mappings, ans, 0, combination) |> :lists.reverse
        end
    end
    
    def helper(digits, mappings, ans, i, combi) do
        cond do
            i == String.length(digits) -> [combi | ans]
            true -> 
                list = mappings[String.at(digits, i)] |> String.graphemes
                
                list |> Enum.reduce({ans, combi}, fn(c, {ans, combi}) -> 
                    combi = combi <> c
                    ans = helper(digits, mappings, ans, i+1, combi)
                    combi = String.slice(combi, 0..String.length(combi)-1) # Backtracking
                    
                    {ans, combi}
                end)
                |> elem(0)
        end
    end
end

digits ="23"
IO.inspect Solution.letter_combinations(digits)

What I’m doing here is creating mappings that maps the phone digits with the corresponding alphabets. Then, inside the helper function, I check to see if the variable i is equal to the size of the string (in this case, we will return ans since our condition has been met).

Then, I extract the graphemes from the map using the digits string as the key and then apply reduce over it. Inside the reduce, I concatenate the letter combinations and then update my ans list along with the backtracking process.

However, my results don’t seem to be accurate and I seem to be getting the output ["ad", "ade", "adef", "abd", "abde", "abdef", "abcd", "abcde", "abcdef"] when it should be ["ad","ae","af","bd","be","bf","cd","ce","cf"].

Can someone guide me as to what am I doing wrong here? Also, for general purposes, how can we perform backtracking in Elixir if it is possible?

Any help will be appreciated. Thank you!

2

This doesn’t shorten combi - it takes the whole thing. You’d need to subtract 2 instead of 1 to get the result you expect.

HOWEVER

A better way to do it is to not rebind combi:

                list |> Enum.reduce({ans, combi}, fn(c, {ans, combi}) -> 
                    longer_combi = combi <> c
                    ans = helper(digits, mappings, ans, i+1, longer_combi)
                    
                    {ans, combi}
                end)
3

You do not need backtracking, all you need is to notice, that <<c>> <> rest is the result of:

Enum.map(keypad_characters[c], &[&1 | letter_combinations(rest)])

Aka, the mapping of the first character of the string with combinations of rest of the characters.

Here you have my solution:

defmodule Solution do
  @letters %{
    ?2 => 'abc',
    ?3 => 'def',
    ?4 => 'ghi',
    ?5 => 'jkl',
    ?6 => 'mno',
    ?7 => 'pqrs',
    ?8 => 'tuv',
    ?9 => 'wxyz'
  }

  @spec letter_combinations(digits :: String.t) :: [String.t]
  def letter_combinations(<<>>), do: []
  def letter_combinations(str), do: do_letter_combinations(str)

  defp do_letter_combinations(""), do: [""]

  defp do_letter_combinations(<<c>> <> rest) do
    for l <- @letters[c],
        suffix <- do_letter_combinations(rest),
        do: <<l>> <> suffix
  end
end

Some additional logic is needed to simplify the the above statement, but in general it is all that is needed.

2 Likes
4

here’s a solution with reduce (which always solves all otherwise unsolvable problems).

defmodule Phone do
  @keys %{
    2 => 'abc',
    3 => 'def',
    4 => 'ghi',
    5 => 'jkl',
    6 => 'mno',
    7 => 'pqrs',
    8 => 'tuv',
    9 => 'wxyz'
  }

  def letter_combinations([]), do: []

  def letter_combinations([digit | digits]) do
    Enum.reduce(
      digits,
      Enum.map(@keys[digit], &[&1]),
      fn digit, acc -> for i <- acc, j <- @keys[digit], do: i ++ [j] end
    )
  end
end
5

Oneliner, fwiw. Change "23" to the desired input.

# thanks Hauleth for letters I stole from your solution :)
letters = %{
    ?2 => 'abc',
    ?3 => 'def',
    ?4 => 'ghi',
    ?5 => 'jkl',
    ?6 => 'mno',
    ?7 => 'pqrs',
    ?8 => 'tuv',
    ?9 => 'wxyz'
  }

for <<c <- "23">>, reduce: [] do
  [] -> letters[c]
  acc -> Enum.flat_map(acc, fn e -> (for l <- letters[c], do: List.wrap(e) ++ [l]) end)
end
#⇒ ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
3 Likes