title: Battle for the Petri Dish

text:
# Question
Title: Battle for the Petri Dish
In this challenge, you must design a species of single-celled organisms to fight to the death in the petri-dish arena. The arena is represented as a rectangular grid, where each cell occupies one space:

```
.....x....
...x...o..
...x.c..o.
.......o..

```

## Attributes

Every cell has three attributes. When specifying your cell species at the start of the game, you allocate 12 points among these attributes.

* **Hit Points** (HP): If a cell's HP falls to zero, it dies. New cells have full HP.
    + When a cell dies, it leaves behind a corpse which can be eaten by other cells for energy.
    + A cell cannot regain lost HP, but it can create a new cell with full HP by dividing.
* **Energy**: Most actions a cell can take require energy. By actively resting, a cell can regain lost energy up to it species' maximum.
    + A cell species with less than 5 energy is likely to fail, because it cannot divide to create new cells.
    + A cell cannot regain energy beyond its species' maximum value.
    + A newly created cell has an initial energy value copied from its parent (and a max value dictated by its species specification).
* **Acidity**: If a cell chooses to explode, the cell's acidity level is used in calculating damage to adjacent cells.

## Actions

Each turn, every cell can take one action:

* **Move:** The cell moves one space in any direction (N/S/E/W/NE/NW/SE/SW) at a cost of 1 energy.

+ A cell cannot move onto a space occupied by another living cell.
    + A cell cannot move off of the grid.
    + Moving onto a cell corpse destroys the corpse.
* **Attack:** A cell attacks an adjacent cell, dealing 1 to 3 damage, by expending 1 to 3 energy points.

+ A cell can attack in any direction (N/S/E/W/NE/NW/SE/SW).
    + It is legal to attack friendly cells.
* **Divide:** The cell divides and creates a new cell on an adjacent space, at a cost of 5 energy.

+ A cell can divide in any direction (N/S/E/W/NE/NW/SE/SW).
    + The new cell has full HP according to your original cell specification.
    + The new cell has as much energy as its parent cell does after subtracting division cost. (For example, a parent cell with an initial 8 energy points will be reduced to 3 energy and produce a child cell with 3 energy).
    + A new cell cannot act until your next turn.
    + A cell cannot divide into an space occupied by a living cell, but it can divide into a space occupied by a dead cell corpse (this destroys the corpse).
* **Eat:** A cell eats an adjacent cell corpse, gaining 4 energy.

+ A cell can eat in any direction (N/S/E/W/NE/NW/SE/SW).
* **Rest:** A cell does nothing for one turn, regaining 2 energy.
* **Explode:** When a cell has 3 or fewer HP and more energy than HP, it may choose to explode, dealing damage to all eight adjacent cells.

+ Damage to each adjacent cell is `(exploding cell HP) + (explodng cell acidity)`
    + An exploded cell dies and leaves behind a corpse, as do any cells killed in the explosion.

## Protocol

### Setup

Your program will run with the string `BEGIN` provided on stdin. Your program must write to stdout a space-separated list of 3 non-negative integers, representing HP, energy, and acidity for your cell species: e.g., `5 6 1`. The numbers must sum to 12. Acidity may be `0`, if you wish. (Other attributes may also be zero, but doing so functionally forfeits the game!)

You begin with one cell, in the northwest or southeast corner, one space away from either edge. The beginning cell has full HP and energy.

### Every cells acts

Every turn, your program will be invoked once for every cell alive on your team (except cells just created this turn) so that cell can act. Your program is provided with data on stdin that includes the petri dish state and information about this particular cell:

```
10 4
..........
..xx.c....
...c...o..
......o...

6 3 5 7

```

The first two numbers indicate arena width and height: here, there is a 10-by-4 arena.

* The `o` cells are yours; the `x` cells are your enemies. (This is always true; each player always sees their own cells as `o`.)
* The `.` spaces are empty.
* The `c` spaces represent edible cell corpses.

The numbers after the empty line represent info about this cell:

* The first two numbers are `x,y` coordinates, indexed from `0,0` in the top left (so `6 3` here refers to the south-most `o` cell).
* The third number is the cell's HP; the fourth number is the cell's energy.

Your program should output (to stdout) an action. In the examples below, we'll use `N` as an example direction, but it can be any direction legal for that action (`N`/`S`/`E`/`W`/`NE`/`NW`/`SE`/`SW`). All program output is case-insensitive, but examples will use uppercase. Any output action that is invalid (either because it has invalid syntax or attempts an illegal action) is ignored and results in the cell `REST`ing (and thus gaining 2 energy).

* `MOVE N`
* `DIVIDE N`
* `EAT N`
* `ATTACK N 2` \- the number represents the strength of the attack (1 - 3)
* `REST`
* `EXPLODE`

Your team's turn consists of all your cells being given an opportunity to act, one by one. All of your cells act before any of the opponent's cells act. Once all of your cells act, your turn ends, and your opponent's turn begins. Once all your opponent's cells act, your turn begins again. Within your turn, each cell is given priority to act based on its age: the oldest cells on your team act first before younger cells.

## Example

Here's how a program might behave. Input from stdin is denoted here with leading `>` arrows (separated from actual input by a clarifying space) and output on stdout has `<` arrows.

```
> BEGIN
< 5 6 1

```

Then, the program is invoked again:

```
> 10 4
> ..........
> .o........
> ........x.
> ..........
>
> 1 1 5 6
< DIVIDE SE

```

After your opponent's turn (who decided to `DIVIDE W` with the single starting cell), your program is invoked twice, once for each cell:

```
> 10 4
> ..........
> .o........
> ..o....xx.
> ..........
>
> 1 1 5 1
< MOVE E

```

For the second invocation on your turn:

```
> 10 4
> ..........
> ..o.......
> ..o....xx.
> ..........
>
> 2 2 5 1
< MOVE SE

```

Note this second cell sees the updated board state based on the other cell's movement earlier in your turn. Also note this cell has been created with 1 energy, because the parent cell had 6 energy when it performed division last turn (so the original 6, minus the 5-energy cost of division, created a child cell with 1 energy).

Now your turn is over and your opponent's turn begins. The two opposing cells will be given a chance to act, and then your next turn begins.

## Victory

You can win by either:

* Destroying all opposing cells, or
* Having more cells than your opponent after each player has completed 150 turns

Scoring will be based on number of wins in 100 games against each other submission. In half of the simulations, your program will be allowed to go first.

Tie games (i.e. exactly the same number of cells after 150 turns, or the only remaining cells are killed together in an explosion) are not counted in either player's win totals.

## Other information

* Your program should not attempt to maintain state (beyond using the state of the Petri dish): monocellular organisms do not have a very good memory and react to the world moment by moment. In particular, writing to a file (or other data store), communicating with a remote server, or setting environment variables are explicitly disallowed.
* Submissions will be run/compiled on Ubuntu 12.04.4.
* The specifics of the 100 scoring games are not yet confirmed, but they will likely involve multiple arena sizes (for example, 50 runs on a small arena and 50 runs on a larger arena). For a larger arena, I may increase the max turn count to ensure that a proper battle can take place.

## Resources

Here is the driver code that runs the simulation, written for Node.js, called by `node petri.js 'first program' 'second program'`. For example, pitting a Python-written cell against a Java-written cell might look like `node petri.js 'python some_cell.py' 'java SomeCellClass'`.

Additionally, I understand that reading and parsing multiple lines on stdin can be a huge pain, so I've drafted a few complete sample cells in different languages which you are free to build upon, completely overhaul, or ignore entirely.

Of course you are free to write a cell in a different language; these are simply three languages I decided to write boilerplate code for as a time-saving aid.

If you have any problems running the driver, feel free to ping me in the chat room I've created for this challenge. If you don't have sufficient reputation for chat, then just leave a comment.

# Answer
Here's my relatively simple bot, which I programmed in Ruby. Basically, it prioritizes dividing first, and attempts to divide towards enemies in order to gain control over the field. Its second priority is eating, and third is attacking. It easily beat the sample Python cell.

```
def surroundingCells(x, y)
  result = Hash.new
  if x >= 1
    if y >= 1
      # northwest
      result["NW"] = $petriDish[x - 1][y - 1]
    end
    if y < ($sizeY - 1) # $sizeY - 1 is the farthest south square
      # southwest
      result["SW"] = $petriDish[x - 1][y + 1]
    end
      # west
      result["W"] = $petriDish[x - 1][y]
  end
  if x < ($sizeX - 1)
    if y >= 1
      # northeast
      result["NE"] = $petriDish[x + 1][y - 1]
    end
    if y < ($sizeY - 1)
      # southeast
      result["SE"] = $petriDish[x + 1][y + 1]
    end
    # east
    result["E"] = $petriDish[x + 1][y]
  end
  # north
  result["N"] = $petriDish[x][y - 1] if y >= 1
  # south
  result["S"] = $petriDish[x][y + 1] if y < ($sizeY - 1)
  return result
end

def directionTowardsEnemies(locX, locY)
  totalXDirections = 0
  totalYDirections = 0
  totalTargetsFound = 0 # enemies or corpses
  optimalDirections = []
  for x in 0..($petriDish.length - 1)
    for y in 0..($petriDish[0].length - 1)
      if $petriDish[x][y] == 'c' or $petriDish[x][y] == 'x'
        totalXDirections += (x - locX)
        totalYDirections += (y - locY)
        totalTargetsFound += 1
      end
    end
  end
  if totalXDirections == 0
    if totalYDirections > 0
      optimalDirections << "S" << "SE" << "SW"
    else
      optimalDirections << "N" << "NE" << "NW"
    end
    return optimalDirections
  end
  if totalYDirections == 0
    if totalXDirections > 0
      optimalDirections << "E" << "NE" << "SE"
    else
      optimalDirections << "W" << "NW" << "SW"
    end
    return optimalDirections
  end
  if totalXDirections > 0
    if totalYDirections > 0
      optimalDirections << "SE"
      if totalYDirections > totalXDirections
        optimalDirections << "S" << "E"
      else
        optimalDirections << "E" << "S"
      end
    else
      optimalDirections << "NE"
      if -totalYDirections > totalXDirections
        optimalDirections << "N" << "E"
      else
        optimalDirections << "E" << "N"
      end
    end
    return optimalDirections
  end
  if totalXDirections < 0
    if totalYDirections > 0
      optimalDirections << "SW"
      if totalYDirections > -totalXDirections
        optimalDirections << "S" << "W"
      else
        optimalDirections << "W" << "S"
      end
    else
      optimalDirections << "NW"
      if -totalYDirections > -totalXDirections
        optimalDirections << "N" << "W"
      else
        optimalDirections << "W" << "N"
      end
    end
  end
  return optimalDirections
end

firstLine = gets
if firstLine == "BEGIN"
  puts "5 7 0"
  exit 0
end
$sizeX, $sizeY = firstLine.split(' ')[0].to_i, firstLine.split(' ')[1].to_i
$petriDish = Array.new($sizeX) { Array.new($sizeY) }
for y in 0..($sizeY - 1)
  line = gets
  chars = line.split('').reverse.drop(1).reverse # this gets every character but     the last
  for x in 0..(chars.length - 1)
    $petriDish[x][y] = chars[x]
  end
end
gets # blank line
info = gets
locX = info.split(' ')[0].to_i
locY = info.split(' ')[1].to_i
hp = info.split(' ')[2].to_i
energy = info.split(' ')[3].to_i

# dividing is our first priority
if(energy >= 5)
  # try to divide towards enemies
  dirs = directionTowardsEnemies(locX, locY)
  directions = { "N" => [0, -1], "NE" => [1, -1], "E" => [1, 0],
    "SE" => [1, 1], "S" => [0, 1], "SW" => [-1, 1],
    "W" => [-1, 0], "NW" => [-1, -1] }
  for dir in dirs
    potentialNewX = locX + directions[dir][0]
    potentialNewY = locY + directions[dir][1]
    if $petriDish[potentialNewX][potentialNewY] == '.'
      puts "DIVIDE #{dir}"
      exit 0
    end
  end
  # otherwise, just divide somewhere.
  surroundingCells(locX, locY).each do |k, v|
    if v == '.'
      puts "DIVIDE #{k}"
      exit 0
    end
  end
end

# next, eating
surroundingCells(locX, locY).each do |k, v|
  if v == 'c'
    puts "EAT #{k}"
    exit 0
  end
end

# next, attacking
surroundingCells(locX, locY).each do |k, v|
  attackStrength = 0
  if (energy > 5) then # we want to save energy for dividing
    attackStrength = [(energy - 5), 3].min
  else
    attackStrength = [energy, 3].min
  end
  if v == 'x'
    puts "ATTACK #{k} #{attackStrength}"
    exit 0
  end
end

# otherwise, rest
puts "REST"

```
> 3 votes

