#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; }