2 versions right now,
acv.c - Recursive solution, runs in 8 minute range
acvent.c - Iterative solution, runs in 20 minute range (it's missing some of the bits from the recursive solution, I've been lazy about copying some of the code over from acv.c )
Some test files
66.in - 6x6 matrix
76.in - 7x6 matrix
78.in - 7x8 matrix
compiled using gcc acv.c -O3
/// From the Quora Challenge Page ///
Programming Challenges
1. 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