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 Bot::~Bot(){
 105 }
 106
 107 /**
 108                                 nod\ eol
 109                                 ( nod: loc node-tag coordinate coordinate eol )*
 110                                 nod/ eol
 111                                 edg\ eol
 112                                 ( edg: loc loc edge-type eol )*
 113                                 edg/ eol
 114 */
 115 void Bot::buildGraph(){
 116         string input;
 117         getline(cin, input);
 118         if (input != "nod\\")
 119                 return;
 120
 121         cerr << "Getting intersections" << endl;
 122         while (true){
 123                 getline(cin, input);
 124                 if (input == "nod/")
 125                         break;
 126                 istringstream node(input);
 127                 node >> input;
 128                 node >> input;
 129                 Intersection& inter = _intersections[input];
 130                 node >> inter.type;
 131                 node >> inter.x;
 132                 node >> inter.y;
 133         }
 134
 135         cerr << "Number of intersections: " << _intersections.size() << endl;
 136
 137         getline(cin, input);
 138         if (input != "edg\\")
 139                 return;
 140
 141         cerr << "Getting streets" << endl;
 142         int streets = 0;
 143         while (true){
 144                 getline(cin, input);
 145                 if (input == "edg/")
 146                         break;
 147                 ++streets;
 148                 istringstream street(input);
 149                 string from;
 150                 street >> from;
 151                 street >> from;
 152                 string to;
 153                 street >> to;
 154                 string type;
 155                 street >> type;
 156                 //cerr << "Street between: " << from << " and " << to << " of type: " << type << endl;
 157                 if (type == "foot"){
 158                         _intersections[from].connections[to] = both;
 159                         Intersection& inter = _intersections[to];
 160                         if (inter.connections.find(from) == inter.connections.end())
 161                                 inter.connections[from] = foot;
 162                 }else
 163                         _intersections[from].connections[to] = car;
 164         }
 165         cerr << "Number of streets: " << streets << endl;
 166 }
 167
 168 void Bot::updateWorld(){
 169         string input;
 170         getline(cin,input);
 171         _world = value<int>(input);
 172         //cerr << "World: " << _world << endl;
 173
 174         getline(cin,input);
 175         _robbed = value<int>(input);
 176         //cerr << "Robbed: " << _robbed << endl;
 177
 178         getline(cin,input);
 179         while (true){
 180                 getline(cin, input);
 181                 if (input == "bv/")
 182                         break;
 183                 istringstream bank(input);
 184                 bank >> input;
 185                 bank >> input;
 186                 bank >> _banks[input];
 187         }
 188         //cerr << "Number of banks: " << _banks.size() << endl;
 189
 190         getline(cin,input);
 191         while (true){
 192                 getline(cin, input);
 193                 if (input == "ev/")
 194                         break;
 195                 istringstream evidence(input);
 196         }
 197
 198         getline(cin,input);
 199         _smell = value<int>(input);
 200
 201         getline(cin,input);
 202         while (true){
 203                 getline(cin, input);
 204                 if (input == "pl/")
 205                         break;
 206                 istringstream player(input);
 207                 player >> input;
 208                 player >> input;
 209                 //cerr << "Player: " << input << endl;
 210                 Player& pl = _players[input];
 211                 player >> pl.location;
 212                 player >> input;
 213                 pl.type = _playerTypes[input];
 214         }
 215         //cerr << "Number of players: " << _players.size() << endl;
 216 }
 217
 218 void Bot::move(std::string location){
 219         cerr << "Moving to: " << location << endl;
 220         cout << "mov: " << location << " " << _playerTypeNames[_type] << endl;
 221 }
 222
 223 template<class T>
 224 T value(std::string input){
 225         istringstream istr(input);
 226         istr >> input;
 227         T s;
 228         istr >> s;
 229         return s;
 230 }
 231
 232 std::string Bot::turn(){
 233         cerr << "Using stupid stand still Bot::turn" << endl;
 234         return _location;
 235 }
 236
 237 struct SPInfo{
 238         string name;
 239         bool settled;
 240         SPInfo* parent;
 241         int cost;
 242 };
 243
 244 struct SPInfoComp{
 245         bool operator()(const SPInfo* v1, const SPInfo* v2){
 246                 return v1->cost > v2->cost;
 247         }
 248 };
 249
 250 std::list<std::string> Bot::shortestPath(const std::string& from, const std::string& to, PlayerType type){
 251
 252         priority_queue<SPInfo*, vector<SPInfo* >, SPInfoComp > pq;
 253         hash_map<string,SPInfo> nodes;
 254
 255         SPInfo* node = &nodes[from];
 256         node->name = from;
 257         node->settled = false;
 258         node->parent = 0;
 259         node->cost = 0;
 260         pq.push(node);
 261
 262         while(!pq.empty()){
 263                 node = pq.top();
 264                 pq.pop();
 265                 //cerr << "Vector with size: " << w.size() << endl;
 266                 //cerr << "Looking at: " << w.back() << endl;
 267                 //copy(w.begin(), w.end(), ostream_iterator<string>(cerr, " : "));
 268                 if (node->name == to){
 269                         list<string> l;
 270                         front_insert_iterator<list<string> > ii(l);
 271                         do{
 272                                 *ii++ = node->name;
 273                                 node = node->parent;
 274                         }while (node != 0);
 275                         return l;
 276                 }
 277                 node->settled = true;
 278
 279                 Intersection& inter = _intersections[node->name];
 280                 for (hash_map<string,StreetType>::const_iterator street = inter.connections.begin();
 281                                 street != inter.connections.end(); ++street){
 282                         hash_map<string,SPInfo>::iterator newNode = nodes.find(street->first);
 283                         bool hascar = type == cop_car;
 284                         if ( (hascar &&  (street->second == car || street->second == both)) ||
 285                                         (!hascar && (street->second == foot || street->second == both))){
 286                                 SPInfo* n = 0;
 287                                 if (newNode == nodes.end()){
 288                                         n = &nodes[street->first];
 289                                         n->name = street->first;
 290                                         n->settled = false;
 291                                         n->parent = 0;
 292                                         n->cost = 10000;
 293                                 }else if (newNode->second.settled)
 294                                         continue;
 295                                 else
 296                                         n = &newNode->second;
 297
 298                                 if (n->cost > node->cost + 1){
 299                                         n->cost = node->cost + 1;
 300                                         n->parent = node;
 301                                         pq.push(n);
 302                                 }
 303                         }
 304
 305                 }
 306
 307         }
 308
 309         return list<string>();
 310 }