Posts: 1,318

# Datacenter Cooling - Programming Exercise

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```
Super User
Posts: 10,778

## Datacenter Cooling - Programming Exercise

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;
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;
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

Posts: 1,318

## Re: Datacenter Cooling - Programming Exercise

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;

Super User
Posts: 10,778

## Re: Datacenter Cooling - Programming Exercise

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

Discussion stats
• 3 replies
• 778 views
• 0 likes
• 2 in conversation