15 game in Flash Actionscript3

Having implemented the 15-game in Java, I thought I would attempt the same with Flash + AS3. And the same was done swiftly and I have presented the output and the code here. This is the same as the applet version, you will have to use your arrow keys to play.




The Layout grid file which I wrote on my own to simulate an exact Grid Layout similar to the one in Java.

Cheers!!
Braga

Print % using printf in C

Problem:

How can you print % using the printf function? (Remember % is used as a format specifier!!!)
Very Simple, following cases are examples


Cheers!!
Jack

Find Output for this C Program

Problem:

What would be the output of the following C program? (Is it a valid C program?)


Explanation:

This will produce output “4321”. The return type of printf is “int” which is the number of characters written to stdout.


Cheers!!
Jack

C - %n format specifier in printf

Well, what does the format specifier %n of printf function do?

Explanation:
Print nothing, but write number of characters successfully written so far into an integer pointer parameter.

Example:

Output:
blah blah
val = 38

Cheers!
Jack

C program to determine endian'ess

We shall see a small C program to determine whether a machine's type is little-endian or big-endian.

Definition:

BigEndian means that the higher order byte of the number is stored in memory at the lowest address, and the lower order byte at the highest address. The big end comes first.

eg: OAOBOCOD will be stored as OA(a) OB(a+1) OC(a+2) OD(a+3)

LittleEndian means that the lower order byte of the number is stored in memory at the lowest address, and the higher order byte is stored at the highest address i.e., the little
end comes first.

eg: OAOBOCOD will be stored as OD(a) OC(a+1) OB(a+2) OA(a+3)

Program:


Cheers!!
Jack

Addition without using the + operator in C

Write a C function which does the addition of two integers without using the '+' operator. You can use only the bitwise operators.(Remember the good old method of implementing the full-adder circuit using the OR and XOR gates....)

Now, for the code implemented in C.

Cheers!
Jack

CAT Brain Teaser

Well, this can be considered off-topic. A brain teaser in CAT. Only 2% students were able to solve this in the CAT Exam. They should have been really sick :) Enough build up, lets see what the problem is.

Given,

5+3+2 = 151022
9+2+4 = 183652
8+6+3 = 482466
5+4+5 = 202541

Then, 7+2+5 = ???


Solution:

5+3+2 = (5*3)(5*2)(5*3 + 5*2 - 3)
9+2+4 = (9*2)(9*4)(9*2 + 9*4 - 2)
8+6+3 = (8*6)(8*3)(8*6 + 8*3 - 6)
5+4+5 = (5*4)(5*5)(5*4 + 5*5 - 4)

Hence,

7+2+5 = (7*2)(7*5)(7*2 + 7*5 - 2) = 143547

Cheers!!
Jack

"Offsetof" Macros in C : What it is and why it is

Problem:

The following is the offset macros which is used many a times. Lets figure out what is it trying to do and what is the advantage of using it.


Explanation:

offsetof tells you where in the memory allocation of the structure you will find a particular member.

Consider the example,


The structure defined takes up 12 bytes:

* byte 0: singlechar
* byte 1: arraymember[0]
* byte 2: arraymember[1]
* byte 3: arraymember[2]
* ...
* byte 10: arraymember[9]
* byte 11: anotherchar

The output will be:

offsetof(mystruct,singlechar) is 0
offsetof(mystruct,arraymember) is 1
offsetof(mystruct,anotherchar) is 11

If you allocate an object of type, and get a byte* to the start of the structure, you can use offsetof to find out where each member is. If you use that pointer offset, and convert it back to the correct type, it will give you a pointer to the member.


The output will be:

anotherchar is 17

The reason you can't assume that each member will be a specific offset from the beginning of the struct is complicated, and compiler dependent. If you must do something like this (which is really low-level stuff which you should avoid unless you have to), then use a macro like offsetof, rather than trying to manually specify the offset yourself.

Hope you learnt something.

Cheers!!
Jack

How to find angle between hour and minute hands in an analog clock?

Given a simple clock, we have to find the angle between the hour and minute hands. Since this is a deliberate question, we should obviously be ignoring the thickness of the hands in the clock.

We need to understand the following things before we arrive at our solution.

• The hour hand moves at the rate of 0.5 degrees per minute.
• The minute hand moves at the rate of 6 degrees per minute.

The reason for the above statements are obvious if you think a layer deep. Now, for the code (works both for C++ and Java)


Cheers!!
Jack.

What is the difference between memcpy and memmove?