# Answer
Simple cell done in `node.js`. Tested it agains examples node cell and against Kostronor it beats them.

**Update**

Still fairly simple, try to move towards enemy or divide.

```
// used in defining cell spec
var MAX_HP = 4;
var MAX_ENERGY = 8;
var ACIDITY = 0;

function decide(arena, cell, outputCallback) {

    var nearbyEmpties = arena.getAdjacentMatches(cell.point, [".", "c"]);
    var nearbyEnemies = arena.getAdjacentMatches(cell.point, ["x"]);
    var nearbyCorpses = arena.getAdjacentMatches(cell.point, ["c"]);
    var nearbyFriends = arena.getAdjacentMatches(cell.point, ["o"]);

    if (nearbyFriends.length >= 8) {
        outputCallback("REST");
        return;
    }

    if (nearbyFriends.length >= 7 && nearbyEnemies.length < 0 && nearbyCorpses.length > 0 && energy < MAX_ENERGY) {
        outputCallback("EAT " + arena.getDirection(cell, nearbyCorpses[(nearbyCorpses.length*Math.random())|0]));
        return;
    }

    // if you have two or more nearby enemies, explode if possible
    if(nearbyEnemies.length >= 1
        && cell.energy >= cell.hp
        && cell.hp <= 1
        && nearbyEnemies.length > nearbyFriends.length) {
        outputCallback("EXPLODE");
        return;
    }

    // if you have two or more nearby enemies, explode if possible
    if(nearbyEnemies.length >= 3 && cell.energy >= cell.hp && nearbyEnemies.length > nearbyFriends.length) {
        outputCallback("EXPLODE");
        return;
    }

    // if you have the energy and space to divide, do it
    if(cell.energy >= 5 && nearbyEmpties.length > 0) {
        var ed = arena.getEnemyDirection(cell);
        if (nearbyEmpties.indexOf(ed) >= 0 && Math.random() < 0.5){
            outputCallback("DIVIDE " + ed);
        } else{
            outputCallback("DIVIDE " + arena.getDirection(cell, nearbyEmpties[(nearbyEmpties.length*Math.random())|0]));
        }
        return;
    }

    // if at least one adjacent enemy, attack if possible
    if(cell.energy > 0 && nearbyEnemies.length > 0) {
        outputCallback("ATTACK " + arena.getDirection(cell, nearbyEnemies[(nearbyEnemies.length*Math.random())|0]) + " " + Math.min(cell.energy, 3));
        return;
    }

    if (Math.random() < 0.5) {
        for(var i=0; i<nearbyEmpties.length; ++i) {
            outputCallback("MOVE " + arena.getEnemyDirection(cell));
            return;
        }
    }

    if (nearbyEmpties.length > 0 && nearbyEnemies.length <= 6) {
        outputCallback("REST"); // because next turn is divide time
        return;
    }

    // if there's a nearby corpse, eat it if your energy is below max
    if(nearbyCorpses.length > 0) {
        outputCallback("EAT " + arena.getDirection(cell, nearbyCorpses[(nearbyCorpses.length*Math.random())|0]));
        return;
    }

    outputCallback("REST");
    return;
}

var input = "";
// quiet stdin EPIPE errors
process.stdin.on("error", function(err) {
    console.log("slight error: " + err);
});
process.stdin.on("data", function(data) {
    input += data;
});
process.stdin.on("end", function() {
    if(input == "BEGIN") {
        // output space-separated attributes
        process.stdout.write([MAX_HP, MAX_ENERGY, ACIDITY].join(" "));
    } else {
        // read in arena and decide on an action
        var arena = new Arena();
        var lines = input.split("\n");
        var dimensions = lines[0].split(" ").map(function(d) { return parseInt(d); });
        arena.width = dimensions[0];
        arena.height = dimensions[1];
        for(var y=1; y<=dimensions[1]; ++y) {
            for(var x=0; x<lines[y].length; ++x) {
                arena.set(x, y-1, lines[y][x]);
            }
        }

        var stats = lines[dimensions[1]+2].split(" ");
        var cell = { x: stats[0], y: stats[1], hp: stats[2], energy: stats[3], point: arena.get(stats[0], stats[1]) };

        // decide on an action and write the action to stdout
        decide(arena, cell, function(output) { process.stdout.write(output); })
    }
});

var Arena = function() {
    this.dict = {};
};
Arena.prototype = {
    // get Point object
    get: function(x,y) {
        return this.dict[x+","+y];
    },

    // store Point object
    set: function(x,y,d) {
        this.dict[x+","+y] = new Point(x,y,d);
    },

    // get an array of all Points adjacent to this one whose symbol is contained in matchList
    // if matchList is omitted, return all Points
    getAdjacentMatches: function(point, matchList) {
        var result = [];
        for(var i=-1; i<=1; ++i) {
            for(var j=-1; j<=1; ++j) {
                var inspectedPoint = this.get(point.x+i, point.y+j);
                if(inspectedPoint &&
                   (i!=0 || j!=0) &&
                   (!matchList || matchList.indexOf(inspectedPoint.symbol) != -1)) {
                    result.push(inspectedPoint);
                }
            }
        }
        return result;
    },

    // return the direction from point1 to point2
    getDirection: function(point1, point2) {
        var dx = point2.x - point1.x;
        var dy = point2.y - point1.y;
        dx = Math.abs(dx) / (dx || 1);
        dy = Math.abs(dy) / (dy || 1);

        c2d = { "0,0":"-",
                "0,-1":"N", "0,1":"S", "1,0":"E", "-1,0":"W",
                "-1,-1":"NW", "1,-1":"NE", "1,1":"SE", "-1,1":"SW" };

        return c2d[dx + "," + dy];
    },

    getEnemyDirection: function(p) {
        for (var i = 0; i < this.width; i++) {
            for (var j = 0; j < this.height; j++) {
                var found = this.get(i,j);
                if (found != null && found.symbol == "x") {
                    return this.getDirection(p, found);
                }
            }
        }
        return "N"; //should never happen
    }
}

var Point = function(x,y,d) {
    this.x = x;
    this.y = y;
    this.symbol = d;
}
Point.prototype.toString = function() {
    return "(" + this.x + ", " + this.y + ")";
}

```
> 3 votes

# Answer
# Amoeba

First splits into four and then tries to get to the middle ground to limit the opponents replication space. Then starts replicating. When moving or replicating, finds the optimal path to the closest enemy, and moves or divides towards it, to try to cut off the enemy available space.

If an enemy is adjacent or one space away, will always attack or move towards it, allowing the row behind doing nothing to fill any empty spaces.

I haven't tested this against any other submissions so have no idea how well it will do.

