topic Re: Datacenter Cooling - Programming Exercise in SAS Programming

Datacenter Cooling - Programming Exercise

FriedEgg — Wed, 14 Mar 2012 20:19:23 GMT

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:

There are two possible ways to run the duct here:

2--0--0--0
         |
0--0--0--0
|
0--0--3  1

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

Datacenter Cooling - Programming Exercise

Ksharp — Fri, 16 Mar 2012 08:51:29 GMT

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

Re: Datacenter Cooling - Programming Exercise

FriedEgg — Mon, 19 Mar 2012 22:24:21 GMT

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;

Re: Datacenter Cooling - Programming Exercise

Ksharp — Tue, 20 Mar 2012 04:18:39 GMT

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