Answer:

With memcpy, the destination cannot overlap the source at all. With memmove copying takes place as if an intermediate buffer was used, allowing the destination and source to overlap. This means that memmove might be very slightly slower than memcpy, as it cannot make the same assumptions.

Cheers!!
Jack

Linked List : Given a pointer to any node, delete the node pointed by the pointer

Given a linked list like this,

Given a pointer to any node, delete the node pointed by the pointer. Note: no head pointer is given.

Solution:

Assume a pointer to p3, lets call it to 'p'. Since only pointer to current node is provided, there is no way to delete the current node from the list. But instead of deleting the current node, we can just move the next node data to current node and delete the next node. The algorithm can be explained simply as,

Cheers!!
Jack

C program to find fibonacci series using only one variable !!!

Problem:
Generating Fibonacci series using only one variable.

There are many ways to achieve this. I have given three ways to do this in the following methods.

Method #1:
We can have a simple function to do this.

Method #2:
The following recursive function would do the job.

Method #3:
The following one works great as well!

Cheers!!
Jack

Interview Puzzle - Equal heads

Puzzle:

There are 50 coins on the table out of which 43 are tail-face up and 7 are head face up. You are blind folded and there is no way to determine which side is up by rubbing, etc. You have to divide the 50 coins in two sets (not necessarily equal) such that both have equal number of coins with heads face up.

Solution:

Divide the 50 coins into two sets - once set with 43 coins and the other set with 7 coins. Thus, the first set will contain 'x' heads and '43-x' tails and the second set will contain '7-x' heads and 'x' tails. The possibilities can be tabulated as shown in the left table.

Now, flip the coins in the second set, so that both will contain 'x' heads. The result after flipping can be seen on the right table. You can see that both sets have equal number of heads whatever be the distribution.

Cheers!!
Jack

Print a Matrix in diagonal zig zag order

Problem:
Given a square matrix, write a program to print the items in zig zag diagonal order.

Following is an example,

So the output expected for the above example is,

1 -> 2 -> 6 -> 3 -> 7 -> 11 -> 4 -> 8 -> 12 -> 16 -> 5 -> 9 -> 13 -> 17 -> 21 -> 10 -> 14 -> 18 -> 22 -> 15 -> 19 -> 23 -> 20 -> 24 -> 25

Solution:

This program is a bit tricky and is very hard to solve immediately when asked in an interview. People who try to attack problems involving matrices always think they need at least two loops to arrive at the solution. But the surprise here is the problem can be solved in just a single loop with a very simple logic. I have provided the solution in C++ below, you may also try to solve the same in the language of your choice!!


Cheers!!
Jack

A Free game in Java

I wanted to play this game so badly as I use to be very good at it. I was not knowing the proper keyword to find it online. So, what the heck, I went ahead and created one! The front end used was Swing.
The objective of this game is to arrange from numbers 1 through 24 (or depending on the size) in proper order and you have one square free. You can move to that empty sqaure by pressing either of the four arrow keys UP/DOWN/LEFT/RIGHT. All the puzzles formed will have a solution. You can use this code anywhere you want.

If you have Java installed in your browser, you should be able to see the Applet. Just click anywhere inside the applet and start playing using the arrow keys! Have fun!

Screenshot	Applet

Cheers,
Bragaadeesh.

Trie data structure - In C++

• 1
• 2
• 3
• 4
• 5
• 6
• 7

Having had a comprehensive coverage of the TRIE data structure in Java, me and my roommate thought it would achieve completion if we have the same implemented in C++. Don't get carried away by the length of the code. Its as simple and easy as the equivalent one in Java. You may go through the comprehensive tutorial here. Trust me, it takes only 10 minutes!!.

Please feel free to ask any questions if you face difficulties in understanding any part of the resource. I would respond to you immediately.


Demonstration of trie operations

Cheers!!
Jack.

Efficient way to calculate prime numbers

In several puzzles/coding competitions we may need to check for prime numbers and this is required to be done in considerable time to save precious run time. The traditional approach is,



This will however will loop through all elements below x to see if a factor exists. Example, for finding if 13 is prime, we check if its divisible by 2,3,4,....12. This can be optimized to loop through only half the elements since the highest factor is going to be num/2 as,


But by analysis you can see that for a number say 100, the factors are (1*100),(2*50),(4*25),(5*20),(10*10),(20*5),(25*4),(50*2),(100*1). For finding out if 100 is prime or not we just need to check if 100 is divisible by any number not greater than 10 i.e., it is sufficient to check from 2 to 10. The reason being if its divisible by 4, its also divisible by 25.

Hence the best approach to check if a number is prime or not will be



Final prime number program in Ruby (bonus)


This approach will check for factors in very minimized number of loops.

Cheers!!
Bragaadeesh

Stack Implementation in C++ through an array

Stack is one of the important data structures that every computer programmer should be aware of. It follows the simple LIFO (Last In First Out) principle. Implementation of stack can be done in many ways. One of the simplest way is using Arrays. Here an array is initialized to a maximum value first, lets call it capacity. As and when we push elements onto the array, its size will get increased. When the size reaches the capacity, we should ideally double the array size. But in the code given below I am not doing that.

Cheers!!
Bragaadeesh.

Motivation

In his book, 7 Habits of Highly Effective People, Stephen Covey tells the story of a woodcutter who took a new job for a timber merchant. The woodcutter was determined to do his best, so when the employer presented him with an axe he went straight to work. The first day the woodcutter brought 18 trees to the boss. “Congratulations,” the boss said. “Keep it up!” With this motivational encouragement the cutter went out the next day with even more determination. However, at the end of the day he could only bring back 15 trees. The third day he worked harder still, yet try as he might only 10 trees could be felled. So it went; each succeeding day yielded fewer trees. “I must be losing my strength,” the woodcutter thought. He decided to approach his boss to apologize for his unexplained deteriorating output. “When was the last time you sharpened your axe?” the boss asked. The woodcutter stared dumbfounded. “Sharpen my axe! I had no time to sharpen my axe. I have been too busy trying to cut trees!”

It is possible to be too busy to maintain your effectiveness. Whatever your personal situation, this might be the right time to ask yourself if it is time to “sharpen your axe.”

Cheers!!
Bragaadeesh.

Project Euler : Considering natural numbers of the form, ab, finding the maximum digital sum.

Problem 56

A googol (10¹⁰⁰) is a massive number: one followed by one-hundred zeros; 100¹⁰⁰ is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.
Considering natural numbers of the form, a^b, where a, b < 100, what is the maximum digital sum?

Solution (in Ruby)

Nothing much to discuss about the solution, I've implemented it directly as given in the problem statement.

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : Evaluate the sum of all amicable pairs under 10000.

Problem 21

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a b, then a and b are an amicable pair and each of a and b are called amicable numbers.
For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.
Evaluate the sum of all the amicable numbers under 10000.

Solution (in Ruby)

For this problem, it is vital to write an efficient method to find the sum of divisors of a number. The divisor finding logic is same as the one stated in Problem 12. Rest is an as-is implementation of the problem statement.

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : How many letters would be needed to write all the numbers in words from 1 to 1000?

Problem 17

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.
If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.

Solution (in Ruby)

We will have to first try to come out with the unique words that are present in the numbers. We start with the ones which are one, two upto nine. Then the elevens starting from eleven to nineteen. Then the tens, twenties upto nineties. We should also define a hundred and thousand. After that the logic is directly readable from the ruby code given below.


Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : Discover all the fractions with an unorthodox cancelling method.

Problem 33

The fraction ⁴⁹/₉₈ is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that ⁴⁹/₉₈ = ⁴/₈, which is correct, is obtained by cancelling the 9s.
We shall consider fractions like, ³⁰/₅₀ = ³/₅, to be trivial examples.
There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.
If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

Solution (in Ruby)

This problem unlike the other problems does not ask us to go to millions and trillions and the scope is such that this can be solved in the least running time. All this problem demands careful inspection of the problem statement itself. Its clear we need to iterate through numbers from 1 to 99. For the outer loop (numerator), its enough we run from 12 since its the first double digit number which does not end with a 0 or their digits being equal. We run upto 97 since the numerator cannot be greater than equal to denominator since the fraction should be less than 1
Same is the case for the inner loop. We should always continue to the next iteration if the last number of either numerator or denominator is 0, or if both digits or equal or if the numerator is greater than or equal to denominator. Rest of the solution is just a language specific implementation of finding whether the two different fractions are indeed equal.

Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : What is the value of the first triangle number to have over five hundred divisors?

Problem 12

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?

Solution (in Ruby)