```
var MAX_HP = 2;
var MAX_ENERGY = 10;
var ACIDITY = 0;

function PathfindingNode(_x, _y, _prevNode, _distance, _adjacentEnemies) {
    this.x = _x;
    this.y = _y;
    this.prevNode = _prevNode;
    this.distance = _distance;
    this.adjacentEnemies = _adjacentEnemies;
}

PathfindingNode.prototype.GetDistance = function()
{
    return this.distance;
}

var evaluatedNodes = {};
var initialNode = {};
var firstEval = true;

function evaluateNode(x, y, arena)
{
    //get surrounding reachable nodes that havent already been checked
    var adjacentEmpties = arena.getAdjacentMatches(arena.get(x, y), [".", "c"]);

    //if this node is adjacent to the start node - special case because the start node isnt an empty
    if (firstEval)
        adjacentEmpties.push({ 'x': initialNode.x, 'y': initialNode.y });

    //find the optimal node to reach this one
    var prevNode = null;
    for (var i in adjacentEmpties)
    {
        if(evaluatedNodes[adjacentEmpties[i].x + "," + adjacentEmpties[i].y])
        {
            var currentNode = evaluatedNodes[adjacentEmpties[i].x + "," + adjacentEmpties[i].y];

            if (!prevNode) {
                prevNode = currentNode;
            }
            else {
                if(currentNode.GetDistance() < prevNode.GetDistance())
                {
                    prevNode = currentNode;
                }
            }
        }
    }

    var adjacentEnemies = arena.getAdjacentMatches(arena.get(x, y), ["x"]);
    var newNode = new PathfindingNode(x, y, prevNode, prevNode.GetDistance() + 1, adjacentEnemies.length);
    evaluatedNodes[x + "," + y] = newNode;
}

function evaluateNeighbours(arena) {
    //breadth first search all reachable cells
    var nodesToEvaluate = [];
    for (var i in evaluatedNodes) {
        var emptyNodes = arena.getAdjacentMatches(arena.get(evaluatedNodes[i].x, evaluatedNodes[i].y), [".", "c"]);
        //only ones that havent already been eval'd
        for (var j in emptyNodes)
            if (!evaluatedNodes[emptyNodes[j].x + "," + emptyNodes[j].y])
                nodesToEvaluate.push(emptyNodes[j])
    }

    //have all available nodes been evaluated
    if (nodesToEvaluate.length === 0)
        return false;

    for (var i in nodesToEvaluate)
    {
        evaluateNode(parseInt(nodesToEvaluate[i].x), parseInt(nodesToEvaluate[i].y), arena)
    }

    firstEval = false;
    return true;
}

function getAllReachableNodes(arena, cell) {
    //return a list of all reachable cells, with distance and optimal path
    evaluatedNodes = {};

    //add the first node to get started
    var adjacentEnemies = arena.getAdjacentMatches(arena.get(cell.x, cell.y), ["x"]);
    var newNode = new PathfindingNode(parseInt(cell.x), parseInt(cell.y), null, 0, adjacentEnemies.length);
    evaluatedNodes[cell.x + "," + cell.y] = newNode;
    initialNode.x = parseInt(cell.x);
    initialNode.y = parseInt(cell.y);
    firstEval = true;

    while (evaluateNeighbours(arena))
        ;

    return evaluatedNodes;
}

function passedMiddleGround(arena)
{
    for (var i = (parseInt(arena.width) / 2) - 1; i < parseInt(arena.width); i++)
    {
        for(var j = 0; j < parseInt(arena.height); j++)
        {
            if (arena.get(i, j).symbol == "o")
                return true;
        }
    }
    return false;
}

function decide(arena, cell, outputCallback) {

    var nearbyEmpties = arena.getAdjacentMatches(cell.point, [".", "c"]);
    var nearbyEnemies = arena.getAdjacentMatches(cell.point, ["x"]);
    var nearbyCorpses = arena.getAdjacentMatches(cell.point, ["c"]);

    if (nearbyEnemies.length > 4 && cell.energy >= cell.hp && cell.hp <= 3) {
        outputCallback("EXPLODE");
        return;
    }

    //attack whenever we get the chance. leave the replication to the cells doing nothing
    if (cell.energy > 0 && nearbyEnemies.length > 0){
        outputCallback("ATTACK " + arena.getDirection(cell, nearbyEnemies[(nearbyEnemies.length * Math.random()) | 0]) + " " + Math.min(cell.energy, 3));
        return;
    }

    //if we are close to an enemy, move towards it. let the back line fill the new space
    if (cell.energy > 2) {
        for (var i = 0; i < nearbyEmpties.length; ++i) {
            var space = nearbyEmpties[i];
            if (arena.getAdjacentMatches(space, ["x"]).length) {
                outputCallback("MOVE " + arena.getDirection(cell, space));
                return;
            }
        }
    }

    //yum
    if (nearbyCorpses.length > 0) {
        outputCallback("EAT " + arena.getDirection(cell, nearbyCorpses[(nearbyCorpses.length * Math.random()) | 0]));
        return;
    }

    //until we pass the middle ground, just keep moving into tactical position. afterwards we can start replication
    if (passedMiddleGround(arena) && cell.energy < 5 && nearbyEmpties.length > 0)
    {
        outputCallback("REST");
        return;
    }

    //try to block the opponent cells - interrupt their replication
    //if we have enough energy to move, choose the best spot
    if (nearbyEmpties.length > 0 && ((cell.energy >= 2 && nearbyEnemies.length == 0) || cell.energy >= 5)) {

        var nextMove = null;

        if (nearbyEmpties.length === 1) {
            nextMove = nearbyEmpties[0];
        }
        else {
            var reachableNodes = getAllReachableNodes(arena, cell);

            //select nodes that have an adjacent enemy
            var enemyAdjacentNodes = {};
            var enemyNodesReachable = false;
            for (var node in reachableNodes) {
                if (reachableNodes.hasOwnProperty(node) && reachableNodes[node].adjacentEnemies > 0) {
                    enemyAdjacentNodes[node] = reachableNodes[node];
                    enemyNodesReachable = true;
                }
            }

            if (enemyNodesReachable)
            {
                //if there are any then select the closest one
                var closest = null;
                for (var node in enemyAdjacentNodes) {
                    if(!closest)
                    {
                        closest = enemyAdjacentNodes[node];
                    }
                    else{
                        if(enemyAdjacentNodes[node].GetDistance() < closest.GetDistance())
                        {
                            closest = enemyAdjacentNodes[node];
                        }
                    }

                }

                //select the first move of the nodes path
                //trace the selected node back to the first node to select the first move towards the cell.
                while (closest.prevNode != null && closest.prevNode.prevNode != null)
                {
                    closest = closest.prevNode;
                }
                nextMove = arena.get(closest.x, closest.y);
            }
        }

        //a path to the enemy was found
        if(nextMove)
        {
            //do this until we get half way across the board, then we just replicate
            if (!passedMiddleGround(arena)) {
                if (cell.energy >= 5) {
                    outputCallback("DIVIDE " + arena.getDirection(cell, nextMove));
                    return;
                }

                outputCallback("MOVE " + arena.getDirection(cell, nextMove));
                return;
            }
            else {
                outputCallback("DIVIDE " + arena.getDirection(cell, nextMove));
                return;
            }

        }

    }

    //if theres no path to an enemy available, just divide anywhere
    if (cell.energy >= 5 && nearbyEmpties.length > 0) {
        outputCallback("DIVIDE " + arena.getDirection(cell, nearbyEmpties[(nearbyEmpties.length * Math.random()) | 0]));
        return;
    }

    outputCallback("REST");
    return;
}

var input = "";
// quiet stdin EPIPE errors
process.stdin.on("error", function(err) {
    log("slight error: " + err);
});
process.stdin.on("data", function(data) {
    input += data;
});
process.stdin.on("end", function() {
    if(input == "BEGIN") {
        // output space-separated attributes
        process.stdout.write([MAX_HP, MAX_ENERGY, ACIDITY].join(" "));
        clearLog();
    } else {
        // read in arena and decide on an action
        var arena = new Arena();
        var lines = input.split("\n");
        var dimensions = lines[0].split(" ").map(function(d) { return parseInt(d); });
        arena.width = dimensions[0];
        arena.height = dimensions[1];
        for(var y=1; y<=dimensions[1]; ++y) {
            for(var x=0; x<lines[y].length; ++x) {
                arena.set(x, y-1, lines[y][x]);
            }
        }

        var stats = lines[dimensions[1]+2].split(" ");
        var cell = { x: stats[0], y: stats[1], hp: stats[2], energy: stats[3], point: arena.get(stats[0], stats[1]) };

        // decide on an action and write the action to stdout
        decide(arena, cell, function(output) { process.stdout.write(output); })
    }
});

var Arena = function() {
    this.dict = {};
};
Arena.prototype = {
    // get Point object
    get: function(x,y) {
        if(!this.dict[x+","+y])
            return 'w';
        return this.dict[x+","+y];
    },

    // store Point object
    set: function(x,y,d) {
        this.dict[x+","+y] = new Point(x,y,d);
    },

    // get an array of all Points adjacent to this one whose symbol is contained in matchList
    // if matchList is omitted, return all Points
    getAdjacentMatches: function(point, matchList) {
        var result = [];
        for(var i=-1; i<=1; ++i) {
            for(var j=-1; j<=1; ++j) {
                var inspectedPoint = this.get(point.x+i, point.y+j);
                if(inspectedPoint &&
                   (i!=0 || j!=0) &&
                   (!matchList || matchList.indexOf(inspectedPoint.symbol) != -1)) {
                    result.push(inspectedPoint);
                }
            }
        }
        return result;
    },

    // return the direction from point1 to point2
    getDirection: function(point1, point2) {
        var dx = point2.x - point1.x;
        var dy = point2.y - point1.y;
        dx = Math.abs(dx) / (dx || 1);
        dy = Math.abs(dy) / (dy || 1);

        c2d = { "0,0":"-",
                "0,-1":"N", "0,1":"S", "1,0":"E", "-1,0":"W",
                "-1,-1":"NW", "1,-1":"NE", "1,1":"SE", "-1,1":"SW" };

        return c2d[dx + "," + dy];
    }
}

var Point = function(x,y,d) {
    this.x = x;
    this.y = y;
    this.symbol = d;
}
Point.prototype.toString = function() {
    return "(" + this.x + ", " + this.y + ")";
}

```
> 3 votes

# Answer
# Evolution

This submission has evolved and is no longer a simple singe-cell organism! It tries to attack/explode whenever possible, otherwise it divides or moves towards the enemy. Moving should solve the problem of a cell surrounded by friendly cells with max energy, unable to do something useful.
After moving there is always 3 energy left to hit the enemy as hard as possible.

