Life -- Code -- Experience

Project Euler #315

2011-10-25T21:42:00.002+05:30

Problem: Digital Root Clocks

Solution: [Spoiler Ahead]

One of the easy problems and one of the easy solutions.
It's just straight forward,

the number of LED on-off by SAM's clock - the number of LED on-off by MAX's clock

Globals I used, a noOfLEDsForDigit[] array holding the number of led's required to glow a particular digit.
A digits[] array holding hex values for the number that represent the ON-OFF LED. e.g.

bit LED
------------
0 top
1 middle
2 bottom
3 top-left
4 top-right
5 bottom-left
6 bottom-right

Digit Binary representation Hex_value
-------------------------------------------------------
0 0111 1101 0x7d
1 0101 0000   0x50
2 0011 0111   0x37
3 0101 0111   0x57e
4 0101 1010   0x5a
5 0100 1111   0x4f
6 0110 1111   0x6f
7 0101 1001   0x59
8 0111 1111   0x7f
9 0101 1111   0x5f

Now the calculations become very easy,

For SAM: it's just the twice the sum of number of LED's in the digit(or no. of 1's in it's binary representation according to above user-defined digits)

For MAX: we need to get the common LED that will not be turn off when number changes from 'a' to 'b', this is given by XORing both value i.e.(a^b), plus the LED's that need to be turned on to complete the number 'b'.

There it is , therein lies the rub !

8 on 8

2011-05-28T00:46:00.017+05:30

So finally, everything is completed and and perfect 8 on 8. I am now a Bachelor of Technology, what I would be liked to be called. After entering the CoEP and seeing all the brilliant students around I had thought that probably getting out of CoEP is more difficult than getting in.

