risorse | greed kata

Greed dice game Kata

Ho trovato un riferimento al kata in oggetto in un tweet di @xpmatteo, così ho deciso di affrontarlo in C++. Il gioco^[2] consiste nel lanciare cinque dadi e nel determinare il punteggio della configurazione ottenuta applicando ciclicamente le seguenti regole fino all'esaurimento dei dadi:

la tripletta ⚀⚀⚀ vale 1000 punti;
ogni altra tripletta vale 100 volte il punto dei dadi (⚁⚁⚁ vale 200 punti);
un singolo ⚀ vale 100 punti;
un singolo ⚄ vale 50 punti;
qualunque altra combinazione non dà diritto ad alcun punto;
una volta applicata una regola, i dadi coinvolti vengono scartati.

1000 punti per tre “uno”

Si inizia con un test che verifica la corretta applicazione della prima regola in elenco:

[file test_greed_kata.cpp]

#include "gut.h"

TEST("a set of three 1's is worth 1000 points") {
  CHECK(score({1, 1, 1}) == 1000);
}

Il compilatore termina con errore, mancando la definizione della funzione score; l'implementazione minima che soddisfa il test è tuttavia banale:

#include "gut.h"

int score(const std::vector<int>& /*roll*/) {
  return 1000;
}

TEST("a set of three 1's is worth 1000 points") {
  CHECK(score({1, 1, 1}) == 1000);
}

/* output:
 *
 * Test suite started...
 * a set of three 1's is worth 1000 points: OK
 * Ran 1 test(s) in 0s.
 * OK - all tests passed.
 */

Refactoring #1

Il parametro roll della funzione score è di tipo troppo generico, meglio circostanziare il contesto:

#include "gut.h"

using Die = int;
using Roll = std::vector<Die>;

int score(const std::vector<int>Roll& /*roll*/) {
  return 1000;
}

TEST("a set of three 1's is worth 1000 points") {
  CHECK(score({1, 1, 1}) == 1000);
}

100 punti volte il valore del dado per le altre triplette

Segue il test dedicato alle altre triplette:

...

TEST("a set of 3 of any other number is worth 100 * that number") {
  CHECK(score({2, 2, 2}) == 200);
  CHECK(score({3, 3, 3}) == 300);
  CHECK(score({4, 4, 4}) == 400);
  CHECK(score({5, 5, 5}) == 500);
  CHECK(score({6, 6, 6}) == 600);
}

/* output
 *
 * Test suite started...
 * a set of three 1's is worth 1000 points: OK
 * a set of 3 of any other number is worth 100 * that number: FAILED
 *  test_greed.cpp(15) : [error] score({2, 2, 2}) == 200 evaluates to 1000 == 200
 *  test_greed.cpp(16) : [error] score({3, 3, 3}) == 300 evaluates to 1000 == 300
 *  test_greed.cpp(17) : [error] score({4, 4, 4}) == 400 evaluates to 1000 == 400
 *  test_greed.cpp(18) : [error] score({5, 5, 5}) == 500 evaluates to 1000 == 500
 *  test_greed.cpp(19) : [error] score({6, 6, 6}) == 600 evaluates to 1000 == 600
 * Ran 2 test(s) in 0s.
 * FAILED - 5 failure(s) in 1 test(s).
 */

Modificare la funzione score per far passare anche questo secondo test non è complicato:

...

int score(const Roll& /*roll*/) {
  Die first_die = roll[0];
  if (first_die == 1)
    return 1000;
  else
    return first_die * 100;
}
...

/* output:
 *
 * Test suite started...
 * a set of three 1's is worth 1000 points: OK
 * a set of 3 of any other number is worth 100 * that number: OK
 * Ran 2 test(s) in 0s.
 * OK - all tests passed.
 */

100 punti per un singolo “uno”

Un nuovo test controlla il punteggio assegnato al dado 1 in virtù della terza regola:

...

TEST("a single 1 is worth 100 points") {
  CHECK(score({1}) == 100);
}
...

