DATA Step, Macro, Functions and more

Datacenter Cooling - Programming Exercise

Reply
Trusted Advisor
Posts: 1,301

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,035

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. Smiley Sad

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

Trusted Advisor
Posts: 1,301

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,035

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

Ask a Question
Discussion stats
  • 3 replies
  • 719 views
  • 0 likes
  • 2 in conversation