copsrc/cop.cpp

   1 #include "cop.h"
   2 #include <iostream>
   3 #include <sstream>
   4 #include <iterator>
   5 #include <queue>
   6 #include <cmath>
   7
   8 using namespace std;
   9 using namespace __gnu_cxx;
  10
  11 string Cop::turn(){
  12         //cerr << "New turn" << endl;
  13         string input;
  14
  15         sendInformation();
  16         //cerr << "Getting information " << endl;
  17         getInformation();
  18
  19         sendPlan();
  20         getPlans();
  21
  22         vote();
  23
  24         getline(cin,input);
  25         if (input != "nowinner:"){
  26                 string winner = value<string>(input);
  27                 if (winner != _name)
  28                         ++_winningPlans[winner];
  29         }
  30
  31         return _location;
  32 }
  33
  34 void Cop::preGamePreparations(){
  35         //cerr << "Preparing.." << endl;
  36         _copTargets[_name].first = _robberLocation;
  37         _copTargets[_name].second = cop_foot;
  38
  39         priority_queue<pair<int,string> > banks;
  40         //cerr << "Number of banks: " << endl;
  41         for(hash_map<string,int>::const_iterator bank = _banks.begin();
  42                                 bank != _banks.end(); ++bank){
  43                 //cerr << "Finding bank: " << bank->first << endl;
  44                 list<string> bankRoute  = shortestPath(_robberLocation, robber, SimpleSPGoal(bank->first));
  45                 //cerr << "Pushing bank" << endl;
  46                 banks.push(pair<int,string>(-bankRoute.size(), bank->first));
  47         }
  48         //cerr << "Done finding banks.." << endl;
  49         priority_queue<pair<int,string> > banks2;
  50         for (int i = 0; i < 4 && banks.size() > 0;++i){
  51                 const pair<int,string>& bank = banks.top();
  52                 //cerr << "Going to bank: " << bank.second << ", distance" << -bank.first << endl;
  53                 list<string> bankRouteFoot = shortestPath(_copHq, cop_foot, SimpleSPGoal(bank.second));
  54                 list<string> bankRouteCar = shortestPath(_copHq, cop_car, SimpleSPGoal(bank.second));
  55                 banks2.push(pair<int,string>(bankRouteCar.size() - bankRouteFoot.size(), bank.second));
  56                 banks.pop();
  57         }
  58         for (hash_map<string,Player>::const_iterator player = _players.begin();
  59                         player != _players.end(); ++player){
  60                 cerr << "Inital plan for player: " << player->first << endl;
  61                 if (player->second.type == robber){
  62                         _robber = player->first;
  63                         continue;
  64                 }else if (banks2.size() <= 0 || player->first == _name)
  65                         continue;
  66
  67                 const pair<int,string>& bank = banks2.top();
  68                 _copTargets[player->first].first = bank.second;
  69                 //cerr << "Sending: " << player->first << " to: " << bank.second;
  70                 if (banks2.size() <= 2)
  71                         _copTargets[player->first].second = cop_car;
  72                 else
  73                         _copTargets[player->first].second = cop_foot;
  74                 //cerr << " on: " << _copTargets[player->first].second << endl;
  75                 _winningPlans[player->first] = 0;
  76                 banks2.pop();
  77         }
  78         _maybeRobber.push_back(hash_map<string,int>());
  79 }
  80
  81 void Cop::sendInformation(){
  82         _maybeRobber.push_back(hash_map<string,int>());
  83         hash_map<string,int>& maybeRobber = _maybeRobber.back();
  84         int possibilities = 0;
  85         if (_robberLocation.empty()){
  86
  87                 hash_map<string, Intersection>::const_iterator intersection = _intersections.find(_location);
  88
  89                 for (hash_map<string,StreetType>::const_iterator adj = intersection->second.connections.begin();
  90                                 adj != intersection->second.connections.end(); ++adj){
  91
  92                         if (_smell == 1){
  93                                 hash_map<string,int>::iterator location = maybeRobber.find(adj->first);
  94                                 if (location == maybeRobber.end()){
  95                                         hash_map<string, Intersection>::const_iterator intersection = _intersections.find(adj->first);
  96                                         int neigh = maybeAtNeighbor(intersection->second);
  97                                         if (neigh > -1){
  98                                                 maybeRobber[adj->first] = 100 + neigh;
  99                                                 ++possibilities;
 100                                         }else
 101                                                 maybeRobber[adj->first] = -100;
 102                                 }
 103                         }else{
 104                                 if (_smell == 0)
 105                                         maybeRobber[adj->first] = -100;
 106                                 hash_map<string, Intersection>::const_iterator intersection = _intersections.find(adj->first);
 107                                 for (hash_map<string,StreetType>::const_iterator adj = intersection->second.connections.begin();
 108                                                 adj != intersection->second.connections.end(); ++adj){
 109                                         hash_map<string,int>::iterator location = maybeRobber.find(adj->first);
 110                                         if (location == maybeRobber.end()){
 111                                                 if (_smell == 0)
 112                                                         maybeRobber[adj->first] = -100;
 113                                                 else {
 114                                                         hash_map<string, Intersection>::const_iterator intersection = _intersections.find(adj->first);
 115                                                         int neigh = maybeAtNeighbor(intersection->second);
 116                                                         if (neigh > -1){
 117                                                                 maybeRobber[adj->first] = 100 + neigh;
 118                                                                 ++possibilities;
 119                                                         }
 120                                                         else
 121                                                                 maybeRobber[adj->first] = -100;
 122                                                 }
 123                                         }
 124                                 }
 125                         }
 126                 }
 127         } else {
 128                 maybeRobber[_robberLocation] = 100;
 129                 possibilities = 1;
 130                 hash_map<string, Intersection>::const_iterator intersection = _intersections.find(_location);
 131
 132                 for (hash_map<string,StreetType>::const_iterator adj = intersection->second.connections.begin();
 133                                 adj != intersection->second.connections.end(); ++adj){
 134                         maybeRobber[adj->first] = -100;
 135                         for (hash_map<string,StreetType>::const_iterator adj = intersection->second.connections.begin();
 136                                         adj != intersection->second.connections.end(); ++adj){
 137                                 hash_map<string,int>::iterator location = maybeRobber.find(adj->first);
 138                                 if (location != maybeRobber.end())
 139                                         maybeRobber[adj->first] = -100;
 140                         }
 141
 142                 }
 143
 144
 145         }
 146         cout << "inf\\" << endl;
 147         for (hash_map<string,int>::iterator location = maybeRobber.begin();
 148                         location != maybeRobber.end(); ++location){
 149                 if (location->second > 0)
 150                         location->second /= possibilities;
 151                 cout << "inf: " << _robber << " " << location->first << " " << _playerTypeNames[robber] << " "
 152                         << _world << " " << location->second << endl;
 153         }
 154         cout << "inf/" << endl;
 155 }
 156
 157 void Cop::getInformation(){
 158         string input;
 159         if (_robberLocation.empty()){
 160                 hash_map<string,int>& maybeRobber = _maybeRobber.back();
 161                 while (true){
 162                         getline(cin, input);
 163                         if (input == "from/")
 164                                 break;
 165
 166                         getline(cin, input);
 167                         getline(cin, input);
 168
 169                         while (true){
 170                                 getline(cin, input);
 171                                 if (input == "inf/")
 172                                         break;
 173                                 istringstream inf(input);
 174                                 inf >> input;
 175                                 string bot;
 176                                 inf >> bot;
 177                                 string loc;
 178                                 inf >> loc;
 179                                 string type;
 180                                 inf >> type;
 181                                 if (type != _playerTypeNames[robber])
 182                                         continue;
 183                                 int world;
 184                                 inf >> world;
 185                                 if (world != _world)
 186                                         continue;
 187                                 int certainty;
 188                                 inf >> certainty;
 189
 190                                 hash_map<string,int>::iterator location = maybeRobber.find(loc);
 191                                 if (location == maybeRobber.end()){
 192                                         hash_map<string, Intersection>::const_iterator intersection = _intersections.find(loc);
 193                                         if (intersection != _intersections.end())
 194                                                 continue; //The intersection doesn't exist, so ignore it.
 195                                         int neigh = maybeAtNeighbor(intersection->second);
 196                                         if (neigh >= 0)
 197                                                 maybeRobber[loc] = certainty + neigh;
 198                                         else
 199                                                 maybeRobber[loc] = -200;
 200                                 }else if (location->second > 0)
 201                                         location->second += certainty;
 202                         }
 203                 }
 204         }else{
 205                 do{
 206                         getline(cin,input);
 207                 }while(input != "from/");
 208         }
 209         _maybeRobber.pop_front();
 210
 211 }
 212
 213 int Cop::maybeAtNeighbor(const Intersection& intersection){
 214         int possibility = -1;
 215         for (hash_map<string,StreetType>::const_iterator adj = intersection.connections.begin();
 216                         adj != intersection.connections.end(); ++adj){
 217                 hash_map<string,int>::iterator oldLoc = _maybeRobber.front().find(adj->first);
 218                 if (oldLoc == _maybeRobber.front().end() || oldLoc->second > 0){
 219                         if (possibility < 0){
 220                                 possibility = 0;
 221                         }
 222                         if (oldLoc != _maybeRobber.front().end())
 223                                 possibility += oldLoc->second;
 224                 }
 225         }
 226         return possibility;
 227 }
 228
 229 void Cop::sendPlan(){
 230         //cerr << "Planning" << endl;
 231         string secondLocation = _robberLocation;
 232         if (_robberLocation.empty()){
 233                 priority_queue<pair<int,string> > positions;
 234                 for (hash_map<string,int>::iterator location = _maybeRobber.front().begin();
 235                                 location != _maybeRobber.front().end(); ++location){
 236                         if (location->second > 0)
 237                                 positions.push(pair<int,string>(location->second,location->first));
 238
 239                 }
 240                 if (positions.size() > 0){
 241                         _robberLocation = positions.top().second;
 242                         cerr << "Sending myself to: " << _robberLocation << ", probability of robber: " << positions.top().first << endl;
 243                 }
 244                 if (positions.size() > 1){
 245                         positions.pop();
 246                         secondLocation = positions.top().second;
 247                         cerr << "Sending another cop to: " << secondLocation << ", probability of robber: " << positions.top().first << endl;
 248                 }
 249         }
 250         if (!_robberLocation.empty()){
 251                 //cerr << "Robber found at " << _robberLocation << endl;
 252                 _copTargets[_name].first = _robberLocation;
 253
 254                 if (!secondLocation.empty()){
 255                         list<string> closestFootCop = shortestPath(_robberLocation, cop_foot, FindPlayer(_players, cop_foot), true);
 256                         list<string> closestCarCop = shortestPath(_robberLocation, cop_car, FindPlayer(_players, cop_car, closestFootCop.size() - 1), true);
 257                         PlayerType copType = cop_foot;
 258                         string copLocation;
 259                         if (closestCarCop.size() > 0){
 260                                 copType = cop_car;
 261                                 copLocation = closestCarCop.back();
 262                         }else
 263                                 copLocation = closestFootCop.back();
 264
 265
 266                         for (hash_map<string,Player>::const_iterator player = _players.begin();
 267                                         player != _players.end(); ++player){
 268                                 if (player->first == _name || player->second.type == robber)
 269                                         continue;
 270                                 if (player->second.type == copType && player->second.location == copLocation)
 271                                         _copTargets[player->first].first = _robberLocation;
 272                         }
 273                 }
 274         }
 275         //cerr << "Sending plan." << endl;
 276         cout << "plan\\" << endl;
 277         for(hash_map<string, pair<string, PlayerType> >::iterator player = _copTargets.begin();
 278                         player != _copTargets.end(); ++player){
 279                         Player& pl = _players[player->first];
 280                 if (pl.type != player->second.second
 281                                 && pl.location != _copHq)
 282                         player->second.second = pl.type;
 283                 list<string> playerRoute = shortestPath(pl.location, player->second.second, SimpleSPGoal(player->second.first));
 284                 if (playerRoute.size() > 1){
 285                         list<string>::iterator i = playerRoute.begin();
 286                         ++i;
 287                         if (*i == _robberLocation || !(playerRoute.size() == 2 && _intersections[*i].type == bank)){
 288                                 if (player->first == _name)
 289                                         _location = *i;
 290                                 //cerr << "Sending " << player->first << " to " << *i << " by " << player->second.second << endl;
 291                                 cout << "plan: " << player->first << " " << *i << " " << _playerTypeNames[player->second.second] << " " << _world+1 << endl;
 292                         }
 293                 }
 294         }
 295
 296         cout << "plan/" << endl;
 297 }
 298
 299 void Cop::getPlans(){
 300         string input;
 301
 302
 303         //ignore From-plan
 304         do{
 305                 getline(cin,input);
 306         }while(input != "from/");
 307
 308
 309 }
 310
 311 void Cop::vote(){
 312         cout << "vote\\" << endl;
 313         cout << "vote: " << _name << endl;
 314         priority_queue<pair<int,string> > players;
 315         for (hash_map<string,int>::const_iterator player = _winningPlans.begin();
 316                         player != _winningPlans.end(); ++player){
 317                 players.push(pair<int,string>(-player->second, player->first));
 318         }
 319         while (players.size() > 0){
 320                 const pair<int,string>& player = players.top();
 321                 cout << "vote: " << player.second << endl;
 322                 //cerr << "voted for " << player.second << " with " << player.first << " previously won plans" << endl;
 323                 players.pop();
 324         }
 325         cout << "vote/" << endl;
 326 }
 327
 328 int main(){
 329         Cop cop("harvCop");
 330         cop.play();
 331
 332         return 0;
 333 }