Toll fee Balancer

Came across an interesting Graph based problem. Try solving the problem, I will post my solution soon

In city to travel from a point A to B there are multiple routes, there can be direct route from A->B and there can few other routes with one or more intermediate nodes like A->C->B or A->C->D->B etc. Each road connecting two points have a cost, so any vehicle using that road should pay that cost to the authorities. This now implies that traveling from A to B will have different costs based on the route that you take.

Let me take an example




In the above figure Node '1' is the starting point and '4' is the ending point and there are 3 different routes to connect 1 and 4, each road has a original cost marked in BLUE. So the cost taking the direct road from 1-4 is 10, whereas taking the path 1-3-4 is just 8 (because 1-3 is 5 and 3-4 is 3), similarly the cost of taking the 3rd route 1-3-2-4 is 12.

Now the problem is to reassign the cost of individual roads so that the cost of all possible routes remains the same. You cannot reduce the cost of a road, but you can increase it. In the above example the cost of road 1->4 and 3->4 is reassigned and the extra cost for these roads are marked in RED. Now taking any of the routes will cost the same amount 12.

Note: There can be few cases with no solution too.


Solution >>>

Here is my solution to the problem

The main objective is to change the cost of the all the routes to the costliest route's cost. In the above example the costliest route is 1-3-2-4 with cost 12. For every other than 1-3-2-4, traverse from the end and try to adjust the fees of the current road. You can do this only if this road is connected by one road, in other words the IN-DEGREE of this road has to be 1. If this road has in-degree more than 1 then traverse back to the previous road in this route and repeat the check. If you cannot find any road with in degree 1 then exit with no solution.

Adjusting the fee of a road is simply done by adding the {cost difference between the costliest route & this route} to this road's fee.

Algorithm

1. Find the costliest route available with us and lets call it as X;
2. Y = ROUTE_COST(X);
3. For (every route other than X) as A
  Begin
4.    R = the last road in this route A;
5.    while (R<>NULL && IN_DEGREE(R) > 1)
     Begin
6.        N = the Previous road connecting to the road R in this route A;
7.        R = N;
     End;

8.    if (R===NULL) then exit with "No Solution";

9.    C = ROUTE_COST(A);
10.  ROAD_FEES(R) = ROAD_FEES(R) + (Y-C);
  End;

Let me know if you see any issues.

Avoid using Fur

The cruelty behind the Fur industry is painful.
See what is happening inside chinese Fur Farms (Warning: Please don't watch this video if you are sensitive)



Pledge to go fur-free at PETA.org.

Let us save them by avoiding Fur.

New members

Yesterday we added two new members to our house. They are just meant for entertaining us and nothing else.

Member 1:
Name: Tropicana Bowling Kit
Origin: Pins from Vinayaka Bakery and Ball from Sapphire






Member 2:
Name: Monopoly
Origin: Sapphire (a Toy shop near Garuda Mall)




The fun has just begun.. :)

The Truth

I came across this video titled "The girl who silenced the world for 5 minutes". Its a video from one of the UN meetings and this girl addressed the audience on the world's environment related issues.

I know she would definitely make you silent for a while!!

Open Hack Day - 2009

It is back again this year.. Yahoo! Open Hack day 2009 being organized at Taj Residency, Bangalore. The second day of the event has begun and the hackers just have 2 hours, 45 minutes left out to complete their ideas. Bangalore has always been very responsive to technical events, this year around 300 people have turned out for this event which included some college students. Yesterday was a eventful day with loads of technical talks, discussions, idea sharing sessions, dance, beer, red-bull, XBOX, PS2, party and of-course HACKING.. I had a chance to make my first external presentation/training yesterday, a memorable one for me.


This time I can really feel the high security at The Taj after the Mumbai attacks, the security was so alert that made few security guards to stop Yahoo!'s founder Filo and asked for his ID.. lol..

With hackers all around me trying to do final integration and presentation of their hacks which they developed through out the night even without taking a small nap (and of course there were few people who played XBOX all the night without any sleep :-P ) I am really eager to know the results..

All the best Hacker!!!

More pics at http://www.flickr.com/search/?q=hackdayindia&ss=2&ct=6

Bangalored

Recently I came across the term "Bangalored". Before going to a dictionary and figuring out what it is, I started making few wild guesses. Could that be a synonym for "struck in traffic" or "costly" or "high tech"? But I was totally wrong, this term means "losing a job just because the project is outsourced". The outsourced place need not be Bangalore it can be any place in the world, still the term remains the same. More info @ http://en.wiktionary.org/wiki/Bangalored

Thanks to all Indian consultancy companies who is responsible for this new term :-). And I hope we Bangalorians are not bangalored anytime.

The World's most popular web browser

The worlds most popular operating system "Windows" comes with the most popular web browser in this globe. The introduction to the almighty "Internet Explorer" is totally unnecessary. Statistics show that more than 65% of the Internet traffic is from Internet explorer, the remaining shared by Firefox, opera, safari, etc. What really made it to be so popular?? Yes, it is Windows, since Windows comes with built-in Internet explorer many people don't even think about installing an alternate browser. But is this Internet Explorer (a.k.a. IE) really worth this popularity?? I would say a big "NOOOO" and I really feel it be the worst piece of software one can ever write. Next time you get a chance just look how smoothly other browsers render the page and how IE does it, you will realize what I mean.

I have been developing web based applications for the past 2 years and writing a piece of code that would work in IE is always a PITA (Pain in the A**). When a organization called W3C is defining standards that the web browsers should follow for rendering the content, what would it cost for M$ to follow them? Every time you write a code one has to do special checks for IE and handle it specially. So at the end of day the code looks like

if (Internet Explorer) {
do something big and complicated to achieve something small
} else if (any other browser) {
write a simple code that work on all browsers.
}

Alright, I write this code and the next step is debugging. Browsers like Firefox provide so much facilities to add 3rd party plug-ins into the browser. Many of these plugins are for developers to help them in debugging HTML, JavaScript, CSS, Network traffic, load time, etc. But unfortunetly the most popular web browser doesn't have any of these abilities and it just dumps with the most idiotic error messages in the world. Some of them i encountered are

• 'null' is null or not an object
• Unspecified Error.
• 'undefined' is null
• Syntax error
  

and the list goes on. How would a developer know what went wrong when a stupid message like this pops-up without any other info like proper line number or statement? In most of the cases the issue is not with our application but with IE. So we are forced to hide the IE's bugs by adding fixes in our code because M$ will never fix it and we cann't do a release with these bugs showing up. There are so many versions of IE that was released IE-5, IE-5.5, IE-6, IE-7 and soon IE-8. But to me they just mean this

IE-5 = (Some functionality + Bugs)
IE-5.5 = (IE-5 + Some more Bugs)
IE-6 = (IE-5.5 + Some more Bugs)
IE-7 = (IE-6 + Some more Bugs)
IE-8 = (IE-7 + Some more Bugs)

and none of them shows any improvements in its functionality and this is not acceptable.

Long live Internet explorer!!!

P.S: This post just contains my personal view about the mentioned products and in no way represents my employer or colleagues