Google Codejam 2009 Qualification problem: Watershed in C++

Question

I tried out this Codejam problem and produced a valid solution in C++. There is a Python solution on the website. Was wondering if any C++ people would offer some improvements/optimizations to this solution. Thanks!

BTW: In Codejam the goal is to write code as fast as possible (a reason why Python would have been a better language choice) but I'm interested in improving the solution.

#include <algorithm>
#include <fstream>
#include <iostream>
#include <iterator>
#include <sstream>
#include <string>
#include <vector>

#include <assert.h>
#include <stdlib.h>

// Watershed Practice Problem
// http://code.google.com/codejam/contest/dashboard?c=90101#s=p1

using namespace std;

#ifdef DEBUG
static int running_time;
#endif

void SplitString(const string &s,
                 char delim,
                 vector<string> &elems) {
  stringstream ss(s);
  string item;
  while(getline(ss, item, delim)) {
    elems.push_back(item);
  }
}

void PrintMap(const char map[], int height, int width) {
    for (int i = 0; i < height; ++i) {
      for (int j = 0; j < width; ++j) {
        cout << map[(i * width) + j] << " "; 
      }
      cout << endl;
    }
}

void MinNeighbor(const int altitude_map[],
                 int height, int width,
                 int i, int j,
                 int & n_i, int & n_j) {
  int min_altitude = altitude_map[(i * width) + j];

  n_i = i;
  n_j = j;

  // North.
  if ((i - 1) >= 0
      && altitude_map[((i - 1) * width) + j] < min_altitude)  {
    min_altitude = altitude_map[((i - 1) * width) + j];
    n_i = i - 1;
    n_j = j;
  }
  // West.
  if ((j - 1) >= 0
      && altitude_map[(i * width) + (j - 1)] < min_altitude) {
    min_altitude = altitude_map[(i * width) + (j - 1)]; 
    n_i = i;
    n_j = j - 1;
  }
  // East.
  if ((j + 1) < width
      && altitude_map[(i * width) + (j + 1)] < min_altitude) {
    min_altitude = altitude_map[(i * width) + (j + 1)]; 
    n_i = i;
    n_j = j + 1;
  }
  // South.
  if ((i + 1) < height
      && altitude_map[((i + 1) * width) + j] < min_altitude)  {
    min_altitude = altitude_map[((i + 1) * width) + j];
    n_i = i + 1;
    n_j = j;
  } 
}

void Drain(const int altitude_map[],
           char label_map[],
           char & label,
           int height, int width,
           int i, int j) {
  int n_i = 0;
  int n_j = 0;

  MinNeighbor(altitude_map, height, width, i, j, n_i, n_j);

#ifdef DEBUG
  cout << endl;
  cout << "The min neighbor of : (" << i << "," << j << ") ";
  cout << "is (" << n_i << "," << n_j << ")" << endl;
#endif

  if (altitude_map[(n_i * width) + n_j] < altitude_map[(i * width) + j]) {
    // We are draining into an existing basin; use its label.
    if (label_map[(n_i*width) + n_j] != '-')
      label = label_map[(n_i*width) + n_j];
    else // Drain into the neighboring cell with the smallest altitude.
      Drain(altitude_map, label_map, label, height, width, n_i, n_j);
  }

  label_map[(i*width) + j] = label;

#ifdef DEBUG
  ++running_time;
#endif
}

int main(int argc, char *argv[]) {
  string file_name;
  if (argc < 2)
    file_name = "B-tiny-practice.in";
  else
    file_name = argv[1];

  ifstream input_file;
  input_file.open(file_name.c_str());

  assert(input_file.is_open());

  string line;
  // The first line contains the number of maps.
  getline(input_file, line); 

  int num_maps = atoi(line.c_str());
  int case_num = 1;

  while (case_num <= num_maps) {
    assert(!input_file.eof());

    getline(input_file, line);  // Line should have two numbers: W H.

    size_t delim = line.find(" ");
    int height = atoi(line.substr(0, delim).c_str());
    int width = atoi(line.substr(delim + 1).c_str());

    int altitude_map[height * width];
    char label_map[height * width];

    // Populate the altitude map and initialize the label map.
    for (int i = 0; i < height; ++i) {
      assert(!input_file.eof());
      getline(input_file, line);

      vector<string> row;
      SplitString(line, ' ', row); 

      int j = 0;
      for (vector<string>::const_iterator ci = row.begin(); 
          ci != row.end(); ++ci) {
        label_map[(i * width) + j] = '-';
        altitude_map[(i * width) + j++] = atoi(ci->c_str());
      }
    }

    char current_label = 'a';

    // Populate the labels.
    for (int i = 0; i < height; ++i) {
      for (int j = 0; j < width; ++j) {
        if (label_map[(i * width) + j] == '-') {
          char label = current_label;
          Drain(altitude_map, label_map, label, height, width, i, j);
          if (label == current_label)
            ++current_label;
        }
      }
    }

    cout << "Case #" << case_num++ << ":" << endl;
    PrintMap(label_map, height, width);

#ifdef DEBUG
    cout << endl << "Running Time: " << running_time << endl;
    running_time = 0;
#endif
  }

  input_file.close();

  return 0;
}

