After I had to wait for my BEAM to crash because of infinite recursion (it blocked my laptop totally, even ssh was impossible) I rewrote to use binaries.

The BEAM can optimise appending on them under certain conditions, and I think I have met them.

Also this way you do not need to create that extra list that holds the code points.

A next step was to remove the case/2 from the public function and let this be handled by the helper function.

Then I combined the “draws” into a single pattern match, in your version it would be defp _find_winner([x, x|rest], acc), do: _find_winner(rest, acc).

After that I extracted another function which would determine the winner of a single match.

And the last thing I did, was to remove the underscore prefix, because I do read it as “this isn’t meant to be used”.

defmodule RockPaperScissors do
  def find_winner(lineup), do: find_winner(lineup, "")

  # Nobody won
  defp find_winner("", ""), do: "None"

  # last man standing wins
  defp find_winner(winner = <<_::utf8>>, ""), do: winner

  # Advance to the next round!
  defp find_winner("", acc), do: find_winner(acc, "")

  # Single player remaining (bc of odd number of players)
  defp find_winner(<<a::utf8>>, acc), do: find_winner("", <<acc::binary, a::utf8>>)

  # Both are the same, both loose
  defp find_winner(<<a::utf8, a::utf8, rest::binary>>, acc), do: find_winner(rest, acc)

  # only one hands wins
  defp find_winner(<<a::utf8, b::utf8, rest::binary>>, acc),
    do: find_winner(rest, <<acc::binary, single_game(a, b)::utf8>>)

  defp single_game(?P, ?R), do: ?P
  defp single_game(?P, ?S), do: ?S
  defp single_game(?R, ?P), do: ?P
  defp single_game(?R, ?S), do: ?R
  defp single_game(?S, ?P), do: ?S
  defp single_game(?S, ?R), do: ?R
end

alias RockPaperScissors, as: RPS

IO.puts(~s'"R" is "R" -> #{RPS.find_winner("R")}')
IO.puts(~s'"RR" is "None" -> #{RPS.find_winner("RR")}')
IO.puts(~s'"RRS" is "S" -> #{RPS.find_winner("RRS")}')
IO.puts(~s'"RRRSRSPS" is "S" -> #{RPS.find_winner("RRRSRSPS")}')

I have not benchmark this or one of your codes. But I have not really optimzed for speed, but instead rewritten in a way that I consider easier to read and maintain.

It’s quite easy to use prepending in this case. (if I am not mistaken) Just reverse the acc when advancing to the next round. I tried it and the results are very nice. I generated three inputs to benchmark on. 10 chars long, 1_000 chars long, 100_000 chars long. I tried 1_000_000 too, but that was taking extremely long.

Generating inputs:

Enum.each([10, 1000, 100000], fn count ->
  str =
    1..count
    |> Enum.reduce([], fn _, arr -> [Enum.random(["R", "S", "P"]) | arr] end)
    |> Enum.join()

  File.write("rsp#{count}.txt", str)
end)

Code:

defmodule Rsp2 do
  def find_winner(lineup) do
    case _find_winner(String.codepoints(lineup), []) do
      "" -> "None"
      result -> result
    end
  end

  # Nobody won
  defp _find_winner([], []), do: ""

  # Cases where only 1 player is left means we're done!
  defp _find_winner([one_remaining], []), do: one_remaining

  # Single player remaining (bc of odd number of players)
  defp _find_winner([one_remaining], acc), do: _find_winner([], [one_remaining | acc])

  # Advance to the next round!
  defp _find_winner([], acc), do: _find_winner(Enum.reverse(acc), [])

  defp _find_winner(["R", "R" | rest], acc), do: _find_winner(rest, acc)
  defp _find_winner(["R", "P" | rest], acc), do: _find_winner(rest, ["P" | acc])
  defp _find_winner(["R", "S" | rest], acc), do: _find_winner(rest, ["R" | acc])

  defp _find_winner(["P", "R" | rest], acc), do: _find_winner(rest, ["P" | acc])
  defp _find_winner(["P", "P" | rest], acc), do: _find_winner(rest, acc)
  defp _find_winner(["P", "S" | rest], acc), do: _find_winner(rest, ["S" | acc])

  defp _find_winner(["S", "R" | rest], acc), do: _find_winner(rest, ["R" | acc])
  defp _find_winner(["S", "P" | rest], acc), do: _find_winner(rest, ["S" | acc])
  defp _find_winner(["S", "S" | rest], acc), do: _find_winner(rest, acc)
end

Benchmark:

path10 = Path.join(File.cwd!(), "rsp10.txt")
rsp10 = File.read!(path10)

path1000 = Path.join(File.cwd!(), "rsp1000.txt")
rsp1000 = File.read!(path1000)

path100000 = Path.join(File.cwd!(), "rsp100000.txt")
rsp100000 = File.read!(path100000)

Benchee.run(%{
  "10-appending" => fn -> Rsp.find_winner(rsp10) end,
  "10-prepending" => fn -> Rsp2.find_winner(rsp10) end
})

Benchee.run(%{
  "1000-appending" => fn -> Rsp.find_winner(rsp1000) end,
  "1000-prepending" => fn -> Rsp2.find_winner(rsp1000) end
})

Benchee.run(%{
  "100000-appending" => fn -> Rsp.find_winner(rsp100000) end,
  "100000-prepending" => fn -> Rsp2.find_winner(rsp100000) end
})

Results:

10-prepending      725.52 K
10-appending       720.15 K - 1.01x slower +0.0103 μs

1000-prepending       10.28 K
1000-appending         3.67 K - 2.80x slower +175.15 μs

100000-prepending         44.95
100000-appending           0.51 - 87.31x slower +1.92 s

I am sure, there are some other improvements to be made, but this was the lowest hanging fruit in my opinion. I am looking forward to other suggestions.

FYI, here’s the comparison to my and to original solution for 100_000 chars:

100000-nobbz             246.44
100000-prepending         41.99 - 5.87x slower +19.76 ms
100000-appending           0.49 - 503.66x slower +2039.71 ms