bot/bot.cpp

   1 #include <iostream>
   2 #include <sstream>
   3 #include <iterator>
   4 #include <queue>
   5 #include <vector>
   6 #include <utility>
   7 #include "bot.h"
   8
   9 using namespace std;
  10 using namespace __gnu_cxx;
  11
  12
  13 Bot::Bot(const string& name, PlayerType type){
  14         _name = name;
  15         _type = type;
  16
  17         _playerTypeNames[robber] = "robber";
  18         _playerTypeNames[cop_foot] = "cop-foot";
  19         _playerTypeNames[cop_car] = "cop-car";
  20
  21         _playerTypes["robber"] = robber;
  22         _playerTypes["cop-foot"] = cop_foot;
  23         _playerTypes["cop-car"] = cop_car;
  24         /*
  25         priority_queue<vector<string>, vector<vector<string> >, VectComp> pq;
  26
  27         vector<string> v;
  28         v.push_back("hej");
  29         pq.push(v);
  30         v.push_back("hå");
  31         pq.push(v);
  32         v.push_back("blaha");
  33         pq.push(v);
  34         v.clear();
  35         v.push_back("hej hå");
  36         pq.push(v);
  37         v.clear();
  38         v.push_back("hejsan");
  39         pq.push(v);
  40         v.push_back("what?");
  41         pq.push(v);
  42         v.push_back("blaha");
  43         pq.push(v);
  44
  45         cerr << "Size: " << pq.top().size() << " " << pq.top()[0] << endl;
  46         pq.pop();
  47         cerr << "Size: " << pq.top().size() << " " << pq.top()[0] << endl;
  48         pq.pop();
  49         cerr << "Size: " << pq.top().size() << " " << pq.top()[0] << endl;
  50         pq.pop();
  51         cerr << "Size: " << pq.top().size() << " " << pq.top()[0] << endl;
  52         pq.pop();
  53         cerr << "Size: " << pq.top().size() << " " << pq.top()[0] << endl;
  54         pq.pop();
  55         cerr << "Size: " << pq.top().size() << " " << pq.top()[0] << endl;
  56         pq.pop();
  57
  58 */
  59
  60 }
  61
  62 void Bot::play(){
  63         cout << "reg: " << _name << " " << _playerTypeNames[_type] << endl;
  64
  65         string input;
  66         getline(cin, input);
  67         if (input != "wsk\\")
  68                 return;
  69         getline(cin, input);
  70         _name = value<string>(input);
  71         cerr << "Got name: " << _name << endl;
  72
  73         //robber and 5 cops
  74         getline(cin, input);
  75         _players[value<string>(input)];
  76         getline(cin, input);
  77         _players[value<string>(input)];
  78         getline(cin, input);
  79         _players[value<string>(input)];
  80         getline(cin, input);
  81         _players[value<string>(input)];
  82         getline(cin, input);
  83         _players[value<string>(input)];
  84
  85         cerr << "Got players, building graph." << endl;
  86         getline(cin, input);
  87         buildGraph();
  88         getline(cin, input);
  89
  90         while (true){
  91                 getline(cin, input);
  92                 if (input == "game-over")
  93                         return;
  94                 updateWorld();
  95                 _type = _players[_name].type;
  96                 _location = _players[_name].location;
  97                 getline(cin, input);
  98                 cerr << "New turn" << endl;
  99                 move(turn());
 100                 cerr << "Done with turn." << endl;
 101         }
 102 }
 103
 104 /**
 105                                 nod\ eol
 106                                 ( nod: loc node-tag coordinate coordinate eol )*
 107                                 nod/ eol
 108                                 edg\ eol
 109                                 ( edg: loc loc edge-type eol )*
 110                                 edg/ eol
 111 */
 112 void Bot::buildGraph(){
 113         string input;
 114         getline(cin, input);
 115         if (input != "nod\\")
 116                 return;
 117
 118         cerr << "Getting intersections" << endl;
 119         while (true){
 120                 getline(cin, input);
 121                 if (input == "nod/")
 122                         break;
 123                 istringstream node(input);
 124                 node >> input;
 125                 node >> input;
 126                 Intersection& inter = _intersections[input];
 127                 node >> input;
 128                 if (input == "bank")
 129                         inter.type = bank;
 130                 else if (input == "hq")
 131                         inter.type = hq;
 132                 else if (input == "robber-start")
 133                         inter.type = robber_start;
 134                 else
 135                         inter.type = ordinary;
 136                 node >> inter.x;
 137                 node >> inter.y;
 138         }
 139
 140         cerr << "Number of intersections: " << _intersections.size() << endl;
 141
 142         getline(cin, input);
 143         if (input != "edg\\")
 144                 return;
 145
 146         cerr << "Getting streets" << endl;
 147         int streets = 0;
 148         while (true){
 149                 getline(cin, input);
 150                 if (input == "edg/")
 151                         break;
 152                 ++streets;
 153                 istringstream street(input);
 154                 string from;
 155                 street >> from;
 156                 street >> from;
 157                 string to;
 158                 street >> to;
 159                 string type;
 160                 street >> type;
 161                 //cerr << "Street between: " << from << " and " << to << " of type: " << type << endl;
 162                 if (type == "foot"){
 163                         _intersections[from].connections[to] = both;
 164                         Intersection& inter = _intersections[to];
 165                         if (inter.connections.find(from) == inter.connections.end())
 166                                 inter.connections[from] = foot;
 167                 }else
 168                         _intersections[from].connections[to] = car;
 169         }
 170         cerr << "Number of streets: " << streets << endl;
 171 }
 172
 173 void Bot::updateWorld(){
 174         string input;
 175         getline(cin,input);
 176         _world = value<int>(input);
 177         //cerr << "World: " << _world << endl;
 178
 179         getline(cin,input);
 180         _robbed = value<int>(input);
 181         //cerr << "Robbed: " << _robbed << endl;
 182
 183         getline(cin,input);
 184         while (true){
 185                 getline(cin, input);
 186                 if (input == "bv/")
 187                         break;
 188                 istringstream bank(input);
 189                 bank >> input;
 190                 bank >> input;
 191                 bank >> _banks[input];
 192         }
 193         //cerr << "Number of banks: " << _banks.size() << endl;
 194
 195         getline(cin,input);
 196         while (true){
 197                 getline(cin, input);
 198                 if (input == "ev/")
 199                         break;
 200                 istringstream evidence(input);
 201                 int world;
 202                 evidence >> input;
 203                 evidence >> input;
 204                 evidence >> world;
 205                 _evidence[world] = input;
 206         }
 207
 208         getline(cin,input);
 209         _smell = value<int>(input);
 210
 211         getline(cin,input);
 212         while (true){
 213                 getline(cin, input);
 214                 if (input == "pl/")
 215                         break;
 216                 istringstream player(input);
 217                 player >> input;
 218                 player >> input;
 219                 //cerr << "Player: " << input << endl;
 220                 Player& pl = _players[input];
 221                 player >> pl.location;
 222                 player >> input;
 223                 pl.type = _playerTypes[input];
 224         }
 225         //cerr << "Number of players: " << _players.size() << endl;
 226 }
 227
 228 void Bot::move(std::string location){
 229         cerr << "Moving to: " << location << endl;
 230         cout << "mov: " << location << " " << _playerTypeNames[_type] << endl;
 231 }
 232
 233 template<class T>
 234 T value(std::string input){
 235         istringstream istr(input);
 236         istr >> input;
 237         T s;
 238         istr >> s;
 239         return s;
 240 }
 241
 242 std::string Bot::turn(){
 243         cerr << "Using stupid stand still Bot::turn" << endl;
 244         return _location;
 245 }
 246
 247 struct SPInfoComp{
 248         bool operator()(const SPInfo* v1, const SPInfo* v2){
 249                 return v1->cost > v2->cost;
 250         }
 251 };
 252
 253 std::list<std::string> Bot::shortestPath(const std::string& from, PlayerType type, const SPGoal& goal){
 254
 255         //cerr << "New shortest path from: " << from << endl;
 256
 257         priority_queue<SPInfo*, vector<SPInfo* >, SPInfoComp > pq;
 258         hash_map<string,SPInfo> nodes;
 259
 260         SPInfo* node = &nodes[from];
 261         node->name = from;
 262         node->settled = false;
 263         node->parent = 0;
 264         node->cost = 0;
 265         pq.push(node);
 266
 267         int g = 0;
 268         while(!pq.empty()){
 269                 node = pq.top();
 270                 pq.pop();
 271                 //cerr << "Vector with size: " << w.size() << endl;
 272                 //cerr << "Looking at: " << node->name << endl;
 273                 //copy(w.begin(), w.end(), ostream_iterator<string>(cerr, " : "));
 274
 275                 g = goal(node);
 276                 if (g < 0)
 277                         break;
 278                 else if (g){
 279                         list<string> l;
 280                         front_insert_iterator<list<string> > ii(l);
 281                         do{
 282                                 *ii++ = node->name;
 283                                 node = node->parent;
 284                         }while (node != 0);
 285                         return l;
 286                 }
 287                 node->settled = true;
 288
 289                 Intersection& inter = _intersections[node->name];
 290                 for (hash_map<string,StreetType>::const_iterator street = inter.connections.begin();
 291                                 street != inter.connections.end(); ++street){
 292                         hash_map<string,SPInfo>::iterator newNode = nodes.find(street->first);
 293                         bool hascar = type == cop_car;
 294                         if ( (hascar &&  (street->second == car || street->second == both)) ||
 295                                         (!hascar && (street->second == foot || street->second == both))){
 296                                 //cerr << "Adding street: " << street->first << endl;
 297                                 SPInfo* n = 0;
 298                                 if (newNode == nodes.end()){
 299                                         n = &nodes[street->first];
 300                                         n->name = street->first;
 301                                         n->settled = false;
 302                                         n->parent = 0;
 303                                         n->cost = 10000;
 304                                 }else if (newNode->second.settled)
 305                                         continue;
 306                                 else
 307                                         n = &newNode->second;
 308
 309                                 if (n->cost > node->cost + 1){
 310                                         n->cost = node->cost + 1;
 311                                         n->parent = node;
 312                                         pq.push(n);
 313                                 }
 314                         }
 315
 316                 }
 317
 318         }
 319
 320         return list<string>();
 321 }