/* output:
 *
 * ...
 * a single 1 is worth 100 points: FAILED
 *  test_greed.cpp(27) : [error] score({1}) == 100 evaluates to 1000 == 100
 * Ran 3 test(s) in 0s.
 * FAILED - 1 failure(s) in 1 test(s).
 */

Viene di conseguenza modificata la funzione score, ancora una volta senza troppe difficoltà:

...

int score(const Roll& roll) {
  Die first_die = roll[0];
  if (first_die == 1)
  if (roll == Roll({1, 1, 1}))
    return 1000;
  else
    return first_die * 100;
}
...

/* output:
 *
 * ...
 * a single 1 is worth 100 points: OK
 * Ran 3 test(s) in 0s.
 * OK - all tests passed.
 */

Refactoring #2

Essendo first_die riferito una volta sola, il riferimento locale può essere eliminato:

...

int score(const Roll& roll) {
  Die first_die = roll[0];
  if (roll == Roll({1, 1, 1}))
    return 1000;
  else
    return first_dieroll[0] * 100;
}
...

50 punti per un singolo “cinque”

Segue il codice di test dedicato alla quarta regola:

...

TEST("a single 5 is worth 50 points") {
  CHECK(score({5}) == 50);
}
...

/* output:
 *
 * ...
 * a single 5 is worth 50 points: FAILED
 *  test_greed.cpp(30) : [error] score({5}) == 50 evaluates to 500 == 50
 * Ran 4 test(s) in 0s.
 * FAILED - 1 failure(s) in 1 test(s).
 */

Per far passare anche questo test è sufficiente aggiungere la nuova casistica in score:

...

int score(const Roll& roll) {
  if (roll == Roll({1, 1, 1}))
    return 1000;
  else if (roll == Roll({5}))
    return 50;
  else
    return roll[0] * 100;
}
...

/* output:
 *
 * ...
 * a single 5 is worth 50 points: OK
 * Ran 4 test(s) in 0s.
 * OK - all tests passed.
 */

Refactoring #3

La presenza di molteplici clausole if/else sta minando la qualità dell'implementazione della funzione score; conviene cambiare approccio. Una possibilità è distinguere la definizione delle regole del gioco dalla loro applicazione. A tal scopo si introduce l'oggetto Rule, che verifica se una data configurazione di dadi corrisponde ad una sequenza prefissata, e fornisce il punteggio ad essa associato; la funzione score si limita così a selezionare ed applicare la regola più adatta alla configurazione di dadi corrente, rispettando ovviamente l'ordine richiesto:

#include "gut.h"
#include <algorithm>

using Die = int;
using Roll = std::vector<Die>;

class Rule {
  const Roll roll_;
  const int score_;
public:
  Rule(const Roll& roll, int score) : roll_(roll), score_(score) {}
  bool matches(const Roll& roll) const {
    return std::equal(roll_.begin(), roll_.end(), roll.begin());
  }
  int score() const { return score_; }
};
...

Le configurazioni che realizzano un punteggio non nullo sono, nell'ordine di applicazione stabilito dalle regole del gioco:

...

static Rule greed_rules[] = {
  Rule({1, 1, 1}, 1000),
  Rule({2, 2, 2},  200),
  Rule({3, 3, 3},  300),
  Rule({4, 4, 4},  400),
  Rule({5, 5, 5},  500),
  Rule({6, 6, 6},  600),
  Rule({1,     },  100),
  Rule({5,     },   50),
};
...

Come anticipato, la funzione score seleziona la prima regola applicabile, e ritorna il punteggio associato; nel caso non sia stata possibile applicare alcuna regola, il punteggio della configurazione è nullo:

...
int score(const Roll& roll) {
  if (roll == Roll({1, 1, 1}))
    return 1000;
  else
    return roll[0] * 100;
  for (auto rule : greed_rules)
    if (rule.matches(roll))
      return rule.score();
  return 0;
}
...