First Year: began with all the intros given to seniors(which I owe a lot as it made me think that I didn't had anything special in me, I need to make myself into some or the other thing). The lectures went repeating some physics and chemistry part.Technically was introduced to the C-Programming which I even didn't know that this is going to be with my entire life henceforth. Even by the end of the first year, I didn't get to know the concept of a programming language, but I sored quite well in it(thanks to my friends, and this is the part where your friends help you a lot :P). As usual not to mention, when it comes to engineering Mathematics never leaves your collar bone. Bunked some lectures for the Regatta.

Second Year: gave exposure to the computer graphics and latest technologies.Also one whole semester was wasted (ohhhhh no I'm sorry *vested*) in understanding stack and queues alone.Trees and graphs still remaining a nightmare to me and many others. Database Systems didn't move a page ahead even after 2 months of continuous efforts of the professor. Tried to make a manual robot for the dogfight and a micro-mouse in the College's Annual Tech-fest MindSpark with very few achievements which would be better to called nil.

Third Year: was busy amongst all the four years. This was the time when I understood what IT is? and what I'll be doing for the rest of my life. Tried to learn new things and got hands on few platforms but was still a naive in all those areas. Graduate Aptitude Test in Engineering didn't go quiet well giving me a rank of above 7000.

Final Year: the main ground and the most important time of my life. This year taught me a lot of good things as well as bad things. I got to learn many things from my experience which eventually improved my point of view towards life and the ways to deal with the problems. As a human I was a changed being by the end of the year.

Aarz hai

2011-05-02T02:36:00.078+05:30

Taaro ko ginne wale hum na the,
akele gungunane wale hum na the,
Ye to dosti aadat laga di,
varna kisi ko itna yaad karne wale hum na the.

Iss kadar na har baat yaaron se pucho,
Jo baat raaz ki ho isharo se pucho,
Lahero se khelna to samandar ka shauk hai,
lagti hai chot kaise kinaron se pucho.

Bheg jati hai palkein tanhayi me,
darte hai koi janna le,
Pasand karte hai tez barsaat mein chlana,
kahi rote hue ko koi pehchaan na le.

Kal fursat na mili toh kya koroge,
itni si mohlat na mili toh kya karoge,
Roj kehte ho kal baat karenge,
kal hamari aakhen na kholi toh kya karoge.

Wo shasks meri jaan bana rehta hai,
uska pyar meri pehchaan bana rehta hai,
Koi yad karta hai usko kitni shidat se,
wo janta he magar anjan bana rehta hai.

Guzra waqt dil ki baat sunaega,
kabhi saath the hum hal pal yaad aayega,
Gaur se palatna zindagi ke panno ko,
kahin na nahin to hamara naam jarur nazar aayega.

Still trying to code ....

2011-05-02T01:43:00.000+05:30

Introduced to programming language C and C++ in first year of my 4 year Engineering Course. Till the end of the year, I hardly understood the power of programming. But eventually the time spent dwindling with online tutorials in the summer break was a real break for me !!!

Spending next 6 months on data-structure, I got to know how to use the correct tool for the given problem, but many a times my decisions didn't gave any result. Codechef, Topcoders, Codeforces as proved a motivational platform to develop my skills.

But still after a period of 3 years, I am not able to get around some difficult problems :( . One needs to really work hard to develop the proper skill, which I think I still haven't.

If I had to put my current scenario in the current sense then the quote correctly depict that. At some point of your life , you reach a stage when you need help, but wouldn't find one. The answer to this is just 'Patience'. As it is rightly said "All human wisdom is summed up into two words wait and hope".

Experience Bolta hai...

2011-03-16T02:32:00.001+05:30

Last semester of engineering really taught me much more than I could perceive.My technical knowledge got boosted but on the other hand I got to know that we have to live a professional life in this professional world.

Bitter truth is something that one has to face at some point of time in your life.Once you start working on something, don't be afraid of failure and don't abandon it. People who work sincerely are the happiest.

Also keep proof of everything you do as this would help you in future to rectify many problems. And try to grasp as many things as possible from the given scenario which would eventually lead to good results.Always be clear of what you need at the end.The person we fear, which we think can do what-ever he wants and which treats you as useless, is a person not to be feared and not to be entertained.It is he who is in the loss and cannot be helped by anyone.

So just lead the life as it comes. Do your best in which ever field you work and what you are capable of, this will make you happy and also the people around you :)

Project Euler 5

2011-02-24T03:20:00.009+05:30

Problem: What is the smallest number divisible by each of the numbers 1 to 20?

Solution: [Spoiler Ahead]

I just checked for numbers that are divisible by all numbers between 11 and 20(inclusive), this algo is not much efficient but works well.

Toggle Code

#include <stdio.h>;

main() 
{ 
    int i; 
    int smallest=0,found=0; 

    for(smallest=20;found < 1;smallest++){ 
        for(i=20;i > 10 ;i--){ 
            if(smallest%i != 0){ 
                found = 0; 
                break; 
            } 
        } 
        if(i == 10){ 
            found = 1; 
            break; 
        } 
    } 
    printf("%d\n",smallest); 
}

Enjoy coding :-)

Project Euler 4

2011-02-24T02:48:00.002+05:30

Problem: Find the largest palindrome made from the product of two 3-digit numbers.

Solution: [Spoiler Ahead]

The initial algorithm to the problem is : Check all products of two 3-digit number and store the required number.

Toggle Code

function reverse(n)
reversed = 0
while n > 0
reversed = 10*reversed + n mod 10
n = n/10
return reversed

function isPalindrome(n)
return n = reverse(n)

largestPalindrome = 0
a = 100
while a <= 999
b = 100
while b <= 999
if isPalindrome(a*b) and a*b > largestPalindrome
largestPalindrome = a*b
b = b+1
a = a+1

output largestPalindrome

This works quiet well but if you observe we are computing the same product twice. So beginning the value of 'b' from the value of 'a' will suffice for this. Also running the loop in reverse order will speed up the algo as lower number need not be checked for the palindrome case as shown in below implementation:

largestPalindrome = 0
a = 999
while a >= 100
b = 999
while b >= a
if a*b <= largestPalindrome
break
if isPalindrome(a*b)
largestPalindrome = a*b
b = b-1
a = a-1

output largestPalindrome

Thus giving us answer in few seconds !!!
Enjoy coding :-)

Project Euler #3

2011-02-23T20:53:00.002+05:30

Problem #3:Find the largest prime factor of a composite number.

Solution:
As usual firstly the straight forward implementation. Run a loop and go on checking whether it divides the given number and check if it is prime, storing the largest one.

#include

#include"prime.h" //My own module,code not shown here

int main(){

long long num=600851475143L;

long largest_prime_factor=0,i;

for(i=10;i<num/2;i++)

if(num%i==0)

if(isPrime(i)) //return true if prime

largest_prime_factor=i;

printf("Answer to Euler #3 : %ld",largest_prime_factor);

return 0;

}

This can be optimized a little by defining a new upper bound for the loop counter and that would be square root of the given number.

More over 2 is a factor which if checked separately will make our life easy. Then we can increase the factor by step of 2.

A little more optimized algorithm is:

n="a large number"
if n mod 2=0
then
    n=n / 2
    lastFactor=2
    while n % 2=0
        n=n / 2
else
    lastFactor=1
    factor=3
    while n>1
         if n % factor=0
         then
                n=n / factor
         lastFactor=factor
         while n % factor=0
                n=n / factor
         factor+=2
output lastFactor

This is not the fully optimized solution but can be modified further. That left to you ;-)

Enjoy coding :-)

Project Euler 2

2011-02-23T20:14:00.005+05:30

Problem #2:Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.

