Solution for "four fours" problem

README.md

Fours

A partial solution to the problem posed here: https://twitter.com/mikelikesbikes/status/1396159019837018117

This solution represents the expressions in reverse Polish notation (RPN) - see also Forth and HP48s.

The version presented here does NOT produce all values from 1 to 100, as it does not use enough operators.

Extending the search to additional operators only requires adding the value to @operators and a clause to eval to handle it.

fours.exs

defmodule Fours do
  @operators [:add, :sub, :mul, :div]

  def seqs(prefix, 0, 1), do: Enum.map(@operators, &(prefix ++ [&1]))
  def seqs(prefix, fours, _) when fours < 0, do: []
  def seqs(prefix, fours, 0), do: [prefix ++ List.duplicate(4, fours)]
  def seqs(prefix, fours, ops) do
    @operators
    |> Enum.map(&seqs(prefix ++ [&1], fours, ops-1))
    |> Kernel.++([seqs(prefix ++ [4], fours-1, ops)])
    |> Stream.concat()
  end

  def eval(expr), do: eval(expr, [])
  def eval([:add | rest], [y, x | stack_rest]) do
    eval(rest, [1.0*(x + y) | stack_rest])
  end
  def eval([:sub | rest], [y, x | stack_rest]) do
    eval(rest, [1.0*(x - y) | stack_rest])
  end
  def eval([:mul | rest], [y, x | stack_rest]) do
    eval(rest, [1.0*(x * y) | stack_rest])
  end
  def eval([:div | rest], [y, x | stack_rest]) when y != 0 do
    eval(rest, [x / y | stack_rest])
  end
  def eval([val | rest], stack) when is_integer(val) do
    eval(rest, [val | stack])
  end
  def eval([], [result]) do
    result
  end
  def eval(_, _) do
    :crash
  end

  def possible_value_map(exprs) do
    exprs
    |> Stream.map(&{&1, Fours.eval(&1)})
    |> Enum.to_list()
    |> Enum.group_by(&elem(&1, 1), &elem(&1, 0))
  end
end

Fours.seqs([4, 4], 2, 3) |> Fours.possible_value_map()