import java.io.*;
import java.net.*;
import java.util.*;
import java.awt.Point;
/*****/
class Player
{
public int m_pid;
public Point m_pos;
public int m_bombs;
public int m_str;
public int m_speed;
public boolean m_infict;
public int m_controlSum;
private int m_bonuses; // 0x000...00gggbbbb; g - good, b - bad
public Player() {}
public Player(int _pid, Point _pos, int _bombs, int _bombsStrength, int _speed, boolean _isInfected) {
m_pid = _pid; m_pos = _pos; m_bombs = _bombs; m_str = _bombsStrength; m_speed = _speed; m_infict = _isInfected;
}
public void controlSumUpdate() {
m_controlSum = (m_bombs << 8) + (m_str << 4) + m_speed;
}
/** Add bonus to bit-mask */
public void addBonus (char _b) {
switch (_b) {
case 'b': m_bonuses |= m_goodBonus[0]; break;
case 'v': m_bonuses |= m_goodBonus[1]; break;
case 'f': m_bonuses |= m_goodBonus[2]; break;
case 'r': m_bonuses |= m_badBonus[0]; m_infict = true; break;
case 's': m_bonuses |= m_badBonus[1]; m_infict = true; break;
case 'u': m_bonuses |= m_badBonus[2]; m_infict = true; break;
case 'o': m_bonuses |= m_badBonus[3]; m_infict = true; break;
}
}
/** Remove bonus from bit-mask */
public void delBonus (char _b ) {
m_infict = true;
switch (_b) {
case 'r': m_bonuses &= ~m_badBonus[0]; m_infict = false; break;
case 's': m_bonuses &= ~m_badBonus[1]; m_infict = false; break;
case 'u': m_bonuses &= ~m_badBonus[2]; m_infict = false; break;
case 'o': m_bonuses &= ~m_badBonus[3]; m_infict = false; break;
default: int error = 0; int isHere = 1 / error; // If (WTF?!) -> Throw hidden exception!!!
}
}
public void randomAdd()
{
int newControlSum = (m_bombs << 8) + (m_str << 4) + m_speed;
newControlSum = (m_controlSum ^ newControlSum);
if (newControlSum == 0) {} //TODO: check for bonuses 'r' and 'u' should be resolved in some way...
else if ((newControlSum >>= 4) == 0) {
if(m_infict) addBonus('s');
else addBonus('v');
}
else if ((newControlSum >>= 4) == 0) addBonus('f');
else {
if(m_infict) addBonus('o');
else addBonus('b');
}
controlSumUpdate();
}
public boolean checkBonus (char _b) {
switch (_b) {
case 'b': return (m_bonuses & m_goodBonus[0]) != 0;
case 'v': return (m_bonuses & m_goodBonus[1]) != 0;
case 'f': return (m_bonuses & m_goodBonus[2]) != 0;
case 'r': return (m_bonuses & m_badBonus[0]) != 0;
case 's': return (m_bonuses & m_badBonus[1]) != 0;
case 'u': return (m_bonuses & m_badBonus[2]) != 0;
case 'o': return (m_bonuses & m_badBonus[3]) != 0;
}
/* throw hidden exception!!! */
int error = 0; int isHere = 1 / error;
return false;
}
public final int[] m_goodBonus = {0x40, 0x20, 0x10}; // 'b', 'v', 'f'
public final int[] m_badBonus = {0x8, 0x4, 0x2, 0x1}; // 'r', 's', 'u', 'o'
}
/*****/
class Bomb implements Cloneable, Comparable<Bomb>
{
public Point m_pos;
public int m_radius;
public int m_timer;
public Bomb (Point _pos, int _damage, int _time) {
m_pos = _pos;
m_radius = _damage;
m_timer = _time;
}
public Bomb clone() {
Bomb copy = new Bomb(m_pos, m_radius, m_timer);
return copy;
}
public int compareTo(Bomb _rhs) {
if (m_timer != _rhs.m_timer) return m_timer - _rhs.m_timer;
else return m_radius - _rhs.m_radius;
}
}
/*****/
public class BotEnv
{
private SocketMaster m_SM;
private AlgoBrain m_AB;
private Parser m_P;
// connection parameters
private String m_host;
private int m_port;
// World's state
public char[][] m_map;
public Player[] m_enemies;
public ArrayList<Bomb> m_bombs;
public int m_scale;
public int m_tick;
// Bot's state
Player m_bot;
public Point m_ourBomb;
public BotEnv(String[] _args) {
m_host = _args[0];
m_port = Utils.parseInt(_args[1]);
m_SM = new SocketMaster(this, m_host, m_port);
m_P = new Parser(this);
m_AB = new AlgoBrain(this);
m_bot = new Player();
m_tick = -1;
}
public String proccessComand (String _cmd) {
if(m_SM.isAvailable())
{
System.out.println("Past time");
}
else
System.out.println("Realtime");
boolean analysis = m_P.parse(_cmd);
return m_tick == -1 ? "" : m_AB.processTactics(analysis);
}
public static void main(String[] _args) {
new BotEnv(_args).m_SM.run();
}
// debug
public void traceMap() {
System.out.println("========================");
for (int i = 0; i < m_map.length; i++) System.out.println(m_map[i]);
System.out.println("========================");
}
public final int BOMB_TIME_TICKS = 40;
public final int MAP_MAX_SIZE = 25;
}
/*** Powerful bot's brain mega-buster!!! **/
class AlgoBrain
{
private BotEnv m_BE;
private int[][] m_dangerMap;
private int[][] m_tmpDangerMap;
private int[] m_par;
private int[] m_queue;
private int[] m_used;
private ArrayList<Integer> m_steps;
private ArrayList<Integer> m_tmpSteps;
private int m_internalCounter;
private boolean m_stayHereTactick;
public AlgoBrain (BotEnv _bptr) {
m_BE = _bptr;
m_dangerMap = new int[m_BE.MAP_MAX_SIZE][m_BE.MAP_MAX_SIZE];
m_tmpDangerMap = new int[m_BE.MAP_MAX_SIZE][m_BE.MAP_MAX_SIZE];
m_par = new int[CACHE_SIZE];
m_queue = new int[CACHE_SIZE];
m_used = new int[CACHE_SIZE];
m_steps = new ArrayList<Integer>();
m_tmpSteps = new ArrayList<Integer>();
}
public String processTactics(boolean _analysis) {
boolean putBomb = false;
int x = m_BE.m_bot.m_pos.x / m_BE.m_scale;
int y = m_BE.m_bot.m_pos.y / m_BE.m_scale;
int nx = -1, ny = -1, need = -1;
if (!m_stayHereTactick && m_steps.size() != 0) {
need = m_steps.get(m_steps.size() - 1); nx = need >> 5; ny = need & 0x1F;
if (x == nx && y == ny)
m_steps.remove(m_steps.size() - 1);
}
if (_analysis || (m_steps.size() == 0 && !m_stayHereTactick)) {
m_stayHereTactick = false;
makeDangerMap(m_dangerMap);
System.out.println(m_dangerMap[y][x]);
if (m_dangerMap[y][x] == Integer.MAX_VALUE) {
m_BE.m_bombs.add(new Bomb(new Point(x, y), m_BE.m_bot.m_str, m_BE.m_tick + m_BE.BOMB_TIME_TICKS));
makeDangerMap(m_tmpDangerMap);
int dangerLvl = getBestPath(m_tmpDangerMap, m_tmpSteps);
m_BE.m_bombs.remove(m_BE.m_bombs.size() - 1);
if (dangerLvl == Integer.MAX_VALUE) { ArrayList<Integer> tmp = m_steps; m_steps = m_tmpSteps; m_tmpSteps = tmp; putBomb = true; }
else {
m_stayHereTactick = false;
getBestPath(m_dangerMap, m_steps);
}
}
// TODO: make this O(1) by LinkedList without ArrayList
else getBestPath(m_dangerMap, m_steps);
}
String res = null;
if (m_stayHereTactick) res = "s";
else {
if (need != m_steps.get(m_steps.size() - 1)) { need = m_steps.get(m_steps.size() - 1); nx = need >> 5; ny = need & 0x1F; }
if (nx == x - 1 && ny == y) res = "l";
else if (nx == x && ny == y + 1) res = "d";
else if (nx == x + 1 && ny == y) res = "r";
else if (nx == x && ny == y - 1) res = "u";
/* throw hidden exception!!! */
else {
System.out.println("LOSE CONTROL!");
//int error = 0; int isHere = 1 / error;
return processTactics(true);
}
}
if (putBomb) { res += 'b'; m_BE.m_ourBomb = new Point(x, y); }
System.out.println(res);
return res + ';';
}
private void makeDangerMap(int[][] _map) {
final int mapWidth = m_BE.m_map[0].length;
final int mapHeight = m_BE.m_map.length;
int head, tail;
char[][] map = m_BE.m_map;
Bomb[] bombs = new Bomb[m_BE.m_bombs.size()];
boolean[] used = new boolean[bombs.length];
// Sort bombs in appriate way
for (int i = 0; i < bombs.length; i++)
bombs[i] = m_BE.m_bombs.get(i).clone();
Arrays.sort(bombs);
// Fill all cells as safe
for (int i = 0; i < mapHeight; i++)
for (int j = 0; j < mapWidth; j++)
_map[i][j] = (map[i][j] == '.') ? Integer.MAX_VALUE : -1;
/*
* Paint the dangerous map by performing BFS (1st) on bombs array
* to pay attention to detonation process
* TODO: update knowing burst speed!
*/
int k, cx, cy, r, t;
for (int i = 0; i < bombs.length; i++)
{
if (used[i]) continue;
head = tail = 0;
m_queue[tail++] = i;
while (tail != head)
{
k = m_queue[head++];
cx = bombs[k].m_pos.x; cy = bombs[k].m_pos.y;
r = bombs[k].m_radius; t = bombs[k].m_timer - m_BE.m_tick;
_map[cy][cx] = t;
left: for (int dx = cx-1; dx >= cx-r; dx--)
if (dx < 0 || _map[cy][dx] == -1) break;
else if (map[cy][dx] != 'B') _map[cy][dx] = Math.min(_map[cy][dx], t);
else if (dx != cx) for (int j = 0; j < bombs.length; j++)
if (bombs[j].m_pos.x == dx && bombs[j].m_pos.y == cy)
{ bombs[j].m_timer = t; m_queue[tail++] = j; break left; }
right: for (int dx = cx+1; dx <= cx+r; dx++) // Go right
if (dx == mapWidth || _map[cy][dx] == -1) break;
else if (map[cy][dx] != 'B') _map[cy][dx] = Math.min(_map[cy][dx], t);
else if (dx != cx) for (int j = 0; j < bombs.length; j++)
{ bombs[j].m_timer = t; m_queue[tail++] = j; break right; }
up: for (int dy = cy-1; dy >= cy-r; dy--) // Go up
if (dy < 0 || _map[dy][cx] == -1) break;
else if (map[dy][cx] != 'B') _map[dy][cx] = Math.min(_map[dy][cx], t);
else if (dy != cy) for (int j = 0; j < bombs.length; j++)
if (bombs[j].m_pos.x == cx && bombs[j].m_pos.y == dy)
{ bombs[j].m_timer = t; m_queue[tail++] = j; break up; }
down: for (int dy = cy+1; dy <= cx+r; dy++) // Go down
if (dy == mapHeight || _map[dy][cx] == -1) break;
else if (map[dy][cx] != 'B') _map[dy][cx] = Math.min(_map[dy][cx], t);
else if (dy != cy) for (int j = 0; j < bombs.length; j++)
if (bombs[j].m_pos.x == cx && bombs[j].m_pos.y == dy)
{ bombs[j].m_timer = t; m_queue[tail++] = j; break down; }
}
}
// System.out.println("==============================");
// for (int i = 0; i < mapHeight; i++) {
// for (int j = 0; j < mapWidth; j++)
// if (_map[i][j] == Integer.MAX_VALUE)
// System.out.printf("%s\t", "I");
// else
// System.out.printf("%d\t", _map[i][j]);
// System.out.println("");
// }
// System.out.println("==============================");
}
// Provide 1 BFS correctness
private int queueInitPack (int[][] _map, int _pos) {
final int sz = m_BE.m_scale, W = m_BE.m_map[0].length, H = m_BE.m_map.length;
int x = m_BE.m_bot.m_pos.x, y = m_BE.m_bot.m_pos.y;
int[] dist = new int[4], p = new int[4];
dist[0] = x%sz; dist[1] = sz - y%sz;
dist[2] = sz - x%sz; dist[3] = y%sz;
for (int i = 0; i < 4; i++) p[i] = i;
for (int i = 1; i < 4; i++) {
int j = i, v = p[i];
while (j > 0 && dist[v] < dist[p[j-1]])
{ p[j] = p[j-1]; j--; }
p[j] = v;
}
int num = 0;
for (int i = 0; i < 4; i++) {
int x2 = x/sz + DX[p[i]], y2 = y/sz + DY[p[i]];
if (x2 >= 0 && x2 < W && y2 >= 0 && y2 < H && _map[y2][x2] != -1) {
int pos2 = (x2 << 5) + y2;
m_queue[num++] = pos2;
m_used[pos2] = m_internalCounter;
m_par[pos2] = _pos;
}
}
return num;
}
/*
* Paint the dangerous map by performing BFS (1st) on bombs array
* to pay attention to detonation process
* TODO: update knowing burst speed!
*/
private int getBestPath(int[][] _map, ArrayList<Integer> _steps)
{
_steps.clear();
Player bot = m_BE.m_bot;
int x, y, tail = 0, head = 0;
final int sz = m_BE.m_scale, mapWidth = m_BE.m_map[0].length, mapHeight = m_BE.m_map.length, INF = Integer.MAX_VALUE;
int dangerLvl = -1, best = -1;
int X = bot.m_pos.x/sz, Y = bot.m_pos.y/sz;
int pos = (X << 5) + Y;
m_par[pos] = -1;
m_used[pos] = ++m_internalCounter;
tail = queueInitPack(_map, pos);
for (int i = 0; i < tail; i++) {
x = m_queue[i] >> 5; y = m_queue[i] & 0x1F;
if (_map[y][x] > dangerLvl) {
best = m_queue[i];
dangerLvl = _map[y][x];
}
}
bfs: while (tail != head)
{
pos = m_queue[head++];
x = pos >> 5; y = pos & 0x1F;
for (int i = 0; i < 4; i++) {
int x2 = x + DX[i], y2 = y + DY[i];
int pos2 = (x2 << 5) + y2;
if (x2 >= 0 && x2 < mapWidth && y2 >= 0 && y2 < mapHeight
&& m_used[pos2] != m_internalCounter && _map[y2][x2] != -1)
{
m_used[pos2] = m_internalCounter;
m_queue[tail++] = pos2;
m_par[pos2] = pos;
if (_map[y2][x2] > dangerLvl) {
dangerLvl = _map[y2][x2];
best = pos2;
if (dangerLvl == INF)
break bfs;
}
}
}
}
while (m_par[best] != -1) {
_steps.add(best);
best = m_par[best];
}
// Is the best choice to do nothing?
if (dangerLvl != INF && _map[Y][X] == INF) {
m_stayHereTactick = true;
_steps.clear();
return INF;
}
return dangerLvl;
}
private final byte[] DX = {-1, 0, 1, 0};
private final byte[] DY = {0, 1, 0, -1};
private final int CACHE_SIZE = 1 << 10;
}
/*****/
class Parser
{
private BotEnv m_BE;
public Parser(BotEnv _bptr) {
m_BE = _bptr;
}
public boolean parse (String _cmd) {
switch(_cmd.charAt(0)) {
case 'P': playerIdComand(_cmd); break;
case 'S': startComand(_cmd); break;
case 'R': roundEnd(_cmd); break;
case 'G': gameEnd(_cmd); break;
case 'T': return timerTick(_cmd);
}
return false;
}
private void playerIdComand (String _cmd) {
// At this stage map is ignored
m_BE.m_bot.m_pid = Utils.parseInt(_cmd, 3);
}
private void startComand (String _cmd) {
m_BE.m_bombs = new ArrayList<Bomb>(20);
int idx = _cmd.indexOf('&') + 1;
m_BE.m_scale = Utils.parseInt(_cmd, idx);
String[] map = _cmd.split("\r\n");
int h = map.length, w = map[1].length();
m_BE.m_map = new char[h-1][w];
for (int i = 1; i < h; i++)
for (int j = 0; j < w; j++)
m_BE.m_map[i-1][j] = map[i].charAt(j);
m_BE.traceMap();
}
private boolean timerTick (String _cmd) {
boolean needAnalysis = false;
String[] parts = _cmd.trim().split("&");
for (int p = 0; p < parts.length; p++)
if (p == 0) parseTickTimePart(parts[p]);
else if (p == 1) parseTickSapkaPart(parts[p]);
else if (p == 2 && parts[p].length() != 0) needAnalysis = parseTickChangesPart(parts[p]);
//else if (p == 3 && parts[p].length() != 0) parseTickDangerPart(parts[p]);
return needAnalysis;
}
private void parseTickTimePart (String _cmd) {
m_BE.m_tick = Utils.parseInt(_cmd.substring(1));
}
private void parseTickSapkaPart (String _cmd) {
int pid;
Player link;
String[] pl = _cmd.trim().split(",");
String[] cur;
if (m_BE.m_enemies == null) {
m_BE.m_enemies = new Player[pl.length-1];
for (int i = 0; i < pl.length-1; i++)
m_BE.m_enemies[i] = new Player();
}
int k = 0;
for (int i = 0; i < pl.length; i++) {
cur = pl[i].trim().split(" ");
pid = Utils.parseInt(cur[0], 1);
link = (pid == m_BE.m_bot.m_pid) ? m_BE.m_bot : m_BE.m_enemies[k++];
if (cur.length == 2) link.m_pos.x = -1;
else {
link.m_pos = new Point(Utils.parseInt(cur[1]), Utils.parseInt(cur[2]));
link.m_bombs = Utils.parseInt(cur[3]);
link.m_str = Utils.parseInt(cur[4]);
link.m_speed = Utils.parseInt(cur[5]);
link.m_infict = cur.length == 7;
//m_BE.traceMap();
}
}
}
private boolean parseTickChangesPart (String _cmd) {
boolean needTactickAnalysis = false;
String[] changes = _cmd.split(","), current;
boolean isAdded = false; // Add or remove
char type, mapMark;
int x, y, pid = 0;
for (int i = 0; i < changes.length; i++) {
current = changes[i].trim().split(" "); // Parse <change-info>
isAdded = current[0].charAt(0) == '+'; // Parse common parts
type = current[0].charAt(1);
x = Utils.parseInt(current[1]);
y = Utils.parseInt(current[2]);
mapMark = isAdded ? type : '.';
switch (type)
{
case '*': // Bomb
{
Point pos = new Point(x, y);
if (pos.equals(m_BE.m_ourBomb)) {
if (!isAdded) m_BE.m_ourBomb = null;
}
else needTactickAnalysis = true;
if (pos.equals(m_BE.m_ourBomb) == false) needTactickAnalysis = true;
if (isAdded) m_BE.m_bombs.add(new Bomb(pos, Utils.parseInt(current[3]), Utils.parseInt(current[4])));
else for (int k = 0; k < m_BE.m_bombs.size(); k++)
if (m_BE.m_bombs.get(k).m_pos.equals(pos)) {
m_BE.m_bombs.remove(k);
break;
}
} break;
case '#': // Explode
{
mapMark = '.';
} break;
case 'w': // Destructable wall
{
} break;
case 'X': // Indestructable wall
{
} break;
default: // Bonuses
{
if (((m_BE.m_bot.m_pos.x/m_BE.m_scale) == x) &&((m_BE.m_bot.m_pos.y/m_BE.m_scale) == y)) {
if (!isAdded){
m_BE.m_bot.addBonus(type);
}}
else{
for(int j = 0; j<m_BE.m_enemies.length-1;++j){
if (((m_BE.m_enemies[j].m_pos.x/m_BE.m_scale) == x )&&((m_BE.m_enemies[j].m_pos.y/m_BE.m_scale) == y )) {
pid = j;
break;
}}
if (!isAdded && (pid != 0)){
m_BE.m_enemies[pid].addBonus(type); }}
} break;
}
m_BE.m_map[y][x] = mapMark;
m_BE.traceMap();
}
return needTactickAnalysis;
}
private void roundEnd(String _cmd) {
m_BE.m_enemies = null;
m_BE.m_bombs = null;
m_BE.m_tick = -1;
}
private void gameEnd(String _cmd) {
// Nothing to do...
}
}
/*****/
class SocketMaster
{
private BotEnv m_BE;
private Socket m_sock;
private BufferedReader m_in;
private PrintWriter m_out;
private String get;
public SocketMaster (BotEnv _bptr, String _host, int _port) {
m_BE = _bptr;
try {
m_sock = new Socket(_host, _port);
m_in = new BufferedReader(new InputStreamReader(m_sock.getInputStream()));
m_out = new PrintWriter(m_sock.getOutputStream());
} catch (Exception _e) {
_e.printStackTrace();
}
}
public void run() {
m_out.println(INIT_STRING);
m_out.flush();
int idx, startdx;
boolean started = false;
String startLex = "PID";
// Here we going to get all fucking shit, from task details to input stream...
String cmd = "";
get= "";
char[] buf = new char[255];
int len;
try {
while(((len = m_in.read(buf))!= -1)){
get += String.copyValueOf(buf, 0, len);
if (!started) {
if ((startdx = get.indexOf(startLex)) != -1) {
started = true;
get = get.substring(startdx);
}
else {
continue;
}
}
idx = get.indexOf(';');
if (idx != -1) {
cmd = get.substring(0,idx);
get = get.substring(idx + 1);
System.out.println(cmd);
// IMPORTANT! Here we will instantly give out solution response!!!
m_out.print(m_BE.proccessComand(cmd) + ";");
m_out.flush();
}
}
} catch (Exception _e) {
_e.printStackTrace();
}
}
public boolean isAvailable()
{
try {
if((m_sock.getInputStream().available()>0) || (get.length()>0))
return true;
} catch (Exception _e) {
_e.printStackTrace();
}
return false;
}
private final String INIT_STRING = "launch heratorz CFGSrUPQPKgtmDcKuOhgCSy#CFGwjQJiWQQUViJiymrQoGY#CFGUfimkSUQhcMgGMqlWQYs#CFGWYiZmCiYpYaYWZuBspkg#CFGAEeaubIIRkDOlIxGmyPM#CFGYLEQYicsFWmjwKmXaOmC#CFGufAMuyIOhKxKaSOxoxUN#CFGowmRWjWSWxcZiqlGeYkF#CFGUpogIViMtiOkulA@IYoZ#CFGQOwAkDwyVAZCoKTqFuyJ#CFGMSYfClQgVEaUuinytily#CFGyNQRgQmanQxKmUAXEepm;";
}
/*****/
class Utils
{
static public int parseInt(String _str, int _startIndex) {
int number = 0, len = _str.length();
char ch;
while (_startIndex < len) {
ch = _str.charAt(_startIndex);
if (ch >= '0' && ch <= '9') { number = number * 10 + ch - '0'; _startIndex++; }
else break;
}
return number;
}
static public int parseInt(String _str) {
return parseInt(_str, 0);
}
// static public String[] split(String _str, char _delim)
// {
// int c = 1; // Number of parts
// for (int i = 0; i < _str.length(); i++) if (_str.charAt(i) == _delim) c++;
//
// String[] result = new String[c];
//
// int left = 0, k = 0;
// for (int right = 0; right < _str.length(); right++)
// {
// result[k++] = _str.substring(left, right);
// left = ++right;
// }
// result[k++] = _str.substring(left);
//
// return result;
// }
}