Solution: A straight forward implementation in C for this problem can be as shown

#include
#define LIMIT 4000000
int main()
{
 long a=1, b=2, c=0, sum=0;
 sum = b;
 while(c < LIMIT ){
  c = a+b;
  if(c < 1000000)
  if(c%2 == 0)
   sum += c;
  a = b;
  b = c;
 }
 printf("\nAnswer to euler #2 : %ld\n",sum);
}

   This code works fine for our required need, but more optimizations can be done.How? Lets look at the fibo seq.

   1 1 2 3 5 8 13 21 34 55 89 144 ...

   As we can see,every 3rd term is a even number. Therefore we can change the code accordingly to just sum up every third number.
   Another approach is we can find a recurrence funtion for this new series i.e. we can have :

F`(n)=4*F`(n-1) + F`(n-2)

It is easy to prove that for Fibonacci series we get:

F(n)=4*F(n-3)+F(n-6)

Thus we get a more faster running code, which we eventually need :-)

Enjoy coding :-)

My all time favourite Movies

2011-02-23T02:46:00.005+05:30

Mughal-e-azam

A Wednesday

Ghajini

Munnabhai M.B.B.S

Swades - we the people

Dil Chahta Hai

Rang De Basanti

Project Euler 1

2011-02-23T02:14:00.009+05:30

Problem #1. Add all the natural numbers below one thousand that are multiples of 3 or 5.

Solution : This can be done in two ways ....

i. The normal method, i.e. run a for from 1 to 1000 and check for the given condition on each number.

This method does solves our problem but is crude.

upperlimit=999
total_sum=0
for i=1 to upperlimit do
if (i mod 3=0) or (i mod 5)=0 then
total_sum:=total_sum+i;
output total_sum

ii. The short-cut method : In this you need only one formula and just need to compute value of 3 expressions.

Just go through---->

The solution to given problem will be the answer of this expression :

ans = sumDivisibleBy(3) + sumDivisibleBy(5) - sumDivisibleBy(15)

Now for n=3 :

3,6,9,12,15,18,21,24,27,.....,999 = 3(1,2,3,4,5,6,7,8,9,....,333)

Now we know that :

1 + 2 + 3 + .... + q = 1/2*q*(q+1)

In our case : q = upperlimit / n

Therefore our solution says :

Function sumDivisibleBy(n):
q = upperlimit div n
return n*(q*(q+1)) div 2
EndFunction

print sumDivisibleBy(3)+sumDivisibleBy(5)-sumDivisibleBy(15)

Feel free to ask any kind of querry, I'll try my best to solve it.

Enjoy coding :-)

The Month of Purity and Patience

2010-08-30T06:10:00.000+05:30

Ramzaan is the month of purity and patience that brings the human soul towards the Creator and makes him think about each and every small and wonderful things He has created. Fasting reschedules all your daily routines that we disturbed otherwise.

---------------------------------------------------------
Take account of yourself before you are called for account.

2010-07-25T17:11:00.001+05:30

A good comparision between Bubble Sort and Quick Sort.

Please Wait while the video loads.......

Impressed by Free Software........

2009-09-10T11:22:00.000+05:30

The starting of the CoFSUG ( Coep's Free Software Users Group) club increased my curiosity towards the world of free software. FREEDOM IS OUR BIRTH RIGHT AND WE SHALL HAVE IT was been rightly said by one great freedom fighter which applies in almost every field.
My thinking got changed a lot and now I believe that the code contributed by a group of people is far more robust and secured than developed by an individual.If anyone wants to write any new implementable software from scratch then even if he has done with it, the code would not be that smarter as it would have been if it was a open source code.

The day everything went wrong .....

2009-08-29T08:21:00.000+05:30

Two days before was a good lesson teaching day for me. All began with those news in the TOI which were showing the cruel face of humans which was too disappointing.
Then I went to the library where to my surprise I found I had lost my collage ID card, then ATM card, Driving license and at last whole wallet.
In the Afternoon my laptop got formatted as I was trying some new command in ubuntu.
In the evening near about 7 p.m. I remembered I had forgotten my pendrive in the collage lab.
I think this all happened due to some reason and as if God was punishing me for some of my sins .

My first POST

2009-07-21T16:43:00.000+05:30

A warm 'hi' to everyone. This is my very first Blog. I didn't knew that anything like Blog existed , but thanks to my friends who are the source of this discovery to me.
Currently, I am a T.Y.B.Tech student in COEP . Recently impressed with one of the faculty's ideas I generated interest in Linux and Free Software like things and to my notice I found that Free Software is a huge and great world. It actually develops a programmers skills and spreads it among others.
Initially , I faced many problems with its installation and other stuff but gradually due to curiosity the solution came all the way.