• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Programming Puzzle

 
Ranch Hand
Posts: 47
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Problem Description:

There are N petrol bunks arranged in circle. Each bunk is separated from the rest by a certain distance. You choose some mode of travel which needs 1 litre of petrol to cover 1 km distance. You can't infinitely draw any amount of petrol from each bunk as each bunk has some limited petrol only. But you know that the sum of liters of petrol in all the bunks is equal to the distance to be covered.
i.e let P1, P2, ... Pn be n bunks arranged circularly. d1 is distance between p1 and p2, d2 is distance between p2 and p3. dn is distance between pn and p1.Now find out the bunk from where the travel can be started such that your mode of travel never runs out of fuel.

Also, derive the time complexity and space complexity measures.
 
Ranch Hand
Posts: 457
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
sounds computationally equivalent to the Traveling Salesman Problem
 
Master Rancher
Posts: 4806
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think it may be a good deal simpler than the traveling salesman, if my guesses about the intent here are correct.

[mani]: But you know that the sum of liters of petrol in all the bunks is equal to the distance to be covered.

What distance to be covered? It seems like there are many possible distances that we might travel, depending on our objectives - and the problem hasn't even given us a goal. Perhaps we are supposed to visit each fuel station once? Perhaps the "distance to be covered" is the total d1 + d2 + d3 + ... + dn? In this case, we could simply travel the circle (or polygon as the case may be), visiting each station in order, never reversing direction. The only important choices would be (a) where to start, and (b) which direction to travel in, so as not to ever run out of fuel. There's a reasonably simple algorithm that can be used here, and there will always be at least two solutions - one in each direction. Maybe more.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic