#include <ctype.h>
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
#include <string>
#include <map>
using namespace std;
/*
* DEBUG ONLY: If compiled -DDEBUG, the program will show the transformed
* scripts (on stderr) for each NPC that avoid collisions and are always
* inherently cyclic. If compiled -DSTEP, the program will show the town state
* (also on stderr) after every single turn. Note that using -DSTEP makes the
* entire program too slow to actually finish running the master data sets.
* With -DSTEP we no longer do the "modulo optimization" that takes advantage
* of cyclic nature of the NPCs walk scripts.
*/
/* SANITY CHECK: assertion macro for verifying input data and internal state */
#define ASSERT(e) { if(!(e)) { cerr << #e << endl; throw; } }
/* Max width/height of a town */
#define MAXSIZE 40
/* Return the minimum of two values */
#define min(a,b) ((a) < (b) ? (a) : (b))
/* Generic integer pair used for several things in the program */
typedef pair<int, int> coord_t;
/* Dictionary to map verb names to indices into the VERB array */
map<string, int> NAMES;
/* DEBUG ONLY: Array mapping VERB array indices to string names for printing */
const char *PRINT[] = {
"NORTH", "SOUTH", "EAST", "WEST", "PAUSE"
};
/* These are the "reversed" verb numbers for each of the commands in NAMES[] */
const int REVERSE[] = { 1, 0, 3, 2, 4 };
/*
* The effect that each of the command verbs has on a NPC's position can be
* encoded in terms of a row and column offset that's applied to the position
* every turn. This array is in the same order as NAMES to facilitate easy
* lookup. The offsets are of the form (row, col).
*/
const coord_t VERB[] = {
coord_t(-1, 0), coord_t(1, 0), coord_t(0, 1), coord_t(0, -1), coord_t(0, 0)
};
/* Index into VERB[] for the pause command */
#define PAUSE 4
/*
* A command is a (verb, value) pair where "verb" is an integer between 0 and 4
* (matching the VERB[] array) and "value" is an integer indicating how far to
* move or how long to pause for. The command map associates each command list
* with the NPC single character id as read from the input data set.
*/
typedef vector<coord_t> cmdlist_t;
typedef map<char, cmdlist_t> cmdmap_t;
/* Maps an NPC char id (number or letter) to the NPC position as (row, col) */
typedef map<char, coord_t> npcmap_t;
/*
* The array is used to hold the town layout but only for tracking the
* open vs wall spaces. Actual NPC locations are only stored in a datalist_t
* object since that's an easier format to update as the NPCs move around.
*/
typedef char grid_t[MAXSIZE][MAXSIZE];
/*
* Print the town layout to the "out" stream and show the location of every
* NPC in "npcmap" by printing the appropriate NPC character on top of the
* layout.
*/
void output(ostream &out, grid_t grid, npcmap_t &npcmap, int width, int height)
{
npcmap_t::iterator i;
/* Temporarily add the NPCs to the grid for printing */
for(i = npcmap.begin(); i != npcmap.end(); ++i) {
grid[i->second.first][i->second.second] = i->first;
}
for(int row = 0; row < height; row++) {
for(int col = 0; col < width; col++) {
out << grid[row][col];
}
out << endl;
}
/* Reset NPC locations back to empty spaces */
for(i = npcmap.begin(); i != npcmap.end(); ++i) {
grid[i->second.first][i->second.second] = '.';
}
}
/*
* DEBUG ONLY: Simulate one turn for a given NPC. The current command in
* "cmdlist" (current as determined by "instptr") is executed and the NPC
* position "pos" updated. Once the current command has finished executing,
* the "instptr" is advanced (possibly wrapping around) to the next command.
*/
void simulate_one(grid_t grid, int width, int height, coord_t &instptr,
cmdlist_t &cmdlist, coord_t &pos)
{
int ip = instptr.first;
/*
* If NPC's command is finished, increment instruction pointer but skip
* over any commands who had their delay value reduced to zero by fixup().
*/
while(instptr.second == 0) {
ip = (ip + 1) % cmdlist.size();
instptr.first = ip;
instptr.second = cmdlist[ip].second;
}
/* Execute current command and decrement instruction delay */
pos.first += VERB[cmdlist[ip].first].first;
pos.second += VERB[cmdlist[ip].first].second;
instptr.second--;
}
/*
* DEBUG ONLY: Simulate one turn across all NPCs in the data set. The
* "instptr" map holds "instruction pointers" for every NPC. Every
* instruction pointer is a pair (cmdnum, delay) where "cmdnum" is an index
* into cmdmap of the currently executing command and "delay" is the number
* of turns remaining until the current command finishes executing.
*/
void simulate_all(grid_t grid, int width, int height, npcmap_t &instptr,
cmdmap_t &cmdmap, npcmap_t &npcmap)
{
npcmap_t::iterator i;
/* Move each NPC by one turn */
for(i = npcmap.begin(); i != npcmap.end(); ++i) {
char npc = i->first;
simulate_one(grid, width, height, instptr[npc],
cmdmap[npc], npcmap[npc]);
}
}
/*
* Execute a command "cmd" a single turn by updating the position of "oldpos" If
* this command caused the NPC to hit a solid object or the edge of the map,
* then return true and don't update "oldpos". Used by fixup() to detect
* collisions in the script and to re-write the script accordingly.
*/
bool execute(coord_t cmd, coord_t &oldpos, grid_t grid, int width, int height)
{
coord_t pos;
pos.first = oldpos.first + VERB[cmd.first].first;
pos.second = oldpos.second + VERB[cmd.first].second;
if(pos.first < 0 || pos.second < 0 || pos.first >= height ||
pos.second >= width || grid[pos.first][pos.second] != '.')
return true;
oldpos = pos;
return false;
}
/*
* Execute the "cmdlist" script one time through and if any collisions are
* found, re-write it to a form that avoids the collisions all together by
* inserting the appropriate number of PAUSEs. Also if the script is not
* already inherently cyclic, make it so by appending a reversed version
* of the collision-free script that will return the NPC to its original
* location. Finally, this function computes the total cycle length (in turns)
* of the NPC's walk script and returns it. The cycle length is used for
* a modulo optimization later on.
*/
int fixup(grid_t grid, coord_t pos, int width, int height, cmdlist_t &cmdlist)
{
cmdlist_t::iterator i;
coord_t start = pos;
/*
* Execute through all the commands in the list and run each command for the
* specified number of turns. If we hit a wall or edge, split this command
* into a shortened original and a PAUSE for the remainder of the
* "collision" time.
*/
for(i = cmdlist.begin(); i != cmdlist.end(); ++i) {
coord_t cmd = *i;
for(int j = 0; j < cmd.second; j++) {
if(execute(cmd, pos, grid, width, height)) {
*i = coord_t(cmd.first, j);
++i;
i = cmdlist.insert(i, coord_t(PAUSE, cmd.second - j));
break;
}
}
}
/* If the script is reversible, make it cyclic */
if(pos != start) {
int size = cmdlist.size();
cmdlist.resize(size * 2);
/* Append a duplicated and reversed command list */
copy(&cmdlist[0], &cmdlist[size], &cmdlist[size]);
reverse(&cmdlist[size], &cmdlist[size * 2]);
/* Reverse directions of individual commands in list */
for(int i = size; i < size * 2; i++) {
cmdlist[i].first = REVERSE[cmdlist[i].first];
}
}
/* Calculate the total cycle length of the walk script */
int total = 0;
for(i = cmdlist.begin(); i != cmdlist.end(); ++i) {
total += i->second;
}
return total;
}
/* Main body of program */
void process(void)
{
int data_num, data_idx;
/* Initialize the global NAMES[] dictionary */
NAMES["NORTH"] = 0;
NAMES["SOUTH"] = 1;
NAMES["EAST"] = 2;
NAMES["WEST"] = 3;
NAMES["PAUSE"] = 4;
/* Read how many data sets to process */
cin >> data_num;
/* Process each data set separately */
for(data_idx = 0; data_idx < data_num; data_idx++) {
int npc_num, npc_idx; /* For looping over command lists */
int width, height, turns; /* Parameters from data set input */
npcmap_t npcmap; /* Tracks position of each NPC */
npcmap_t instptr; /* DEBUG ONLY: current command during sim */
cmdmap_t cmdmap; /* Command list per NPC */
map<char, int> cycle; /* Total walk cycle length per NPC */
grid_t grid; /* Town layout */
cin >> npc_num >> height >> width;
ASSERT(1 <= npc_num && npc_num <= 35);
ASSERT(1 <= height && height <= 40);
ASSERT(1 <= width && width <= 40);
/* Read in the town grid */
for(int row = 0; row < height; row++) {
for(int col = 0; col < width; col++) {
char npc;
cin >> npc;
/* Numbers and letters are NPC locations; record in npcmap */
if(isalnum(npc)) {
npcmap[npc] = coord_t(row, col);
grid[row][col] = '.';
}
/* Otherwise it's a wall or empty space; record in grid */
else {
ASSERT(npc == '.' || npc == '#');
grid[row][col] = npc;
}
}
}
#if defined(STEP) || defined(DEBUG)
cerr << "DATA SET #" << data_idx + 1 << endl;
#endif
/* Read in the command scripts for each NPC */
for(npc_idx = 0; npc_idx < npc_num; npc_idx++) {
int cmd_idx, cmd_num;
char npc;
/* Read NPC id and command count */
cin >> npc >> cmd_num;
ASSERT(npcmap.find(npc) != npcmap.end());
ASSERT(1 <= cmd_num && cmd_num <= 20);
/* DEBUG ONLY: Init "instruction pointer" used by simulate_all() */
instptr[npc] = coord_t(-1, 0);
/* Read the list of commands into cmdmap[npc] list */
for(cmd_idx = 0; cmd_idx < cmd_num; cmd_idx++) {
string word;
int value;
cin >> word >> value;
ASSERT(NAMES.find(word) != NAMES.end());
ASSERT(1 <= value <= 40);
cmdmap[npc].push_back(coord_t(NAMES[word], value));
}
/* Detect collisions and make reversible walks cyclic */
cycle[npc] = fixup(grid, npcmap[npc], width, height, cmdmap[npc]);
#if defined(STEP) || defined(DEBUG)
/* DEBUG ONLY: Show transformed command list with no collisions */
cerr << "Transformed script " << npc << ":" << endl;
cmdlist_t::iterator i;
for(i = cmdmap[npc].begin(); i != cmdmap[npc].end(); ++i) {
cerr << PRINT[i->first] << " " << i->second << endl;
}
cerr << "Cycle length: " << cycle[npc] << endl << endl;
#endif
}
/* Read the number of turns to simulate for */
cin >> turns;
ASSERT(1 <= turns && turns <= 1000000);
#ifdef STEP
/* DEBUG ONLY: Show initial grid layout before simulation */
cerr << "Initial layout:" << endl;
output(cerr, grid, npcmap, width, height);
cerr << endl;
/* DEBUG ONLY: Run a full simulation to show how NPCs move */
for(int i = 0; i < turns; i++) {
simulate_all(grid, width, height, instptr, cmdmap, npcmap);
cerr << "Turn " << i + 1 << ":" << endl;
output(cerr, grid, npcmap, width, height);
cerr << endl;
}
#else
/*
* Because every NPC movement is cyclic, we can reduce the computation
* time by separately simulating only "turns modulo cycle length" for
* every NPC.
*/
for(npcmap_t::iterator i = npcmap.begin(); i != npcmap.end(); ++i) {
int ip = 0;
char npc = i->first;
int npcturns = turns % cycle[npc];
coord_t &pos = npcmap[npc];
cmdlist_t &cmdlist = cmdmap[npc];
/*
* We can get a further optimization by executing a single command
* per loop iteration and "scaling" the distance moved by the
* command's "value".
*/
while(npcturns) {
int verb = cmdlist[ip].first;
int value = min(npcturns, cmdlist[ip].second);
/* Execute current command and decrement instruction delay */
pos.first += VERB[verb].first * value;
pos.second += VERB[verb].second * value;
/* Advance to next instruction in command list */
npcturns -= value;
ip = (ip + 1) % cmdlist.size();
}
}
#endif
/* Show the final state of the town */
cout << "DATA SET #" << data_idx + 1 << endl;
output(cout, grid, npcmap, width, height);
}
}
/* Run program and print out any exceptions that occur */
int main(void)
{
/* Throw exceptions on failed data extraction in >> operator */
cin.exceptions(ios::failbit);
/* Run main body of code */
try {
process();
}
/* Catch unexpected EOF or bad input data */
catch(ios::failure const &e) {
cerr << "Unexpected EOF or data type mismatch on input" << endl;
}
return 0;
}