Robert Eisele
Engineer, Systems Architect and DBA

Codingame: Surface

Original Problem

The Goal

"The wars of the 21st century will be fought over water."
Although freshwater is available in limited quantity, it’s not actually scarce. There’s more than enough to satisfy the current needs of the global population, but only if it were possible to locate and measure the bodies of water available in a geographical area!

Your mission is to pinpoint the surface areas of water. You have a map which describes the contents of each square meter of a geographical zone. One square meter is composed of either land or water. One map can contain several bodies of water.

Rules

Your program receives as input a list of coordinates. For each one you must determine the surface area of the lake which is located there. If there is no lake, then the surface area equals 0.

Here's an example of a map. The green squares represent land, and the blue squares represent water. A lake is made up of a set of water squares which are horizontally or vertically adjacent. Two squares which are only diagonally adjacent are not part of the same lake.
In this example, the lake which is located in coordinates (1, 2) has a surface area of 3 square meters.

A map in ASCII format is provided as input. The character # represents land and the letter O (uppercase) represents water. In this format, the map shown above will be represented as follows:
####
##O#
#OO#
####

Game Input

Input

Line 1: the width L of the map

Line 2: the height H of the map

H following lines: L characters # or O

Following line: the number N of coordinates to be tested

N following lines: the coordinates X Y to be tested, separated by a space

Output
N lines: each displaying the surface area of the lake located at the coordinates given in input.
Constraints
0 < L < 10000
0 < H < 10000
0 ≤ X < L
0 ≤Y < H
0 < N < 1000

Solution

This problem is pretty nice. It's really easy to implement but due to the size of the grid and the maximum number of test cases, this one becomes quite interesting. My first idea was generating a map, where each cell contains the size of the adjacent water area. This would be the fastest when it comes to execution time, but uses tremendous amounts of memory (1000x1000 grid with 4 byte per cell). Also creating a map like this would be really slow.

The next idea was using a flood fill algorithm. The recursive implementation could have the problem of stack overflows on large water areas, so I decided to go with a stack based version. When we get a cell-coordinate, we push it on a stack and check if that coordinate was water. If it was, we can increment the area counter and push all adjacent cells on the stack. We also mark the already visited spot with an X to not come into an endless loop:

function getWaterArea(map, x, y) {

  var stack = [[x, y]];
  var cnt = 0;

  while (stack.length > 0) {
    [x, y] = stack.pop();

    if (map[y] && map[y][x] === 'O') {
      map[y][x] = 'X';
      cnt++;
      stack.push([x, y + 1]);
      stack.push([x, y - 1]);
      stack.push([x + 1, y]);
      stack.push([x - 1, y]);
    }
  }
  return cnt;
}

When executing this algorithm, we need to make sure that the two dimensional array is copied for every iteration, so that we have a clean map all the time. I now made several optimizations. 1. I stored the map in a one-dimensional typed array with the small additional cost of coordinate calculation, but loss of loads of array creations. 2. I removed the array creation and added another loop which was resetting every marked cell. I also added checks before adding new coordinates to the stack, if they are valid. The final clou was removing the cleaning loop by passing the index of the current test case (offsetted by two). This allows the identification of a marked cell of the current test case. All in all, this is what I came up with, after all the optimizations:

function _(x, y) {
  return y * L + x;
}

function getWaterArea(map, x, y, ndx) {

  var stack = [_(x, y)];
  var cnt = 0;

  while (stack.length > 0) {
    var c = stack.pop();

    if (map[c] !== 0 && map[c] !== ndx) {
      map[c] = ndx;

      x = c % L;
      y = c / L | 0;

      if (y + 1 < H) stack.push(_(x, y + 1));
      if (y > 0)     stack.push(_(x, y - 1));
      if (x + 1 < L) stack.push(_(x + 1, y));
      if (x > 0)     stack.push(_(x - 1, y));
      cnt++;
    }
  }
  return cnt;
}

var L = +readline();
var H = +readline();

var M = new Uint16Array(L * H);

for (var y = 0; y < H; y++) {
  var line = readline();
  for (var x = 0; x < L; x++) {
    M[_(x, y)] = line[x] === 'O';
  }
}

var N = +readline();
for (var y = 0; y < N; y++) {
  var inputs = readline().split(' ');
  print(getWaterArea(M, +inputs[0], +inputs[1], y + 2));
}

Go to overview

All images are copyright to Codingame