Further minimization on RPSSL resolution logic

Further minimization on RPSSL resolution logic#

We can further reduce the number of tests 🤓.

By:

  1. only thinking in forwards steps on the resolution circle

  2. changing the layout of the shapes so that we win against the two shapes in front (and lose against two behind)

Describing the difference only as positive numbers#

There is a “mathematical world” where the following number pairs have the same meaning:

  • -4 and 1

  • -2 and 3

  • -1 and 4

If we operate in this world, we can describe our solution in a shorter way.

🤔 Question to ponder

Which mathematical operator could be helpful to land in this mathematical world described above?

Hint: Check this section.

This operation basically gets rid of the negative steps and converts them to positive steps on a circle.

We get:

p2-p1 mod 5

p1 …

0

tie

1 or 3

wins

2 or 4

loses

This table is shorter than the rock paper scissors table and much shorter than the rock paper scissors lizard Spock table.

This table can be implemented as an if-if else-else statement or switch using the following Boolean expressions in order after calculating diff = (p2 - p1) mod 5.

  1. diff == 0

  2. diff == 1 || diff == 3

So we have three comparisons in total.

Moving shapes in the circle to get rid of holes#

🤔 Question to ponder

We need three comparisons to check which player wins. We would only need two comparisons if the condition for winning would be 1 or 2 instead of 1 or 3, because then we only have to test for diff <= 2.

Can we change the id of the shapes accordingly so that we get the described behavior?

The resolution table is symmetrical. Every shape wins against two other shapes and loses against two others. So it should be possible to put the shapes that one shape wins/loses against in front:

        flowchart LR

a --> b
b --> c
c --> d
d --> e
e --> a

a --> c
b --> d
c --> e
d --> a
e --> b

In the graph above, a wins against b and c; and loses against d and e. Every node wins against two in front and loses against two behind.

So if we begin with 🪨 as a, then:

  1. b and c must be 🦎 and ️✂️.

  2. At the same time b must win against c, so b must be ✂️ and c 🦎.

  3. If b is ✂️, then d must be 🗒️.

  4. Finally e gets the remaining 🖖

        flowchart LR

a[🪨]
b[🦎]
c[✂️]
d[🗒️]
e[🖖]

a --> b
b --> c
c --> d
d --> e
e --> a

a --> c
b --> d
c --> e
d --> a
e --> b

Ultimately we get the following table.

p2-p1 mod 5

p1 …

0

tie

<= 2 (1 or 2)

wins

else (3 or 4)

loses

Activity 53 (Modulo in C (and Python))

Calculate the following of the operations on paper, C (and Python).

  1. \(6\mod{5}\)

  2. \(2\mod{5}\)

  3. \(-4\mod{5}\)

  4. \(-2\mod{5}\)

  5. \(2\mod{-5}\)

You can use the following template:

#include <stdio.h>
int main() { printf("%i", 5); }

Tip: If you have, use cling and ipython. By using them you don’t have to write and whole program to evaluate statements.

Modulo with negative operands#

Modulo operator is implemented using the % operator in C. However it behaves differently than you would expect as you have seen in Activity 53.

C and Python make sure that the following equation holds for a dividend d and divisor v, where both variables are integers.

\[ \frac{d}{v} \cdot v + (d\mod{v}) = d \]

This equation corresponds to:

\[ \mathrm{quotient} \cdot \mathrm{divisor} + \mathrm{remainder} = \mathrm{divisor} \]

So if we divide \(d\) with \(v\) using integer division, we should be able to get the original dividend using the remainder \(d\mod{v}\) and divisor \(d\).

The integer divisions used by programming languages can be different, which calls for different kinds of modulo to fulfill the equation above.

Python’s …

… integer division uses floored division \(q = \left\lfloor\frac{a}{n}\right\rfloor\). So, if the quotient is negative the result is rounded towards negative infinity.

https://upload.wikimedia.org/wikipedia/commons/c/c4/Divmod_floored.svg

Fig. 25 Quotient and remainder as functions of dividend, using floored division.
CC BY-SA 3.0. By Mathnerd314159. Source: Wikimedia Commons#

