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

I decided to test things with the previous solution, but matching binaries directly :

defmodule Rps do

    defp battle2(a,a), do: :none
    defp battle2(:none, b), do: b
    defp battle2(a, :none), do: a
    defp battle2({:some, ?P}, {:some, ?R}), do: {:some, ?P}
    defp battle2({:some, ?P}, {:some, ?S}), do: {:some, ?S}
    defp battle2({:some, ?R}, {:some, ?S}), do: {:some, ?R}
    defp battle2({:some, ?R}, {:some, ?P}), do: {:some, ?P}
    defp battle2({:some, ?S}, {:some, ?P}), do: {:some, ?S}
    defp battle2({:some, ?S}, {:some, ?R}), do: {:some, ?R}

    def tournament2(acc, ""), do: acc
    def tournament2(acc, <<a::utf8>>), do: battle2(acc, {:somme, a})
    def tournament2(acc, <<a::utf8, b::utf8>>), do: battle2(acc, battle2({:some, a}, {:some, b}))
    def tournament2(acc, <<a::utf8, b::utf8, rest::binary>>) do
      newacc = battle2(acc, battle2({:some, a}, {:some, b}))
      tournament2(newacc, rest)
    end  
    def find_winner2(lineup) do
      case tournament2(:none, lineup) do
        :none ->  "None"
        {:some, ch} -> <<ch>>
      end
    end
end

I believe it is still correct, but much faster and I think still readable. Running the benchmarks provided by EskiMaq gives the following results :

Name                      ips        average  deviation         median         99th %
10-bin_match        1452.02 K        0.69 μs  ±5238.39%        0.55 μs        1.23 μs
10-prepending        758.06 K        1.32 μs  ±1740.29%        1.13 μs        2.84 μs
10-appending         708.89 K        1.41 μs  ±2114.40%        1.18 μs        3.09 μs
10-nobbz             668.64 K        1.50 μs  ±2798.65%        1.12 μs        2.81 μs
10-string_match      653.29 K        1.53 μs  ±1934.94%        1.29 μs        3.37 μs

Comparison:
10-bin_match        1452.02 K
10-prepending        758.06 K - 1.92x slower +0.63 μs
10-appending         708.89 K - 2.05x slower +0.72 μs
10-nobbz             668.64 K - 2.17x slower +0.81 μs

Name                        ips        average  deviation         median         99th %
1000-bin_match          20.53 K       48.71 μs    ±18.48%          47 μs       73.92 μs
1000-nobz               14.48 K       69.08 μs     ±9.76%       66.72 μs       97.05 μs
1000-prepending          8.38 K      119.34 μs    ±21.28%      106.37 μs      209.73 μs
1000-string_match        6.81 K      146.85 μs    ±23.76%      142.24 μs      274.32 μs
1000-appending           3.15 K      317.80 μs    ±28.53%      297.69 μs      717.89 μs

Comparison:
1000-bin_match          20.53 K
1000-nobz               14.48 K - 1.42x slower +20.37 μs
1000-prepending          8.38 K - 2.45x slower +70.63 μs
1000-string_match        6.81 K - 3.01x slower +98.14 μs
1000-appending           3.15 K - 6.52x slower +269.09 μs

Name                          ips        average  deviation         median         99th %
100000-bin_match           158.51        6.31 ms    ±26.68%        5.63 ms       11.24 ms
100000-prepending           27.91       35.83 ms    ±21.76%       34.06 ms       77.84 ms
100000-string_match         27.51       36.34 ms    ±25.03%       34.85 ms       84.56 ms
100000-nobz                 27.33       36.59 ms    ±22.42%       34.72 ms       80.46 ms
100000-appending             0.27     3649.52 ms     ±4.37%     3649.52 ms     3762.41 ms

Comparison:
100000-bin_match           158.51
100000-prepending           27.91 - 5.68x slower +29.52 ms
100000-string_match         27.51 - 5.76x slower +30.04 ms
100000-nobz                 27.33 - 5.80x slower +30.28 ms
100000-appending             0.27 - 578.47x slower +3643.21 ms