(further-minimization-ideas-on-rpsls-resolution-logic)=
# Further minimization on RPSSL resolution logic

:::{dropdown} 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.

:::{card} 🤔 Question to ponder
Which mathematical operator could be helpful to land in this mathematical world described above?

Hint: Check [this section](project:#math-expressions).
:::

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

We get:

:::{list-table}
:width: 20%
:header-rows: 1
* - 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](project:#rps-long-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`
1. `diff == 1 || diff == 3`

So we have three comparisons in total.

## Moving shapes in the circle to get rid of holes

:::{card} 🤔 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](project:#rpsls-resolution-diagram) 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:

:::{mermaid}
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 🖖

:::{mermaid}
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.

:::{list-table}
:width: 20%
:header-rows: 1
* - p2-p1 mod 5
  - p1 ...
* - 0
  - tie
* - <= 2 (1 or 2)
  - wins
* - else (3 or 4)
  - loses
:::

:::{activity} Modulo in C (and Python)
:label: modulo-in-c-and-python
Calculate the following of the operations on paper, C (and Python).
1. $6\mod{5}$
1. $2\mod{5}$
1. $-4\mod{5}$
1. $-2\mod{5}$
1. $2\mod{-5}$

You can use the following template:
```c
#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 {numref}`modulo-in-c-and-python`.

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.


:::::{grid} 2
::::{grid-item-card} 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.
:::{commons-figure} https://commons.wikimedia.org/wiki/File:Divmod_floored.svg
:name: floored-division
<span style="color:red">Quotient</span> and <span style="color:green">remainder</span> as functions of dividend, using *floored* division.
:::
::::
::::{grid-item-card} 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.
:::{commons-figure} https://commons.wikimedia.org/wiki/File:Divmod_truncated.svg
:name: truncated-division
<span style="color:red">Quotient</span> and <span style="color:green">remainder</span> as functions of dividend, using *truncated* division.
:::
::::
:::::

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

:::{list-table}
:width: 25%
:header-rows: 1
* - (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} Game resolution logic implementation
Implement the modulo logic above to the template below, so you get the output below.
```{literalinclude} ../code/masked/rpssl-resolution-logic-modulo.c
:language: c
```
```{literalinclude} ../code/rpssl-resolution-logic-modulo.txt
:language: text
```
:::

## Appendix

- [Variants of modulo](https://en.wikipedia.org/wiki/Modulo#Variants_of_the_definition)