- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content
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
- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content
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
- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content
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;
- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content
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