## Anti-FOR tips from the Yahtzee Kata

Again on the Kata Yahtzee, that I blogged about some time ago.

If you have not solved the kata at least once, please stop reading this! Get back when you have.

* *

*

Good to see you again! Now that you solved it, you probably know that the naive solution takes many “for” loops. Let *D* be the player dice, represented as *an array of die results*, e.g., D=(1,6,1,6,4). The naive rules for sixes would be

```
``` def sixes_score
sum = 0
for d in D
if d == 6
sum += 6
end
end
return sum
end

This solution involves *searching* for sixes and adding up. Why do we need to search? We need to search because there are many different D that are worth exactly the same for the sixes rule. For instance, both D=(1,2,3,6,6) and D=(6,6,1,2,3) are worth 12.

One way to avoid the search is to represent the die rolls in a *canonical form*, that is a form where two equivalent results are represented in the same way. The obvious way to obtain a canonical form is to sort D; but in this particular case, we’d still need to search for sixes.

An alternative canonical form would be to count how many results we have: for instance D=(1,1,3,6,6) would be represented as C = [2,0,1,0,0,2], that is “two times 1, one time 3, two times 6.” The rule for sixes becomes

```
``` def sixes_score
return 6*C[6]
end

(Note: we take C to be a 1-based array. It’s easy to make one in Java or Ruby: use an array of length 7 and ignore index 0.)

The straight rules are also easy, because C is a canonical form for them as well:

```
``` def small_straight_score
if C == [1,1,1,1,1,0] then 15 else 0
end
def large_straight_score
if C == [0,1,1,1,1,1] then 20 else 0
end

Now, how does this help us with the other rules? Take the Yahtzee rule, for instance. The naive solution

```
``` def really_naive_yahtzee_score
for (i=1; i < 5 ; i++)
return 0 if D[i-1] ≠ D[i]
end
return 50
end

can be slightly improved by

```
``` def slighly_less_naive_yahtzee_score
for d in D
return 0 if D[0] ≠ d
end
return 50
end

Using C does not improve much as we still have to search:

```
``` def still_naive_yahtzee_score
for c in C
return 50 if c == 5
end
return 0
end

This is because there are many different C that are equivalent with respect to the Yahtzee rule: for instance C = [0,0,0,5,0] and C=[0,5,0,0,0]. Can we apply the same reasoning and find another canonical representation? Why yes! If we sort C = [0,0,0,5,0] to obtain S = {5,0,0,0,0} the yahtzee rule becomes very simple:

```
``` def cool_yahtzee_score
if S[0] == 5 then 50 else 0
end

Many other rules are immediately codified this way:

```
``` def four_of_a_kind_score
if S[0] ≥ 4 then sum(D) else 0
end
def full_house_score
if S[0] == 3 ∧ S[1] == 2 then 25 else 0
end

The pair rule is a bit more challenging: it is not part of the “official” rules but it make for interesting coding :o). The rule is “Pair: The player scores the sum of the two highest matching dice. For example, 3, 3, 3, 4, 4 gives 8.” Using C requires searching. Using S would be no good (can you see why?)

Again: can you find a canonical representation for the pair rule so that we don’t have to search? Hint: remove “noise” to reveal information.

### Conclusion

It’s important to find ways to remove IFs. It’s also important to find ways to remove FORs! I blogged about this before.

We used two ways to remove FORs here:

- Use canonical representations, like C and S;
- Hide them in well-known functions like sort and sum.

Our search for canonical forms helps us develop a *language* for reasoning effectively about our problem domain. In fact we are building a little *theory*.