```
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;

public class Evolution {
    public static final int MAX_HP = 4;
    public static final int MAX_ENERGY = 8;
    public static final int ACIDITY = 0;

    // given arena state and cell stats, return an action string (e.g., "ATTACK NW 2", "DIVIDE S")
    public static String decide(Arena arena, Point cell, int hp, int energy) {
        ArrayList<Point> nearbyEmpty = arena.getAdjacentMatches(cell, ".");
        ArrayList<Point> nearbyEnemies = arena.getAdjacentMatches(cell, "x");
        ArrayList<Point> nearbyCorpses = arena.getAdjacentMatches(cell, "c");
        ArrayList<Point> nearbyFriends = arena.getAdjacentMatches(cell, "o");

        // more than 1 enemy around => explode if possible and worth it
        if(nearbyEnemies.size() > 1 && energy > hp && hp <= 3 && nearbyEnemies.size() > nearbyFriends.size()) {
            return "EXPLODE";
        }

        // enemies around => always attack with max strength
        if(energy > 0 && nearbyEnemies.size() > 0) {
            int attackStrength = Math.min(energy, 3);
            Point enemy = nearbyEnemies.get(0);
            return "ATTACK " + arena.getDirection(cell, enemy) + " " + attackStrength;
        }

        // safe spot => divide if possible
        if(energy >= 5 && nearbyEmpty.size() > 0) {
            Point randomEmpty = nearbyEmpty.get((int)Math.floor(nearbyEmpty.size()*Math.random()));
            return "DIVIDE " + arena.getDirection(cell, randomEmpty);
        }

        // nearby corpse and missing energy => eat
        if(nearbyCorpses.size() > 0 && energy < MAX_ENERGY) {
            Point corpse = nearbyCorpses.get(0);
            return "EAT " + arena.getDirection(cell, corpse);
        }

        // move towards enemy => constant flow of attacks
        if(energy == 4) {
            return "MOVE " + arena.getEnemyDirection(cell);
        }

        return "REST";
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br =
            new BufferedReader(new InputStreamReader(System.in));

        String firstLine;

        firstLine = br.readLine();
        if(firstLine.equals("BEGIN")) {
            System.out.println(MAX_HP + " " + MAX_ENERGY + " " + ACIDITY);
        } else {
            String[] dimensions = firstLine.split(" ");
            int width = Integer.parseInt(dimensions[0]);
            int height = Integer.parseInt(dimensions[1]);
            Point[][] arena = new Point[height][];
            String input;
            int lineno = 0;

            while(!(input=br.readLine()).equals("")) {
                String[] charList = input.substring(1).split("");
                arena[lineno] = new Point[width];
                for(int i=0; i<charList.length; ++i) {
                    arena[lineno][i] = new Point(i, lineno, charList[i]);
                }
                lineno++;
            }

            String[] stats = br.readLine().split(" ");
            int x = Integer.parseInt(stats[0]);
            int y = Integer.parseInt(stats[1]);
            int hp = Integer.parseInt(stats[2]);
            int energy = Integer.parseInt(stats[3]);

            Arena arenaObj = new Arena(arena, width, height);
            System.out.print(decide(arenaObj, arenaObj.get(x,y), hp, energy));
        }
    }

    public static class Arena {
        public Point[][] array;
        public HashMap<String, String> c2d;
        public int height;
        public int width;

        public Arena(Point[][] array, int width, int height) {
            this.array = array;
            this.width = width;
            this.height = height;

            this.c2d = new HashMap<String, String>();
            this.c2d.put("0,0", "-");
            this.c2d.put("0,-1", "N");
            this.c2d.put("0,1", "S");
            this.c2d.put("1,0", "E");
            this.c2d.put("-1,0", "W");
            this.c2d.put("-1,-1", "NW");
            this.c2d.put("1,-1", "NE");
            this.c2d.put("-1,1", "SW");
            this.c2d.put("1,1", "SE");
        }

        // get the character at x,y
        // or return empty string if out of bounds
        public Point get(int x, int y) {
            if(y < 0 || y >= this.array.length){
                return null;
            }

            Point[] row = this.array[y];

            if(x < 0 || x >= row.length) {
                return null;
            }

            return row[x];
        }

        // get arraylist of Points for each adjacent space that matches the target string
        public ArrayList<Point> getAdjacentMatches(Point p, String match) {
            ArrayList<Point> result = new ArrayList<Point>();
            for(int i=-1; i<=1; ++i) {
                for(int j=-1; j<=1; ++j) {
                    Point found = this.get(p.x+i, p.y+j);
                    if((i!=0 || j!=0) && found != null && found.symbol.equals(match)) {
                        result.add(found);
                    }
                }
            }
            return result;
        }

        // get the direction string from point 1 to point 2
        public String getDirection(Point p1, Point p2) {
            int dx = p2.x - p1.x;
            int dy = p2.y - p1.y;
            dx = Math.abs(dx) / (dx==0?1:dx);
            dy = Math.abs(dy) / (dy==0?1:dy);

            return this.c2d.get(dx + "," + dy);
        }

        public String getEnemyDirection(Point p) {
            for (int x = 0; x < width; x++) {
                for (int y = 0; y < height; y++) {
                    Point found = this.get(x,y);
                    if (found != null && found.symbol.equals("x")) {
                        return getDirection(p, found);
                    }
                }
            }
            return "N"; //should never happen
        }
    }

    public static class Point {
        int x, y;
        String symbol;

        public Point(int x, int y, String sym) {
            this.x=x;
            this.y=y;
            this.symbol=sym;
        }
    }
}

```
> 2 votes

# Answer
## Hungry, hungry bot

Here is an entry in R. I hope I understood correctly what were the technical specs on how to communicate with your program. Should be triggered with `Rscript Hungryhungrybot.R`.
If it has at least 6 of energy it divides, preferentially in the direction of the enemy. Otherwise it eats whatever's next to it or whatever's reachable. If no food is reachable then it will either explode when there is more enemies around than sister cells, or fight with nearby enemies. Rests only if energy is 0 and nothing to eat is available.

```
infile <- file("stdin")
open(infile)
input1 <- readLines(infile,1)
if(input1=="BEGIN"){
    out <- "4 7 1"
    }else{
        nr <- as.integer(strsplit(input1," ")[[1]][2])
        nc <- as.integer(strsplit(input1," ")[[1]][1])
        input2 <- readLines(infile, 2+as.integer(nr))
        arena <- do.call(rbind,strsplit(input2[1:nr],""))
        stats <- strsplit(input2[nr+2]," ")[[1]]
        coords <- as.integer(stats[2:1])+1
        hp <- as.integer(stats[3])
        nrj <- as.integer(stats[4])
        closest <- function(coords,arena,object){
            a <- which(arena==object,arr.ind=TRUE)
            if(length(a)){
                d <- apply(a,1,function(x)max(abs(x-coords)))
                b <- which.min(d)
                f <- a[b,]
                dir <- f-coords
                where <- ""
                if(dir[1]<0)where <- paste(where,"N",sep="")
                if(dir[1]>0)where <- paste(where,"S",sep="")
                if(dir[2]<0)where <- paste(where,"W",sep="")
                if(dir[2]>0)where <- paste(where,"E",sep="")
                dist <- d[b]
                }else{dist <- NA; where <- ""}
            list(dist,where)
            }
        near <- expand.grid((coords[1]-1):(coords[1]+1),(coords[2]-1):(coords[2]+1))
        near <- near[near[,1]<=nr&near[,2]<=nc,]
        adjacent <- t(matrix(apply(near,1,function(x)arena[x[1],x[2]]),nr=3,byrow=TRUE))
        w <- matrix(c('NW','N','NE','W','','E','SW','S','SE'),nr=3,byrow=TRUE)
        if(coords[1]==1) w <- w[-1,]
        if(coords[1]==nr) w <- w[-3,]
        if(coords[2]==1) w <- w[,-1]
        if(coords[2]==nc) w <- w[,-3]
        if(any(arena=="c")){food <- closest(coords,arena,"c")}else{food <- list(nrj+2,"")}
        enemies <- closest(coords,arena,"x")
        if(nrj>=6){
            empties <- w[adjacent=="."]
            if(!length(empties)){
                if(sum(adjacent=="x")>sum(adjacent=="o") & hp<=3 & nrj>=hp){
                    out <- "EXPLODE"
                    }else{out <- "REST"}
                }else if(enemies[[2]]%in%empties & enemies[[1]]!=1){
                out <- paste("DIVIDE", enemies[[2]])
                }else{
                out <- paste("DIVIDE", empties[1])
                }
            }else{
                if(nrj==0 & !any(adjacent=="c")){
                    out <- "REST"
                    }else{
                        if(any(adjacent=="c")){
                            out <- paste("EAT",w[adjacent=="c"][1])
                            }else if(any(arena=="c") & food[[1]]<=(nrj+1)){
                                    out <- paste("MOVE",food[[2]])
                            }else if(sum(adjacent=="x")>sum(adjacent=="o") & hp<=3 & nrj>=hp){
                                out <- "EXPLODE"
                            }else if(any(adjacent=="x")){
                                out <- paste("ATTACK",w[adjacent=="x"][1],max(nrj,3))
                            }else{
                                out <- paste("MOVE", enemies[[2]])
                            }
                    }
            }
        }
cat(out)
flush(stdout())

```
> 2 votes

# Answer
## Berserker

Because I used Clojure, which has some limitations, mainly the huge startup time, I took a little liverty. When the program is given `BEGIN` it outputs `4 6 2 LOOP`, indicating that it doesn't stop. Then it takes the inputs as a continuous stream and ends with `END`. It doesn't save any state, which is made clear by not using any global variables or reusing return values. Because the implementation for this loopy action hasn't been done yet, I couldn't fully test the code (I hope the code is clear enough).

The cell gained it's name from it's nature of exploding whenever possible (and thus having acidity) and by prioritising attacking right after dividing.

I uploaded the generated jar-file to my Dropbox. Run with `java -jar petridish-clojure.jar`

Just to clarify:

```
> BEGIN
< 4 6 2 LOOP
> 10 4
> ..........
> ..xx.c....
> ...c...O..
> ......o...
>
> 3 4 6
< DIVIDE NW
> 10 4
> ..........
> ..xx.c....
> ...c.o.o..
> ......o...
>
> 5 2 4 1
< EAT N
> END

```

```
(ns petridish.core
  (:require [clojure.string :as s])
  (:gen-class))

(def ^:const maxhp     4)
(def ^:const maxenergy 6)
(def ^:const acidity   2)

(defn str->int
  [x]
  (if (empty? x)
    0
    (Integer. (re-find #"\d+" x))))

(defn sum-vectors [vec1 vec2]
  (vec (map #(vec (map + % vec2)) vec1)))

(defn find-adjacent [[width height] board pos target]
  (let [cells (sum-vectors [[-1 -1] [0 -1] [1 -1]
                            [-1  0]        [1  0]
                            [-1  1] [0  1] [1  1]]
                           pos)
        directions ["NW" "N" "NE"
                    "W"      "E"
                    "SW" "S" "SE"]]
    (for [cell cells
          :when (and (> width  (cell 0) -1)
                     (> height (cell 1) -1)
                     (= target (get-in board (reverse cell))))]
      (directions (.indexOf cells cell)))))

(defn decide [size board [x y hp energy]]
  (let [friends (find-adjacent size board [x y] \o)
        enemies (find-adjacent size board [x y] \x)
        corpses (find-adjacent size board [x y] \c)
        empty   (find-adjacent size board [x y] \.)]
    (cond
      (and (<= hp 3) (> energy hp) (seq enemies))
        "EXPLODE"
      (and (>= energy 5) (seq empty))
        (str "DIVIDE " (first empty))
      (and (>= energy 3) (seq enemies))
        (str "ATTACK " (first enemies) " " (min 3 energy))
      (and (< energy maxenergy) (seq corpses))
        (str "EAT " (first corpses))
      (or (and (<= 5 energy maxenergy) (not (seq empty))) (< energy 5))
        "REST"
      (seq empty)
        (str "MOVE " (rand-nth empty)))))

(defn read-board [[width height]]
  (let [result (vec (for [i (range height)]
                        (read-line)))]
    (read-line) ; Skip the empty line
    result))

(defn reader []
  (loop []
    (let [firstline (read-line)]
      (when (not= firstline "END")
        (println
          (if (= firstline "BEGIN")
            (str maxhp " " maxenergy " " acidity " LOOP")
            (let [size   (map str->int (s/split firstline #"\s+"))
                  board  (read-board size)
                  status (map str->int (s/split (read-line) #"\s+"))]
              (decide size board status))))
        (recur)))))

(defn -main []
  (reader))

```

