X-Git-Url: https://ruin.nu/git/?p=icfp05.git;a=blobdiff_plain;f=bot%2Fbot.cpp;h=28e8004a2167997f2b5a8bbe629a486ac03f6711;hp=8946d03f6feba2764407b3f0dedd7174a6c0acc6;hb=d7d9942fc9d1066670e166182e36791dfbf035d7;hpb=1e91b29637d981acb253bc4be7d0eeab63602790 diff --git a/bot/bot.cpp b/bot/bot.cpp index 8946d03..28e8004 100644 --- a/bot/bot.cpp +++ b/bot/bot.cpp @@ -1,18 +1,31 @@ #include #include #include +#include +#include +#include #include "bot.h" using namespace std; using namespace __gnu_cxx; -Bot::Bot(string name, string type){ + +Bot::Bot(const string& name, PlayerType type){ _name = name; _type = type; + + _playerTypeNames[robber] = "robber"; + _playerTypeNames[cop_foot] = "cop-foot"; + _playerTypeNames[cop_car] = "cop-car"; + + _playerTypes["robber"] = robber; + _playerTypes["cop-foot"] = cop_foot; + _playerTypes["cop-car"] = cop_car; + } void Bot::play(){ - cout << "reg: " << _name << " " << _type << endl; + cout << "reg: " << _name << " " << _playerTypeNames[_type] << endl; string input; getline(cin, input); @@ -22,22 +35,11 @@ void Bot::play(){ _name = value(input); cerr << "Got name: " << _name << endl; - //robber and 5 cops - getline(cin, input); - _players[value(input)].type = "robber"; - getline(cin, input); - _players[value(input)].type = "cop-foot"; - getline(cin, input); - _players[value(input)].type = "cop-foot"; - getline(cin, input); - _players[value(input)].type = "cop-foot"; - getline(cin, input); - _players[value(input)].type = "cop-foot"; + getPlayers(); cerr << "Got players, building graph." << endl; getline(cin, input); buildGraph(); - getline(cin, input); while (true){ getline(cin, input); @@ -46,12 +48,25 @@ void Bot::play(){ updateWorld(); _type = _players[_name].type; _location = _players[_name].location; - getline(cin, input); + cerr << "New turn" << endl; move(turn()); + cerr << "Done with turn." << endl; } } -Bot::~Bot(){ +void Bot::getPlayers(){ + string input; + //robber and 5 cops + getline(cin, input); + _players[value(input)].type = robber; + getline(cin, input); + _players[value(input)].type = cop_foot; + getline(cin, input); + _players[value(input)].type = cop_foot; + getline(cin, input); + _players[value(input)].type = cop_foot; + getline(cin, input); + _players[value(input)].type = cop_foot; } /** @@ -77,7 +92,15 @@ void Bot::buildGraph(){ node >> input; node >> input; Intersection& inter = _intersections[input]; - node >> inter.type; + node >> input; + if (input == "bank") + inter.type = bank; + else if (input == "hq") + inter.type = hq; + else if (input == "robber-start") + inter.type = robber_start; + else + inter.type = ordinary; node >> inter.x; node >> inter.y; } @@ -98,10 +121,12 @@ void Bot::buildGraph(){ istringstream street(input); string from; street >> from; + street >> from; string to; street >> to; string type; street >> type; + //cerr << "Street between: " << from << " and " << to << " of type: " << type << endl; if (type == "foot"){ _intersections[from].connections[to] = both; Intersection& inter = _intersections[to]; @@ -111,17 +136,18 @@ void Bot::buildGraph(){ _intersections[from].connections[to] = car; } cerr << "Number of streets: " << streets << endl; + getline(cin, input); } void Bot::updateWorld(){ string input; getline(cin,input); _world = value(input); - cerr << "World: " << _world << endl; + //cerr << "World: " << _world << endl; getline(cin,input); _robbed = value(input); - cerr << "Robbed: " << _robbed << endl; + //cerr << "Robbed: " << _robbed << endl; getline(cin,input); while (true){ @@ -133,7 +159,7 @@ void Bot::updateWorld(){ bank >> input; bank >> _banks[input]; } - cerr << "Number of banks: " << _banks.size() << endl; + //cerr << "Number of banks: " << _banks.size() << endl; getline(cin,input); while (true){ @@ -141,6 +167,11 @@ void Bot::updateWorld(){ if (input == "ev/") break; istringstream evidence(input); + int world; + evidence >> input; + evidence >> input; + evidence >> world; + _evidence[world] = input; } getline(cin,input); @@ -154,16 +185,19 @@ void Bot::updateWorld(){ istringstream player(input); player >> input; player >> input; - cerr << "Player: " << input << endl; + //cerr << "Player: " << input << endl; Player& pl = _players[input]; player >> pl.location; - player >> pl.type; + player >> input; + pl.type = _playerTypes[input]; } - cerr << "Number of players: " << _players.size() << endl; + //cerr << "Number of players: " << _players.size() << endl; + getline(cin, input); } void Bot::move(std::string location){ - cout << "mov: " << location << " " << _type << endl; + cerr << "Moving to: " << location << endl; + cout << "mov: " << location << " " << _playerTypeNames[_type] << endl; } template @@ -176,6 +210,121 @@ T value(std::string input){ } std::string Bot::turn(){ + cerr << "Using stupid stand still Bot::turn" << endl; return _location; } +struct SPInfoComp{ + bool operator()(const SPInfo* v1, const SPInfo* v2){ + return v1->cost > v2->cost; + } +}; + +std::list Bot::shortestPath(const std::string& from, PlayerType type, const SPGoal& goal, bool reverse){ + + //cerr << "New shortest path from: " << from << endl; + + priority_queue, SPInfoComp > pq; + hash_map nodes; + + SPInfo* node = &nodes[from]; + node->name = from; + node->settled = false; + node->parent = 0; + node->cost = 0; + pq.push(node); + + int g = 0; + bool hascar = type == cop_car; + while(!pq.empty()){ + node = pq.top(); + pq.pop(); + //cerr << "Vector with size: " << w.size() << endl; + //cerr << "Looking at: " << node->name << endl; + //copy(w.begin(), w.end(), ostream_iterator(cerr, " : ")); + + g = goal(node); + if (g < 0) + break; + else if (g){ + list l; + front_insert_iterator > ii(l); + do{ + *ii++ = node->name; + node = node->parent; + }while (node != 0); + return l; + } + node->settled = true; + + Intersection& inter = _intersections[node->name]; + for (hash_map::const_iterator street = inter.connections.begin(); + street != inter.connections.end(); ++street){ + hash_map::iterator newNode = nodes.find(street->first); + bool travelStreet = false; + if (hascar){ + if (reverse){ + if (street->second != foot){ + hash_map::const_iterator st = _intersections[street->first].connections.find(node->name); + if (st != _intersections[street->first].connections.end()) + travelStreet = st->second != foot; + else + travelStreet = false; + }else + travelStreet = true; + }else + travelStreet = street->second != foot; + }else{ + travelStreet = street->second != car; + } + if (travelStreet){ + //cerr << "Adding street: " << street->first << endl; + SPInfo* n = 0; + if (newNode == nodes.end()){ + n = &nodes[street->first]; + n->name = street->first; + n->settled = false; + n->parent = 0; + n->cost = 10000; + }else if (newNode->second.settled) + continue; + else + n = &newNode->second; + + if (n->cost > node->cost + 1){ + n->cost = node->cost + 1; + n->parent = node; + pq.push(n); + } + } + + } + + } + + return list(); +} + +SimpleSPGoal::SimpleSPGoal(std::string to):_to(to){ +} + +int SimpleSPGoal::operator()(const SPInfo* node) const{ + if (node->name == _to) + return 1; + return 0; +} + +FindPlayer::FindPlayer(const hash_map& players, PlayerType type, int limit) : _players(players), _type(type), _limit(limit){ +} + +int FindPlayer::operator()(const SPInfo* node) const{ + if (_limit > 0 && node->cost >= _limit) + return -1; + for(hash_map::const_iterator player = _players.begin(); + player != _players.end(); ++player){ + if (player->second.type == _type && player->second.location == node->name){ + return 1; + } + } + return 0; +}