Skip to content

Instantly share code, notes, and snippets.

@izanbf1803
Created September 12, 2017 21:32
Show Gist options
  • Save izanbf1803/504eb9cb9f521660408c885e3af5d34c to your computer and use it in GitHub Desktop.
Save izanbf1803/504eb9cb9f521660408c885e3af5d34c to your computer and use it in GitHub Desktop.
codingame.com tron bot
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <array>
#include <algorithm>
#include <cmath>
using namespace std;
#define null (-1)
#define RIGHT (0)
#define UP (1)
#define LEFT (2)
#define DOWN (3)
#define WIDTH (30)
#define HEIGHT (20)
#define DEPTH 2
typedef struct {
short x, y;
} Point;
typedef struct {
Point p;
short owner;
} VP; // Voronoi point
typedef struct {
Point p;
short dir;
} Player;
Point operator+(const Point a, const Point b) {
return {a.x + b.x, a.y + b.y};
}
Point operator-(const Point a, const Point b) {
return {a.x - b.x, a.y - b.y};
}
bool operator==(const Point a, const Point b) {
return a.x == b.x and a.y == b.y;
}
ostream& operator<<(ostream& o, const Point p) {
return o << "p{ " << p.x << ", " << p.y << " }";
}
template <typename T>
ostream& operator<<(ostream& o, const vector<T> v) {
o << "v{ ";
for (T elem : v)
o << elem << ' ';
o << '}';
return o;
}
const array<Point, 4> dirs = {{
{+1, 0}, // R
{0, -1}, // U
{-1, 0}, // L
{0, +1}, // D
}};
const array<string, 4> str_dirs = {{ "RIGHT", "UP", "LEFT", "DOWN" }};
static int P; // your player number (0 to 3).
static int N; // total number of players (2 to 4).
static vector<Player> players;
static vector<vector<short>> grid;
static deque<short> moves;
void show_grid() { // DEBUG
for (auto elem : grid)
cerr << elem << endl;
cerr << endl;
}
void show_vnoi(const vector<vector<short>>& vnoi) { // DEBUG
for (auto elem : vnoi)
cerr << elem << endl;
cerr << endl;
}
inline int dist(const Point a, const Point b) // manhattan
{
return abs(a.x - b.x) + abs(a.y - b.y);
}
array<short, 3> genPossibleDirs(const vector<Player>& _players)
{
return array<short, 3> {{
(_players[P].dir - 1) % dirs.size(),
_players[P].dir,
(_players[P].dir + 1) % dirs.size(),
}};
}
// Returns area of self player
int flood_fill(vector<vector<short>>& vnoi, const vector<Player>& _players)
{
int area = 0;
deque<VP> q;
for (int i = 0; i < N; i++) {
if (players[i].p == (Point){-1, -1}) continue;
q.push_back({_players[i].p, i});
}
while (not q.empty()) {
VP cp = q.front(); q.pop_front();
if (vnoi[cp.p.y][cp.p.x] != null) continue;
vnoi[cp.p.y][cp.p.x] = cp.owner;
if (cp.owner == P) area++;
for (int i = 0; i < dirs.size(); i++) {
Point np = cp.p + dirs[i];
if (np.x < 0 or np.y < 0 or np.x >= WIDTH or np.y >= HEIGHT or grid[np.y][np.x] != null)
continue;
q.push_back({np, cp.owner});
}
}
return area;
}
int gen_voronoi(const vector<Player>& _players, int depth)
{
vector<vector<short>> vnoi = vector<vector<short>>(HEIGHT, vector<short>(WIDTH, null));
int area = flood_fill(vnoi, _players);
if (depth > 1) {
array<short, 3> possibleDirs = genPossibleDirs(_players);
for (int i = 0; i < possibleDirs.size(); i++) {
vector<Player> __players__ = _players;
__players__[P].p = __players__[P].p + dirs[possibleDirs[i]];
Point p = __players__[P].p;
if (p.x < 0 or p.y < 0 or p.x >= WIDTH or p.y >= HEIGHT or grid[p.y][p.x] != null)
continue;
area += gen_voronoi(__players__, depth - 1);
}
}
return area;
}
int choice_dir()
{
int area = 0;
int bestDirIndex = null;
array<short, 3> possibleDirs = genPossibleDirs(players);
for (int i = 0; i < possibleDirs.size(); i++) {
vector<Player> _players = players;
_players[P].p = _players[P].p + dirs[possibleDirs[i]];
Point p = _players[P].p;
if (p.x < 0 or p.y < 0 or p.x >= WIDTH or p.y >= HEIGHT or grid[p.y][p.x] != null)
continue;
int newArea = gen_voronoi(_players, DEPTH);
if (bestDirIndex == null or newArea > area) {
area = newArea;
bestDirIndex = possibleDirs[i];
}
}
return bestDirIndex;
}
int main()
{
// cerr << showpos; // Show + sign, just for alignment with negative
grid = vector<vector<short>>(HEIGHT, vector<short>(WIDTH, null));
moves = deque<short>();
while (1) {
cin >> N >> P; cin.ignore();
if (players.size() < N)
players = vector<Player>(N, {{null, null}, null});
cerr << "N: " << N << endl;
for (int i = 0; i < N; i++) {
Point oldPos = players[i].p;
int x0; // starting X coordinate of lightcycle (or -1)
int y0; // starting Y coordinate of lightcycle (or -1)
cin >> x0 >> y0 >> players[i].p.x >> players[i].p.y; cin.ignore();
if (i == P) {
cerr << "ME: " << P << " " << players[i].p << endl;
}
if (players[i].p == (Point){-1, -1}) continue; // Player died
grid[players[i].p.y][players[i].p.x] = i;
if (oldPos.x != null) {
cerr << players[i].p - oldPos << endl;
players[i].dir = find(dirs.begin(), dirs.end(), players[i].p - oldPos) - dirs.begin();
}
cerr << i << " " << players[i].p << " "
<< players[i].dir << " "
<< (players[i].dir != -1 ? str_dirs[players[i].dir] : "") << endl;
}
if (moves.empty())
moves.push_back(choice_dir());
cerr << "DIR: " << moves.front() << endl;
if (moves.front() == -1) return 0; // Can't move
players[P].dir = moves.front();
cout << str_dirs[moves.front()] << endl; // A single line with UP, DOWN, LEFT or RIGHT
moves.pop_front();
}
}
@izanbf1803
Copy link
Author

It's not finished, currently it has some bugs, but it's starting to work.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment