The Supply Ship 1

[SamBones]

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.

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?

 

[Olaf Doschke]

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.

 

[PHV]

I don't see why 5 months is'nt the obvious right repply ...

Hope This Helps, PH.
FAQ219-2884
FAQ181-2886

 

[guitarzan]

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.

 

[PHV]

But there is no mention of time spent in a supply station ...

Hope This Helps, PH.
FAQ219-2884
FAQ181-2886

 

[Olaf Doschke]

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.

 

[Olaf Doschke]

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.

 

[guitarzan]

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

 

[guitarzan]

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?

 

[kwbMitel]

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.

 

[guitarzan]

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.

 

[Olaf Doschke]

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.

 

[IPGuru]

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

 

[vacunita]

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

 

[vacunita]

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

 

[SamBones]

Spoiler

Like I said, I won't know the official answer until next months issue , 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.

 

[kwbMitel]

@ 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.

 

[randy700]

Spoiler

[pre]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[/pre]

Randy

 

[jges]

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!

 

[vacunita]

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.










----------------------------------
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