Androids on a Bridge

[DejMar]

There exist two equal length spans of a rickety bridge over a raging, hazardous river that a group of nine androids must safely cross in the wee hours of a dark, moonless night.

To safely cross the spans, each crossing android needs to be plugged into a portable device that allows their eye-sensors to use the dim starlight to "see". Available to the androids for this purpose are two cyberbotic lanterns. Each cyberbotic lantern has two sockets that permit one or two androids to plug into it. The construction of the device is such that only one can be carried at a time by a single android. The androids do not need to "see" to plug into or disconnect from the device, and it takes virtually no time to do so. The limitiation of the device, other than the limit that at most two androids may be plugged into it at a time and that no connected android may be connected to another cyberbotic latern concurrently, is that it only works if the sum of the voltages of the androids plugged into it is not prime.

Each of the nine androids have an internal power source with a different positive integer voltage that ranges from 1 to 9. The voltage of each android also is in direct relation to the minimum time in which the android may cross a span. That is, Android A, with voltage 1, can move across a span in 1 minute; Android B, with voltage 2, can move across a span in 2 minutes; Android C, with voltage 3, can move across a span in 3 minutes; etc. The speed at which two androids together may cross one span of the bridge is no greater than the slowest of the two in the pair.

The center of the bridge between the two spans can safely harbor all nine androids, and that it takes virtually no time to enter or exit this center support. Each span of the bridge can safely support only two androids at a time. The narrowness of each span of the bridge only allows one direction of movement for any crossing android or pair of androids. An android or a pair of androids may reverse direction only after reaching the center support or either of the two ends of the bridge.

What is the shortest amount of time it would take for all nine androids to safely cross both spans of the bridge during this dark night using only two cyberbotic lanterns?

[Trojan Horse]

[DejMar]

Correct in that 2, 3, 5 and 7 need an escort (or they need to escort).

[Trojan Horse]

I know you said that no robot can be plugged into two lanterns at the same time. But can a robot be plugged into one lantern and CARRY the other lantern at the same time?

I'm picturing the following scenario: four robots cross the bridge using the two lanterns, and then just ONE robot returns, bringing both lanterns with him.

[DejMar]

[Zag]

[Trojan Horse]

Zag: your first move is illegal, since 1+2 is prime.

[Trojan Horse]

Okay, just so that we have a score to beat, here is my naive first attempt. I'm using Zag's format, but I'm also throwing in a couple of asterisks to represent the lanterns.

The basic idea is to use the super-speedy 1 robot to do the dirty work of bringing the lanterns back to the start. Also, no one ever stops in the middle of the bridge; everyone always keeps going until they have reached the other side.

[DejMar]

I know I said yes. But I unfortunately meant no. The error is due to my haste in trying to simplify the answer.
No android can carry more than one cyberbotic lantern. Consider them as holding a magnetic charge of like charges. The combined repelling nature conducted through the metallic skins of an android would disrupt an android's own power circuits if he were to hold onto more than one, preventing his gyro-servos from operating safely.

[lostdummy]

Is it possible for two lanterns to be carried over same span?

That still satisfy all your current conditions:
- two lanterns
- not more than two androids on span
- max 2 androids per lantern

For example, one android start from left side of span on one lantern, and another android start from right side of span on second lantern?

Another example would be one android start from left side on first lantern, and at same time another android starts from same side on second lantern?

Or there is another condition: two lanterns can not cross same span at same time ?

Also, where is initial position of lanterns? If we say that all androids start on left side of bridge, are both lanterns also starting on left side? Or maybe second lantern is waiting on center?

[DejMar]

Two androids crossing a span together may carry one cyberbotic latern each. This would allow two laterns on the same span.
The rickety bridge is too narrow for androids to cross over each other safely, thus they must be travelling in the same direction until they reach one side or the other of a span..
The two cyberbotic laterns begin on the same side as the androids.

[novice]

[lostdummy]

[lostdummy]

Currently I have solution in 82min.

Since it was first 145min, then 89min, I'm still trying to see if there is better one.

After I was stuck at 89min solution, I tried to make program to find definite 'best' solution, but it proved bit too complex to be sure it works correctly. I had to make many assumptions and 'optimizations' to cut possible search time/space, so I can not be 100% sure this is really 'best' solution. I'm still checking that, so I consider this as 'currently best that it found' instead of 'definitely best' solution.

But at least it found 82min, which is slightly better solution than my previous manual 89min one ;p

Code:

