Follow this blog by Email

Saturday, 13 December 2014

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.

Monday, 24 November 2014

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.

Saturday, 15 November 2014

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

Saturday, 8 November 2014

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.

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).
• 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  
   lut = [0]*lenC  
   for v in C:  
     if v == -1:  
       cumwt[i] = B[i]  
       if cumwt[i] > A[i]:  
         return i  
         i = i + 1                
       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]  
 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. 
Detected time complexity: O(N*log(N))
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.

Sunday, 9 March 2014

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.

Thursday, 9 January 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.
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)

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

Friday, 22 November 2013

Commands for various tools to do Static Code analysis of C C++ source

Static code analysis is a very important step that every software developer, organisation should carry out to check if the code has any subtle possible issues which could cause bugs in the code.
A static code analysis of code using various tools can detect many errors or warning in the code like uninitialized variables, dangerous variable type conversions signed to unsigned, language specification violations etc.

Here I am going to explain in detail, usage of multiple static analysis tools
which I use for detecting such possible issues in my C,C++ code. After I get the output errors and warnings from these static analysis tools, a thorough code review of the code is done and then I try to remove as much errors and warnings as possible considering there could be some 'false positive' issues reported by some of these tools at some places of code. But either ways it is good to have all diagnostics of the code done and available to you, to be able to take an informed decision about possible changes to the code.

My code development setup is such that the C C++ code I have needs to be able to compile on Windows-x86, Linux-x86, and Linux-ARMV7 platforms.
The code is written in a protable way with all architecture specific, os specific calls inside conditional statements such that it does not cause build issues on either of the platform mentioned above.

Below is the exact command-line options, settings used in each code analysis/compiler tool to get maximum information in form of errors and warnings about possible issues in code.
1] gcc 
I always compile my code using below gcc options in the make file:-
 -Wall -Wextra -Wuninitialized -pedantic
These options almost always detect many issues like variables used
before initializing them, all warnings , even some pedantic warnings about
non-adherence to code language standard.
Few sample warnings these options generated on my code:
   ../../../../../code/my1.cpp:218:54: warning: ‘pChannel’ may be used uninitialized in this function
   ./../../../../../IP/Lib/src/portablity.h:90:12: warning: unused parameter ‘numberOfElem’ [-Wunused-parameter]
2] clang
Clang is an opensource compiler frontend used with llvm
It has a very good code analysis tool to analyze source code.
To analyze a single source file the command is as below:
clang++ --analyze -I/home/ad/IP/Lib/src/  -Weverything -pedantic -fshow-column 
-fcaret-diagnostics -fcolor-diagnostics -ferror-limit=9999999 -fdiagnostics-show-category -std=c++98 file1.cpp

Sample warnings and errors clang static analyzer generated:
 /home/ad/IP/Lib/src/Pkt.h:60:6:error: ISO C++ forbids forward references to 'enum' types
 /home/ad/IP/Lib/src/Pkt.h:67:4:error: field has incomplete type 'Pkt_t

3] PRQA-C++
 This tool from PRQA research is a good tool which enforces MISRA C/C++ rules in its static code analysis process.
There is a evaluation version of this tool available for download and try.
You can add all source files into the project in this tool and run code analysis on them
It generates a compliance report on analyzing the source files and detect and report issues like Conversion to unsigned,
  Overflow and wraparound issues, Portability Problems and many others.

4] PCLint
 PCLint is a static analysis tool which has been around for a long time now.

 lint-nt-8p.exe -w4 -wlib(0) -e309 -e1904 +fce +fcp +cpp(cpp,cxx,cc) -i"C:\mycode\include" file1.cpp > file1cpp_lintoutput.txt

This will generate the lint code analysis report in the file file1cpp_lintoutput.txt

Sample output of the lint static code analysis:

 #define NUM_OF_ERROR_CODES 88
 ErrorCodes.h  45  Note 1923: macro 'NUM_OF_ERROR_CODES' could become const variable

  Msgs.h  352  Note 958: Padding of 7 byte(s) is required to align member
    on 8 byte boundary

5] Eclipse Codan Analysis
 Eclipse is a free tool. Download and install Eclipse CDT.
Create a workspace in ecliplse. Create new empty C/C++ project in it. Then add your source and header files to that project.
Eclipse has a inbuilt code analysis toot called CODAN.
Right-click Eclipse project-->Run C/C++ Code analysis. This shows all errors/warnings generated from this analysis.

6] Cppcheck 
This is a static C/C++ code analysis tool available of linux. On Ubuntu we can install it as
sudo apt-get install cppcheck

cppcheck --enable=all -I ./ -I /home/ad/IP/Lib/include/ -I /home/ad/src/include/  file1.cpp
If you want you can redirect the output of this static analysis to a text file for later analysis:

cppcheck --enable=all -I ./ -I /home/ad/IP/Lib/include/ -I /home/ad/src/include/  file1.cpp >file1cpp.txt 2>&1

Sample outcome of static code analysis using cppcheck:

[/home/ad/IP/Lib/src/hash.h:160]: (error) Uninitialized variable: data8  
[/home/ad/IP/Lib/src/Log.h:375]: (error) Null pointer dereference
[file1.cpp:5837]: (style) Variable 'pString' is assigned a value that is never used

7] Mac OS XCode static analysis
    I create a XCode C++ project for my code, on MacOSx or iOS.
Then use the XCode inbuild static Code analysis tool which is also pretty nifty and gives information about your source code.

8] Visual C++ 2008 / Visual Studio X All Warnings enabled
  In your Visual C++ solution, you have a project created. Once you add all source files to that project.
  Right click Project-->Properties-->C/C++-->General-->Warning level:
  Here selecting highest level of warning Level 4 /W4 option enables all warnings and diagnostic messages.
  Once you compile the code using VC++, the warnings are displayed in the Build output window of VC++.

 Static analyze your source and catch all potential bugs early before they get a chance to execute and become a pain to debug, as ounce of prevention is better than pounds of cure!

Tuesday, 15 October 2013

C++ Class destructor throwing an exception ... No No

In C++ exception handling is feature provided by the C++ run-time environment to handle errors in execution of functions.
Exceptions are helpful if the code which handles error or failure happening in a function is different than the one which calls the function.
C++ allows exceptions using the try, throw and catch constructs provided by the language.
Technically any of the users class member functions can throw an exception if it faces any error or failure in some operation like- memory allocation, dynamic type casting.
It is a bad practice  to have a user defined destructor throw an exception. It could cause many issues in the program and system, few of which listed below -

1] C++ run-time aborts the execution of the program if there are two exceptions throw from same function as it does not know which one to catch -
  So if a destructor which throws is invoked when a local class object
 goes out of scope on end of a function which happens on the account of a exception thrown from the function, the catch block in the hierarchy cannot catch two exceptions and program terminates.

2] A destructor throwing an exception could cause memory leaks in the system due to freeing up of memory not happening -
 If a user has  his classes and objects ,then it could have the 'new' and 'delete' operators overloaded for his class.
 When a dynamically allocated user defined class object is deleted,  first the destructor of the class is invoked and then it invokes the delete operator function.
 But since this destructor throws an exception, the delete operator function is never executed and memory allocated in new operator function is never freed and it leaks memory.

Below cooked up example code demonstrates this behavior.

On compiling this below code using g++ and executing on a Linux it's output is as shown :

Inside constructor
Inside my()
operator new called
Inside constructor
inside try , before deleting pBomb
Inside destructor
caught exception from destructor
Inside my() Before throw no boom
terminate called after throwing an instance of 'char const*'

#include "iostream"  
 #include "string"   
 #include "stdlib.h"  
 class Bomb { // bad class throws exception from destructor  
   int x;  
   Bomb() : x(0) {std::cout << "Inside constructor\n" ;}  
   ~Bomb() { std::cout << "Inside destructor\n"; throw "boom"; }  
   void * operator new(size_t n) throw() //This function does not throw  
     std::cout << "operator new called\n" ;  
     return malloc(n);  
   void operator delete(void *p) throw() //This function does not throw  
     std::cout << "operator delete called\n" ; // never gets here  
     if (p != 0) free(p);  
 void my() { //This function throws std::string  
   Bomb myBomb; // local variable that will go out of scope when code exits this function  
   std::cout << "Inside my()\n";  
   Bomb *pBomb = new Bomb();  
   try {  
     std::cout << "inside try , before deleting pBomb\n" ;  
     delete pBomb;  
   } catch (...) {  
     // Gets here but leaks storage. Print output shows that  
     // operator new was called but operator delete was not.  
     std::cout << "caught exception from destructor\n";  
   // program dies here: can't throw two exceptions  
   // ("boom" and "no boom") at the same time.  
   std::cout << "Inside my() Before throw no boom\n";  
   throw "no boom"; // program dies here  
   std::cout << "Inside my() After throw no boom\n";  
 int main(int argc, char **argv)  
   try {  
   } catch (std::string message) {  
     std::cout << "function my() threw %s\n", message; // This is never printed as program terminates before reaching here  

Monday, 23 September 2013

Multipath TCP connections

Just recently , read about an interesting technology in network programming which is implemented for the first time in a commercial setting, in the just  launched Apple iOS-7. It  uses e Multipath TCP connections for the voice activated personal assistant Siri, to improve the Siri user experience which does bulk of its processing on the cloud, hoping that multipath tcp would inprove responsiveness and/or error robustness in case of congested channels.

Multipath TCP connections would allow a device to use various available internet connections like 3G, WiFi, or ethernet(if its connected via laptop/PC which has internet conenction via ethernet) over the most efficient(least congested) connection, in turn giving the user a robust/error free experience. It could also send data concurrently over these multiple connections to provide greater throughput to the application which needs to connect from the device( phone, PC, tablet,..) to the cloud or a application server, thus decreasing latencies and response times, and increasing the overall responsiveness.

This concept of Multipath tcp connections was proposed first in 2008,  in a initiative named Trilogy Project.
There is a document talking about technical guidelines for Multipah TCP development here.

I think and hope that this implementation of multipath TCP in a commercial product should pave way for more devices and protocol stacks having this implementation. I believe and wish this technology helps many bandwidth hungry applications which are also sensitive to network errors due to congestion and packet drops. Although UDP is the protocol of choice for Realtime Audio/Video communication applications like Skype, Google hangouts; Network audio streaming, IPTV, network gaming,  but if various related players in  the industry try implementing a proof of concept solution for this technology in their systems, they can see if their solutions and systems are benefited in some way by using multipath TCP specification. There will be issues about whether it becomes adopted widely, if it resolves interoperability issues and becomes mainstream choice for all networked data communication applications, but nonetheless as a technologist, it excites me for sure. We shall see how it fares in due course of time.