Hope the image is clear and readable.
Friday, 19 June 2015
Friday, 12 June 2015
Here is an interesting puzzle (graph colouring problem!):
In figure below, it shows 5 circular nodes connected by lines. Assuming you have three colours to colour these nodes(One node can use one colour, same colour can be used by any other node subject to below condition)
In how many different ways is it possible to color all five nodes with a condition that two nodes which are connected by a line segment cannot be of the same color?
I shall post my answer sometime soon.
In figure below, it shows 5 circular nodes connected by lines. Assuming you have three colours to colour these nodes(One node can use one colour, same colour can be used by any other node subject to below condition)
In how many different ways is it possible to color all five nodes with a condition that two nodes which are connected by a line segment cannot be of the same color?
I shall post my answer sometime soon.
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.
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:-) )
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.
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).
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)
-------------------------------------------------------------------------------------------------------------------
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.
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.
Mathematical Equations That Changed the World pic.twitter.com/0He57IQyzk
— news.yc Popular (@newsycombinator) March 9, 2014Thursday, 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.
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.
gives output as
[('1', '2', '3', '4', '5'), ('1', '2', '3', '5', '4'),...
List of tuples of characters.
Then tried
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:
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.
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.
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:
Command:
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.
Command:
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
Command:
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!
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:
Command:
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.
Command:
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
Command:
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!
Subscribe to:
Posts (Atom)