Thursday, June 28, 2007

Code Challenge: "John the courier"

Yet another brillian idea popped into my mind today: Why not celebrate the rainy summer with a nice indoor competition - a Code Challenge!


Through the next couple of weeks I intend to publish a couple of challenges like the one below.

Think fast, solve the problem and post it as a comment!

The various challenges will have different winning criterias. These could be: "First valid solution posted", "Valid solution with fewest code-lines", "Funniest approach", "Best Performance", etc.

The Winner will win ... well... the honour along with mocking rights over all other coders in the world (at least those who read this blog and who didn't win).

We'll start off with an easy one...



Challenge #1 "John the courier"

In John's little world there is n cities, named by numbers starting at 0. In every city there is a parcel that's supposed to go to another city in John's world.

John live in City no. 0 and starts by picking up a package there. Then, whenever he delivers a package in a city he takes the package from that city and takes it to where it should go.

The distance between the cities is oddly enough the same as the difference in their names (e.g. the distance between city 10 and city 7 is 10-7=3).

John starts off his day with receiving a list of where the parcels in each city should be delivered. Now, John wonders: How far will I have to travel before I get back to my home (City 0).

Suggest a method that takes an int-array where the city is the index and the value is the destination of the package in the city (like this: int CalculateDistanceToHome(int[] CityPackages);) that returns the distance John must travel before he gets home. You can assume that the packages are distributed in such a way that John will always eventually get home.
First valid solution posted is the winner. Bonus points for recursive solutions.
Let the games begin!

4 comments:

Kerry Bellerose said...

I'm sure the challenges will get harder, so I had best offer a solution to the first one (where I have a fighting chance :-).

Here's my solution in psuedo code:

int CalculateDistanceToHome(int[] CityPackages)
{
// find the distance to home when starting from City 0
return CalculateDistanceToHome(CityPackages, 0);
}

int CalculateDistanceToHome(int[] CityPackages, int startCity)
{
if (CityPackages[startCity] == 0)
return startCity;
else
// Assuming that ABS returns the non-negative value of the given expression.
return ABS(CityPackages[startCity] - startCity) + CalculateDistanceToHome(CityPackages, CityPackages[startCity]);
}

Allan Thræn said...

Looks like we have a winner! Good job, Kerry.
The race is still on for second and third place - however in order for the entries to be accepted they should be significantly different than Kerry's.

Stavros said...

I just saw your post..
int CalculateDistanceToHome(int[] CityPackages){
int i=0;
int distance = 0;
while (CityPackages[i]!=0)
{
distance += abs(i-CityPackages[i]);
i = CityPackages[i];
}
distance += i;
return distance;
}

Allan Thræn said...

Nice and valid solution, Stavros. Congrats on getting second place.