---

Update log

```
1. Fixed the logic a little and removed redundancies.

```
> 2 votes

# Answer
### Coordinated Bacteria

I hope I'm not too late.

Win against other opponents (and always by killing them all -- after many rounds), in my tests, and the battle will never end if it faces itself, an evidence that the strategy is strong. Always win within the 150 rounds limit, and if continued indefinitely will always kill all.

When you are single-celled, you can memorize previous state, but you can exploit your own position to behave differently! =)

This will divide the bacteria into divider and mover, and in doing so will keep more bacteria useful instead of just the front line, while keeping the defense line up.

It also coordinates its attacks to focus on specific enemy, so that enemies get killed faster (this is to face my other single-cell which focuses on HP).

In mid-game, which is detected by the number of cells on the board, they will try to shove into enemy territory by out-flanking them. This is the key winning strategy.

This has the highest growth rate compared to all other opponents currently, but it has a slow start, so this works better on large arena.

Run it with `java CoordinatedBacteria`

```
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;

public class CoordinatedBacteria {
    public static final int MAX_HP = 6;
    public static final int MAX_ENERGY = 6;
    public static final int ACIDITY = 0;

    // given arena state and cell stats, return an action string (e.g., "ATTACK NW 2", "DIVIDE S")
    public static String decide(final Arena arena, Point cell, int hp, int energy) {
        // empty and corpses are free for movement and division
        final Point2D enemyCenter = arena.getCenterOf("x");
        final Point2D ourCenter = arena.getCenterOf("o");
        final int moverPos = (enemyCenter.x <= ourCenter.x || enemyCenter.y <= ourCenter.y) ? (arena.width+arena.height+1)%2 : 1;
        final int attackPos = (enemyCenter.x <= ourCenter.x || enemyCenter.y <= ourCenter.y) ? (arena.width+arena.height)%2 : 1;

        int selfCount = arena.count("o");
        boolean isMidWay = selfCount > (arena.width*arena.height/2-1);

        if(!isMidWay){
            if(enemyCenter.x < ourCenter.x){
                enemyCenter.x = 0;
                enemyCenter.y = 0;
                ourCenter.x = arena.width;
                ourCenter.y = arena.height;
            } else {
                enemyCenter.x = arena.width;
                enemyCenter.y = arena.height;
                ourCenter.x = 0;
                ourCenter.y = 0;
            }
        }
        ArrayList<Point> nearbyEmpty = arena.getAdjacentMatches(cell, ".");
        Collections.sort(nearbyEmpty, new Comparator<Point>(){
            @Override
            public int compare(Point o1, Point o2) {
                Double score1 = arena.getAdjacentMatches(o1, ".").size()
                        + arena.getAdjacentMatches(o1, "c").size()
                        + arena.getAdjacentMatches(o1, "x").size()
                        - arena.getAdjacentMatches(o1, "o").size()
                        + distance(o1.x, o1.y, enemyCenter.x, enemyCenter.y)*100;
                Double score2 = arena.getAdjacentMatches(o2, ".").size()
                        + arena.getAdjacentMatches(o2, "c").size()
                        + arena.getAdjacentMatches(o2, "x").size()
                        - arena.getAdjacentMatches(o2, "o").size()
                        + distance(o1.x, o1.y, enemyCenter.x, enemyCenter.y)*100;
                return Double.compare(score2, score1);
            }
        });
        ArrayList<Point> nearbyEnemies = arena.getAdjacentMatches(cell, "x");
        Collections.sort(nearbyEnemies, new Comparator<Point>(){
            @Override
            public int compare(Point o1, Point o2) {
                Integer score1 = (arena.getAdjacentMatches(o1, ".").size()
                        + arena.getAdjacentMatches(o1, "c").size()
                        - arena.getAdjacentMatches(o1, "x").size()
                        + arena.getAdjacentMatches(o1, "o").size())
                        *10
                        + (isAtBoundary(o1, arena)?1000:0)
                        + (o1.x + o1.y + attackPos + 1)%2;
                Integer score2 = (arena.getAdjacentMatches(o2, ".").size()
                        + arena.getAdjacentMatches(o2, "c").size()
                        - arena.getAdjacentMatches(o2, "x").size()
                        + arena.getAdjacentMatches(o2, "o").size())
                        *10
                        + (isAtBoundary(o2, arena)?1000:0)
                        + (o2.x + o2.y + attackPos + 1)%2;
                return Integer.compare(score2, score1);
            }
        });
        ArrayList<Point> nearbyCorpses = arena.getAdjacentMatches(cell, "c");
        Collections.sort(nearbyCorpses, new Comparator<Point>(){
            @Override
            public int compare(Point o1, Point o2) {
                Integer score1 = arena.getAdjacentMatches(o1, "x").size()
                        - arena.getAdjacentMatches(o1, "o").size();
                Integer score2 = arena.getAdjacentMatches(o2, "x").size()
                        - arena.getAdjacentMatches(o2, "o").size();
                return Integer.compare(score1, score2);
            }
        });
        ArrayList<Point> nearbyFriends = arena.getAdjacentMatches(cell, "o");

        for(Point empty: nearbyEmpty){
            if(nearbyFriends.size()>=2 && energy >= 1 && arena.getAdjacentMatches(empty, "x").size()==3 && isAtBoundary(empty, arena)){
                return "MOVE "+arena.getDirection(cell, empty);
            }
        }

        for(Point empty: nearbyCorpses){
            if(nearbyFriends.size()>=2 && energy >= 1 && arena.getAdjacentMatches(empty, "x").size()==3 && isAtBoundary(empty, arena)){
                return "MOVE "+arena.getDirection(cell, empty);
            }
        }

        if ((cell.x+cell.y)%2 == moverPos && energy >= 1 && energy <= 5){
            if(nearbyEmpty.size()>0){
                Point foremost = nearbyEmpty.get(0);
                if(nearbyFriends.size() >= 4){
                    return "MOVE "+arena.getDirection(cell, foremost);
                }
            }
            if(nearbyCorpses.size() > 0) {
                Point corpse = nearbyCorpses.get(0);
                return "EAT " + arena.getDirection(cell, corpse);
            }

            if(energy > 0 && nearbyEnemies.size() > 0) {
                int attackStrength = Math.min(energy, 3);
                Point enemy = nearbyEnemies.get(0);
                return "ATTACK " + arena.getDirection(cell, enemy) + " " + attackStrength;
            }

            if(nearbyFriends.size() >= 4 && nearbyEmpty.size() > 0){
                Point movePoint = getBestPointToDivide(arena, nearbyEmpty);
                return "MOVE " + arena.getDirection(cell, movePoint);
            }
        }

        if(energy >= 5 && nearbyEmpty.size() > 0) {
            Point divisionPoint = getBestPointToDivide(arena, nearbyEmpty);
            if(energy == MAX_ENERGY && nearbyFriends.size() >= 5
                    && distance(enemyCenter.x, enemyCenter.y, cell.x, cell.y) > distance(enemyCenter.x, enemyCenter.y, divisionPoint.x, divisionPoint.y)){
                return "MOVE " + arena.getDirection(cell, divisionPoint);
            }
            return "DIVIDE " + arena.getDirection(cell, divisionPoint);
        }

        if(nearbyCorpses.size() > 0) {
            Point corpse = nearbyCorpses.get(0);
            if (energy < MAX_ENERGY){
                return "EAT " + arena.getDirection(cell, corpse);
            } else {
                return "DIVIDE " + arena.getDirection(cell, corpse);
            }
        }

        if(energy >= 5 && nearbyCorpses.size() > 0) {
            Point divisionPoint = getBestPointToDivide(arena, nearbyCorpses);
            if(energy == MAX_ENERGY && nearbyFriends.size() >= 5
                    && distance(enemyCenter.x, enemyCenter.y, cell.x, cell.y) < distance(enemyCenter.x, enemyCenter.y, divisionPoint.x, divisionPoint.y)){
                return "MOVE " + arena.getDirection(cell, divisionPoint);
            }
            return "DIVIDE " + arena.getDirection(cell, divisionPoint);
        }

        // if at least one adjacent enemy, attack if possible
        if(energy > 0 && nearbyEnemies.size() > 0) {
            int attackStrength = Math.min(energy, 3);
            Point enemy = nearbyEnemies.get(0);
            return "ATTACK " + arena.getDirection(cell, enemy) + " " + attackStrength;
        }

        return "REST";

    }

    public static boolean isAtBoundary(Point point, Arena arena){
        return point.x==0 || point.x==arena.width-1 || point.y==0 || point.y==arena.height-1;
    }

    public static double distance(double x1, double y1, double x2, double y2){
        return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
    }

    public static Point getBestPointToDivide(Arena arena, List<Point> nearbyEmpty){
        Point result = null;
        double minDist = 100000;
        List<Point> mostEmpty = new ArrayList<Point>();
        int max = -1000;
        List<Point> neighbor = nearbyEmpty;
        for(Point point: neighbor){
            int emptyNeighborScore = arena.getAdjacentMatches(point, ".").size()
                    + arena.getAdjacentMatches(point, "c").size()
                    + arena.getAdjacentMatches(point, "x").size()
                    - arena.getAdjacentMatches(point, "o").size();
            if(emptyNeighborScore > max){
                mostEmpty = new ArrayList<Point>();
                mostEmpty.add(point);
                max = emptyNeighborScore;
            } else if(emptyNeighborScore == max){
                mostEmpty.add(point);
            }
        }
        for(Point point: mostEmpty){
            Point2D enemyCenter = arena.getCenterOf("x");
            double dist = Math.pow(point.x-enemyCenter.x, 2) + Math.pow(point.y-enemyCenter.y, 2);
            if(dist < minDist){
                minDist = dist;
                result = point;
            }
        }
        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br =
                new BufferedReader(new InputStreamReader(System.in));

        String firstLine;

        firstLine = br.readLine();
        if(firstLine.equals("BEGIN")) {
            System.out.println(MAX_HP + " " + MAX_ENERGY + " " + ACIDITY);
        } else {
            String[] dimensions = firstLine.split(" ");
            int width = Integer.parseInt(dimensions[0]);
            int height = Integer.parseInt(dimensions[1]);
            Point[][] arena = new Point[height][];
            String input;
            int lineno = 0;

            while(!(input=br.readLine()).equals("")) {
                char[] charList = input.toCharArray();
                arena[lineno] = new Point[width];
                for(int i=0; i<charList.length; ++i) {
                    arena[lineno][i] = new Point(i, lineno, charList[i]);
                }
                lineno++;
            }

            String[] stats = br.readLine().split(" ");
            int x = Integer.parseInt(stats[0]);
            int y = Integer.parseInt(stats[1]);
            int hp = Integer.parseInt(stats[2]);
            int energy = Integer.parseInt(stats[3]);

            Arena arenaObj = new Arena(arena, width, height);
            System.out.print(decide(arenaObj, arenaObj.get(x,y), hp, energy));
        }
    }

    public static class Arena {
        public Point[][] array;
        public HashMap<String, String> c2d;
        public int height;
        public int width;

        public Arena(Point[][] array, int width, int height) {
            this.array = array;
            this.width = width;
            this.height = height;

            this.c2d = new HashMap<String, String>();
            this.c2d.put("0,0", "-");
            this.c2d.put("0,-1", "N");
            this.c2d.put("0,1", "S");
            this.c2d.put("1,0", "E");
            this.c2d.put("-1,0", "W");
            this.c2d.put("-1,-1", "NW");
            this.c2d.put("1,-1", "NE");
            this.c2d.put("-1,1", "SW");
            this.c2d.put("1,1", "SE");
        }

        // get the character at x,y
        // or return empty string if out of bounds
        public Point get(int x, int y) {
            if(y < 0 || y >= this.array.length){
                return null;
            }

            Point[] row = this.array[y];

            if(x < 0 || x >= row.length) {
                return null;
            }

            return row[x];
        }

        // get arraylist of Points for each adjacent space that matches the target string
        public ArrayList<Point> getAdjacentMatches(Point p, String match) {
            ArrayList<Point> result = new ArrayList<Point>();
            for(int i=-1; i<=1; ++i) {
                for(int j=-1; j<=1; ++j) {
                    Point found = this.get(p.x+i, p.y+j);
                    if((i!=0 || j!=0) && found != null && found.symbol.equals(match)) {
                        result.add(found);
                    }
                }
            }
            return result;
        }

        public ArrayList<Point> getAdjacents(Point p){
            ArrayList<Point> result = new ArrayList<Point>();
            for(int i=-1; i<=1; ++i) {
                for(int j=-1; j<=1; ++j) {
                    Point found = this.get(p.x+i, p.y+j);
                    if((i!=0 || j!=0) && found != null) {
                        result.add(found);
                    }
                }
            }
            return result;
        }

        public int count(String sym){
            int result = 0;
            for(int y=0; y<array.length; y++){
                for(int x=0; x<array[y].length; x++){
                    Point cur = this.get(x, y);
                    if(cur!=null && cur.symbol.equals(sym)){
                        result++;
                    }
                }
            }
            return result;
        }

        // get the direction string from point 1 to point 2
        public String getDirection(Point p1, Point p2) {
            int dx = p2.x - p1.x;
            int dy = p2.y - p1.y;
            dx = Math.abs(dx) / (dx==0?1:dx);
            dy = Math.abs(dy) / (dy==0?1:dy);

            return this.c2d.get(dx + "," + dy);
        }

        public Point2D getCenterOf(String sym){
            Point2D result = new Point2D(0,0);
            int count = 0;
            for(int y=0; y<array.length; y++){
                for(int x=0; x<array[y].length; x++){
                    if(this.get(x,y).symbol.equals(sym)){
                        result.x += x;
                        result.y += y;
                        count++;
                    }
                }
            }
            result.x /= count;
            result.y /= count;
            return result;
        }

    }

    public static class Point {
        int x, y;
        String symbol;

        public Point(int x, int y, String sym) {
            this.x=x;
            this.y=y;
            this.symbol=sym;
        }

        public Point(int x, int y, char sym){
            this(x, y, ""+sym);
        }
    }

    public static class Point2D{
        double x,y;
        public Point2D(double x, double y){
            this.x = x;
            this.y = y;
        }
    }
}

```
> 2 votes

