Zen - C++
This Codémon is not here to eat but to fight. He knows that a dead enemy will not stole his apples.
Name| Author |Launch with
Zen GholGoth21 Zen.exe
Strategy
Everybody (excepted CircleOfLife) rush to the apples, but not Zen, not always. If the enemy can reach the food before him, he simply wait at the center (what? but what are you doing here, CircleOfLife?). Else, Zen goes at the apple and turns around while waiting that something happens. In fact, he uses the apple as a bait.
I didn't coded anything against the curious strategy of CircleOfLife because he can only win with very very much luck.
The code
This is the complete code of the C++ project. Cut the 11 source files and the Makefile and compile with make
$ cat src/* Makefile
/*
* @file Enemy.cpp
* @author GholGoth21
* @date Créé le 1 mars 2015 à 14:10
*/
#include "Enemy.h"
#include <fstream>
Enemy::Enemy()
{
}
Enemy::~Enemy()
{
}
std::ostream &operator<<(std::ostream &os, const Enemy& e)
{
return os<<e.m_pos<<" "<<e.m_date;
}
std::istream &operator>>(std::istream &is, Enemy& e)
{
return is>>e.m_pos>>e.m_date;
}
int Enemy::distTo(int2 const &target, int date) const
{
return m_pos.distTo(target)-(date-m_date);
}
bool Enemy::recentActivity(int2 const &pos, int date, int maxDelay) const
{
return pos.distTo(m_pos)<=date-m_date && date-m_date<=maxDelay;
}
/*
* @file Enemy.h
* @author GholGoth21
* @date Créé le 1 mars 2015 à 14:10
*/
#ifndef ENEMY_H
#define ENEMY_H
#include "int2.h"
class Enemy
{
public:
Enemy();
virtual ~Enemy();
public:
void setPos(int2 const &pos, int date) { m_pos=pos; m_date=date; }
int distTo(int2 const &target, int date) const;
int2 const &pos() const { return m_pos; }
bool recentActivity(int2 const &pos, int date, int maxDelay) const;
friend std::ostream &operator<<(std::ostream &os, const Enemy& e);
friend std::istream &operator>>(std::istream &is, Enemy& e);
private:
int2 m_pos;
int m_date;
};
#endif /* ENEMY_H */
/*
* @file Snake.cpp
* @author GholGoth21
* @date Créé le 28 février 2015 à 17:47
*/
#include "Snake.h"
#include "enums.h"
#include "StrManip.h"
#include "Enemy.h"
#include <vector>
#include <cmath>
Snake::Snake(std::string const &body)
{
std::vector<std::string> posList;
split(body, '/', posList);
for(auto &pos : posList)
m_body.push_back(int2(pos));
}
Snake::~Snake()
{
}
Command Snake::move(int2 food, int date, Enemy const &enemy)
{
Command bestCommand[Command::count];
int myDist=curPos().distTo(food);
int enemyDist=enemy.distTo(food,date);
if(myDist>=enemyDist && enemyDist>2)
{
orderCommand(int2(MAPSIZE/2,MAPSIZE/2), bestCommand);
for(int i=0; i<Command::count; i++)
if(validCommand(bestCommand[i]) && !enemy.recentActivity(nextPos(bestCommand[i]),date,5))
return bestCommand[i];
}
if((myDist==1 && enemyDist>((len()-1)/2)*2+3) || enemyDist<-5)
{
orderCommand(food, bestCommand);
for(int i=0; i<Command::count; i++)
if(validCommand(bestCommand[i]))
return bestCommand[i];
}
int2 embushPoint;
int minDist=-1;
foreach_enum(Direction, d)
{
int2 point(food+d.vector());
int dist=point.quadDistTo(enemy.pos());
if(dist<minDist || minDist<0)
{
minDist=dist;
embushPoint=point;
}
}
if(curPos().distTo(embushPoint)<enemy.distTo(embushPoint,date)-((len()-1)/2)*2)
{
int minimalAction=-1;
int qMinDist = curPos().quadDistTo(embushPoint);
Command minimalCommand;
foreach_enum(Command, c)
{
int2 np=nextPos(c);
int qDist = np.quadDistTo(embushPoint);
if((qDist<minimalAction || minimalAction<0) && qDist>qMinDist && validCommand(c))
{
minimalAction=qDist;
minimalCommand=c;
}
}
return minimalCommand;
}
else
{
orderCommand(embushPoint, food, bestCommand);
for(int i=0; i<Command::count; i++)
if(validCommand(bestCommand[i]) && nextPos(bestCommand[i])!=food)
return bestCommand[i];
}
return Command::forward;
}
bool Snake::validCommand(Command c) const
{
if(!c.isValid())
return false;
int2 np = nextPos(c);
if(!(0<np.x && np.x<MAPSIZE-1 && 0<np.y && np.y<MAPSIZE-1))
return false;
for(unsigned int i=2; i<m_body.size()-1; i++)
if(np==m_body.at(i))
return false;
return true;
}
bool Snake::isStarting() const
{
if(m_body.size()==3)
{
if(m_body.at(0)==int2(3,(MAPSIZE)/2) && m_body.at(1)==int2(2,(MAPSIZE)/2) && m_body.at(2)==int2(1,(MAPSIZE)/2))
return true;
else if(m_body.at(0)==int2(MAPSIZE-4,(MAPSIZE)/2) && m_body.at(1)==int2(MAPSIZE-3,(MAPSIZE)/2) && m_body.at(2)==int2(MAPSIZE-2,(MAPSIZE)/2))
return true;
}
return false;
}
void Snake::orderCommand(int2 target, Command *tab)
{
int weight[Command::count];
foreach_enum(Command, c)
{
int2 np = nextPos(c);
weight[c]=np.quadDistTo(target);
tab[c]=c;
}
for(int i=0; i<Command::count-1; i++)
{
while(i>=0 && weight[tab[i]]>weight[tab[i+1]])
{
varSwitch(tab[i], tab[i+1]);
i--;
}
}
}
void Snake::orderCommand(int2 target1, int2 target2, Command *tab)
{
int weight[Command::count];
foreach_enum(Command, c)
{
int2 np = nextPos(c);
weight[c]=np.quadDistTo(target1)+np.quadDistTo(target2);
tab[c]=c;
}
for(int i=0; i<Command::count-1; i++)
{
while(i>=0 && weight[tab[i]]>weight[tab[i+1]])
{
varSwitch(tab[i], tab[i+1]);
i--;
}
}
}
/*
* @file Snake.h
* @author GholGoth21
* @date Créé le 28 février 2015 à 17:47
*/
#ifndef SNAKE_H
#define SNAKE_H
#include "int2.h"
#include <vector>
#define MAPSIZE 15
class Enemy;
class Snake
{
public:
Snake(std::string const &body);
virtual ~Snake();
public:
Command move(int2 food, int date, Enemy const &enemy);
Direction curDir() const { return (m_body.at(0)-m_body.at(1)).direction(); }
int2 curPos() const { return m_body.at(0); }
int2 nextPos(Command c) const { return curPos()+curDir().applyCommand(c).vector(); }
bool validCommand(Command c) const;
bool isStarting() const;
void orderCommand(int2 target, Command *tab);
void orderCommand(int2 target1, int2 target2, Command *tab);
int len() const { return m_body.size(); }
private:
std::vector<int2> m_body;
};
#endif /* SNAKE_H */
/*
* @file StrManip.cpp
* @author GholGoth21
* @date Créé le 7 février 2015 à 17:26
*/
#include "StrManip.h"
#include <sstream>
std::vector<std::string> &split(const std::string &s, char delim, std::vector<std::string> &elems)
{
std::stringstream ss(s);
std::string item;
while(std::getline(ss, item, delim))
elems.push_back(item);
return elems;
}
int atoi(std::string const &text)
{
std::stringstream ss(text);
int val;
ss >> val;
return val;
}
/*
* @file StrManip.h
* @author GholGoth21
* @date Créé le 7 février 2015 à 17:26
*/
#ifndef STRMANIP_H
#define STRMANIP_H
#include <string>
#include <vector>
std::vector<std::string> &split(const std::string &s, char delim, std::vector<std::string> &elems);
int atoi(std::string const &text);
#endif /* STRMANIP_H */
/*
* @file enums.cpp
* @author GholGoth21
* @date Créé le 28 février 2015 à 17:55
*/
#include "enums.h"
#include "int2.h"
Command Direction::turnTo(Direction newDir) const
{
if(!isValid() || !newDir.isValid())
return Command::count; //Invalid
else if((m_value==Direction::up && newDir==Direction::left) || (m_value==Direction::left && newDir==Direction::down) ||
(m_value==Direction::down && newDir==Direction::right) || (m_value==Direction::right && newDir==Direction::up))
return Command::left;
else if((m_value==Direction::up && newDir==Direction::right) || (m_value==Direction::right && newDir==Direction::down) ||
(m_value==Direction::down && newDir==Direction::left) || (m_value==Direction::left && newDir==Direction::up))
return Command::right;
else if(m_value==newDir)
return Command::forward;
else
return Command::count; // Invalid
}
Direction Direction::applyCommand(Command c) const
{
if(c==Command::forward)
return m_value;
else if(c==Command::left)
{
switch(m_value)
{
case Direction::left:
return Direction::down;
case Direction::up:
return Direction::left;
case Direction::right:
return Direction::up;
case Direction::down:
return Direction::right;
default:
break;
}
}
else if(c==Command::right)
{
switch(m_value)
{
case Direction::left:
return Direction::up;
case Direction::up:
return Direction::right;
case Direction::right:
return Direction::down;
case Direction::down:
return Direction::left;
default:
break;
}
}
return Direction::count; // Invalid
}
int2 Direction::vector() const
{
switch(m_value)
{
case Direction::left:
return int2(-1,0);
case Direction::up:
return int2(0,-1);
case Direction::right:
return int2(1,0);
case Direction::down:
return int2(0,1);
default:
return int2(0,0);
}
}
std::ostream &operator<<(std::ostream &os, const Command& c)
{
switch(c.m_value)
{
case Command::left:
return os<<"L";
case Command::right:
return os<<"R";
default:
return os<<"F";
}
}
/*
* @file enums.h
* @author GholGoth21
* @date Créé le 28 février 2015 à 17:55
*/
#ifndef ENUMS_H
#define ENUMS_H
#include <ostream>
struct int2;
#define DECL_ENUM_STRUCT(_name) \
_name() : m_value(static_cast<Type>(0)) {} \
_name(Type value) : m_value(value) {} \
_name(int value) : m_value(static_cast<Type>(value)) {} \
static Type begin() { return static_cast<Type>(0); } \
static Type end() { return count; } \
_name &operator++() { m_value=static_cast<Type>(static_cast<int>(m_value)+1); return *this; } \
operator int() const { return static_cast<Type>(m_value); } \
Type m_value;
#define foreach_enum(_type,_var) for(_type _var = _type::begin(); _var<_type::end(); ++_var)
struct Command
{
enum Type
{
left,
forward,
right,
count
};
bool isValid() const { return m_value<count; }
friend std::ostream &operator<<(std::ostream &os, const Command& c);
DECL_ENUM_STRUCT(Command)
};
struct Direction
{
enum Type
{
left,
up,
right,
down,
count
};
bool isValid() const { return m_value<count; }
Command turnTo(Direction newDir) const;
Direction applyCommand(Command c) const;
int2 vector() const;
DECL_ENUM_STRUCT(Direction)
};
#endif /* ENUMS_H */
/*
* @file int2.cpp
* @author GholGoth21
* @date Créé le 28 février 2015 à 17:37
*/
#include "int2.h"
#include "enums.h"
#include "StrManip.h"
#include <vector>
#include <cmath>
int2::int2()
{
}
int2::~int2()
{
}
int2::int2(std::string const &text)
{
std::vector<std::string> posList;
split(text, ',', posList);
x=atoi(posList.at(0));
y=atoi(posList.at(1));
}
Direction int2::direction() const
{
if(x==0 && y==0)
return Direction::count; // Invalid
else if(y>=std::abs(x))
return Direction::down;
else if(x>=std::abs(y))
return Direction::right;
else if(x<=-std::abs(y))
return Direction::left;
else
return Direction::up;
}
Direction int2::secondary() const
{
if(x==0 || y==0)
return Direction::count; //Invalid
else if(y<=std::abs(x) && y>=0)
return Direction::down;
else if(x<=std::abs(y) && x>=0)
return Direction::right;
else if(x>=-std::abs(y) && x<=0)
return Direction::left;
else
return Direction::up;
}
int int2::distTo(int2 const &other) const
{
return std::abs(x-other.x)+std::abs(y-other.y);
}
int int2::quadDistTo(int2 const &other) const
{
return sq(x-other.x)+sq(y-other.y);
}
int2 int2::operator+(int2 const &other) const
{
return int2(x+other.x,y+other.y);
}
int2 int2::operator-(int2 const &other) const
{
return int2(x-other.x,y-other.y);
}
std::ostream &operator<<(std::ostream &os, const int2& c)
{
return os<<c.x<<","<<c.y;
}
std::istream &operator>>(std::istream &is, int2& c)
{
std::string text;
is>>text;
c=int2(text);
return is;
}
/*
* @file int2.h
* @author GholGoth21
* @date Créé le 28 février 2015 à 17:37
*/
#ifndef INT2_H
#define INT2_H
#include "enums.h"
#include <string>
struct int2
{
public:
int2();
int2(int p_x, int p_y) : x(p_x), y(p_y) {}
int2(std::string const &text);
virtual ~int2();
public:
Direction direction() const;
Direction secondary() const;
int distTo(int2 const &other) const;
int quadDistTo(int2 const &other) const;
int2 operator+(int2 const &other) const;
int2 operator-(int2 const &other) const;
bool operator==(int2 const &other) const { return x==other.x && y==other.y; }
bool operator!=(int2 const &other) const { return x!=other.x || y!=other.y; }
friend std::ostream &operator<<(std::ostream &os, const int2& c);
friend std::istream &operator>>(std::istream &is, int2& c);
public:
int x;
int y;
};
inline int sq(int val) { return val*val; }
template<typename T>
inline void varSwitch(T &a, T &b) { T tmp=a; a=b; b=tmp; }
#endif /* INT2_H */
/*
* @file main.cpp
* @author GholGoth21
* @date Créé le 28 février 2015 à 17:23
*/
#include "int2.h"
#include "Snake.h"
#include "Enemy.h"
#include <cstdlib>
#include <iostream>
#include <fstream>
using namespace std;
/*
* @brief La fonction principale du programme.
* @param argc Le nombre de paramètres passés en ligne de commandes.
* @param argv La liste des paramètres passés en ligne de commandes.
*/
int main(int argc, char** argv)
{
/* Error handling */
if(argc<3)
{
cerr<<"Error : not enough arguments on the command line."<<endl;
cout<<"F"<<endl;
return 1;
}
/* Init and load */
int2 prevFood;
int date = 0;
Enemy enemy;
ifstream load("PreviousState.txt");
if(load)
{
load>>date;
load>>prevFood;
load>>enemy;
load.close();
}
int2 food(argv[1]);
Snake me(argv[2]);
if(me.isStarting())
{
date=0;
if(me.curPos().x<MAPSIZE/2)
enemy.setPos(int2(MAPSIZE-4,MAPSIZE/2), 0);
else
enemy.setPos(int2(3,MAPSIZE/2), 0);
}
else if(prevFood!=food && me.curPos()!=prevFood)
{
enemy.setPos(prevFood, date);
}
/* Moving */
cout<<me.move(food,date,enemy)<<endl;
/* Saving */
ofstream save("PreviousState.txt");
if(save)
{
save<<++date<<endl;
save<<food<<endl;
save<<enemy<<endl;
save.close();
}
return 0;
}
# Makefile
HEADERS = $(wildcard $(SRCPATH)/*.h)
SOURCES = $(wildcard $(SRCPATH)/*.cpp)
OBJECTS = $(patsubst $(SRCPATH)/%.cpp,$(BUILDPATH)/%.o,$(SOURCES))
M = Makefile
CFLAGS = -Wall -std=c++11
BINPATH = bin
BUILDPATH = build
SRCPATH = src
ifeq ($(OS),Windows_NT)
EXE = Zen.exe
else
EXE = Zen
endif
$(BINPATH)/$(EXE): $(BINPATH) $(BUILDPATH) $(OBJECTS)
g++ -o $@ $(OBJECTS)
$(BUILDPATH)/%.o: $(SRCPATH)/%.cpp $(HEADERS) $M
g++ $(CFLAGS) -o $@ -c $<
$(BINPATH) $(BUILDPATH):
mkdir $@
clean:
rm $(OBJECTS)
Or download the zip file : Zen.zip
Results
| Name | Master | Score |
|--------------|------------|-------|
| Zen | GholGoth21 | 24 |
| SneakySnake | Cipher | 10 |
| ViciousViper | Cipher | 6 |
| CircleOfLife | Manu | 4 |
And some typical battles (ViciousViper vs Zen and SneakySnake vs Zen) :
Edit : I add this very intersting battle against CircleOfLife :
1I suppose ties result in no points (like if both snakes run into each other, or hit the wall on the same turn)? – Zgarb – 2015-02-24T13:44:39.677
12I'm not sure how much interesting interacting strategies you'll get if bots have almost no way of knowing where any other bots are. – Martin Ender – 2015-02-24T13:49:51.267
6Since we're limited to length <7, even knowing where the opponent is only matters for avoidance. You're not really long enough to do anything but the simplest of blocking. I suspect that most matches will just come down to who was closest to each food as it spawned. – Geobits – 2015-02-24T13:59:31.177
Will we know if we are facing a new bot or the same as the one in the last match? Like the data files will be deleted if a new bot will be the opponent. (We probably want to find out the tactic of the opponent through matches.) – randomra – 2015-02-24T14:24:51.457
7I had an amazing plan for how to do really really well in this. Then I read the rules more. If you can't see the other snake your options are really "take the direct path" or "take some longer path". Neither are very interesting if it is just dumb luck avoiding the other snake. – captncraig – 2015-02-24T16:17:32.327
8I don't think you guys have thought this through. When your enemy takes an apple, you know exactly where he is. You can then predict the path he will take to the current apple. You may figure out you can reach it first with no chance of collision, or you may lay a trap by dragging your tail across his likely path. You can also estimate his strategy by how long it takes him to get an apple, or when he has collided with your tail in previous games. And, of course, he knows that you know that he knows...etc. Excellent puzzle Cipher +1. – Logic Knight – 2015-02-25T02:54:50.080
2The idea behind this was like CarpetPython said, it's about finding the right balance between playing hide-and-seek and actual Snake – Cipher – 2015-02-25T07:54:33.467
4I'm thinking about creating a separated tournament with more focus on the original game and stuff like seeing your opponent, increased length limit, etc. Anyone interested? – Cipher – 2015-02-25T08:01:32.733
1@CarpetPython: +1 for the insight – justhalf – 2015-02-25T11:47:28.757
@CarpetPython There was a bit of talk in chat about that, but I'm unconvinced it will matter that much in practice. Hopefully I'm wrong, but we'll see :) – Geobits – 2015-02-25T13:37:01.010