There were 27 test cases. The first 23 were worth 4 points each, while the last 4 were worth 2 points each. Each test case is represented by an assertion that must be true for you to pass that test. To run the test cases:
#include <iostream>
#include <sstream>
#include <streambuf>
#include <string>
#include <map>
#include <algorithm>
#include <cstdlib>
#include <cassert>
using namespace std;
class StreambufSwitcher
{
public:
StreambufSwitcher(ios& dest, streambuf* sb,
ios::iostate exceptions = ios::goodbit)
: dest_stream(dest), oldsb(dest.rdbuf(sb)), oldex(dest.exceptions())
{ dest_stream.exceptions(exceptions); }
StreambufSwitcher(ios& dest, ios& src)
: StreambufSwitcher(dest, src.rdbuf(), src.exceptions())
{}
~StreambufSwitcher()
{ dest_stream.rdbuf(oldsb); dest_stream.exceptions(oldex); }
private:
ios& dest_stream;
streambuf* oldsb;
ios::iostate oldex;
};
map<void*, size_t> allocMap;
bool recordaddrs = false;
inline bool isRecordedSize(size_t n)
{
return n == sizeof(Zombie) || n == sizeof(Player);
}
void* operator new(size_t n)
{
void* p = malloc(n);
fill_n(static_cast<char*>(p), n, 0xCA);
if (recordaddrs && isRecordedSize(n))
{
recordaddrs = false;
allocMap.insert(make_pair(p, n));
recordaddrs = true;
}
return p;
}
void unrecordaddr(void* p)
{
recordaddrs = false;
auto it = allocMap.find(p);
if (it != allocMap.end())
{
fill_n(static_cast<char*>(p), it->second, 0xCB);
allocMap.erase(it);
}
recordaddrs = true;
}
#if __cplusplus >= 201402L && ! defined(__clang__)
// Unless clang is supplied the -fsized-deallocation flag, it will
// not call the C++14/17 sized operator delete.
void operator delete(void* p) noexcept
{
free(p);
}
void operator delete(void* p, size_t n) noexcept
{
if (recordaddrs && isRecordedSize(n))
unrecordaddr(p);
operator delete(p);
}
#else
void operator delete(void* p) noexcept
{
if (recordaddrs)
unrecordaddr(p);
free(p);
}
#endif
bool recommendMove(const Arena& a, int r, int c, int& bestDir);
struct Pos
{
int r;
int c;
};
bool noZombiesAround(const Arena& a, Pos z)
{
for (int dr = -1; dr <= 1; dr++)
{
for (int dc = -1; dc <= 1; dc++)
{
if ((dr != 0 || dc != 0) && a.numberOfZombiesAt(z.r+dr, z.c+dc) != 0)
return false;
}
}
return true;
}
bool locateTheZombie(const Arena& a, Pos& z, bool shouldHaveMoved)
{
if (!shouldHaveMoved)
{
if (a.numberOfZombiesAt(z.r, z.c) != 1)
return false;
}
else
{
if (a.numberOfZombiesAt(z.r-1, z.c) == 1) z.r--;
else if (a.numberOfZombiesAt(z.r+1, z.c) == 1) z.r++;
else if (a.numberOfZombiesAt(z.r, z.c-1) == 1) z.c--;
else if (a.numberOfZombiesAt(z.r, z.c+1) == 1) z.c++;
else return false;
}
return noZombiesAround(a, z);
}
void encircleWithPoison(Arena& a, Pos z)
{
a.setCellStatus(z.r-1, z.c, HAS_POISON);
a.setCellStatus(z.r+1, z.c, HAS_POISON);
a.setCellStatus(z.r, z.c-1, HAS_POISON);
a.setCellStatus(z.r, z.c+1, HAS_POISON);
}
void testone(int n)
{
StreambufSwitcher sso(cout, cerr);
switch (n)
{
default: {
cout << "Bad argument" << endl;
} break; case 1: {
int k;
for (k = 0; k < 300; k++)
{
Arena a(1, 20);
a.addPlayer(1, 3);
Zombie z(&a, 1, 18);
assert(z.row() == 1 && z.col() == 18);
z.move(); assert(z.row() == 1);
if (z.col() != 19)
{
assert(z.col() == 17 || z.col() == 18);
continue;
}
z.move(); assert(z.row() == 1);
if (z.col() == 20)
break;
assert(z.col() == 18 || z.col() == 19);
}
assert(k < 300);
} break; case 2: {
int k;
for (k = 0; k < 600; k++)
{
Arena a(1, 20);
a.addPlayer(1, 3);
Zombie z(&a, 1, 19);
assert(z.row() == 1 && z.col() == 19);
z.move(); assert(z.row() == 1);
if (z.col() != 19)
{
assert(z.col() == 18 || z.col() == 20);
continue;
}
z.move(); assert(z.row() == 1);
if (z.col() != 19)
{
assert(z.col() == 18 || z.col() == 20);
continue;
}
z.move(); assert(z.row() == 1);
if (z.col() != 19)
{
assert(z.col() == 18 || z.col() == 20);
continue;
}
z.move(); assert(z.row() == 1);
if (z.col() != 19)
{
assert(z.col() == 18 || z.col() == 20);
continue;
}
z.move(); assert(z.row() == 1);
if (z.col() == 18 || z.col() == 20)
break;
assert(z.col() == 19);
}
assert(k < 600);
} break; case 3: {
int k;
for (k = 0; k < 600; k++)
{
Arena a(20, 1);
a.addPlayer(3, 1);
Zombie z(&a, 19, 1);
assert(z.row() == 19 && z.col() == 1);
z.move(); assert(z.col() == 1);
if (z.row() != 19)
{
assert(z.row() == 18 || z.row() == 20);
continue;
}
z.move(); assert(z.col() == 1);
if (z.row() != 19)
{
assert(z.row() == 18 || z.row() == 20);
continue;
}
z.move(); assert(z.col() == 1);
if (z.row() != 19)
{
assert(z.row() == 18 || z.row() == 20);
continue;
}
z.move(); assert(z.col() == 1);
if (z.row() != 19)
{
assert(z.row() == 18 || z.row() == 20);
continue;
}
z.move(); assert(z.col() == 1);
if (z.row() == 18 || z.row() == 20)
break;
assert(z.row() == 19);
}
assert(k < 600);
} break; case 4: {
Arena a(10,20);
a.addPlayer(9, 19);
for (int r = 5-2; r <= 5+2; r++)
for (int c = 10-2; c <= 10+2; c++)
a.setCellStatus(r, c, HAS_POISON);
Zombie z(&a, 5, 10);
z.move();
assert((z.row() == 5 && abs(z.col() - 10) == 1) ||
(z.col() == 10 && abs(z.row() - 5) == 1));
int oldr = z.row();
int oldc = z.col();
z.move();
assert(z.row() == oldr && z.col() == oldc);
z.move();
assert((z.row() == oldr && abs(z.col() - oldc) == 1) ||
(z.col() == oldc && abs(z.row() - oldr) == 1));
} break; case 5: {
Arena a(10,20);
a.addPlayer(9, 19);
for (int r = 5-2; r <= 5+2; r++)
for (int c = 10-2; c <= 10+2; c++)
if (r != 5 || c != 10)
a.setCellStatus(r, c, HAS_POISON);
Zombie z(&a, 5, 10);
assert(!z.isDead());
z.move();
assert((z.row() == 5 && abs(z.col() - 10) == 1) ||
(z.col() == 10 && abs(z.row() - 5) == 1));
int oldr = z.row();
int oldc = z.col();
assert(!z.isDead());
a.setCellStatus(5, 10, HAS_POISON);
z.move();
assert(z.row() == oldr && z.col() == oldc);
assert(!z.isDead());
z.move();
assert((z.row() == oldr && abs(z.col() - oldc) == 1) ||
(z.col() == oldc && abs(z.row() - oldr) == 1));
assert(z.isDead());
} break; case 6: {
Arena a(10,20);
a.addPlayer(9, 19);
a.setCellStatus(4, 10, HAS_POISON);
a.setCellStatus(6, 10, HAS_POISON);
a.setCellStatus(5, 9, HAS_POISON);
a.setCellStatus(5, 11, HAS_POISON);
Zombie z(&a, 5, 10);
z.move();
assert((z.row() == 5 && abs(z.col() - 10) == 1) ||
(z.col() == 10 && abs(z.row() - 5) == 1));
int oldr = z.row();
int oldc = z.col();
z.move();
assert(z.row() == oldr && z.col() == oldc);
z.move();
assert((z.row() == oldr && abs(z.col() - oldc) == 1) ||
(z.col() == oldc && abs(z.row() - oldr) == 1));
oldr = z.row();
oldc = z.col();
z.move();
assert(z.row() == oldr && z.col() == oldc);
a.setCellStatus(oldr-1, oldc, EMPTY);
a.setCellStatus(oldr+1, oldc, EMPTY);
a.setCellStatus(oldr, oldc-1, EMPTY);
a.setCellStatus(oldr, oldc+1, EMPTY);
z.move();
assert((z.row() == oldr && abs(z.col() - oldc) == 1) ||
(z.col() == oldc && abs(z.row() - oldr) == 1));
} break; case 7: {
Arena a(1, 20);
a.addPlayer(1, 3);
Player* p = a.player();
assert(p->row() == 1 && p->col() == 3);
p->move(WEST); assert(p->row() == 1 && p->col() == 2);
p->move(WEST); assert(p->row() == 1 && p->col() == 1);
} break; case 8: {
Arena a(1, 20);
a.addPlayer(1, 3);
Player* p = a.player();
p->move(WEST); assert(p->row() == 1 && p->col() == 2);
p->move(WEST); assert(p->row() == 1 && p->col() == 1);
p->move(WEST); assert(p->row() == 1 && p->col() == 1);
p->move(NORTH); assert(p->row() == 1 && p->col() == 1);
p->move(SOUTH); assert(p->row() == 1 && p->col() == 1);
} break; case 9: {
Arena a(10, 20);
a.addPlayer(3, 6);
Player* p = a.player();
assert( ! p->isDead());
p->setDead();
assert(p->isDead());
} break; case 10: {
Arena a(20, 1);
a.addPlayer(1, 1);
Player* p = a.player();
assert(p->move(WEST).find(" stands") != string::npos);
assert(p->move(EAST).find(" stands") != string::npos);
assert(p->move(NORTH).find(" stands") != string::npos);
assert(p->move(SOUTH).find(" south") != string::npos);
} break; case 11: {
Arena a(20, 1);
a.addPlayer(1, 1);
Player* p = a.player();
a.addZombie(2, 1);
assert(p->move(SOUTH).find(" died") != string::npos);
} break; case 12: {
Arena a(20, 1);
a.addPlayer(1, 1);
Player* p = a.player();
a.addZombie(2, 1);
assert(!p->isDead());
p->move(SOUTH);
assert(p->isDead());
} break; case 13: {
Arena a(6, 15);
assert(a.rows() == 6 && a.cols() == 15);
} break; case 14: {
Arena a(10, 20);
a.addPlayer(3, 6);
a.addZombie(7, 5);
assert(a.numberOfZombiesAt(7, 5) == 1 && a.zombieCount() == 1);
} break; case 15: {
Arena a(10, 20);
a.addPlayer(3, 6);
a.addZombie(7, 5);
a.addZombie(4, 7);
a.addZombie(7, 5);
assert(a.numberOfZombiesAt(7, 5) == 2 && a.zombieCount() == 3);
} break; case 16: {
Arena a(1, 20);
a.addPlayer(1, 8);
a.addZombie(1, 1);
a.setCellStatus(1, 2, HAS_POISON);
a.setCellStatus(1, 3, HAS_POISON);
a.addZombie(1, 16);
a.setCellStatus(1, 14, HAS_POISON);
a.setCellStatus(1, 15, HAS_POISON);
a.setCellStatus(1, 17, HAS_POISON);
a.setCellStatus(1, 18, HAS_POISON);
assert(a.zombieCount() == 2);
int k;
for (k = 0; k < 200; k++)
{
a.moveZombies();
int nb1 = (a.getCellStatus(1, 2) == HAS_POISON) +
(a.getCellStatus(1, 3) == HAS_POISON);
int nb2 = (a.getCellStatus(1, 14) == HAS_POISON) +
(a.getCellStatus(1, 15) == HAS_POISON) +
(a.getCellStatus(1, 17) == HAS_POISON) +
(a.getCellStatus(1, 18) == HAS_POISON);
assert(a.zombieCount() == (nb1 > 0) + (nb2 > 2));
if (a.zombieCount() == 0)
break;
}
assert(k < 200);
} break; case 17: {
Arena a(1, 3);
a.addPlayer(1, 1);
Player* p = a.player();
for (int j = 0; j < 10; j++)
a.addZombie(1, 3);
assert(!p->isDead());
a.moveZombies();
int k;
for (k = 0; k < 100; k++)
{
assert(!p->isDead());
a.moveZombies();
if (a.numberOfZombiesAt(1, 1) > 0)
{
assert(p->isDead());
break;
}
}
assert(k < 100);
} break; case 18: {
ostringstream oss;
StreambufSwitcher sso2(cout, oss);
Arena a(2, 3);
a.addPlayer(2, 3);
a.addZombie(2, 1);
a.addZombie(2, 1);
a.addZombie(2, 2);
a.display("");
assert(oss.str().find("2Z@") != string::npos);
} break; case 19: {
ostringstream oss;
StreambufSwitcher sso2(cout, oss);
Arena a(2, 3);
a.addPlayer(2, 3);
for (int k = 1; k <= 20; k++)
a.addZombie(2, 1);
a.display("");
assert(oss.str().find("9.@") != string::npos);
} break; case 20: {
recordaddrs = true;
int n = allocMap.size();
{
Arena a(20, 20);
for (int r = 1; r <= 5; r++)
for (int c = 11; c <= 20; c++)
a.setCellStatus(r, c, HAS_POISON);
for (int r = 16; r <= 20; r++)
for (int c = 15; c <= 20; c++)
a.setCellStatus(r, c, HAS_POISON);
a.addPlayer(19, 19);
int n2 = allocMap.size();
a.setCellStatus(3, 13, EMPTY);
a.setCellStatus(3, 18, EMPTY);
a.addZombie(3, 13);
a.addZombie(3, 18);
for (int k = 0; k < 4; k++)
{
a.addZombie(1, 1);
a.addZombie(1, 4);
a.addZombie(4, 1);
a.addZombie(4, 4);
}
assert(allocMap.size() >= n2 + 18);
a.moveZombies();
a.setCellStatus(3, 13, HAS_POISON);
a.setCellStatus(3, 18, HAS_POISON);
a.moveZombies();
a.moveZombies();
assert(a.zombieCount() == 18-2);
for (int k = a.zombieCount(); k < MAXZOMBIES; k++)
assert(a.addZombie(1, 1));
int j;
for (j = 0; j < 1000 && a.zombieCount() > 20; j++)
{
for (int r = 1; r <= 20; r++)
for (int c = 1; c <= 20; c++)
if (a.numberOfZombiesAt(r, c) == 0 && !(r == 19 && c == 19))
a.setCellStatus(r, c, HAS_POISON);
a.moveZombies();
}
assert(j < 1000);
a.setCellStatus(1, 1, EMPTY);
for (int k = a.zombieCount(); k < MAXZOMBIES; k++)
assert(a.addZombie(1, 1));
assert(allocMap.size() >= n2 + MAXZOMBIES);
}
assert(allocMap.size() == n);
recordaddrs = false;
} break; case 21: {
Arena a(20, 20);
a.addPlayer(19, 19);
for (int r = 1; r < 19; r++)
for (int c = 1; c < 19; c++)
if (r != 10 || c != 10)
a.setCellStatus(r, c, HAS_POISON);
for (int k = 0; k < 100; k++)
a.addZombie(10, 10);
assert(a.zombieCount() == 100 && a.numberOfZombiesAt(10, 10) == 100);
int nr[1+20][1+20];
a.moveZombies();
int tot = 0;
for (int r = 1; r < 19; r++)
{
for (int c = 1; c < 19; c++)
{
nr[r][c] = a.numberOfZombiesAt(r, c);
tot += nr[r][c];
assert((r == 10 && c >= 9 && c <= 11) ||
(c == 10 && r >= 9 && r <= 11) ||
nr[r][c] == 0);
}
}
assert(nr[10][10] == 0 && tot == a.zombieCount());
assert(nr[9][10] == 0 || a.getCellStatus(9, 10) == EMPTY);
assert(nr[11][10] == 0 || a.getCellStatus(11, 10) == EMPTY);
assert(nr[10][9] == 0 || a.getCellStatus(10, 9) == EMPTY);
assert(nr[10][11] == 0 || a.getCellStatus(10, 11) == EMPTY);
a.setCellStatus(10, 10, HAS_POISON);
a.moveZombies();
assert(a.numberOfZombiesAt(9, 10) == (nr[9][10] == 0 ? 0 : 1));
assert(a.numberOfZombiesAt(11, 10) == (nr[11][10] == 0 ? 0 : 1));
assert(a.numberOfZombiesAt(10, 9) == (nr[10][9] == 0 ? 0 : 1));
assert(a.numberOfZombiesAt(10, 11) == (nr[10][11] == 0 ? 0 : 1));
for (int k = 0; k < 17; k++)
{
for (int r = 1; r < 19; r++)
for (int c = 1; c < 19; c++)
if (a.numberOfZombiesAt(r, c) == 0)
a.setCellStatus(r, c, HAS_POISON);
a.moveZombies();
}
tot = 0;
for (int r = 1; r < 19; r++)
for (int c = 1; c < 19; c++)
tot += a.numberOfZombiesAt(r, c);
assert(a.zombieCount() == tot && tot < 100);
} break; case 22: {
Arena a(18, 22);
Pos z[4] = { { 6, 6 }, { 6, 17 }, { 13, 6 }, { 13, 17 } };
for (int k = 0; k < 4; k++)
a.addZombie(z[k].r, z[k].c);
assert(a.zombieCount() == 4);
for (int k = 0; k < 4; k++)
{
assert(locateTheZombie(a, z[k], false)); // none moved at start
if (k <= 1)
encircleWithPoison(a, z[k]);
}
a.moveZombies();
assert(a.zombieCount() == 4);
for (int k = 0; k < 4; k++)
{
assert(locateTheZombie(a, z[k], true)); // all moved
if (k <= 1)
encircleWithPoison(a, z[k]);
}
a.moveZombies();
assert(a.zombieCount() == 4);
for (int k = 0; k < 4; k++)
assert(locateTheZombie(a, z[k], k >= 2)); // two slept, two moved
a.moveZombies();
assert(a.zombieCount() == 2);
for (int k = 0; k < 2; k++)
{
assert(a.numberOfZombiesAt(z[k].r, z[k].c) == 0); // these two died
assert(noZombiesAround(a, z[k]));
}
for (int k = 2; k < 4; k++)
assert(locateTheZombie(a, z[k], true)); // these two moved
encircleWithPoison(a, z[2]);
a.moveZombies();
assert(a.zombieCount() == 2);
for (int k = 2; k < 4; k++)
assert(locateTheZombie(a, z[k], true)); // both moved
encircleWithPoison(a, z[2]);
a.moveZombies();
assert(a.zombieCount() == 2);
assert(locateTheZombie(a, z[2], false)); // this one slept
assert(locateTheZombie(a, z[3], true)); // this one moved
a.moveZombies();
assert(a.zombieCount() == 1);
assert(a.numberOfZombiesAt(z[2].r, z[2].c) == 0); // this one died
assert(noZombiesAround(a, z[2]));
assert(locateTheZombie(a, z[3], true)); // this one moved
} break; case 23: {
Arena a(4, 2);
a.addPlayer(1, 1);
Player* p = a.player();
a.addZombie(4, 2);
for (int k = 0; k < 10000 && ! a.player()->isDead() &&
a.zombieCount() != 0; k++)
{
int dir;
if (recommendMove(a, p->row(), p->col(), dir))
p->move(dir);
else
p->dropPoisonedBrain();
a.moveZombies();
}
assert(! a.player()->isDead() && a.zombieCount() == 0);
} break; case 24: {
Arena a(10, 10);
a.addPlayer(6, 6);
a.addZombie(5, 6);
a.addZombie(7, 6);
a.addZombie(6, 7);
int dir;
assert(recommendMove(a, 6, 6, dir) && dir == WEST);
} break; case 25: {
Arena a(10, 10);
a.addPlayer(6, 6);
a.addZombie(4, 6);
a.addZombie(5, 7);
a.addZombie(6, 8);
a.addZombie(7, 7);
a.addZombie(8, 6);
a.addZombie(7, 5);
a.addZombie(6, 4);
a.addZombie(5, 5);
int dir;
assert(!recommendMove(a, 6, 6, dir));
} break; case 26: {
Arena a(2, 3);
a.addPlayer(1, 2);
a.addZombie(1, 1);
for (int k = 0; k < 10; k++)
a.addZombie(2, 3);
int dir;
assert(!recommendMove(a, 1, 2, dir));
} break; case 27: {
Arena a(3, 2);
a.addPlayer(3, 1);
a.addZombie(1, 1);
for (int k = 0; k < 10; k++)
a.addZombie(3, 2);
int dir;
assert(recommendMove(a, 3, 1, dir) && dir == NORTH);
} break;
}
}
int main()
{
cout << "Enter test number (1-27): ";
int n;
cin >> n;
testone(n);
cout << "Passed!" << endl;
}