# Answer
I think i will post my submission, since you are so generous to add the boilerplate logic...

There was a problem in your logic, where the eat-action would issue an ATTACK instead of an EAT and would waste the corpse.

I have modified your gist just as much to have a working solution, that should perform relatively well. It starts with 4 hp and 8 energy, so after a split and a rest, both cells can split again. It will try to multiply itself, attack enemies, eat corpses and rest, in this order. So inner cells will store their 8 energy points, to quickly replace killed outer cells and leave them 3 energy points to make a 3 point attack or multiply themselves after one turn rest. The 4 hp are to survive at least one full force attack.

acid seems to be a waste of points for me so i kept it out...

I did not tested the submission, as it was a 2 minute thing ;)

here is my code:

```
/*
 Sample code for a "Battle for the Petri Dish" cell

 Released under the terms of the WTF Public License
 No warranty express or implied is granted, etc, etc.

 I just hacked this together very quickly; improvements are welcome, so please fork the Gist if you like.

 used this code for a submission @kostronor

 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;

public class SlimeCell {
    public static final int MAX_HP = 4;
    public static final int MAX_ENERGY = 8;
    public static final int ACIDITY = 0;

    // given arena state and cell stats, return an action string (e.g., "ATTACK NW 2", "DIVIDE S")
    public static String decide(final Arena arena, final Point cell, final int hp, final int energy) {
        // empty and corpses are free for movement and division
        ArrayList<Point> nearbyEmpty = arena.getAdjacentMatches(cell, ".");
        nearbyEmpty.addAll(arena.getAdjacentMatches(cell, "c"));

        ArrayList<Point> nearbyEnemies = arena.getAdjacentMatches(cell, "x");
        ArrayList<Point> nearbyCorpses = arena.getAdjacentMatches(cell, "c");
        ArrayList<Point> nearbyFriends = arena.getAdjacentMatches(cell, "o");

        // if you have energy and space to divide, divide into a random space
        if((energy >= 5) && (nearbyEmpty.size() > 0)) {
            Point randomEmpty = nearbyEmpty.get((int)Math.floor(nearbyEmpty.size()*Math.random()));
            return "DIVIDE " + arena.getDirection(cell, randomEmpty);
        }

        // if at least one adjacent enemy, attack if possible
        if((energy > 0) && (nearbyEnemies.size() > 1)) {
            int attackStrength = Math.min(energy, 3);
            Point enemy = nearbyEnemies.get((int)Math.floor(nearbyEnemies.size()*Math.random()));
            return "ATTACK " + arena.getDirection(cell, enemy) + " " + attackStrength;
        }

        // if there's a nearby corpse, eat it if your energy is below max
        if(nearbyCorpses.size() > 0) {
            Point corpse = nearbyCorpses.get((int)Math.floor(nearbyCorpses.size()*Math.random()));
            return "EAT " + arena.getDirection(cell, corpse);
        }

        return "REST";

    }

    public static void main(final String[] args) throws IOException {
        BufferedReader br =
                new BufferedReader(new InputStreamReader(System.in));

        String firstLine;

        firstLine = br.readLine();
        if(firstLine.equals("BEGIN")) {
            System.out.println(MAX_HP + " " + MAX_ENERGY + " " + ACIDITY);
        } else {
            String[] dimensions = firstLine.split(" ");
            int width = Integer.parseInt(dimensions[0]);
            int height = Integer.parseInt(dimensions[1]);
            Point[][] arena = new Point[height][];
            String input;
            int lineno = 0;

            while(!(input=br.readLine()).equals("")) {
                String[] charList = input.substring(1).split("");
                arena[lineno] = new Point[width];
                for(int i=0; i<charList.length; ++i) {
                    arena[lineno][i] = new Point(i, lineno, charList[i]);
                }
                lineno++;
            }

            String[] stats = br.readLine().split(" ");
            int x = Integer.parseInt(stats[0]);
            int y = Integer.parseInt(stats[1]);
            int hp = Integer.parseInt(stats[2]);
            int energy = Integer.parseInt(stats[3]);

            Arena arenaObj = new Arena(arena, width, height);
            System.out.print(decide(arenaObj, arenaObj.get(x,y), hp, energy));
        }
    }

    public static class Arena {
        public Point[][] array;
        public HashMap<String, String> c2d;
        public int height;
        public int width;

        public Arena(final Point[][] array, final int width, final int height) {
            this.array = array;
            this.width = width;
            this.height = height;

            this.c2d = new HashMap<String, String>();
            this.c2d.put("0,0", "-");
            this.c2d.put("0,-1", "N");
            this.c2d.put("0,1", "S");
            this.c2d.put("1,0", "E");
            this.c2d.put("-1,0", "W");
            this.c2d.put("-1,-1", "NW");
            this.c2d.put("1,-1", "NE");
            this.c2d.put("-1,1", "SW");
            this.c2d.put("1,1", "SE");
        }

        // get the character at x,y
        // or return empty string if out of bounds
        public Point get(final int x, final int y) {
            if((y < 0) || (y >= this.array.length)){
                return null;
            }

            Point[] row = this.array[y];

            if((x < 0) || (x >= row.length)) {
                return null;
            }

            return row[x];
        }

        // get arraylist of Points for each adjacent space that matches the target string
        public ArrayList<Point> getAdjacentMatches(final Point p, final String match) {
            ArrayList<Point> result = new ArrayList<Point>();
            for(int i=-1; i<=1; ++i) {
                for(int j=-1; j<=1; ++j) {
                    Point found = this.get(p.x+i, p.y+j);
                    if(((i!=0) || (j!=0)) && (found != null) && found.symbol.equals(match)) {
                        result.add(found);
                    }
                }
            }
            return result;
        }

        // get the direction string from point 1 to point 2
        public String getDirection(final Point p1, final Point p2) {
            int dx = p2.x - p1.x;
            int dy = p2.y - p1.y;
            dx = Math.abs(dx) / (dx==0?1:dx);
            dy = Math.abs(dy) / (dy==0?1:dy);

            return this.c2d.get(dx + "," + dy);
        }

    }

    public static class Point {
        int x, y;
        String symbol;

        public Point(final int x, final int y, final String sym) {
            this.x=x;
            this.y=y;
            this.symbol=sym;
        }
    }
}

```
> 1 votes

# Answer
# Thinly spread bomber

Since you so kindly provided boilerplate code, I decided to make my own simple cell; This cell has 4 acidity, only 1 hp and 7 energy. It tries to get out of range of friendlies and then waits there (or eats if possible) until it gets the chance to blow up or replicate. Attacks only if it's the only option.

It's a pretty ballsy strategy and will probably perform badly, but I'm curious to see how it does. I'll test it and improve it later today, maybe.

