V
Jester schrieb:
So, die Auswertung ist fertig: http://wpc.schornboeck.net/viewtopic.php?p=351#351
du hast meine einsendung also nicht mehr genommen. schade.
falls es jemanden interessiert. er hat 342.803 punkte.
weil mein internet-provider einen server-umzug nicht hinkriegt, konnte ich am freitag abend keine mail verschicken. hab's erst samstag bemerkt und erst um um 13:44 es geschafft, jester eine mail zu schicken. der isp hat an jester auch eine mail geschickt, in der er sagt, daß der server nicht geht und deswegen ich keine mail absetzen konnte.
#include "Agent.h" // inheriting class's header file
#include <cstddef>
class Volkard:public Agent{
private:
template<class T,size_t SIZE>
class RingBuffer{
private:
size_t write;
size_t read;
T data[SIZE];
public:
RingBuffer(){
read=0;
write=0;
}
bool empty(){
return write==read;
}
void push(T const& t){
data[write]=t;
++write;
write%=SIZE;
}
T& front(){
return data[read];
}
void pop(){
++read;
read%=SIZE;
}
};
typedef unsigned int u32;
typedef u32 Map;
//W: wall
//x: datenfeld
//WWWWWWWWxxxxWxxxxWxxxxWxxxxWWWWW
//10987654321098765432109876543210
//links oben ist 5
//rechts oben ist 8
static const Map WALL=0xFF08421F;
//11111111000010000100001000011111
//WWWWWWWWxxxxWxxxxWxxxxWxxxxWWWWW
static const Map START=1<<20;
typedef u32 Position;
static Position moveLeft(Position pos){
return pos>>=1;
}
static Position moveRight(Position pos){
return pos<<=1;
}
static Position moveUp(Position pos){
return pos>>=5;
}
static Position moveDown(Position pos){
return pos<<=5;
}
typedef u32 Direction;
static Direction turnLeft(Direction dir){
return (dir+1)%4;
}
static Direction turnRight(Direction dir){
return (dir+3)%4;
}
static Position move(Position pos,Direction dir){
switch(dir){
case 0: return moveRight(pos);
case 1: return moveUp(pos);
case 2: return moveLeft(pos);
case 3: return moveDown(pos);
}
return 0;//only to make the compiler happy
}
struct PosDir{
Position position;
Direction direction;
PosDir(){
};
PosDir(Position pos,Direction dir):
position(pos),
direction(dir){
}
static int findFirstBitTrue(Position x){
int result=0;
while((x&1)==0){
x>>=1;
++result;
}
return result;
}
int pack() const{
//WWWWWWWWxxxxWxxxxWxxxxWxxxxWWWWW
return findFirstBitTrue(position>>5)*4+direction;
}
};
Position position;
Direction direction;
Map visited;
Map pit;
Map monster;
Map unknown;//ich war noch nie in der nachbarschaft
bool gold;
bool shot;
static Map getNeighbours(Position pos){
Map neighbours=moveLeft(pos)|moveUp(pos);
neighbours|=moveRight(moveDown(neighbours));
return neighbours;
}
static Map removeNear(Map map,Position pos){
return map&~getNeighbours(pos);
}
static Map removeNotNear(Map map,Position pos){
return map&getNeighbours(pos);
}
static int population(Map x){
int result=0;
while(x){
x&=(x-1);
++result;
}
return result;
}
static int value(Position position,Map val1,Map val2){
//zielfeld bewerten, falls wegsuche mehrere gleich weit entfernte ziele findet
//kleine ergebnisse sind gut
return 55-10*population(getNeighbours(position)&val1)-population(getNeighbours(position)&val2);
}
static int calcDistance(Position position,Direction direction,Map interest,Map blocked,Map val1,Map val2){
if(position&blocked) return 1000000;
if(position&interest) return (100*1)+value(position,val1,val2);
//einfachste breitensuche
char dist[19*4]={0};
dist[PosDir(position,direction).pack()]=1;
RingBuffer<PosDir,32> toDo;
toDo.push(PosDir(position,direction));
while(!toDo.empty()){
PosDir here=toDo.front();
toDo.pop();
PosDir next[3]={
PosDir(here.position,turnLeft(here.direction)),
PosDir(move(here.position,here.direction),here.direction),
PosDir(here.position,turnRight(here.direction))
};
for(int i=0;i<3;++i){
PosDir const& there=next[i];
if(there.position&blocked) continue;
if(there.position&interest) return 100*(dist[here.pack()]+1)+value(there.position,val1,val2);
int thereid=there.pack();
if(dist[thereid]) continue;
dist[thereid]=dist[here.pack()]+1;
toDo.push(there);
}
}
return 1000000;
}
Action think(Sense const& sense){
//sofort-aktionen
if(gold) return FINISH;
if(sense.glitter) return GRAB;
//keine sofort-aktionen gefunden, also erstmal sensor-daten einspeisen
if(sense.scream) monster=0;
if(!(position&visited)){
visited|=position;
unknown=removeNear(unknown,position);
if(!sense.breeze)
pit=removeNear(pit,position);
if(!sense.stench)
monster=removeNear(monster,position);
else
monster=removeNotNear(monster,position);
}
//unbesuchtes ungefõhrliches feld suchen
if(Map interest=~visited&~pit&~monster&~WALL){
Map blocked=pit|monster|WALL;
Map val1=~visited&~pit&~monster&~WALL;
Map val2=unknown&~WALL;
int dl=calcDistance(position,turnLeft(direction),interest,blocked,val1,val2);
int dm=calcDistance(move(position,direction),direction,interest,blocked,val1,val2);
int dr=calcDistance(position,turnRight(direction),interest,blocked,val1,val2);
if(dl<dm && dl<dr) return TURN_LEFT;
if(dr<dm && dr<dl) return TURN_RIGHT;
if(dl<dm && dr<dm) return TURN_RIGHT;
return MOVE;
}
//nix ungefõhrliches mehr da.
//dann ballere ich mal das monster ab
if(Map interest=monster&~pit&~WALL){
if(shot) return FINISH;//ups, zwecklos
if(move(position,direction)&monster) return SHOOT;//haha, ich hab dich!
Map blocked=pit|WALL;
Map val1=~visited&~pit&~monster&~WALL;
Map val2=unknown&~WALL;
int dl=calcDistance(position,turnLeft(direction),interest,blocked,val1,val2);
int dm=calcDistance(move(position,direction),direction,interest,blocked,val1,val2);
int dr=calcDistance(position,turnRight(direction),interest,blocked,val1,val2);
if(dl<dm && dl<dr) return TURN_LEFT;
if(dr<dm && dr<dl) return TURN_RIGHT;
if(dl<dm && dr<dm) return TURN_RIGHT;
return MOVE;
}
//schade, nix mehr zu holen
return FINISH;
}
public:
Volkard():
position(START),
direction(0),
visited(0),
pit(~WALL&~START),
monster(~WALL&~START),
unknown(~WALL&~START),
gold(false),
shot(false){
}
virtual ~Volkard(){
}
virtual Action decideNextAction(Sense sense){
Action action=think(sense);
switch(action){
case TURN_LEFT:
direction=turnLeft(direction);
break;
case TURN_RIGHT:
direction=turnRight(direction);
break;
case MOVE:
position=move(position,direction);
break;
case GRAB:
gold=true;
break;
case SHOOT:
//ich schie▀e nur, wenn es stinkt
monster&=~move(position,direction);
shot=true;
break;
case FINISH:
break;
}
return action;
}
static char const* getName(){
return "volkard";
}
static char const* getMail(){
return "volkard@normannia.de";
}
static Agent* createAgent(){
return new Volkard;
}
static void destroyAgent(Agent* agent){
delete agent;
}
};