Solving 24 Puzzle with Elixir

in elixir

A recent blog post I read reminded me how good computers are at solving puzzles. In the linked post the author solved a game called 24, in which you take 4 digits and need to find an arithmetic combinations of them to reach the number 24.

Elixir's strong recursion and pattern matching capabilities are a good match to the challenge.

The Gist

Let's start with the code. Explanation follows:

defmodule Game do

  def play(ops, [24]) do
    ops
  end

  def play(_ops, [_x]) do
    false
  end

  def play([], [ head | rest]) do
    play(head, [ head | rest])
  end

  def play(ops, [ head | [next | rest ]]) do    
    Game.play({ :+, ops, next }, [head + next] ++ rest) ||
    Game.play({ :*, ops, next }, [head * next] ++ rest) ||
    (next != 0 && Game.play({ :/, ops, next }, [div(head, next)] ++ rest)) ||
    Game.play({ :-, ops, next }, [head - next] ++ rest) ||
    Game.play({ :-, next, ops }, [next - head] ++ rest) ||
    (head != 0 && Game.play({ :/, next, ops }, [div(next, head)] ++ rest))
  end

  def play(digits) do
    IO.puts "Searching for solution to:"
    IO.inspect digits
    IO.inspect(play([], digits))
  end
end

Game.play([4, 5, 1, 5])

That was quick! The entire module takes less than 30 lines, and the important function takes less than 10.

How It Works

With elixir's pattern matching, the recursion's halting condition is obvious. In our program the first 2 function definitions are the two possible halts: Either you found 24 or you didn't. In the first case return the path you took, and in the second return false.

The third function definition handles the first invocation. Let's put it aside for a moment and move on to the fourth and main code.

The function takes a path taken so far and the remaining digits and needs to decide if there's a way to continue the path to reach 24. It does so by recursion: If there is a path it must use one of the 6 arithmetic operations described, so let's take each step and see if it would lead us to 24 (leaving breadcrumbs along the way by adding the step taken to path).

If we run the code thus far, without the skipped function definition we should get:

Searching for solution to:
[4, 5, 1, 5]
{:+, {:-, {:*, [], 5}, 1}, 5}

This is almost correct, but you'd probably expect to find the 4 instead of the empty list. That's what the third function definition is for:

  def play([], [ head | rest]) do
    play(head, [ head | rest])
  end

It handles the first invocation where path is still empty and uses the first digit as an initial path value. With it the correct solution is printed:

Searching for solution to:
[4, 5, 1, 5]
{:+, {:-, {:*, 4, 5}, 1}, 5}

With its immutable data and pattern matching, elixir allows us to build complex recursions leaving the code concise and well organized.

Edit: Solving 2, 2, 5, 7

Turns out I'm not that good at playing the 24 puzzle as I thought. As Mark Dominus (the author of the original post which inspired this one) noticed, it wasn't able to solve 2, 2, 5, 7.

The reason obviously is my suggested code added one digit at a time, but some puzzles require different pairings.

That sent me back to the drawing board but turned out to be for the better. Here's a fixed version that solves 2, 2, 5, 7 (as well as tons of other puzzles) AND looks much nicer.

This time I used list comprehension to select any two items from the list and pair them, AND the module Ratio to get rational number division to work as expected:

defmodule P24 do
  use Ratio
  def value({ op, x, y }) do
    apply(Ratio, op, [value(x), value(y)])
  end

  def value(n) do
    n
  end

  def play([ t ]) do        
    if value(t) == 24, do: t
  end

  def play(digits) do
    for head <- digits, next <- List.delete(digits, head) do
      rest = List.delete(digits, head) |> List.delete(next)
      
      play([{:+, head, next}] ++ rest) ||
      play([{:*, head, next}] ++ rest) ||
      (value(next) != 0 && play([{:/, head, next}] ++ rest)) ||
      play([{:-, head, next }] ++ rest) ||
      play([{:-, next, head }] ++ rest) ||
      (value(head) != 0 && play([{:/, next, head}] ++ rest))
    end |>
    Enum.find(fn(x) -> !!x end)
  end
end

Performance is probably not great due to the list comprehension which calculates all possible solutions even after a solution is found. Still code is mostly clear and easy to understand.

The main advantage over the previous version (besides being more correct) is the use of tuples to represents expressions instead of their results. This makes it trivial to see the full path and allowed me to remove the ops argument.

Comments