Hamiltonian path count (Quora coding challenge)

I found the following programming challenge at quora.

Datacenter Cooling (Read more)

We have some rooms in our datacenter, and we need to connect them all with a single cooling duct.
Here are the rules:

The datacenter is represented by a 2D grid.
Rooms we own are represented by a 0.

Read more
.....
...

Datacenter Cooling (Less)

We have some rooms in our datacenter, and we need to connect them all with a single cooling duct.
Here are the rules:

The datacenter is represented by a 2D grid.
Rooms we own are represented by a 0.
Rooms we do not own are represented by a 1.
The duct has to start at the air intake valve, which is represented by a 2.
The duct has to end at the air conditioner, which is represented by a 3.
The duct cannot go in multiple directions out of the intake or the AC - they must be the two endpoints of the duct.
The duct must pass through each room exactly once.
The duct cannot pass through rooms we do not own.
The duct can connect between rooms horizontally or vertically but not diagonally.
Here is an example datacenter:

2 0 0 0

0 0 0 0

0 0 3 1

There are two possible ways to run the duct here:

2--0--0--0
|
0--0--0--0
|
0--0--3 1
or
2 0--0--0
| | |
0 0 0--0
| | |
0--0 3 1
Write a program to compute the number of possible ways to run the duct. For the above example, the correct answer is 2.

Input format:
Your program should read from stdin. The input will be a series of integers separated by whitespace.

The first two integers will be W and H, with width and height of the datacenter. These will be followed by W*H more integers, specifying the 2D grid representing the datacenter.

Output format:
Your program should write a single integer out to stdout: the number of possible ways to run the duct.

See how fast you can make it.

Our best solution (written in C) can solve the following test case in under 5 seconds on a 2.4GHz Pentium 4, but it's pretty good if you can get to within 1-2 orders of magnitude of that.

7 8
2 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
3 0 0 0 0 1 1

Submission
Send your solutions to jobs@quora.com


Less.

---

This problem amounts to count the number of Hamiltonian paths in a graph.
I wrote a small program to compute them, it runs in less than 45 seconds.
The code is (hidden) below.


Show the code.

Hide the code.


Implementation details:

*Recursive DFS graph exploration
*Truncate exploration as soon as the current path partitions the graph in two disconnected components.
If it separates the source from the target, then there is no chance to get a hamiltonian path.
*Stores the observed configurations in a hash. (Not in this version. See the c++ version.)

/* 
*  Count Hamiltonian paths.
*  Author: Gabriele Facciolo, (C) 2011
*
*  Compile with:
*     gcc --fast-math -O3 cool.c
*
*  Implementation details:
*    +Recursive DFS graph exploration
*    +Truncate exploration as soon as the current path 
*     partitions the graph in two disconnected components. 
*     If it separates the source from the target, then there 
*     is no chance to get a hamiltonian path.
*/


#include <stdio.h>

/* THE MATRIX */
#define M  7 // columns
#define N  8 // rows
int MAXl;

int A[N][M] = 
{ 
 {2, 0 ,0 ,0 ,0 ,0 ,0 },
 {0, 0 ,0 ,0 ,0 ,0 ,0 },
 {0, 0 ,0 ,0 ,0 ,0 ,0 },
 {0, 0 ,0 ,0 ,0 ,0 ,0 },
 {0, 0 ,0 ,0 ,0 ,0 ,0 },
 {0, 0 ,0 ,0 ,0 ,0 ,0 },
 {0, 0 ,0 ,0 ,0 ,0 ,0 },
 {3, 0 ,0 ,0 ,0 ,1 ,1 },
};


/* Neighbor offsets */
int dx[] = {0,-1,0,1};
int dy[] = {-1,0,1,0};


/* Position of the sink */
int zi=-1,zj=-1;

/* traverse the connected component of the graph
 with 0's starting from x,y and paint all them with -1*/
void recZero(int x,int y){
 int i,x1,y1;
 int retval=0;

 // find the next adjacent empty position 
 // with 0, or endpoint 3.
 for(i=0;i<4;i++) {
  x1 = x + dx[i];
  y1 = y + dy[i];
  if(x1>=0 && x1<M && y1>=0 && y1<N) { // sanity
   switch (A[y1][x1])  {
    case 0: 
     A[y1][x1] = -1;
     recZero(x1,y1);
     break;
   }
  }
 }
}

/* traverse the connected component of the graph
 with 0's starting from x,y, determine if it is the ONLY
 component, otherwise the graph is cut*/
int test_disconnected(void) {
 int i,j;
 int bad=0;
 // verify connectivity by painting connected nodes with -1
 // zi,zj are global and defined in main()
 recZero(zi,zj); 
 // unpaint the nodes and count the remaining zeros
 for(j=0;j<N;j++) for(i=0;i<M;i++) {
  if (A[j][i] == 0) bad ++ ;
  if (A[j][i] == -1)  A[j][i] = 0; 
 }
 return bad;
}