```
/*
 Sample code for a "Battle for the Petri Dish" cell

 Released under the terms of the WTF Public License,
 No warranty express or implied is granted, etc, etc.

 I just hacked this together very quickly; improvements are welcome, so please fork the Gist if you like.
*/

// used in defining cell spec
var MAX_HP = 1;
var MAX_ENERGY = 7;
var ACIDITY = 4;

/*
   The decide function takes an Arena object (see below for prototype methods), a cell object,
   and an outputCallback, which accepts a command string to output
*/
function decide(arena, cell, outputCallback) {
    var nearbyEmpties = arena.getAdjacentMatches(cell.point, [".", "c"]);
    var nearbyEnemies = arena.getAdjacentMatches(cell.point, ["x"]);
    var nearbyCorpses = arena.getAdjacentMatches(cell.point, ["c"]);
    var nearbyFriendlies = arena.getAdjacentMatches(cell.point, ["o"]);

    //attempt to move away from friendlies if possible
    if(nearbyFriendlies.length>1 && cell.energy>0)
    {
        for(var i=0; i<nearbyEmpties.length; ++i)
        {
            var space = nearbyEmpties[i];
            if(arena.getAdjacentMatches(space, ["o"]).length == 1)
            {
                outputCallback("MOVE " + arena.getDirection(cell,space));
                return;
            }
        }
    }

    // Explode if there are two more adjacent enemies than friendlies or enemies and no friendlies.
    if((nearbyEnemies.length - nearbyFriendlies.length > 1 || (nearbyEnemies.length>0 && nearbyFriendlies.length == 0))
        && cell.energy >= cell.hp && cell.hp <= 3)
    {
        outputCallback("EXPLODE");
        return;
    }

    // if you have the energy and space to divide, and there's a way for the child to get away from friendlies, do it.
    if(cell.energy >= 5 && nearbyEmpties.length > 0)
    {
        for(var i=0; i<nearbyEmpties.length; ++i)
        {
            var space = nearbyEmpties[i];
            var possiblePositions = arena.getAdjacentMatches(space, ["o"]);
            for(var i=0; i<possiblePositions.length; ++i)
            {
                if(arena.getAdjacentMatches(possiblePositions[i], ["o"]).length == 0)
                {
                    outputCallback("DIVIDE " + arena.getDirection(cell,space));
                    return;
                }
            }
        }
    }

    // if at least one adjacent enemy, attack if possible
    if(cell.energy > 0 && nearbyEnemies.length > 0)
    {
        outputCallback("ATTACK " + arena.getDirection(cell, nearbyEnemies[(nearbyEnemies.length*Math.random())|0]) + " " + Math.min(cell.energy, 3));
        return;
    }

    // if there's a nearby corpse, eat it if your energy is below max
    if(nearbyCorpses.length > 0)
    {
        outputCallback("EAT " + arena.getDirection(cell, nearbyCorpses[(nearbyCorpses.length*Math.random())|0]));
        return;
    }

    outputCallback("REST");
    return;
}

var input = "";
// quiet stdin EPIPE errors
process.stdin.on("error", function(err) {
    //console.log("slight error: " + err);
});
process.stdin.on("data", function(data) {
    input += data;
});
process.stdin.on("end", function() {
    if(input == "BEGIN") {
        // output space-separated attributes
        process.stdout.write([MAX_HP, MAX_ENERGY, ACIDITY].join(" "));
    } else {
        // read in arena and decide on an action
        var arena = new Arena();
        var lines = input.split("\n");
        var dimensions = lines[0].split(" ").map(function(d) { return parseInt(d); });
        arena.width = dimensions[0];
        arena.height = dimensions[1];
        for(var y=1; y<=dimensions[1]; ++y) {
            for(var x=0; x<lines[y].length; ++x) {
                arena.set(x, y-1, lines[y][x]);
            }
        }

        var stats = lines[dimensions[1]+2].split(" ");
        var cell = { x: stats[0], y: stats[1], hp: stats[2], energy: stats[3], point: arena.get(stats[0], stats[1]) };

        // decide on an action and write the action to stdout
        decide(arena, cell, function(output) { process.stdout.write(output); })
    }
});

var Arena = function() {
    this.dict = {};
};
Arena.prototype = {
    // get Point object
    get: function(x,y) {
        return this.dict[x+","+y];
    },

    // store Point object
    set: function(x,y,d) {
        this.dict[x+","+y] = new Point(x,y,d);
    },

    // get an array of all Points adjacent to this one whose symbol is contained in matchList
    // if matchList is omitted, return all Points
    getAdjacentMatches: function(point, matchList) {
        var result = [];
        for(var i=-1; i<=1; ++i) {
            for(var j=-1; j<=1; ++j) {
                var inspectedPoint = this.get(point.x+i, point.y+j);
                if(inspectedPoint &&
                   (i!=0 || j!=0) &&
                   (!matchList || matchList.indexOf(inspectedPoint.symbol) != -1)) {
                    result.push(inspectedPoint);
                }
            }
        }
        return result;
    },

    // return the direction from point1 to point2
    getDirection: function(point1, point2) {
        var dx = point2.x - point1.x;
        var dy = point2.y - point1.y;
        dx = Math.abs(dx) / (dx || 1);
        dy = Math.abs(dy) / (dy || 1);

        c2d = { "0,0":"-",
                "0,-1":"N", "0,1":"S", "1,0":"E", "-1,0":"W",
                "-1,-1":"NW", "1,-1":"NE", "1,1":"SE", "-1,1":"SW" };

        return c2d[dx + "," + dy];
    }
}

var Point = function(x,y,d) {
    this.x = x;
    this.y = y;
    this.symbol = d;
}
Point.prototype.toString = function() {
    return "(" + this.x + ", " + this.y + ")";
}

```
> 1 votes

---
Tags: king-of-the-hill
---


title: How strong are nonary numbers?

text:
# Question
Title: How strong are nonary numbers?
You are given a nonary (base 9) non-negative integer consisting of the digits 0 through 8 as usual. However the number of digits in this number (with no leading zeros) is a prefect square.

Because of this, the number can be arranged in a square grid (with the reading order still preserved).

Example with 1480 (1125 base 10):

```
14
80

```

Now let every digit in such a nonary grid indicate a motion to another grid space (with periodic boundary conditions):

```
432
501
678

```

This is saying that

```
0 = stay still
1 = move right
2 = move right and up
3 = move up
...
8 = move right and down

```

So, if in the 1480 grid you start at the 4, you then move up (remember pbc) and left to the 8, which means you move right and down back to the 4, starting a cycle with period 2.

In general this process is continued until you get to a 0 or a cycle is noticed. (A 0 is considered a cycle with period 1.)

In the case of 1480, the period eventually reached at each of the 4 starting digits is `2 2 2 1` respectively.

For a larger grid these numbers might be larger than 8, but we can still use them as "digits" in a new nonary number (simply the coefficients of 9^n as if they were digits):

```
2*9^3 + 2*9^2 + 2*9 + 1 = 1639 (base 10) = 2221 (base 9)

```

We will call this the *strength* of the original nonary number. So the strength of 1480 is 1639 (base 10) or, equivalently, 2221 (base 9).

## Challenge

Write the shortest program that tells whether the strength of a nonary number is greater than, less than, or equal to the nonary number itself. (You do not necessarily need to compute the strength.)

The input will be a non-negative nonary number that contains a square number of digits (and no leading zeros besides the special case of 0 itself). It should come from the command line or stdin.

The output should go to stdout as:

```
G if the strength is larger than the original number (example: 1480 -> strength = 2221)
E if the strength is equal to the original number (example: 1 -> strength = 1)
L if the strength is less than the original number (example: 5 -> strength = 1)

```

**Fun Bonus Challenge:**
Whats the highest input you can find that is equal to its strength? (Is there a limit?)

# Answer
> 2 votes
# Python 296

Not actually too inefficient, it only checks as many digits as it needs to.

```
n=raw_input();s=int(len(n)**.5);t=0
for i in range(s**2):
    l=[]
    while i not in l:l.append(i);c=n[i];i=(i%s+(-1 if c in'456'else 1 if c in'218'else 0))%s+((i/s+(-1 if c in'432'else 1 if c in'678'else 0))%s)*s
    t=t*9+len(l)-l.index(i)
print'EGL'[cmp(t,long(n,9))]

```

As for numbers equal to their strength, I think the only solutions are, for every N x N square up to N=8 a square containing N in every space. My thinking is that since every number in a loop must be the same number (the length of the loop) each loop would have to be all in one direction. This of course means that the loop's size must be N (and each element must be N). I'm pretty sure that this logic can be applied to squares and loops of any size, meaning there are no squares equal to their strength other than the first 8.

# Answer
> 2 votes
# Python 2, 213 209 202

Edit: Removed shortcircuiting, which is sometimes incorrect. See below.

(Largely) The same algorithm as @KSab, but very heavily golfed.

```
n=`input()`
s=int(len(n)**.5)
c=0
for i in range(s*s):
 a=[]
 while(i in a)<1:a+=[i];x='432501678'.find(n[i]);i=(i+x%3-1)%s+((i/s+x/3-1)%s)*s
 c=c*9+len(a)-a.index(i)
d=long(n,9)
print'EGL'[(c>d)-(c<d)]

```

Golfs:

* 213: Short-circuiting, flawed solution.
* 209: First working solution.
* 202: Combined the two string lookups into one.

Edit: I just realised that this program, and thus KSab's too, were flawed in that they ignore multidigit cycle lengths. Example failure:

```
3117
2755
3117
7455

```

While the 3 has a cycle length of 2, and thus the above algorithm short circuits to 'L', this should in fact return 'G', because the cycle length of 14 on the second digit more than overcomes that. I have therefore changed the program. It also got shorter, funnily enough. To test your program, use `3117275531177455`. It should return `G`.

# Answer
> 1 votes
# CJam - 81

```
q:X,:L,{[L2*{_[_Lmqi:Smd@X=432501678s#3md]2/z{~+(S+S%}%Sb}*]L>_&,\X=~-}%9bg"EGL"=

```

Try it at http://cjam.aditsu.net/

It can probably be golfed some more.

# Answer
> 0 votes
# Lua - Not golfed yet

Just putting in here for safekeeping. I'll golf it (and implement the "For a larger grid these numbers might be larger than 8, but we can still use them as "digits"") later. Works though.