/* output:
 *
 * Test suite started...
 * a set of three 1's is worth 1000 points: OK
 * a set of 3 of any other number is worth 100 * that number: OK
 * a single 1 is worth 100 points: OK
 * a single 5 is worth 50 points: OK
 * Ran 4 test(s) in 0s.
 * OK - all tests passed.
 */

0 punti per tutte le altre combinazioni

Tutti i test predisposti fino ad ora sono soddisfatti. Resta da verificare che alle restanti combinazioni venga effettivamente attribuito il punteggio nullo:

...

TEST("any other die or combination is worth 0 points") {
  CHECK(score({2         }) == 0);
  CHECK(score({3         }) == 0);
  CHECK(score({4         }) == 0);
  CHECK(score({6         }) == 0);
  CHECK(score({2, 2      }) == 0);
  CHECK(score({2, 3      }) == 0);
  CHECK(score({2, 2, 3   }) == 0);
  CHECK(score({2, 3, 4, 6}) == 0);
}

/* output:
 *
 * ...
 * any other die or combination is worth 0 points: OK
 * Ran 5 test(s) in 0s.
 * OK - all tests passed.
 */

Applicazione ciclica delle regole /1

score si limita ad attivare la prima regola pertinente, ma in realtà deve applicarle in sequenza fino all'esaurimento dei dadi. Un nuovo test evidenzia questa non-conformità:

...

TEST("after applying a rule, dice involved in it are removed from the roll") {
  CHECK(score({5, 5, 5, 5, 3}) == 550);
  CHECK(score({2, 3, 4, 6, 2}) ==   0);
  CHECK(score({1, 5, 1, 2, 4}) == 250);
  CHECK(score({5, 5, 5, 5, 5}) == 600);
}

/* output:
 *
 * ...
 * after applying a rule, dice involved in it are removed from the roll: FAILED
 *  test_greed.cpp(69) : [error] score({5, 5, 5, 5, 3}) == 550 evaluates to 500 == 550
 *  test_greed.cpp(71) : [error] score({1, 5, 1, 2, 4}) == 250 evaluates to 100 == 250
 *  test_greed.cpp(72) : [error] score({5, 5, 5, 5, 5}) == 600 evaluates to 500 == 600
 * Ran 6 test(s) in 0s.
 * FAILED - 3 failure(s) in 1 test(s).
 */

Il numero di dadi da eliminare dalla configurazione in esame coincide con la lunghezza della configurazione che caratterizza l'oggetto Rule, che per questa ragione la pubblica:

class Rule {
...

  int score() const { return score_; }
  int length() const { return roll_.size(); }
};

L'applicazione ciclica delle regole si ottiene introducendo una ricorsione in score:

...

int score(const Roll& roll) {
  if (roll.empty()) // avoid infinite recursion
    return 0;
  for (auto rule : greed_rules)
    if (rule.matches(roll))
      return rule.score()
        // calculate the score for the remaining dice
        + score(Roll(roll.begin() + rule.length(), roll.end()));
  return 0;
}

/* output:
 *
 * ...
 * after applying a rule, dice involved in it are removed from the roll: OK
 * Ran 6 test(s) in 0s.
 * OK - all tests passed.
 */

Refactoring #4

Il secondo commento della funzione score è una chiara indicazione che si può fare meglio:

...

Roll drop(const Roll& roll, int count) {
  return Roll(roll.begin() + count, roll.end());
}

int score(const Roll& roll) {
  if (roll.empty()) // avoid infinite recursion
    return 0;
  for (auto rule : greed_rules)
    if (rule.matches(roll))
      return rule.score() + score(drop(roll, rule.length()));
        // calculate the score for the remaining dice
        + score(Roll(roll.begin() + rule.length(), roll.end()));
  return 0;
}

Applicazione ciclica delle regole /2

Il ciclo realizzato dalla funzione score non soddisfa pienamente i requisiti iniziali, poiché si arresta alla prima regola disattesa anziché proseguire fino all'esaurimento dei dadi, come dimostra il seguente test:

...