C’s …

… integer division uses truncated division \(q = \operatorname{trunc}\left(\frac{a}{n}\right)\). So, if the quotient is negative, the result is rounded towards 0.

https://upload.wikimedia.org/wikipedia/commons/c/c3/Divmod_truncated.svg

Fig. 26 Quotient and remainder as functions of dividend, using truncated division.
CC BY-SA 3.0. By Mathnerd314159. Source: Wikimedia Commons#

Python’s approach seems to me more intuitive compared to C’s, as

  1. We stay always in the same (positive or negative) world if the divisor is fixed.

  2. The negative and positive intervals of the dividend are continuous. There is not break like in C.

C’s approach probably stems from the fact that many processors support truncated integer division as default.

Working with truncated division to solve the problem#

C’s modulo will give negative results if p2-p1 is negative, however we want always positive values. Additionally -4 should correspond to 1. We have two options:

  1. Fixing the remainder values for negative differences by adding 5 to the result only if the quotient is 5.

  2. We know that the minimum value we may get is -4, so we can shift our difference 5 to the right, so the minimum value we may get will be 1.

The second one requires only a single operation, where the first two. Let us proceed with the second:

(p2-p1+5) mod 5

p1 …

0

tie

<= 2 (1 or 2)

wins

else (3 or 4)

loses

🎉 This was a long improvement process, in which we minimized our problem to:

  • one or two additions

  • a modulo (integer division)

  • two comparisons

Now let us leverage this in our code:

Activity 54 (Game resolution logic implementation)

Implement the modulo logic above to the template below, so you get the output below.

#include <stdio.h>
enum { ROCK, LIZARD, SCISSORS, PAPER, SPOCK, SHAPE_COUNT } player1, player2;

const char *SHAPE_STRINGS[] = {"🪨", "🦎", "️✂️", "🗒️", "🖖"};

int main() {

  for (size_t player1 = ROCK; player1 < SHAPE_COUNT; ++player1) {
    for (size_t player2 = ROCK; player2 < SHAPE_COUNT; ++player2) {
      printf("If player1: %s  and player2: %s  => ", SHAPE_STRINGS[player1],
             SHAPE_STRINGS[player2]);
      // YOUR CODE HERE
    }
    puts("");
  }
}


If player1: 🪨  and player2: 🪨  => Tie.
If player1: 🪨  and player2: 🦎  => Player1 wins.
If player1: 🪨  and player2: ️✂️  => Player1 wins.
If player1: 🪨  and player2: 🗒️  => Player1 looses.
If player1: 🪨  and player2: 🖖  => Player1 looses.

If player1: 🦎  and player2: 🪨  => Player1 looses.
If player1: 🦎  and player2: 🦎  => Tie.
If player1: 🦎  and player2: ️✂️  => Player1 wins.
If player1: 🦎  and player2: 🗒️  => Player1 wins.
If player1: 🦎  and player2: 🖖  => Player1 looses.

If player1: ️✂️  and player2: 🪨  => Player1 looses.
If player1: ️✂️  and player2: 🦎  => Player1 looses.
If player1: ️✂️  and player2: ️✂️  => Tie.
If player1: ️✂️  and player2: 🗒️  => Player1 wins.
If player1: ️✂️  and player2: 🖖  => Player1 wins.

If player1: 🗒️  and player2: 🪨  => Player1 wins.
If player1: 🗒️  and player2: 🦎  => Player1 looses.
If player1: 🗒️  and player2: ️✂️  => Player1 looses.
If player1: 🗒️  and player2: 🗒️  => Tie.
If player1: 🗒️  and player2: 🖖  => Player1 wins.

If player1: 🖖  and player2: 🪨  => Player1 wins.
If player1: 🖖  and player2: 🦎  => Player1 wins.
If player1: 🖖  and player2: ️✂️  => Player1 looses.
If player1: 🖖  and player2: 🗒️  => Player1 looses.
If player1: 🖖  and player2: 🖖  => Tie.

Appendix#

Contents