82 :     123456789**---------------               ---------------                   :        (13>C) |              [ -3] 79 :        2456789*---------------      13*      ---------------                   :         (L<1) |              [ -1] 78 :      12456789**---------------       3       ---------------                   :        (19>C) |              [ -9] 69 :         245678*---------------      139*     ---------------                   :         (L<1) |              [ -1] 68 :       1245678**---------------       39      ---------------                   :        (46>C) |              [ -6] 62 :          12578*---------------     3469*     ---------------                   :        (17>C) |              [ -7] 55 :             258---------------    134679**   ---------------                   :         (L<4) |              [ -4] 51 :           2458*---------------     13679*    ---------------                   :        (24>C) | (13>R)       [ -3] 48 :              58---- (24)*>1---      679      ---------------            13*    :               | (C<1)        [ -1] 47 :              58---------------    124679**   ---------------              3    :         (L<1) |              [ -1] 46 :            158*---------------     24679*    ---------------              3    :        (18>C) | (24>R)       [ -4] 42 :               5---- (18)*>4---      679      ---------------           234*    :               | (C<4)        [ -4] 38 :               5---------------    146789**   ---------------             23    :               | (17>R)       [ -7] 31 :               5---------------     4689*     ---------------          1237*    :               | (C<1)        [ -1] 30 :               5---------------    14689**    ---------------            237    :         (L<4) | (19>R)       [ -4] 26 :             45*---------------       68      ---- (19)*>5---            237    :        (45>C) |              [ -5] 21 :                ---------------     4568*     ---------------         12379*    :               | (C<1)        [ -1] 20 :                ---------------    14568**    ---------------           2379    :               | (18>R)       [ -8] 12 :                ---------------      456*     ---------------        123789*    :               | (C<1)        [ -1] 11 :                ---------------     1456**    ---------------          23789    :               | (46>R)       [ -6] 5  :                ---------------      15*      ---------------       2346789*    :               | (15>R)       [ -5] 0  :                ---------------               ---------------    123456789**    :             SOLVED           [ -5]

*EDIT* Explanation of result format (although most should be self evident):
"------------------" bridge span
"---- (18)*>4---" means at this point there are androids 1 and 8 on lantern crossing this span, with 4min left to finish
"(18>C) | (24>R)" means from this position, androids 1&8 will use lantern to move from left side to center, while androids 2&4 will use other lantern to move from center to right side ('|' means center there)
"[-4]" means that this move will last 4min, until next shown state

Ah, and [ spoiler ] is not working with [ code ]

[Trojan Horse]

[Icarus*]

I come up with 32 minutes. I am pretty sure I followed all the rules.

I will try to paste my solution soon.

[Icarus*]

Step 1
1 & 9 cross span 1 - 1 returns solo
4 & 8 cross span 2 - 4 returns solo
8 & 9 at finish
total cross/return time = 12 minutes

Step 2
1 & 7 cross span 1 - 1 returns solo
4 & 6 cross span 2 - 4 returns solo
6, 7, 8 & 9 at finish
total cross/return time = 11 minutes

Step 3
1 & 5 cross span 1 - 1 returns solo
2 & 4 cross span
2, 4, 5, 6, 7, 8 & 9 at finish
total cross/return time = 6 minutes

Step 4
1 & 3 cross span
total cross time = 3 minutes

Total time 12 + 11 + 6 + 3 = 32 minutes

[DejMar]

I will post the solution soon.
Hint: The actual time it takes for the androids to all cross is nearly an hour.

[Icarus*]

Step 2 total time should have only been 10 minutes, not 11, so total time is only 31 minutes, not 32

[DejMar]

[lostdummy]

[Icarus*]

OK

I interpreted 2 spans to mean 2 parallel spans with a center platform, not 1 serial span with a "break" in the middle.

[lostdummy]

Found few better solutions.

Actually, I found way for my program to use previous results to 'refine' next search - and while it is still not full search, and I can not be sure that what it found is best, it was able to improve from 82min to 75 to 62, and now at 59.

I'm still checking if it can go lower, but here it is:

[Vagrant]

[Trojan Horse]

[DejMar]

Solution:

[lostdummy]

I must say that I expected different solution than mine, both based on your hint and on fact that there is more than one solution with 59min time.

Also I noticed that you changed your hint from 'over an hour' to 'nearly an hour' ;p

Anyway, I'll try and see if I can find 58min solution, or barring that, how many different 59min ones.

[itisally]

I think I got a 58 min solution, can someone check my work?


_________________
I could agree with you, but then we would both be wrong.

[lostdummy]

[itisally]

Doh! Can't belive I missed that.
_________________
I could agree with you, but then we would both be wrong.