//recursive graph exploration
//take the current position, and the number of assigned positions
int rec(int x,int y, int l){
 int i,x1,y1;
 int retval=0;

 // REMOVE ALL PATHS THAT DISCONNECT THE GRAPH
 if( test_disconnected()) return 0;

 // find the next adjacent empty position 
 // with 0, or endpoint 3.
 for(i=0;i<4;i++) {
  x1 = x + dx[i];
  y1 = y + dy[i];
  if(x1>=0 && x1<M && y1>=0 && y1<N) { // sanity
   switch (A[y1][x1])  {
    case 0: 
     // in case of empty position, set it to 2
     A[y1][x1] = 2;
     // call the recursion
     retval+=rec(x1,y1,l+1);
     // unset it 
     A[y1][x1] = 0;
     break;
    case 3: 
     // in case of endpoint verify stuff.
     if (l >= MAXl){
      retval++;
     }
     break;
   }
  }
 }
 return retval;
}


int main() {

 printf("M=%d, N=%d\n", M,N);

 int i,j;
 // search the source
 int zis,zjs;
 for(j=0;j<N;j++) for(i=0;i<M;i++)  if (A[j][i] == 2 ){ zis=i; zjs=j; i=M;j=N; /* break */ } 

 // search the sink
 zi=-1, zj=-1;
 for(j=0;j<N;j++) for(i=0;i<M;i++)  if (A[j][i] == 3 ){ zi=i; zj=j;   i=M;j=N; /* break */ }

 // count zeros
 MAXl=0;
 for(j=0;j<N;j++) for(i=0;i<M;i++) { if (A[j][i] == 0) MAXl++; }

 // recursive call
 printf("%d\n", rec(zis,zjs,0));

}

---

syntax highlighted by Code2HTML, v. 0.9.1

Hide the code.

---

Show the C++ code.

Hide the C++ code.

Implementation details:

*Recursive DFS graph exploration
*Truncate exploration as soon as the current path partitions the graph in two disconnected components.
If it separates the source from the target, then there is no chance to get a hamiltonian path.
*Stores the observed configurations in a hash.

/* 
*  Count Hamiltonian paths.
*  Author: Gabriele Facciolo, (C) 2011
*
*  Compile with:
*     g++ -O3 --fast-math cool_store_hash.cpp
*
*  Implementation details:
*    +Recursive DFS graph exploration
*    +Truncate exploration as soon as the current path 
*     partitions the graph in two disconnected components. 
*     If it separates the source from the target, then there 
*     is no chance to get a hamiltonian path.
*    +Stores in a hash number of paths found for an already
*     observed configuration of the graph (that is: same 
*     current node and same free nodes).
*/


#include <stdio.h>
#include <string> 
#include <iostream> 
#include <ext/hash_map> 
//#include <tr1/unordered_map>




/* THE MATRIX */
#define M  7 // columns
#define N  8 // rows
int MAXl;

int A[N][M] = 
{ 
 {2, 0 ,0 ,0 ,0 ,0 ,0 },
 {0, 0 ,0 ,0 ,0 ,0 ,0 },
 {0, 0 ,0 ,0 ,0 ,0 ,0 },
 {0, 0 ,0 ,0 ,0 ,0 ,0 },
 {0, 0 ,0 ,0 ,0 ,0 ,0 },
 {0, 0 ,0 ,0 ,0 ,0 ,0 },
 {0, 0 ,0 ,0 ,0 ,0 ,0 },
 {3, 0 ,0 ,0 ,0 ,1 ,1 },
};



/* Neighbor offsets */
int dx[] = {0,-1,0,1};
int dy[] = {-1,0,1,0};


/* Position of the sink */
int zi=-1,zj=-1;

// trade some memory for speed by defining a hash to store
// the observed configurations

struct eqstr
{
 bool operator()(const char* s1, const char* s2) const
 {
  return strcmp(s1, s2) == 0;
 }
};


//typedef std::tr1::unordered_map<const char*, int> CFGtype;
typedef __gnu_cxx::hash_map<const char*, int, __gnu_cxx::hash<const char*>, eqstr> CFGtype;
CFGtype configs;

char codes[] = { '0', '1', '2','3'};

// compute an unique id for the configuration (a hash should be sufficient)
// encode each empty position as a bit
char* id(int A[][M], int x,int y,int l) {
 char * s =(char*) malloc((M*N+4)*sizeof(char));
 s[0]=l+1;
 s[1]=x+1;
 s[2]=y+1;
 int i,j;
 int t=3;
 for(j=0;j<N;j++) for(i=0;i<M;i++) {
  s[t]=codes[A[j][i]];
  t++;
 }
 s[t] = (char) NULL;

 return s;

}

