Optimizing an Elixir puzzle: Rock Paper Scissors

Questions / Help
, ,
1

I worked out some code for a little interview-type puzzle question that requires one to implement code to solve a “Rock Paper Scissors” tournament. The task was to write a function that would accept a string of letters consisting of R, P, and S’s (denoting Rock, Paper, or Scissors) and return the letter of the winner or “None” if nobody won.

The rules are as follows:

  1. For each round, the 1st “player” (i.e. letter) competes with the 2nd, the 3rd with the 4th, the 5th with the 6th, and so on.
  2. If there’s an odd number of players, the odd-man-out advances to the next round
  3. If there’s a tie (e.g. RR), both are eliminated and do not advance to the next round.
  4. Keep advancing through rounds until there is one winner or return “None”.

I came up with code that meets the spec:

defmodule RockPaperScissors 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([], acc ++ [one_remaining])

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

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

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

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

end

For clarity, here are a few test cases:

assert RockPaperScissors.find_winner("R") == "R"
assert RockPaperScissors.find_winner("RR") == "None"
assert RockPaperScissors.find_winner("RRS") == "S"
assert RockPaperScissors.find_winner("RRRSRSPS") == "S"

This solution works, but I’m wondering about optimizations to this… appending to a list is expensive, but because the order of the players is important, prepending won’t work. So this ends up being O(n) complexity I think. I’m wondering if there are other ways to tackle this – using folding or captures or passing anonymous functions that would be more efficient so execution can happen more efficiently.

Any thoughts?

2

Looks like a nice puzzle. Do you have some example inputs and their expected outputs to test against?

Edit, ok I’m stupid and blind at the same time :wink:

3

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. :grin:

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. :slight_smile:

1 Like
4

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.

3 Likes
5

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
1 Like
6

I think this would be correct, and it gets rid of appending (but not of the String.codepoints call), and it’s fairly simple :

  defp battle(a,a), do: :none
  defp battle(:none, b), do: b
  defp battle({:some, "P"}, {:some, "R"}), do: {:some, "P"}
  defp battle({:some, "P"}, {:some, "S"}), do: {:some, "S"}
  defp battle({:some, "R"}, {:some, "S"}), do: {:some, "R"}
  defp battle(x,y) do
    # If the input is malformed we'll enter an infinite loop
    battle(y,x)
  end

  def tournament(acc, []), do: acc
  def tournament(acc, [a | []]), do: battle(acc, {:somme, a})
  def tournament(acc, [a |[ b | []]]), do: battle(acc, battle({:some, a}, {:some, b}))
  def tournament(acc, [a | [b | rest]]) do
    newacc = battle(acc, battle({:some, a}, {:some, b}))
    tournament(newacc, rest)
  end

def find_winner(lineup) do
  case tournament(:none, String.codepoints(lineup) do
         :none -> "None"
        {:some, ch} -> ch
end

Edit -> I had not read Nobbz solution, the general idea seems close, but matching directly on binaries is indeed better.

7

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
1 Like