Datacenter Cooling - Programming Exercise

[FriedEgg]

This challenge is courtesy of Quora http://www.quora.com/challenges

Datacenter Cooling

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

[Ksharp]

FriedEgg,

I can't get result. My memory is broken.

I can't believe it can spend 5 seconds to find the answer. there is must be some special algorithm.

I am collapsed.

data x(drop=r c);
length start $ 2;
retain c r;
if _n_ eq 1 then do;
                   input c r;
                 end;
 else do;
  do row=1 to r;
   do col=1 to c;
    start=cats(row,col);
    input v @@;
    if v ne 1 then output;
    if v='2' then call symputx('start',cats(row,col));
     else if v='3' then call symputx('end',cats(row,col));
   end;
 end;
end;
cards;
4 3
2  0  0  0
0  0  0  0
0  0  3  1
;
run; 
data path(keep=start end);
if _n_ eq 1 then do;
 if 0 then set x;
 declare hash ha(dataset:'x');
  ha.definekey('row','col');
  ha.definedata('v');
  ha.definedone();
end;
set x nobs=n end=last;
length end $ 2;
if start ne "&end" then do;
r=row-1;c=col;
if ha.find(key:r,key:c)=0 and v ne 2 then do;end=cats(r,c);output;end;
r=row+1;c=col;
if ha.find(key:r,key:c)=0 and v ne 2 then do;end=cats(r,c);output;end;
r=row; c=col-1;
if ha.find(key:r,key:c)=0 and v ne 2 then do;end=cats(r,c);output;end;
r=row; c=col+1;
if ha.find(key:r,key:c)=0 and v ne 2 then do;end=cats(r,c);output;end;
end;
if last then call symputx('n',n-1);
run;

data _null_;
 if 0 then set path;
 declare hash ha(hashexp:10,dataset:'path',multidata:'Y');
 declare hiter hi('ha');
  ha.definekey('start');
  ha.definedata('start','end');
  ha.definedone();
length path _path $ 200;
 declare hash _ha(hashexp:10,ordered:'Y');
 declare hiter _hi('_ha');
  _ha.definekey('count');
  _ha.definedata('count','path');
  _ha.definedone();

set path(where=(start="&start")) end=last;
x=0;x+1;count=x;path=catx(' ',start,end);_ha.add();
rc=_hi.first();
do while(rc=0);
 _path=path;index=scan(_path,-1); _count=count; 
 do while(hi.next()=0);
 if index=start then do;
                if not find(path,end) then do;
                 if end ne "&end" then do;
                    x+1;count=x;path=catx(' ',path,end);_ha.add();path=_path;
                                       end;
                    else if countw(path)=&n then n_path+1;
                                           end;
                end;
 end;
rc=_hi.next();
rx=_ha.remove(key:_count);
end;
if last then putlog "How many path: " n_path ;
run;

Ksharp

[FriedEgg]

KSharp,

This one is very difficult.  I would not have actually posted this one had I though it through fully first (a mistake on my part).  I have come with the following solution thanks to help from a friend and it definitly breaks convention since I have written the program in JAVA...  But SAS can use JAVA so maybe cheating is okay, hah.

