INTELLIGENT WORK FORUMS
FOR COMPUTER PROFESSIONALS

Log In

Come Join Us!

Are you a
Computer / IT professional?
Join Tek-Tips Forums!
  • Talk With Other Members
  • Be Notified Of Responses
    To Your Posts
  • Keyword Search
  • One-Click Access To Your
    Favorite Forums
  • Automated Signatures
    On Your Posts
  • Best Of All, It's Free!

*Tek-Tips's functionality depends on members receiving e-mail. By joining you are opting in to receive e-mail.

Posting Guidelines

Promoting, selling, recruiting, coursework and thesis posting is forbidden.

Jobs

The Supply Ship

The Supply Ship

(OP)
Not sure if this is a "Puzzle for Programmers", or just a puzzle, but here goes. First a word of warning, I won't have the answer until next month's issue, so I may not be able to tell you if you've solved it or not for one month. bigsmile

Quote:

We need to get to the planet Omega from the planet Alpha (which has unlimited supplies). It's five months away. In between are four supply stations, Delta, Kappa, Sigma, and Phi, which are on a straight line and spaced evenly one month apart from the planets and/or each other. Our spaceship can only hold three months of supplies. The supply stations are empty but can hold two months supplies each. Using only our spaceship, what is the minimum amount of time needed to get from Alpha to Omega?


RE: The Supply Ship

Hi Sam,

this is a nice example for a program finding the shortest route in a trial & error or also more intelligent approach. It may be doable without any coding, too. But without trying anything the feeling I have about this puzzle is the solution might not be very straight forward or obvious. I'd not be surprised, if I'm wrong, but I'd be disappointed.

Let's make a start with some obvious things:

Spoiler:

You can't get straight to omega with a 3 month supply, so the first journey will start and end at alpha, starting with 3 month supplies. Arriving at Delta, 2 month supplies remain, one month supply is needed to fly back, so one month supply can be deposited on this journey taking two months.

OK, having thought as far, I think it's doable without programming something.

Bye, Olaf.

RE: The Supply Ship

PHV:

Spoiler:

Only Alpha has supplies, and you can only hold 3 months worth of supplies in the spaceship. If you took the direct route, you would pass Delta and Kappa, then die shortly after you arrived at Sigma.

RE: The Supply Ship

PHV: Don't only think about fuel, think about food. People will die, if you simply stay somewhere. Also the question is about the minimum time needed, so you'll never pause anywhere.

Bye, Olaf.

RE: The Supply Ship

Here's a solution without using any code:

Spoiler:

To keep it short, just the list of stations after each turn/month: A '+' denotes depositing supplies to a station, a '-' denotes loading supplies to the ship.
start at 0 months: α → δ+ → α → δ+ → α → δ- → κ+ → δ- → α → δ+ → α → δ- → κ- → σ → φ → ω :arriving after 15 months with 0 supply.

So there is no way back then, unless Omega also has unlimited supplies.

Bye, Olaf.

RE: The Supply Ship

Spoiler:

(I started this earlier, it seems to be the same as Olaf's answer, just with my logic spelled out in words)

We want to get travel Alpha => Delta => Kappa => Sigma => Phi => Omega

Working backwards, if we can be on Kappa with a 3 month supply, we can make it all the way to Omega.

One way to achieve that (maybe the only way?) is to make 4 round trips to Delta as Olaf described in his first post, each time depositing one month's worth of supplies on Delta. This would take 8 months to complete.

Then, load up at Alpha, say your goodbyes to friends and family and make a one-way trip to Delta (9 months have passed now). Add a month's worth of supplies from Delta (leaving 3 more there), to max your ship out, then make a single 2-month round trip to Kappa, leaving one month of supplies there. (11 months have now passed)

Finally, take the remaining supples from Delta (maxing your ship out), and celebrate the 1-year anniversary of your journey on Kappa. Take the month of supplies you left there earlier, to "top off the tank" so to speak, and begin the final leg of your journey. Three months later, you arrive at Omega, 15 months after you started.

This is when you need to hope Omega has unilimited supplies like Alpha. Or, any supplies for that matter

RE: The Supply Ship

But there is no mention of time spent in a supply station ...
True, but wouldn't that make the journey even longer than 5 months?

RE: The Supply Ship

My Solution Matches Olafs's

@Guitarzan - you've broken the max 2 month supply at each supply station

Spoiler:


Trip 1 - Drop 1 month supply at Delta return to Alpha - 2 Months (1 month supply at Delta)
Trip 2 - Drop 1 month supply at Delta return to Alpha - 2 Months (2 Month Supply at Delta)
Trip 3 - Resupply 1 month at Delta and continue to Kappa, drop 1 month supply at Kappa, return to Delta and resupply at Delta and return to Alpha - 4 month round trip (1 month supply at Kappa)
Trip 4 - Drop 1 month supply at Delta return to Alpha - 2 Months (1 month supply at Delta and 1 Month supply at Kappa)
Trip 5 - Resupply at Delta, resupply at Kappa, then Sigma, then Phi, then Omega - 5 Months
Total time = 15 months

**********************************************
What's most important is that you realise ... There is no spoon.

RE: The Supply Ship

kwbMitel
RATS, i did completely miss that rule. Odd that even violating that rule, i got 15 months (unless I made another error?).

Spoiler:

The good thing about my error is that, upon landing on Delta for what should have been the third round trip, when we attempted to unload another month of supplies, we would have said, in unison, "WHAAAAAT??? Theres no more space?", which would have left us a great deal of embarassment, and also a limited set of choices:
1) take a month's supplies from Delta and continue to Kappa and drop off one month there (which are the next steps of the correct Olaf / kwbMitel route)
2) head directly to Kappa (then we only have 1 month supplies left, for our pointless trip back to Delta, that would be dumb)
3) Just head back to Alpha. Also pointless.