void  showid(char* s){
 int i,j,t;
 printf("%d %d %d\n",s[0]-1, s[1]-1,s[2]-1);
 t=3;
 for(j=0;j<N;j++){ 
  for(i=0;i<M;i++) { 
   printf("%c ",s[t]);
   t++;
  } 
  printf("\n");
 }
}




void recZero(int x,int y){
 int i,x1,y1;
 int retval=0;

 // find the next adjacent empty position 
 // with 0, or endpoint 3.
 for(i=0;i<4;i++) {
  x1 = x + dx[i];
  y1 = y + dy[i];
  if(x1>=0 && x1<M && y1>=0 && y1<N) { // sanity
   switch (A[y1][x1])  {
    case 0: 
     A[y1][x1] = -1;
     recZero(x1,y1);
     break;
   }
  }
 }
}

/* traverse the connected component of the graph
 with 0's starting from x,y, determine if it is the ONLY
 component, otherwise the graph is cut*/
int test_disconnected(void) {
 int i,j;
 int bad=0;
 // verify connectivity by painting connected nodes with -1
 // zi,zj are global and defined in main()
 recZero(zi,zj); 
 // unpaint the nodes and count the remaining zeros
 for(j=0;j<N;j++) for(i=0;i<M;i++) {
  if (A[j][i] == 0) bad ++ ;
  if (A[j][i] == -1)  A[j][i] = 0; 
 }
 return bad;
}





int NEWcount = 0;
int HITcount = 0;

//recursive graph exploration
//take the current position, and the number of assigned positions
//store all the explored positions
int rec2(int x,int y, int l){
 int i,x1,y1;
 int retval=0;

 // REMOVE ALL PATHS THAT DISCONNECT THE GRAPH
 if( test_disconnected()) return 0;

 // STORE RESULTS FOR PATH LENGHTS UP TO 100
 if(l <= 100) {
  char* str = id(A,x,y,l);
  //  showid(str);
  CFGtype::iterator iter  = configs.find(str);
  if (iter == configs.end() ) {
   // if the configuration is new -> compute the value of count, store it 
   // find the next adjacent empty position 
   // with 0, or endpoint 3.
   for(i=0;i<4;i++) {
    x1 = x + dx[i];
    y1 = y + dy[i];
    if(x1>=0 && x1<M && y1>=0 && y1<N) { // sanity
     switch (A[y1][x1])  {
      case 0: 
       // in case of empty position, set it to 2
       A[y1][x1] = 2;
       // call the recursion
       retval+=rec2(x1,y1,l+1);
       // unset it 
       A[y1][x1] = 0;
       break;
      case 3: 
       // in case of endpoint verify stuff.
       if (l >= MAXl){
        retval++;
       }
       break;
     }
    }
   }

   // store
   //configs.insert(std::pair<char *, int>(str, c));
   NEWcount++;
   configs[str] = retval;

   return retval;
  } else {
   // if the configuration is known -> just retrive the value and increse Ccount.
   HITcount++;

   retval = iter->second;
   free(str);
   return retval;
  }
 } else {
  // OTHERWISE DO NOT STORE AND JUST COMPUTE

  // find the next adjacent empty position 
  // with 0, or endpoint 3.
  for(i=0;i<4;i++) {
   x1 = x + dx[i];
   y1 = y + dy[i];
   if(x1>=0 && x1<M && y1>=0 && y1<N) { // sanity
    switch (A[y1][x1])  {
     case 0: 
      // in case of empty position, set it to 2
      A[y1][x1] = 2;
      // call the recursion
      retval+=rec2(x1,y1,l+1);
      // unset it 
      A[y1][x1] = 0;
      break;
     case 3: 
      // in case of endpoint verify stuff.
      if (l >= MAXl){
       retval++;
      }
      break;
    }
   }
  }
  return retval;
 }
}



int main() {

 printf("M=%d, N=%d\n", M,N);

 int i,j;
 // search the source
 int zis,zjs;
 for(j=0;j<N;j++) for(i=0;i<M;i++)  if (A[j][i] == 2 ){ zis=i; zjs=j; i=M;j=N; /* break */} 

 // search the sink
 zi=-1, zj=-1;
 for(j=0;j<N;j++) for(i=0;i<M;i++)  if (A[j][i] == 3 ){ zi=i; zj=j;   i=M;j=N; /* break */ } 

 // count zeros
 MAXl=0;
 for(j=0;j<N;j++) for(i=0;i<M;i++) { if (A[j][i] == 0) MAXl++; }

 // recursive call
 int c = rec2(zis,zjs,0);
 printf("CACHE STATISTICS: %d \nHITS%d NEWS%d\n", c , HITcount, NEWcount);

}

---

syntax highlighted by Code2HTML, v. 0.9.1

Hide the C++ code.