```
d={{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1}}
d[0]={0,0}ssd=''
n=arg[1]
q=math.sqrt(#n)t={}

    for y=1,q do
    table.insert(t,y,{})
    for x =1,q do
        v=(y-1)*q+x
        table.insert(t[y],x,n:sub(v,v)+0)
        io.write(t[y][x])
    end
end
for y=1,q do
    for x=1,q do
        cx=x cy=y pxy=''sd=0
        while pxy:match(cx..':%d*:'..cy..' ')==nil do
            pxy=pxy..cx..':'..sd..':'..cy.." "
            ccx=cx+d[t[cx][cy]][2]
            ccy=cy+d[t[cx][cy]][1]
            cx=ccx cy=ccy
            if cx<1 then cx=q elseif cx>q then cx=1 end
            if cy<1 then cy=q elseif cy>q then cy=1 end
            sd=sd+1
        end
        dds=(pxy:sub(pxy:find(cx..':%d+:'..cy)):match(':%d*'))
        ssd=ssd..(sd-dds:sub(2))
    end
end
print(ssd)
nn=tonumber(n,9) tn=tonumber(ssd,9)
if tn>nn then print("G") elseif tn==nn then print("E") else print("L") end

```

---
Tags: code-golf, graph-theory
---


title: Find a thumbnail in a mosaic

text:
# Question
Title: Find a thumbnail in a mosaic
After the last Ludum Dare (LD) game programming contest a friend of mine made a nice mosaic of all the LD game thumbnails:

After searching for my own game I quickly gave up and decided to solve it like a real programmer... by writing code that finds my game thumbnail.

This is the thumbnail of my game:

More examples can be found by going to the Ludum Dare list of games.

So what is the challenge? Write a program that has the following input:

```
<filename_mosaic> <amount_of_tiles_x> <amount_of_tiles_y> <filename_target>

```

For example using the images above:

```
mosaic.jpg 59 43 target.png

```

The output should be the index of the target image. For the mosaic and screenshot above the correct index is:

```
48,18

```

The following (non-golfed) code provides a working example:

```
public class MosaicFinder {

    //Start with java MosaicFinder mosaic.jpg  59 43 target.png
    public static void main(String[] args)  throws Exception {
        String mosaicFilename = args[0];
        int tilesX = Integer.parseInt(args[1]);
        int tilesY = Integer.parseInt(args[2]);
        String targetFilename = args[3];

        BufferedImage mosaic = ImageIO.read(new File(mosaicFilename));
        int tileHeight = mosaic.getHeight()/tilesY;
        int tileWidth = mosaic.getWidth()/tilesX;

        BufferedImage tofind = ImageIO.read(new File(targetFilename));

        //Translate target.png to correct size:
        BufferedImage matchCanvas = new BufferedImage(tileWidth, tileHeight, BufferedImage.TYPE_INT_RGB);
        AffineTransform at = AffineTransform.getScaleInstance((tileWidth*1.0)/tofind.getWidth(), (tileHeight*1.0)/tofind.getHeight());
        ((Graphics2D)matchCanvas.getGraphics()).drawRenderedImage(tofind, at);

        int bestIndexX = 0, bestIndexY = 0;
        BigInteger lowest = null;
        for(int x = 0; x<tilesX;x++) {
            for(int y = 0; y<tilesY;y++) {
                //For all tiles:
                BigInteger error = BigInteger.ZERO;
                for(int x1 = 0; x1<tileWidth;x1++) {
                    for(int y1 = 0; y1<tileHeight;y1++) {
                        int rgb1 = matchCanvas.getRGB(x1, y1);
                        int rgb2 = mosaic.getRGB((x*tileWidth)+x1, (y*tileHeight)+y1);
                        int r1 = (rgb1 >> 16) & 0xFF;
                        int r2 = (rgb2 >> 16) & 0xFF;
                        error = error.add(BigInteger.valueOf(Math.abs(r1-r2)));

                        int g1 = (rgb1) & 0xFF;
                        int g2 = (rgb2) & 0xFF;
                        error = error.add(BigInteger.valueOf(Math.abs(g1-g2)));

                        int b1 = rgb1 & 0xFF;
                        int b2 = rgb2 & 0xFF;
                        error = error.add(BigInteger.valueOf(Math.abs(b1-b2)));
                    }
                }
                if(lowest == null || lowest.compareTo(error) > 0) {
                    lowest = error;
                    bestIndexX = (x+1);
                    bestIndexY = (y+1);
                }
            }
        }
        System.out.println(bestIndexX+","+bestIndexY);
    }
}

```

This is a visual example of the code running:

This contest is a code-golf contest, the shortest code wins the challenge.

**Update:** It seems stackexchange messes up the images a bit, on my blog you can find the source images for the examples in correct resolution. Also: I've fixed the amount of images from 42 to 43

**Current best: David Carraher, Mathematica (280)**

# Answer
> 4 votes
# Mathematica - ~~280~~ 247

No need to scale the target to the tile size. The key is to match the average color for the target and for each tile. Closest match wins.
In principle, it would be possible for the routine to choose the wrong match, but the test case suggests that this approach is surprisingly robust. The mean colors of target and selected tile were almost a perfect match: a distance of 0.00296966 away from the target mean color in RGB colorspace "cube" with edges of length 1.

## Ungolfed 364 chars

```
f[{m_, tilesx_, tilesy_, targ_}] :=
 Module[{mosaic = Import[m],target = Import[targ], mDim = ImageDimensions[mosaic],

 (* find the average RGB colors for the target *)
 meanTargetPixelColor = Mean[Flatten[ImageData[target], 1]], m, t},
 m = ImagePartition[mosaic, {mDim[[1]]/tilesx, mDim[[2]]/tilesy}];

 (*Find the color distances between target mean rob and each mosaic tile
 Select the tile that best matches the average pixel color.*)
 t = SortBy[{#, EuclideanDistance[Mean[Flatten[ImageData[#], 1]],
 meanTargetPixelColor]} & /@ Flatten[m], Last][[1, 1]];
 Reverse[Position[m, t][[1]]]]

```

**Example**

Assuming that `mosaic` and `target`hold the respective filenames.

```
f[{mosaic, 59, 43, target}]

```

> {48,18}

---

## Golfed 247

```
f@{p_,x_,y_,s_}:=Module[{k=Flatten,i=Import,z=i@p,w,m,t,r},r=ImageDimensions@z;
w=Mean[k[ImageData[i@s],1]];m=ImagePartition[z,{r[[1]]/x,r[[2]]/y}];
Reverse[Position[m,SortBy[{#,EuclideanDistance[Mean[k[ImageData@#,1]],w]}&/@k@m,Last][[1,1]]][[1]]]]

```

# Answer
> 2 votes
# Python (360)

I seem to have broken PIL somehow, so load PPMs instead. For this reason, I insist that the thumbnail is already scaled correctly to the size of the tile in the mosaic. Its my first ever codegolf submission and I'm unsure the leeway I can expect in this regard.

```
import sys
I=int
R=range
O=open
M=map
N='\n'
A=ord
S=sum
# parse arguments
_,m,c,r,t=sys.argv
c=I(c)
r=I(r)
# load mosaic ppm
_,w,_,m=O(m).read().split(N,3)
w,h=M(I,w.split())
u=w/c
v=h/r
m=M(A,m)
# load thumbnail ppm
t=M(A,O(t).read().split(N,3)[3])
# make a list of the MSE of each tile in the mosaic, sort it, print the best
print sorted((S(S((p-q)**2 for p,q in zip(t[(y*u+x)*3:][:3],
m[((i*v+y)*w+j*u+x)*3:][:3])) for x in R(u) for y in R(v)),
j+1,i+1) for j in R(c) for i in R(r))[0][1:]

```

Its **really** slow because of the `m[ofs*3:][:3]` to get the channels for each pixel; that's creating a list of the remainder of the pixels, and then slicing just the first three... horrid performance :)

# Answer
> 1 votes
# Java ~~(551)~~ (523)

```
public class F{
    public static void main(String[]j)throws Exception{
        BufferedImage m=read(new File(j[0])),c;
        int x=parseInt(j[1]),a=parseInt(j[2]),
        w=m.getWidth()/x,h=m.getHeight()/a,
        b=0;
        c=new BufferedImage(w,h,1);
        c.getGraphics().drawImage(read(new File(j[3])).getScaledInstance(w,h,Image.SCALE_SMOOTH),0,0,null);
        for(int d=1<<30,y=x*a,e;--y>0;) {
            e=0;
            for(int z=w*h;z-->0;)
                for(int i=0,l=c.getRGB(z/h,z%h),k=m.getRGB(y/a*w+z/h,y%a*h+z%h);++i<3;l>>=8,k>>=8)
                    e+=pow((l&255)-(k&255),2);
            if(d>e){d=e;b=y;}
        }
        out.print(b/a+1+","+(b%a+1));
    }
}

```

Whitespace added to make it a bit clearer.

Based on Roy's, but using a MSE, which is I believe a much superior metric. And less characters.

Java is *really* verbose :/

Imports etc are:

```
import java.awt.Image;
import java.awt.image.BufferedImage;
import java.io.File;
import static javax.imageio.ImageIO.*;
import static java.lang.System.*;
import static java.lang.Math.*;
import static java.lang.Integer.parseInt;

```

# Answer
> 0 votes
# Java (707)

My example code in golfed mode, removing spaces and using small variable names, without the needed imports:

```
public class F{public static void main(String[]j)throws Exception{BufferedImage m=read(new File(j[0]));int M=0xFF,x=parseInt(j[1]),a=parseInt(j[2]),w=m.getWidth()/x,h=m.getHeight()/a,b=0,n=0;BufferedImage u=read(new File(j[3])),c=new BufferedImage(w,h,1);((Graphics2D)c.getGraphics()).drawRenderedImage(u,getScaleInstance((w*1.0)/u.getWidth(),(h*1.0)/u.getHeight()));BigInteger d=null;for(;x-->0;)for(int y=a;y-->0;){BigInteger e=ZERO;for(int z=w;z-->0;)for(int v=h;v-->0;){int l=c.getRGB(z,v),k=m.getRGB(x*w+z,y*h+v);e=e.add(valueOf(abs(((l>>16)&M)-((k>>16)&M)))).add(valueOf(abs(((l>>8)&M)-((k>>8)&M)))).add(valueOf(abs((l&M)-(k&M))));}if(d==null||d.compareTo(e)>0){d=e;b=x+1;n=y+1;}}out.print(b+","+n);}}

```

The imports are:

```
import java.awt.Graphics2D;
import java.awt.image.BufferedImage;
import java.io.File;
import java.math.BigInteger;
import static javax.imageio.ImageIO.*;
import static java.awt.geom.AffineTransform.*;
import static java.lang.System.*;
import static java.lang.Math.*;
import static java.lang.Integer.parseInt;
import static java.math.BigInteger.*;

```

Java is horrible for code golf, but at least it is below 1000.

---
Tags: code-golf, image-processing
---