Or to better put the question, who is the winner after the rotation?
To make things a bit more interesting, both the board size and the winning sequence length are variable. They should be somewhere in the [3..50] range.
We'll have as input the board size, the winning length, and the current game configuration. And we have to give as output the name of the winner (Blue or Red) or, in case of a tie, tell if this happens because both are winner (Both) or no one (Neither).
The resulting code is not excessively complicated, but it is longish and require some carefulness. Here I present my C++11 solution, with a few of the test cases that helped me driving the development. I put the full source code on github.
Trying to keep my code understandable, I have organized it in a class. Its public interface is quite innocent. Just a constructor and a method that gives the winner name(s):
class Rotator
{
private:
// ...
public:
Rotator(unsigned size, unsigned len, const Input& input);
std::string winner();
};
The first two constructor parameters shouldn't require any explanation, the third one is the representation of the board, before our cheating attempt. "Input" is an alias for the STL string vector.Given this interface, I can start writing a few test cases.
TEST(Rotate, TestBad)
{
const unsigned size = 7;
const unsigned len = 3;
Input input {
".......",
".......",
".......",
"...R...",
"...BB..",
"..BRB..",
".RRBR." // too short!
};
ASSERT_THROW(Rotator r(size, len, input), std::logic_error);
}
TestBad was not required by the problem. But what if the input is corrupted? I couldn't feel right if I didn't add I bit of robustness to my solution. I want the Rotator constructor to throw a logic_error standard exception when something goes wrong.TEST(Rotate, Test1)
{
const unsigned size = 7;
const unsigned len = 3;
Input input {
".......",
".......",
".......",
"...R...",
"...BB..",
"..BRB..",
".RRBR.."
};
Rotator r(size, len, input);
ASSERT_EQ(results[Neither], r.winner());
}
After rotation, there are not enough aligned R or B. We are in a no-winner case.In the second test case both players win:
TEST(Rotate, Test2)
{
const unsigned size = 6;
const unsigned len = 4;
Input input {
"......",
"......",
".R...R",
".R..BB",
".R.RBR",
"RB.BBB"
};
Rotator r(size, len, input);
ASSERT_EQ(results[Both], r.winner());
}
After rotation we'll have 4 blues in the first column (now they are on the last row, and there is a dot splitting the sequence), and also 4 reds, in a diagonal line from the first column down to the fourth one.Third test case, the red player wins:
TEST(Rotate, Test3)
{
const unsigned size = 4;
const unsigned len = 4;
Input input {
"R...",
"BR..",
"BR..",
"BR.."
};
Rotator r(size, len, input);
ASSERT_EQ(results[Red], r.winner());
}
After rotating, the gravity will put 4 red checkers in the bottom row.Here is the constructor:
Rotator::Rotator(unsigned size, unsigned len, const Input& input) : size_(size), len_(len)
{
if(!consistency(input)) // 1
throw std::logic_error("Bad input");
for(unsigned y = 0; y < size_; ++y) // 2
{
unsigned iBoard = size_ - 1; // 3
for(unsigned x = 0; x < size_; ++x) // 4
{
unsigned iInput = size_ - 1 - x;
if(input[y][iInput] != '.') // 5
board_[y][iBoard--] = input[y][iInput]; // 6
}
}
}
1. This private method does some minimal check on the user input. If it fails, an exception is thrown.2. The input is used to set the internal board. Actually, I do not perform the rotation. There is no added value in doing it, it is enough to simulate a gravity effect that push all the checkers to the right. It is much more simple, and there is no side effect on the solution.
3. "iBoard" is the current "x" position were I should put the checker. Initially is the rightmost one.
4. Notice the double for-loop. I scan the complete board looking for checkers. In case of a huge board with a very sparse distribution, this is not an optimal strategy. But remember that we have just 50 as max size.
5. Dot means no checker, we can happily ignore it.
6. We have a checker, we copy it from the input board to the internal one. After that, I decrease the internal index, so that it is ready for the next checker.
Something is missing in the code we have just seen. What the heck is "board_"? It is the private data member representing the board, a 50x50 bidimensional array that I declared in this way:
namespace
{
const char* results[] { "Neither", "Red", "Blue", "Both" };
enum Results { Neither, Red, Blue, Both };
const unsigned minSize = 3;
const unsigned maxSize = 50;
}
using Board = std::array<std::array<char, maxSize>, maxSize>;
using Input = std::vector<std::string>;
class Rotator
{
private:
Board board_ {};
// ...
Instead of using a raw C-array, I preferred the C++11 STL-array, much more friendly. So friendly that I can initialize it to have all '\0' values by the C++11 initializer list notation, as you can see I have done on board_ declaration.Once the board is set, I simply have to check who is the winner:
std::string Rotator::winner()
{
for(unsigned row = 0; row < size_ && (!blue_ || !red_); ++row) // 1
{
for(unsigned col = 0; col < size_ && (!blue_ || !red_); ++col) // 2
{
if((board_[row][col] == 'R' && !red_) || (board_[row][col] == 'B' && !blue_)) // 3
{
if(checkRight(row, col)) // 4
continue;
if(checkDown(row, col))
continue;
if(checkRightUp(row, col))
continue;
checkRightDown(row, col);
}
}
}
return results[blue_*2 + red_]; // 5
}
1. Same remark as for the ctor. A double for-loop is not smart at all, and here it is even worse. The structure of the problem makes all the checkers to group in the lower left corner of the board, it would be easy to start checking from that corner and stop looking when we find an empty space. Still, I've already spent an awful lot of time on this problem, maybe I'll post a code refactor in the near future to show a better solution.2. Notice that I have already used a tiny improvement. When I find that both players have won (both blue_ and red_ are true) I stop looping.
3. I check if the current position is a winning one only if there is a checker in this position, and if we don't already know that that color is a winner.
4. I check for a winning sequence straight on the right and down, and on the diagonal up and down. As soon I find a winning, I stop looking.
5. Sorry for this very C-like code, but I couldn't help to write it. I'm implicitly converting the booleans blue_ and red_ to integers, 0 is for false, 1 is for true. I weight blue_ with a 2 so that summing their values I get the index of the appropriate C-string to return the caller.
The differences among the four checkXxx() are minimal, I'll show here just one of them. See on github for the other ones.
bool Rotator::checkRight(unsigned row, unsigned col)
{
if(col + len_ > size_) // 1
return false;
for(unsigned k = 1; k < len_; ++k)
if(board_[row][col] != board_[row][col + k]) // 2
return false;
if(board_[row][col] == 'R') // 3
red_ = true;
else
blue_ = true;
return true;
}
1. I'm checking if the current position is the start of a winning sequence straight to the right. If there is not enough room, there is no need to check anything.2. As soon as I see a checker of a different color on the right of the first one, I can stop the loop.
3. A winner has been found.
No comments:
Post a Comment