TEST("rules are applied until all dice are evaluated") {
  CHECK(score({1, 2, 3, 4, 5}) == 150);
  CHECK(score({2, 3, 3, 3, 4}) == 300);
  CHECK(score({2, 2, 2, 3, 5}) == 250);
}

/* output:
 *
 * ...
 * rules are applied until all dice are evaluated: FAILED
 *  test_greed.cpp(81) : [error] score({1, 2, 3, 4, 5}) == 150 evaluates to 100 == 150
 *  test_greed.cpp(82) : [error] score({2, 3, 3, 3, 4}) == 300 evaluates to 0 == 300
 *  test_greed.cpp(83) : [error] score({2, 2, 2, 3, 5}) == 250 evaluates to 200 == 250
 * Ran 7 test(s) in 0s.
 * FAILED - 3 failure(s) in 1 test(s).
 */

La soluzione al problema consiste nell'introdurre una fallback-rule che, in caso di mancata applicazione delle regole, prosegua la valutazione scartando il primo dado (senza modificare il punteggio):

...

int score(const Roll& roll) {
  if (roll.empty()) // avoid infinite recursion
    return 0;
  for (auto rule : greed_rules)
    if (rule.matches(roll))
      return rule.score() + score(drop(roll, rule.length()));
  return 0score(drop(roll, 1));
}

/* output:
 *
 * ...
 * rules are applied until all dice are evaluated: OK
 * Ran 7 test(s) in 0s.
 * OK - all tests passed.
 */

Refactoring #5

I due return della funzione score hanno forma molto simile, e viene naturale chiedersi se è possibile eliminarne uno. La regola di fallback implicitamente implementata dal secondo return potrebbe essere esplicitata sotto forma di Rule? Dopotutto, sarebbe sufficiente definire una nuova regola il cui metodo match torna sempre true, il cui punteggio è nullo, e ha length pari a 1. D'altra parte, il C++ non consente di memorizzare oggetti di tipo diversi all'interno di un array; occorre allora separare le due responsabilità assegnate alla classe Rule: la verifica dell'applicabilità della regola viene ora attribuito ad un nuovo oggetto, denominato Match, mentre Rule conserva il punteggio associato alla regola:

...

class Match {
public:
  virtual ~Match() = default;
  virtual bool matches(const Roll& roll) const = 0;
  virtual int length() const = 0;
};

class Sequence : public Match {
  const Roll roll_;
public:
  Sequence(const Roll& roll) : roll_(roll) {}
  bool matches(const Roll& roll) const override {
    return std::equal(roll_.begin(), roll_.end(), roll.begin());
  }
  int length() const override { return roll_.size(); }
};

class Rule {
  const Roll roll_;
  const std::shared_ptr<const Match> match_;
  const int score_;
public:
  Rule(const Roll& roll, int score) : roll_(roll), score_(score) {}
  Rule(const Match* match, int score) : match_(match), score_(score) {}
  bool matches(const Roll& roll) const { return match_->matches(roll); }
    return std::equal(roll_.begin(), roll_.end(), roll.begin());
  }
  int score() const { return score_; }
  int length() const { return roll_.size()match_->length(); }
};
...

static Rule greed_rules[] = {
  Rule(new Sequence({1, 1, 1}), 1000),
  Rule(new Sequence({2, 2, 2}),  200),
  Rule(new Sequence({3, 3, 3}),  300),
  Rule(new Sequence({4, 4, 4}),  400),
  Rule(new Sequence({5, 5, 5}),  500),
  Rule(new Sequence({6, 6, 6}),  600),
  Rule(new Sequence({1,     }),  100),
  Rule(new Sequence({5,     }),   50),
};
...

A questo punto è possibile implementare la fallback-rule, introducendo un nuovo oggetto Match dalle caratteristiche già discusse:

...

class Fallback : public Match {
public:
  bool matches(const Roll& /*roll*/) const override { return true; }
  int length() const override { return 1; }
};
...

