Monday 15 September 2014

Programming Puzzle to solve

Here is a good programming puzzle I solved over the weekend just to "sharpen my code axe"

-------------------------------------------------------------------------------------------------------------------
Ropes and Weights

In a room there are N ropes and N weights. Each rope is connected to exactly one weight (at just one end), and each rope has a particular durability − the maximum weight that it can suspend.
There is also a hook, attached to the ceiling. The ropes can be attached to the hook by tying the end without the weight. The ropes can also be attached to other weights; that is, the ropes and weights can be attached to one another in a chain. A rope will break if the sum of weights connected to it, directly or indirectly, is greater than its durability.
We know the order in which we want to attach N ropes. More precisely, we know the parameters of the rope (durability and weight) and the position of each attachment. Durabilities, weights and positions are given in three zero-indexed arrays A, B, C of lengths N. For each I (0 ≤ I < N): • A[I] is the durability of the I-th rope, • B[I] is the weight connected to the I-th rope, • C[I] (such that C[I] < I) is the position to which we attach the I-th rope; if C[I] equals −1 we attach to the hook, otherwise we attach to the weight connected to the C[I]-th rope. The goal is to find the maximum number of ropes that can be attached in the specified order without breaking any of the ropes. Write a function: int solution(int A[], int B[], int C[], int N); that, given three zero-indexed arrays A, B, C of N integers, returns the maximum number of ropes that can be attached in a given order. For example, given the following arrays: A[0] = 5 B[0] = 2 C[0] = -1 A[1] = 3 B[1] = 3 C[1] = 0 A[2] = 6 B[2] = 1 C[2] = -1 A[3] = 3 B[3] = 1 C[3] = 0 A[4] = 3 B[4] = 2 C[4] = 3

 See image below. When the rope breaks(weight, think cumulative weight, attached to it becomes more than its durability) it is shown as dotted line.
 

the function should return 3, as if we attach a fourth rope then one rope will break, because the sum of weights is greater than its durability (2 + 3 + 1 = 6 and 6 > 5).
Given the following arrays:
A[0] = 4 B[0] = 2 C[0] = -1
A[1] = 3 B[1] = 2 C[1] = 0
A[2] = 1 B[2] = 1 C[2] = 1

See image blow.


the function should return 2, as if we attach a third rope then one rope will break, because the sum of weights is greater than its durability (2 + 2 + 1 = 5 and 5 > 4).
Assume that:
• N is an integer within the range [0..100,000];
• each element of array A is an integer within the range [1..1,000,000];
• each element of array B is an integer within the range [1..5,000];
• each element of array C is an integer such that −1 ≤ C[I] < I, for each I (0 ≤ I < N).
Complexity:
• expected worst-case time complexity is O(N*log(N));
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.
-------------------------------------------------------------------------------------------------------------------
I chose Python as my programming language as it becomes really easy to manipulate the arrays as lists, and many complex tasks of array indexing, and other operations are easily done by various Python idioms and modules.

Here is my Solution which won me a Silver Badge award in the programming challenge(Yeah! Weekend well spent I say)

def solution(A, B, C):  
   lenC = len(C)  
   if lenC==0:  
     return 0      
   cumwt = [0]*lenC  
   i=0   
   lut = [0]*lenC  
   for v in C:  
     if v == -1:  
       cumwt[i] = B[i]  
       if cumwt[i] > A[i]:  
         return i  
       else:  
         i = i + 1                
     else:  
       cumwt[i] = cumwt[i] + B[i]   
       if cumwt[i] > A[i]:  
         return i              
       while v != -1:  
         idx = v  
         v =C[idx]  
         cumwt[idx] = cumwt[idx] + B[i]                   
         if cumwt[idx] > A[idx]:  
           return i   
       i = i + 1       
   return i    
 #D= [5,3,6,3,3]  
 #D=[4,3,1]  
 D=[]  
 #W=[2,3,1,1,2]  
 #W=[2,2,1]  
 W=[]  
 #P=[-1,0,-1,0,3]  
 #P=[-1,0,1]  
 P=[]  
 print solution(D,W,P) 
Below is the complete test report of my solution which was evaluated against various functionality and performance tests.My solution failed 1 large data-set performance test because solution wasn't optimized for speed and outran the stipulated time for that test case. 
Analysis
Detected time complexity: O(N*log(N))
testtimeresult
Example tests
example1  first example from the problem statement0.064 sOK
example2  second example from the problem statement0.060 sOK
Correctness tests
extreme_empty_one  no ropes and only one rope0.064 sOK
tiny  only two ropes0.060 sOK
small  only three ropes0.068 sOK
small_random  small random trees, 10 <= N <= 300.064 sOK
Performance tests
star  tree forms a star, N ~= 5,0000.084 sOK
medium_random  medium random trees, N ~= 10,0000.104 sOK
large_random  large random trees, N ~= 100,0000.660 sOK
line  large random trees, N ~= 100,000>11.000 sTIMEOUT ERROR  running time: >11.00 sec., time limit: 5.33 sec.

2 comments:

Parkash said...

Can't we add

A[3] = 3 B[3] = 1 C[3] = 0

node right after node 1 i.e in right sub tree instead of left sub-tree ?
If ad it in right sub-tree durability will remain under control i.e. (1+1 <6)

fatih tekin said...

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;


public class RopeQuestion {

public static void main(String[] args) {

int A[] = {5,3,6,3,3};
int B[] = {2,3,1,1,2};
int C[] = {-1,0,-1,0,3};
System.out.println((new RopeQuestion().solution(A, B, C)));
}

class RopeNode{
List childNodes =new ArrayList();
RopeNode parentNode;
int strength;
int value;
int total;
RopeNode weakestRopeNode;
}

public int solution(int[] A, int[] B, int[] C) {

if(A == null || B== null || C== null || A.length==0 || B.length==0 || C.length == 0){
return 0;
}

int abMin = Math.min(A.length, B.length);
int min = Math.min(abMin, C.length);
if(C[0] != -1){
return 0;
}
HashMap ropeNodesMap = new HashMap();
for (int order = 0; order < A.length && order < min; order++) {
RopeNode ropeNode = new RopeNode();
ropeNodesMap.put(order, ropeNode);
ropeNode.value = B[order];
ropeNode.strength = A[order];
ropeNode.total = B[order];
if(ropeNode.value > ropeNode.strength){
return ropeNodesMap.size() - 1;
}
if(C[order] != -1){
RopeNode parentNode = ropeNodesMap.get(C[order]);
if(parentNode == null) {
return ropeNodesMap.size() - 1;
}
ropeNode.parentNode = parentNode;
parentNode.childNodes.add(ropeNode);

// if((parentNode.weakestRopeNode.strength - (parentNode.weakestRopeNode.total + ropeNode.value) >= 0)){
// if((ropeNode.strength-ropeNode.total) < (parentNode.weakestRopeNode.strength - (parentNode.weakestRopeNode.total + ropeNode.value))){
// ropeNode.weakestRopeNode = ropeNode;
// parentNode.weakestRopeNode.total += ropeNode.value;
// }else{
// ropeNode.weakestRopeNode = parentNode.weakestRopeNode;
// ropeNode.weakestRopeNode.total += ropeNode.value;
// }
// }else{
// return ropeNodesMap.size() - 1;
// }

parentNode = ropeNode;
while((parentNode = parentNode.parentNode) != null){
parentNode.total += ropeNode.value;
if(parentNode.total > parentNode.strength){
return ropeNodesMap.size() - 1;
}
}
}else{
ropeNode.weakestRopeNode = ropeNode;
}
}
return ropeNodesMap.size();
}

}