Here is the solution for the puzzle cards in envelopes in a previous post some time back here.

Its a snapshot of hand written solution on a piece of paper. Hope the image is sharp enough to be readable.

Cards inside envelopes

Here is a combinatorics related puzzle.
We have 6 envelopes numbered from 1 to 6.  Likewise we have 6 cards numbered 1 to 6.
You have to put each card in one envelope(it would have only 1 card), such that the card number is never the same as the number of the envelope its placed in.

Question 1: How many different ways can it be done in?

Question: If card # 1 is to be always placed in envelope #2, other constraints remaining same, how many ways are possible now?

Will post my solution in some days.

Solution to the puzzle of Same number of coin tosses

Here is my solution to the probability puzzle asked last week about finding the probability of 2 people tossing a fair coin 6 times independently, and coming up with same number of heads or (tails)
I had written it on a paper, so decided to put a image snapshot of that solution. Hope its readable.
(Whats the probability of that:-) )

Same coin tosses

Here is a nice puzzle about Probability theory.

If two people toss 6 fair coins independently at same time, what is the probability that they have same number of tails come up.

I will post the solution in a while.

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))

test
time
result

Example tests

example1 
first example from the problem statement
0.064 s
OK
example2 
second example from the problem statement
0.060 s
OK

Correctness tests

extreme_empty_one 
no ropes and only one rope
0.064 s
OK
tiny 
only two ropes
0.060 s
OK
small 
only three ropes
0.068 s
OK
small_random 
small random trees, 10 <= N <= 30
0.064 s
OK

Performance tests

star 
tree forms a star, N ~= 5,000
0.084 s
OK
medium_random 
medium random trees, N ~= 10,000
0.104 s
OK
large_random 
large random trees, N ~= 100,000
0.660 s
OK
line 
large random trees, N ~= 100,000
>11.000 s
TIMEOUT ERROR 
running time: >11.00 sec., time limit: 5.33 sec.

17 world changing equations.

Here is a interesting tweet I read from YCombinator Popular about mathematical equations that caused a great impact and advancement of world.

Mathematical Equations That Changed the World pic.twitter.com/0He57IQyzk

— news.yc Popular (@newsycombinator) March 9, 2014

All permutations of numbers in Python

Just recently, I was looking to fill an excel sheet with all possible permutations of five numbers : 1,2,3,4,5 . One permutation in each cell. The excel sheet was a test case document and each permutation meant to go in each cell was a test case.
I was looking to write permutations in below format.
e.g.
1-->2-->3-->5-->4
Which meant From condition one, code should enter condition 2, then condition 3, then condition 5, then condition 4 which described 1 test case scenario.

Writing all the 120 permutations (5!) by hand was painful. Was looking for getting the permutations printed on screen programmatically.
Turned to python. Python has module itertools which provides lot of functions for various iterators to loop the input data.
But the problem was I was looking output from the permutations logic as below:
1->2->3->4->5 ( 1st permutation of 1,2,3,4,5)
1->2->3->5->4 ( 2nd permutation)
...etc

But this below python code did not gave output as I desired.

import itertools  
 print([x for x in itertools.permutations('12345')])

gives output as
[('1', '2', '3', '4', '5'), ('1', '2', '3', '5', '4'),...

List of tuples of characters.

Then tried

import itertools  
 a=[1,2,3,4,5]  
 print([x for x in itertools.permutations(a)])  

This gave closer output to what I needed but still not exactly what I was looking for

[(1, 2, 3, 4, 5), (1, 2, 3, 5, 4),

List of tuples of numbers

But as I say, if it can be done in life, it can be done using Python:

I coded as below to output of the permutations, exactly as as I wanted:

import itertools  
 a=[1,2,3,4,5]  
 permuted_a = [x for x in itertools.permutations(a)]  
 len_perm = len(permuted_a)  
 for i in range(len_perm):  
   print permuted_a[i][0],'-->',permuted_a[i][1],'-->',permuted_a[i][2],'-->',permuted_a[i][3],'-->',permuted_a[i][4] 

This generated output as below:
1 --> 2 --> 3 --> 4 --> 5
1 --> 2 --> 3 --> 5 --> 4
1 --> 2 --> 4 --> 3 --> 5
1 --> 2 --> 4 --> 5 --> 3
1 --> 2 --> 5 --> 3 --> 4

Just copied the console output from above and pasted to my excel sheet.
One permutation, in one cell of the excel sheet.
Voila! Just works.