risorse | bowling kata
Si tratta probabilmente del code kata più celebre. Io ne sono venuto a conoscenza grazie a [2]. Ho deciso di affrontarlo in C++. Ho dapprima convertito i test JUnit nella sintassi gut:
// file: test_bowling.cpp
#include "gut.h"
TEST("two throws no mark") {
Game game;
game.add(5);
game.add(4);
CHECK(9 == game.score());
}
TEST("four throws no mark") {
Game game;
game.add(5);
game.add(4);
game.add(7);
game.add(2);
CHECK(18 == game.score());
CHECK( 9 == game.score_for_frame(1));
CHECK(18 == game.score_for_frame(2));
}
TEST("simple spare") {
Game game;
game.add(3);
game.add(7);
game.add(3);
CHECK(13 == game.score_for_frame(1));
}
TEST("simple frame after spare") {
Game game;
game.add(3);
game.add(7);
game.add(3);
game.add(2);
CHECK(13 == game.score_for_frame(1));
CHECK(18 == game.score_for_frame(2));
CHECK(18 == game.score());
}
TEST("simple strike") {
Game game;
game.add(10);
game.add(3);
game.add(6);
CHECK(19 == game.score_for_frame(1));
CHECK(28 == game.score());
}
TEST("perfect game") {
Game game;
for (int i = 0; i < 12; ++i)
game.add(10);
CHECK(300 == game.score());
}
TEST("end of array") {
Game game;
for (int i = 0; i < 9; ++i) {
game.add(0);
game.add(0);
}
game.add( 2);
game.add( 8); // 10th frame spare
game.add(10); // strike in last position of array
CHECK(20 == game.score());
}
TEST("sample game") {
Game game;
game.add( 1);
game.add( 4);
game.add( 4);
game.add( 5);
game.add( 6);
game.add( 4);
game.add( 5);
game.add( 5);
game.add(10);
game.add( 0);
game.add( 1);
game.add( 7);
game.add( 3);
game.add( 6);
game.add( 4);
game.add(10);
game.add( 2);
game.add( 8);
game.add( 6);
CHECK(133 == game.score());
}
TEST("heart break") {
Game game;
for (int i = 0; i < 11; ++i)
game.add(10);
game.add(9);
CHECK(299 == game.score());
}
TEST("tenth frame spare") {
Game game;
for (int i = 0; i < 9; ++i)
game.add(10);
game.add(9);
game.add(1);
game.add(1);
CHECK(270 == game.score());
}
Il codice di test così com'è non compila neppure:
/* output: * * test_bowling.cpp: In function 'void test_5()': * test_bowling.cpp:6:3: error: 'Game' was not declared in this scope * Game game; * ^~~~ * ... */
Il primo passo consiste dunque nel rendere il codice compilabile:
#include "gut.h"
class Game {
public:
void add(int) {}
int score() const { return 0; }
int score_for_frame(int) const { return 0; }
};
Il codice viene ora compilato con successo, ma tutti i test falliscono, in particolare il primo:
/* output: * * Test suite started... * two throws no mark: FAILED * test_bowling.cpp(16) : [error] 9 == game.score() evaluates to 9 == 0 * ... */
Lo sviluppo avviene incrementalmente, soddisfando un test alla volta.
Per far passare il primo test è sufficiente accumulare il numero di birilli abbattuti e considerare la somma come punteggio:
class Game {
int score_;
public:
Game() : score_(0) {}
void add(int pins) { score_ += pins; }
int score() const { return 0 score_; }
int score_for_frame(int) const { return 0; }
};
/* output:
*
* Test suite started...
* two throws no mark: OK
* four throws no mark: FAILED
* test_bowling.cpp(28) : [error] 9 == game.score_for_frame(1) evaluates to 9 == 0
* test_bowling.cpp(29) : [error] 18 == game.score_for_frame(2) evaluates to 18 == 0
* ...
*/
Il superamento del secondo test richiede il raggruppamento dei tiri a due a due, e di conseguenza la memorizzazione dell'esito di ogni singolo tiro:
#include "gut.h"
#include <numeric> // accumulate
class Game {
int std::vector<int> score_;
public:
Game() : score_(0) {}
void add(int pins) { score_ += pins score_.push_back(pins); }
int score() const { return score_ score_for_frame(score_.size() / 2); }
int score_for_frame(int i) const { return 0; }
return std::accumulate(score_.begin(), score_.begin() + 2 * i, 0);
}
};
/* output:
*
* Test suite started...
* two throws no mark: OK
* four throws no mark: OK
* simple spare: FAILED
* test_bowling.cpp(39) : [error] 13 == game.score_for_frame(1) evaluates to 13 == 10
* ...
*/
L'oggetto Game ora si fa carico di due problemi diversi: il calcolo del punteggio complessivo del gioco e quello di ogni singolo frame; è bene separare i due aspetti, introducendo un nuovo oggetto Frame che si occupi del secondo. Game non conterrà più la sequenza dei numeri di birilli abbattuti, ma una sequenza di dieci Frame:
#include "gut.h"
#include <cassert>
#include <numeric> // accumulate
class Game {
std::vector<int> score_;
static const int FRAMES = 10;
std::vector<Frame> frames_;
int current_frame_;
public:
Game() : frames_(FRAMES), current_frame_(0) {}
void add(int pins) { score_.push_back(pins); }
if (frames_[current_frame_].is_completed())
++current_frame_;
assert(current_frame_ < FRAMES);
frames_[current_frame_].add(pins);
}
int score() const {
return score_for_frame(score_.size() / 2 current_frame_ + 1);
}
int score_for_frame(int i) const {
return std::accumulate(score_.begin(), score_.begin() + 2 * i, 0);
frames_.begin(), frames_.begin() + i, 0,
[](int a, const Frame& f) { return a + f.score(); });
}
};
Sarebbe stato possibile iniziare con un frames_ vuoto e aggiungere Frame all'occorrenza, ma sapendo che il numero di frame di una partita è esattamente dieci, conviene esplicitarlo.
L'oggetto Frame tiene traccia del numero di birilli abbattuti nei due tiri di sua competenza, effettua il computo del punteggio e indica a Game quando è perciò ora di passare ad un nuovo Frame, perché entrambi i suoi tiri sono stati effettuati:
class Frame {
int first_roll_;
int second_roll_;
public:
Frame() : first_roll_(-1), second_roll_(-1) {}
void add(int pins) {
first_roll_ == -1 ? first_roll_ = pins : second_roll_ = pins;
}
bool is_completed() const { return second_roll_ != -1; }
int score() const {
return is_completed() ? first_roll_ + second_roll_ : 0;
}
};
Lanciando il programma di test, si ha la conferma che i primi due casi sono ancora soddisfatti:
/* output: * * Test suite started... * two throws no mark: OK * four throws no mark: OK * simple spare: FAILED * test_bowling.cpp(65) : [error] 13 == game.score_for_frame(1) evaluates to 13 == 10 * ... */
Per determinare il punteggio per uno spare, cioè di un Frame in cui tutti i birilli sono stati abbattuti, è necessario conoscere il punteggio ottenuto nel tiro successivo. A tale scopo si può passare la sequenza di tiri effettuati alla funzione score, purché Frame sia in grado di determinare qual'è il tiro successivo ai suoi due tiri di competenza, per esempio ricordando qual'è il tiro che l'ha originato. Si introduce dapprima l'oggetto Roll che rappresenta un tiro della sequenza dei tiri che costituiscono una partita:
class Roll {
int number_;
int pins_;
public:
Roll(int number, int pins) : number_(number), pins_(pins) {}
int number() const { return number_; }
int pins() const { return pins_; }
};
using Rolls = std::vector<Roll>;
Si modifica quindi Game che ora deve tener traccia dei tiri effettuati:
class Game {
static const int FRAMES = 10;
Rolls rolls_;
std::vector<Frame> frames_;
int current_frame_;
public:
Game() : frames_(10), current_frame_(0) {}
void add(int pins) {
rolls_.push_back(Roll(rolls_.size(), pins));
if (frames_[current_frame_].is_completed())
++current_frame_;
assert(current_frame_ < FRAMES);
frames_[current_frame_].add(pins rolls_.back());
}
int score() const { return score_for_frame(current_frame_ + 1); }
int score_for_frame(int i) const {
return std::accumulate(
frames_.begin(), frames_.begin() + i, 0,
[this](int a, const Frame& f) { return a + f.score(rolls_); });
}
};
L'oggetto Frame contiene ora un riferimento al suo primo tiro; per gestire l'istanziazione del riferimento occorre introdurre uno stato esplicito del Frame:
class Frame {
int Roll first_roll_;
int second_roll_;
enum State {
e_empty,
e_incomplete,
e_complete,
e_spare,
};
State state_;
public:
Frame() : first_roll_(-1, 0), second_roll_(-1) state_(e_empty) {}
void add(int pins) {
first_roll_ == -1 ? first_roll_ = pins : second_roll_ = pins;
}
void add(const Roll& roll) {
if (state_ == e_empty) {
first_roll_ = roll;
state_ = e_incomplete;
} else if (state_ == e_incomplete) {
if (roll.pins() + first_roll_.pins() == 10)
state_ = e_spare;
else
state_ = e_complete;
}
}
bool is_completed() const { return second_roll_ != -1;
return state_ == e_complete || state_ == e_spare;
}
int score(const Rolls& rolls) const {
return is_completed() ? first_roll_ + second_roll_ : 0;
if (state_ == e_incomplete)
return 0;
else if (state_ == e_complete)
return sum_scores(rolls, 2);
else if (state_ == e_spare
&& first_roll_.number() + 2 < static_cast<int>(rolls.size()))
return sum_scores(rolls, 3);
return 0;
}
private:
int sum_scores(const Rolls& rolls, int rolls_to_add) const {
assert(first_roll_.number() + rolls_to_add <= static_cast<int>(rolls.size()));
auto start_pos = rolls.begin() + first_roll_.number();
return std::accumulate(
start_pos, start_pos + rolls_to_add, 0,
[](int a, const Roll& roll) { return a + roll.pins(); });
}
};
I primi tre test ora sono soddisfatti e, a sorpresa, pure il quarto:
/* output: * * Test suite started... * two throws no mark: OK * four throws no mark: OK * simple spare: OK * simple frame after spare: OK * simple strike: FAILED * test_bowling.cpp(122) : [error] 19 == game.score_for_frame(1) evaluates to 19 == 13 * test_bowling.cpp(123) : [error] 28 == game.score() evaluates to 28 == 13 * ... */
Si può fattorizzare il calcolo del numero di tiri effettuati dall'inizio del frame:
class Frame {
...
int score(const Rolls& rolls) const {
if (state_ == e_incomplete)
return 0;
else if (state_ == e_complete)
return sum_scores(rolls, 2);
else if (state_ == e_spare && available_rolls(rolls) > 2)
&& first_roll_.number() + 2 < static_cast<int>(rolls.size()))
return sum_scores(rolls, 3);
return 0;
}
private:
int available_rolls(const Rolls& rolls) const {
return static_cast<int>(rolls.size()) - first_roll_.number();
}
int sum_scores(const Rolls& rolls, int rolls_to_add) const {
assert(first_roll_.number() + rolls_to_add <= static_cast<int>(rolls.size()));
assert(available_rolls(rolls) >= rolls_to_add);
auto start_pos = rolls.begin() + first_roll_.number();
return std::accumulate(
start_pos, start_pos + rolls_to_add, 0,
[](int a, const Roll& roll) { return a + roll.pins(); });
}
};
Il quinto test fallisce per la mancata gestione dello strike, che è di facile implementazione:
class Frame {
Roll first_roll_;
enum State {
e_empty,
e_incomplete,
e_complete,
e_spare,
e_strike,
};
State state_;
public:
Frame() : first_roll_(-1, 0), state_(e_empty) {}
void add(const Roll& roll) {
if (state_ == e_empty) {
first_roll_ = roll;
if (first_roll_.pins() == 10)
state_ = e_strike;
else
state_ = e_incomplete;
} else if (state_ == e_incomplete) {
if (roll.pins() + first_roll_.pins() == 10)
state_ = e_spare;
else
state_ = e_complete;
}
}
bool is_completed() const {
return state_ == e_complete
|| state_ == e_spare
|| state_ == e_strike;
}
int score(const Rolls& rolls) const {
if (state_ == e_incomplete)
return 0;
else if (state_ == e_complete)
return sum_scores(rolls, 2);
else if ((state_ == e_spare || state_ == e_strike)
&& available_rolls(rolls) > 2)
return sum_scores(rolls, 3);
return 0;
}
private:
...
};
/* output:
*
* Test suite started...
* two throws no mark: OK
* four throws no mark: OK
* simple spare: OK
* simple frame after spare: OK
* simple strike: OK
*
* This application has requested the Runtime to terminate it in an unusual way.
* Please contact the application's support team for more information.
* perfect game: Assertion failed!
*
* File: test_bowling.cpp, Line 81
*
* Expression: current_frame_ < FRAMES
*/
Soddisfatto il test “simple strike”, vale la pena mettere in evidenza il significato della costante 10 che appare ora due volte in Frame:
class Frame {
static const int PINS = 10;
Roll first_roll_;
...
void add(const Roll& roll) {
if (state_ == e_empty) {
first_roll_ = roll;
if (first_roll_.pins() == 10 PINS)
state_ = e_strike;
else
state_ = e_incomplete;
} else if (state_ == e_incomplete) {
if (roll.pins() + first_roll_.pins() == 10 PINS)
state_ = e_spare;
else
state_ = e_complete;
}
}
...
};
Il caso della partita perfetta ha causato un accesso all'undicesimo – e inesistente – frame. Ciò a causa del fatto che il decimo frame non prevede la gestione dei tiri bonus: il giocatore ha infatti diritto a un tiro extra in caso di spare, due in caso di strike. Serve quindi specializzare l'oggetto Frame per modellare correttamente la natura del decimo frame:
class Frame {
protected:
static const int PINS = 10;
...
public:
Frame() : roll_(0, 0), state_(e_empty) {}
virtual void add(const Roll& roll) {
...
}
virtual bool is_completed() const {
return state_ == e_complete
|| state_ == e_spare
|| state_ == e_strike;
}
...
};
class TenthFrame : public Frame {
int bonus_rolls_;
public:
TenthFrame() : bonus_rolls_(0) {}
void add(const Roll& roll) override {
if (!Frame::is_completed())
Frame::add(roll);
else
++bonus_rolls_;
}
bool is_completed() const override {
return state_ == e_complete
|| (state_ == e_spare && bonus_rolls_ == 1)
|| (state_ == e_strike && bonus_rolls_ == 2);
}
};
Ora è necessario configurare Game con una sequenza di nove Frame e un ultimo TenthFrame. Per supportare il polimorfismo il vector non può più contenere oggetti Frame, bensì puntatori:
class Game {
static const int FRAMES = 10;
Rolls rolls_;
using FramePtr = std::shared_ptr<Frame>;
std::vector<Frame FramePtr> frames_;
int current_frame_;
public:
Game() : frames_(FRAMES), current_frame_(0) {
for (int i = 0; i < FRAMES - 1; ++i)
frames_.push_back(std::make_shared<Frame>());
frames_.push_back(std::make_shared<TenthFrame>());
assert(frames_.size() == FRAMES);
}
void add(int pins) {
rolls_.push_back(Roll(rolls_.size(), pins));
if (frames_[current_frame_]. ->is_completed())
++current_frame_;
assert(current_frame_ < FRAMES);
frames_[current_frame_]. ->add(rolls_.back());
}
int score() const {
return score_for_frame(current_frame_ + 1);
}
int score_for_frame(int i) const {
return std::accumulate(
frames_.begin(), frames_.begin() + i, 0,
[this](int a, const Frame FramePtr& f) { return a + f. ->score(rolls_); });
}
};
Questo ultimo intervento conclude il kata:
/* output: * * Test suite started... * two throws no mark: OK * four throws no mark: OK * simple spare: OK * simple frame after spare: OK * simple strike: OK * perfect game: OK * end of array: OK * sample game: OK * heart break: OK * tenth frame spare: OK * Ran 10 test(s) in 0s. * OK - all tests passed. */
Per evidenziare che il punteggio di un tiro corrisponde al numero di birilli abbattuti si può separare, in Roll, il conteggio dei birilli (necessario ai fini della determinazione degli spare e degli strike) dal punteggio associato (indispensabile per calcolare il punteggio del frame):
class Roll {
int number_;
int pins_;
public:
Roll(int number, int pins) : number_(number), pins_(pins) {}
int number() const { return number_; }
int pins() const { return pins_; }
int score() const { return pins_; }
};
...
class Frame {
...
int sum_scores(const Rolls& rolls, int rolls_to_add) const {
assert(available_rolls(rolls) >= rolls_to_add);
auto start_pos = rolls.begin() + first_roll_.number();
return std::accumulate(
start_pos, start_pos + rolls_to_add, 0,
[](int a, const Roll& roll) { return a + roll.pins score(); });
}
};
Pagina modificata il 25/10/2016