I would like to think our crew would re-group, and decide the correct path at this crossroad, but given that we missed the whole "2-month max" thing, I'm not so sure.

RE: The Supply Ship

guitarzan,

Indeed you just have to reorder some things and get to a functioning route. The storage limitation does not allow doing what you do in that order, but the amount of partial routes is correct and you therefore have determined the time needed correctly.

Bye, Olaf.

RE: The Supply Ship

I havn't sorted the answer to this one yet but the trick is to work backwards.
ie retrace you final journy from alpha to omega & work out what the minimum suplies required at the inverviening stations, them move back & plan how to arive at that state & so on.

A Maintenance contract is essential, not a Luxury.
Do things on the cheap & it will cost you dear

RE: The Supply Ship

As far as I can tell, all your really need is to manage to store 2 months worth of supplies in kappa and you are golden.

So basically:

Spoiler:


Alpha->Delta (drop one month of supplies)->Alpha (2 months travel)
Alpha->Delta (drop another month of supplies)->Alpha (2 months travel)
Delta now has 2 months worth of supplies
Alpha->Kappa(Pick One month of supplies)->Delta(Drop off one month of supplies)->Kappa(pick up month of supplies)->Alpha (4 months travel)
Alpha->Delta (drop one month of supplies)->Alpha (2 months travel)
Alpha->Delta (drop another month of supplies)->Alpha (2 months travel)
Alpha->Kappa(Pick One month of supplies)->Delta(Drop off one month of supplies)->Kappa(pick up month of supplies)->Alpha (4 months travel)
Delta now has 2 months worth of supplies.
Set Off from Alpha, stop by Delta to restock, fly off to Omega non stop. 5 months.

Total time: 21 months.


Don't see how it can be done in less, if you need 4 months each time to get to Delta and back.

----------------------------------
Phil AKA Vacunita
----------------------------------
Ignorance is not necessarily Bliss, case in point:
Unknown has caused an Unknown Error on Unknown and must be shutdown to prevent damage to Unknown.

Web & Tech

RE: The Supply Ship

The Above should have read:

Spoiler:




Alpha->Delta (drop one month of supplies)->Alpha (2 months travel)
Alpha->Delta (drop another month of supplies)->Alpha (2 months travel)
Delta now has 2 months worth of supplies
Alpha->Delta(Pick One month of supplies)->Kappa(Drop off one month of supplies)->Delta(pick up month of supplies)->Alpha (4 months travel)
Alpha->Delta (drop one month of supplies)->Alpha (2 months travel)
Alpha->Delta (drop another month of supplies)->Alpha (2 months travel)
Delta now has 2 months worth of supplies
Alpha->Delta(Pick One month of supplies)->Kappa(Drop off one month of supplies)->Delta(pick up month of supplies)->Alpha (4 months travel)
Kappa now has 2 months worth of supplies.
Set Off from Alpha, stop by Delta to restock, fly off to Omega non stop. (5 months travel)

Total time: 21 months.

----------------------------------
Phil AKA Vacunita
----------------------------------
Ignorance is not necessarily Bliss, case in point:
Unknown has caused an Unknown Error on Unknown and must be shutdown to prevent damage to Unknown.

Web & Tech

RE: The Supply Ship