This problem is a Hamiltonian path (http://en.wikipedia.org/wiki/Hamiltonian_path).  Solving a problem of this nature is difficult.  Possibly well suited in SAS for the recursion available through FCMP or maybe in IML a friend also said SAS/OR NETFLOW Procedure may be useful here.  But I'd rather not hurt my head trying anymore.

JAVA Code, minorly adapted, by Pathikrit Bhowmick

import java.util.HashMap; 
public class Quora {
    static final int NULL = -1, OPEN = 0, BLOCKED = 1, START = 2, END = 3,
            XSHIFT = 3, YMASK = (1 << XSHIFT) - 1,  //SHIFT needs to be increased if X or Y need more than SHIFT bits
            D[] = new int[]{1, -1, -(1 << XSHIFT), 1 << XSHIFT}, //deltas for Left, Right, Up, Down
            CACHE_SIZE = 1 << 16;
    static final boolean VISITABLE = true;
    static boolean matrix[];
    static int remaining,
            start, end,     // last SHIFT bits are y; x is stored in SHIFT bits on the left of y.
            X, Y;
    static long state; // use 64-bits to represent upto 64 cells, always make sure you use 1L when shifting, for large cases use BitSet
    static HashMap<String, Integer> cache = new HashMap<String, Integer>(CACHE_SIZE);
    static int compute(final int p) {
        matrix
 = !VISITABLE;
        remaining--;
        final int stateBit = ((p >> XSHIFT) - 1) * Y + ((p & YMASK) - 1);
        state |= (1L << stateBit);
        try {
            {
                Integer cachedValue = cache.get(state + "$" + p);
                if (cachedValue != null)
                    return cachedValue;
            }
            if (numOfExits(end) == 0 || !isFloodFillable())  // TODO: smart schedule floodfills - maybe more later or after 3 running sum left turns?
                return cacheAndReturn(state, p, remaining == 1 ? 1 : 0);
            int onlyChoice = NULL;
            for (int d : D) {
                if (matrix[d += p] && d != end && numOfExits(d) == 1) {
                    if (onlyChoice != NULL)
                        return cacheAndReturn(state, p, 0);
                    onlyChoice = d;
                }
            }
            if (onlyChoice == NULL) {
                int paths = 0;
                for (int d : D)
                    if (matrix[d += p])
                        paths += compute(d);
                return cacheAndReturn(state, p, paths);
            }
            return cacheAndReturn(state, p, compute(onlyChoice));
        } finally {
            matrix
 = VISITABLE;
            state &= ~(1L << stateBit);
            remaining++;
        }
    }
    static int cacheAndReturn(final long state, final int p, final int ans) {
        cache.put(state + "$" + p, ans);
        return ans;
    }
    static int queue[];
          private static String dataCenter;
    static boolean isFloodFillable() {
        int p = end, tail = 0;
        queue[tail++] = p;
        matrix
 = !VISITABLE;
        for (int head = 0; tail > head; head++) {
            p = queue[head];
            for (int d : D)
                if (matrix[d += p])
                    matrix[queue[tail++] = d] = !VISITABLE;
        }
        for (int i = 0; i < tail; i++)
            matrix[queue] = VISITABLE;
        return remaining == tail;
    }
    static int numOfExits(int p) {
        int exits = 0;
        for (int d : D)
            if (matrix[p + d])
                exits++;
        return exits;
    }
    public static void main(String args[]) {
        java.util.Scanner in = new java.util.Scanner(dataCenter);
        remaining = (Y = in.nextInt()) * (X = in.nextInt());
        matrix = new boolean[((X + 2) << XSHIFT) | (Y + 2)];
        int p;
        for (int i = 1; i <= X; i++)
            for (int j = 1; j <= Y; j++) {
                matrix[p = (i << XSHIFT) | j] = VISITABLE;
                switch (in.nextInt()) {
                    case START:
                        start = p;
                        break;
                    case END:
                        end = p;
                        break;
                    case BLOCKED: {
                        remaining--;
                        matrix
 = !VISITABLE;
                        state |= 1L << ((i - 1) * Y + (j - 1));
                    }
                }
            }
        queue = new int[remaining];
        System.out.println(compute(start));
    }
}

Compile Class

javac Quora.java

Launch SAS

sas -SET CLASSPATH /path/to/class/folder

data foo;

declare javaobj s('Quora');

s.setStaticStringField('dataCenter','4 3 2 0 0 0 0 0 0 0 0 0 3 1');

s.callVoidMethod("main");

s.flushJavaOutput();

run;

[Ksharp]

FriedEgg,

Thank you to point it out that it is Hamiltonian Cycle, I will study the URL you posted.

I am beginner of JAVA, therefore I can't understand the Java code totally. Honestly I hope to see some SAS code to solve this problem.

BTW, I really hope my computer has very large of memory to run it out .

Ksharp