The main aspect about this solution is finding an efficient way to calculate the number of divisors. Lets take a simple example. The number 6 has 4 divisors namely 1,2,3,6. For this number its enough we run upto the Square root of 6 which is integer floored value to be 2. 1 is divisible by 6 by 6 times, so 1 and 6 are divisors. 2 is divisble by 6 3 times, so 2 and 3 are divisors. So totally we have 4 divisors.
There is one more point to be noted here. For a square number such as 16, if we apply this formula, we will end up getting 6 divisors --> 1, 2, 4, 4, 8, 16. You may see we may calculate 4 twice. But it occurs only once for a square number. This special case is handled in the solution given below. The rest is an as-is implementation of the problem statement.

Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : How many Lychrel numbers are there below ten-thousand?

Problem 55

If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.
Not all numbers produce palindromes so quickly. For example,

349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337

That is, 349 took three iterations to arrive at a palindrome.
Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).
Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.
How many Lychrel numbers are there below ten-thousand?

NOTE: Wording was modified slightly on 24 April 2007 to emphasise the theoretical nature of Lychrel numbers.

Solution (in Ruby)

This problem had a higher difficulty rating in project euler problems. But it was one of the straightforward ones that I solved it with Ruby. Nothing to say about the solution, its an as-is implementation of the problem statement.


Hover here to see the solution

Cheers!!
Bragaadeesh.

Project Euler : Concealed Square

Problem 206

Find the unique positive integer whose square has the form 1_2_3_4_5_6_7_8_9_0,
where each “_” is a single digit.

Solution (in Ruby)

Before we look at the optimal solution, lets look at what brute force has to offer us. There are nine slots in the number which leaves us to iterate on 1000000000 times (1 trillion times). This is simply not doable, it will take years to run through this loop. So brute force is out of the equation. We need to find a digit or two to reduce the loop count.

So its wiser to look at some of the property of square numbers. Square number ending with zero, has to have the previous digit also 0, which leaves us with only 8 slots now. One more property is that the square root for this particular number has to start with 1. The reason is in finding the square root, we need pair numbers from the back and need to find the square root of the first hanging digit/pair. In this case its 1. Square root 1 is 1 and its enough to inspect only one digit. This leaves us 1 more slot less in our problem. And one final property is the ending digit. Here its 9. Only numbers that end with 3 and 7 produces 9. This leaves our permutation reduce by one more digit (since its enough for us to step 10 times every time in the loop). We need to find the lower bound of the number which is 10203040506070809. The square root of this number is 101010101. We shall end with either 3 or 7. And start with the maximum digit in that sequence which is 199999999. Thats it!! Now we've shortened the problem to be solved within seconds!!


Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : How many circular primes are there below one million?

Problem 35

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.
There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.
How many circular primes are there below one million?

Solution (in Ruby)

The solution to this problem invovles one performance enhancement in finding the prime numbers. If you want to check whether the same number is prime more than once in your program, it is highly important to have a look on the running time. That is why I am using an array to store the number as the index itself. This would make sure that the number given is found to be prime or not in O(1) time. Rest of the solution did what the problem statement demands


Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : Find the sum of all numbers less than one million, which are palindromic in base 10 and base 2.

Problem 36

The decimal number, 585 = 1001001001₂ (binary), is palindromic in both bases.
Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

Solution (in Ruby)

The solution is one the simplest and straightforward when implemented in Ruby.

sum = 0
1.upto(1000000) do |num|
  sum+=num if num.to_s == num.to_s.reverse && num.to_s(base=2) == num.to_s(base=2).reverse
end
puts "Sum is #{sum}"

Hover here to see the solution

Cheers!!
Bragaadeesh

Project Euler : How many triangle words does the list of common English words contain?

Problem 42

The n^th term of the sequence of triangle numbers is given by, t_n = ½n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t₁₀. If the word value is a triangle number then we shall call the word a triangle word.
Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

Solution (in Ruby)

The main place where we need to attack this problem involves in finding the roots of the quadratic equation. We know the roots of the quadratic equation

If you apply this equation to the simple formula to find the triangle numbers, we will find out that a = 1 and b = 1 and c will be twice the triangle number. There will be two roots possible, one will be positive and other will be negative. It is enough to find the positive root. If that root is a whole number, then that will be a proper triangle number.

names = File.new("/words.txt","r").gets.split(/,/)
count = 0
names.each do |n|
  value = n.gsub!(/^"(.*?)"$/,'\1').split(//).inject(0){|b,i| b+i[0]-64}
  positive_root = (-1+Math.sqrt(1+8*value))/2
  count+=1 if positive_root == positive_root.ceil
end
puts "The total number of words is #{count}"

Hover here to see the solution

Cheers!!
Bragaadeesh