(OP)

Spoiler:

Like I said, I won't know the official answer until next months issue bigsmile, but I came up with 21 months too and that seems correct to me.

BUT, that leaves us stranded on Omega with no supplies! There's no mention of Omega having any supplies. We either wait for another (empty?) ship to follow in another 21 months, or, we need to leave enough supplies on each station to return. Just one month supplies on each station is enough to get us home (assuming we have one month supplies upon our arrival on Omega). Anyone care to compute how many months to get there AND return?

Or maybe two scenarios, one with Omega having unlimited supplies, one with Omega having none.

RE: The Supply Ship

@ Vacunita (and possibly Sambones)

Spoiler:

you do not need to store 2 months supplies at Kappa
you need 1 month each at Delta and Kappa
This shortens your timeframe considerably

**********************************************
What's most important is that you realise ... There is no spoon.

RE: The Supply Ship

Spoiler:

Month   Ship Location   Action          Ship   Delta   Kappa   Sigma   Phi
  0     Alpha           Load supplies     3      0       0       0      0
  1     Delta           Arrive            2      0       0       0      0
        Delta           Leave supplies    1      1       0       0      0
  2     Alpha           Arrive            0      1       0       0      0
        Alpha           Load supplies     3      1       0       0      0
  3     Delta           Arrive            2      1       0       0      0
        Delta           Leave supplies    1      2       0       0      0
  4     Alpha           Arrive            0      2       0       0      0
        Alpha           Load supplies     3      2       0       0      0
  5     Delta           Arrive            2      2       0       0      0
        Delta           Load supplies     3      1       0       0      0
  6     Kappa           Arrive            2      1       0       0      0
        Kappa           Leave supplies    1      1       1       0      0
  7     Delta           Arrive            0      1       1       0      0
        Delta           Load supplies     1      0       1       0      0
  8     Alpha           Arrive            0      0       1       0      0
        Alpha           Load supplies     3      0       1       0      0
  9     Delta           Arrive            2      0       1       0      0
        Delta           Leave supplies    1      1       1       0      0
 10     Alpha           Arrive            0      1       1       0      0
        Alpha           Load supplies     3      1       1       0      0
 11     Delta           Arrive            2      1       1       0      0
        Delta           Load supplies     3      0       1       0      0
 12     Kappa           Arrive            2      0       1       0      0
        Kappa           Load supplies     3      0       0       0      0
 13     Sigma           Arrive            2      0       0       0      0
 14     Phi             Arrive            1      0       0       0      0
 15     Omega           Arrive            0      0       0       0      0 

Randy

RE: The Supply Ship

Making a one-way trip to Omega:

Spoiler:

15 months


Stocking up to allow a return trip:

Spoiler:

157 months
Assuming the explorers don't stay for any significant length of time.
If we want to stay for a month on Omega and make a return trip, the time will be much higher.

Final Answer:

Spoiler:

send robots!

RE: The Supply Ship

Spoiler:


kwb you are of course correct.
Having one month stock on each planet Delta and Kappa reduces the time by 6 months down to 15.

As to the return, if omega has unlimited supplies, then it works the same way as before. another 15 months to get back.

If omega has no supplies, the then time required would be better spent developing an interplanetary teleporter. I'm sure it would take much less time. 2thumbsupbigglasses








----------------------------------
Phil AKA Vacunita
----------------------------------
Ignorance is not necessarily Bliss, case in point:
Unknown has caused an Unknown Error on Unknown and must be shutdown to prevent damage to Unknown.

Web & Tech

RE: The Supply Ship

(OP)
If Omega has no supplies, you just need to arrive there with one months supplies, and have left at least one months supplies on each space station.


RE: The Supply Ship

for a real world example google Blackbuck raid refuling smile

A Maintenance contract is essential, not a Luxury.
Do things on the cheap & it will cost you dear

Red Flag This Post

Please let us know here why this post is inappropriate. Reasons such as off-topic, duplicates, flames, illegal, vulgar, or students posting their homework.

Red Flag Submitted

Thank you for helping keep Tek-Tips Forums free from inappropriate posts.
The Tek-Tips staff will check this out and take appropriate action.

Reply To This Thread

Posting in the Tek-Tips forums is a member-only feature.

Click Here to join Tek-Tips and talk with other members!

Resources

Close Box

Join Tek-Tips® Today!

Join your peers on the Internet's largest technical computer professional community.
It's easy to join and it's free.

Here's Why Members Love Tek-Tips Forums:

Register now while it's still free!

Already a member? Close this window and log in.

Join Us             Close