// vim:set sw=2 sts=2 ts=2:

Answer 1

One way to at least make the code look nicer is to use what I call direction vectors. I don't know if there's a name for them in the literature or not. Say you are at a position [X][Y] and want to list its neighbours. Consider:

dx[] = {1, 0, 0 - 1};
dy[] = {0, -1, 1, 0};

Now, this will give you the neighbours in order as asked by the problem:

for ( i = 0; i < 4; ++i )
{
  newx = X + dx[i];
  newy = Y + dy[i];
  // [newx][newy] is a neighbour of [X][Y]
}

Second, I would suggest you avoid using the vector type in a programming contest, as it tends to be slower than using char arrays. Same with the string type. Try to stick to classic C data types unless a C++ data structure will REALLY make your life easier.

Third, don't use a a one-dimensional array when you could use a 2d one, doing the multiplications yourself is probably slower anyway. It's definitely not going to get you an advantage anyway.

Fourth, try to avoid local variables. Declaring things like:

int altitude_map[height * width];
char label_map[height * width];

locally can be VERY expensive in a contest, especially since yours are in a loop. It's good PROGRAMMING practice, but it's bad if you want every bit of speed you can get.

Other than that, the theoretical complexity is O(rows x cols), which is optimal.

Edit: are you reading the numbers as strings? Don't, stringstreams are also slow, just read them in as ints or use the C fread function if you want to have a really fast reading.

Edit 2: avoid recursion! you can use a FIFO queue that stores your position and thus avoid your recursive calls. Basically, do a BF search instead of your current DF search. Look up the Lee algorithm. Check my reply here: http://stackoverflow.com/questions/2288830/change-floodfill-algorithm-to-get-voronoi-territory-for-two-data-points/2288898#2288898

Answer 2

Here is the solution from the fastest (7 mins) contestant in C. Very concise. He doesn't even take the time to use the Spacebar :)

#include<stdio.h>
#include<memory.h>
#include<string.h>
#define INF 999999
int n, m;
int a[128][128];
int path[128][128];
int dx[4]={-1, 0, 0, 1};
int dy[4]={0, -1, 1, 0};
int inv[4]={3, 2, 1, 0};
int ans[128][128], anscnt;
bool v[128][128];
void f1(int x, int y)
{
    v[x][y]=true; ans[x][y]=anscnt;
    int k, nx, ny;
    if(path[x][y]!=-1)
    {
        nx=x+dx[path[x][y]];
        ny=y+dy[path[x][y]];
        if(!v[nx][ny]) f1(nx, ny);
    }
    for(k=0;k<4;k++)
    {
        nx=x+dx[k]; ny=y+dy[k];
        if(nx<1 || ny<1 || nx>n || ny>m) continue;
        if(path[nx][ny]!=-1 && nx+dx[path[nx][ny]]==x && ny+dy[path[nx][ny]]==y && !v[nx][ny])
            f1(nx, ny);
    }
}
int main()
{
    char filename[32];
    char infile[32], outfile[32];
    scanf("%s", filename);
    strcpy(infile, filename); strcpy(outfile, filename);
    strcat(infile, ".in"); strcat(outfile, ".out");
    FILE *fp=fopen(infile, "r"), *ofp=fopen(outfile, "w");

    int t, tc;
    int i, j, k;
    int nx, ny;
    int mh, pt;
    fscanf(fp, "%d", &tc);
    for(t=1;t<=tc;t++)
    {
        fscanf(fp, "%d%d", &n, &m);
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++) fscanf(fp, "%d", &a[i][j]);
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                mh=INF;
                path[i][j]=-1;
                for(k=0;k<4;k++)
                {
                    nx=i+dx[k]; ny=j+dy[k];
                    if(nx<1 || ny<1 || nx>n || ny>m) continue;
                    if(mh>a[nx][ny]){mh=a[nx][ny]; pt=k;}
                }
                if(mh>=a[i][j]) continue;
                path[i][j]=pt;
            }
        }
        anscnt=0;
        memset(v, false, sizeof(v));
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                if(v[i][j]) continue;
                anscnt++; f1(i, j);
            }
        }
        fprintf(ofp, "Case #%d:\n", t);
        for(i=1;i<=n;i++)
        {
            for(j=1;j<m;j++)
            {
                fprintf(ofp, "%c ", ans[i][j]+'a'-1);
            }
            fprintf(ofp, "%c\n", ans[i][m]+'a'-1);
        }
    }
    return 0;
}