static Rule greed_rules[] = {
  ...
  Rule(new Sequence({1,     }),  100),
  Rule(new Sequence({5,     }),   50),
  Rule(new Fallback(),             0),
};

La presenza della nuova regola rende superfluo il return finale in score, dato che ad ogni ciclo una regola applicabile sarà sempre disponibile:

#include "gut.h"
#include <algorithm>
#include <cassert>
...

int score(const Roll& roll) {
  if (roll.empty()) // avoid infinite recursion
    return 0;
  for (auto rule : greed_rules)
    if (rule.matches(roll))
      return rule.score() + score(drop(roll, rule.length()));
  return score(drop(roll, 1));
  auto target_rule = std::find_if(
    std::begin(greed_rules), std::end(greed_rules),
    [&roll](const Rule& rule) { return rule.matches(roll); });
  assert(target_rule != std::end(greed_rules));
  return target_rule->score() + score(drop(roll, target_rule->length()));
}
...

/* output:
 *
 * Test suite started...
 * a set of three 1's is worth 1000 points: OK
 * a set of 3 of any other number is worth 100 * that number: OK
 * a single 1 is worth 100 points: OK
 * a single 5 is worth 50 points: OK
 * any other die or combination is worth 0 points: OK
 * after applying a rule, dice involved in it are removed from the roll: OK
 * rules are applied until all dice are evaluated: OK
 * Ran 7 test(s) in 0s.
 * OK - all tests passed.
 */

L'assert sull'effettiva disponibilità di una regola applicabile è d'obbligo!

L'ordine dei dadi non conta

Il codice sviluppato presuppone che i dadi si presentino sempre in ordine crescente, ma questo non è un prerequisito; un test per verificare che il calcolo del punteggio funziona anche in assenza di questa condizione è il seguente:

...

TEST("dice order does not matter") {
  CHECK(score({1, 1, 5, 1, 1}) == 1150);
  CHECK(score({3, 4, 5, 3, 3}) ==  350);
  CHECK(score({5, 5, 3, 5, 5}) ==  550);
  CHECK(score({3, 4, 3, 5, 3}) ==  350);
}

/* output:
 *
 * ...
 * dice order does not matter: FAILED
 *  test_greed.cpp(112) : [error] score({1, 1, 5, 1, 1}) == 1150 evaluates to 450 == 1150
 *  test_greed.cpp(113) : [error] score({3, 4, 5, 3, 3}) == 350 evaluates to 50 == 350
 *  test_greed.cpp(114) : [error] score({5, 5, 3, 5, 5}) == 550 evaluates to 200 == 550
 *  test_greed.cpp(115) : [error] score({3, 4, 3, 5, 3}) == 350 evaluates to 50 == 350
 * Ran 8 test(s) in 0s.
 * FAILED - 4 failure(s) in 1 test(s).
 */

Per ovviare a questa mancanza si nasconde l'attuale funzione score e si utilizza la sua firma per definire una funzione di comodo che ha l'unico scopo di ordinare la sequenza dei dadi prima di sottoporla all'attuale implementazione:

...

int sorted_roll_score(const Roll& roll) {
  if (roll.empty()) // avoid infinite recursion
    ...
  return target_rule->score()
    + sorted_roll_score(drop(roll, target_rule->length()));
}

int score(const Roll& roll) {
  Roll sorted_roll = roll;
  std::sort(sorted_roll.begin (), sorted_roll.end());
  return sorted_roll_score(sorted_roll);
}
...

/* output:
 *
 * ...
 * dice order does not matter: OK
 * Ran 8 test(s) in 0s.
 * OK - all tests passed.
 */

Codice sorgente

test_greed.cpp

Riferimenti

Vaccari, M. "Greed and Simple Design". Matteo Vaccari Blog. <http://matteo.vaccari.name/blog/archives/709>. Visitato il 04 agosto 2016.
"Farkle". Wikipedia. <https://en.wikipedia.org/wiki/Farkle>. Visitato il 04 agosto 2016.

Pagina modificata il 05/08/2016