Alex, Bert and Carl are traveling, each with their own luggage. They have just collected their luggage after arriving from their flight. They need to get themselves and their luggage to the hotel. When they go to the car rental company, the company tells them that the only car available is a tiny compact car.
The car can hold either two people or one person plus one set of luggage. Obviuosly multiple back-and-forth trips are needed to get everyone and everything to the hotel.
The airport and hotel are trustworthy places but the three men do not trust each other. Each man will ransack the luggage of another person if left alone with the luggage. Specifically Alex will ransack Bert's luggage, Bert will ransack Carl's luggage, and Carl will ransack Alex's luggage. Ransacking can occur at the airport, the hotel, or in the car. The inverse relations will not result in a ransack (Alex won't ransack Carl's luggage, etc.)
Is it possible for Alex, Bert, and Carl to get themselves and all their luggage to the hotel without anybody having an opportunity to ransack any of the luggage? If so then how?
The airport is to the right of the vertical bar and the hotel is on the left.
Here's the transfer in 9 trips:
| ABCabc
<Cc
Cc | ABab
C>
c | ABCab
<CA
ACc | Bab
C>
Ac | BCab
<Cb
ACbc | Ba
A>
Cbc | ABa
<BA
ABCbc | a
A>
BCbc | Aa
<Aa
ABCabc |
People are capital letters and luggage is represented by lower case.
For some reason the program left out the lower case a in the last carload and I inserted it manually. These are kept in the hst() array, for history. The program:
DefDbl A-Z
Dim crlf$, hotel, airport, state(4096), states, a, b, c, alug, blug, clug
Dim hst$(50), lowCt, ct
Private Sub Form_Load()
Form1.Visible = True
Text1.Text = ""
crlf = Chr$(13) + Chr$(10)
a = 32: b = 16: c = 8
alug = 4: blug = 2: clug = 1
airport = 63
state(1) = 64 * hotel + airport
states = 1
lowCt = 50
airport2hotel
Text1.Text = Text1.Text & crlf & " done"
End Sub
Sub airport2hotel()
driver = 8
For d = 0 To 2
If airport And driver Then
carried = 1
For crd = 0 To 5
DoEvents
If airport And carried Then
newhotel = hotel Or driver Or carried
newairport = airport And (Not driver) And (Not carried)
newstate = 64 * newhotel + newairport
If isOK(newairport) And isOK(newhotel) Then
good = 1
If driver = a And carried = blug Or driver = b And carried = clug Or driver = c And carried = alug Then good = 0
For i = 1 To states
If newstate = state(i) Then good = 0: Exit For
Next
If good Then
states = states + 1
state(states) = newstate
oldhotel = hotel
oldairport = airport
airport = newairport
hotel = newhotel
hist$ = ""
Select Case driver
Case 8
hist = "C"
Case 16
hist = "B"
Case 32
hist = "A"
End Select
If carried <> driver Then
Select Case carried
Case 1
hist = hist + "c"
Case 2
hist = hist + "b"
Case 42
hist = hist + "a"
Case 8
hist = hist + "C"
Case 16
hist = hist + "B"
Case 32
hist = hist + "A"
End Select
End If
hst(states) = "<" + hist
If newairport = 0 Then
If ct < 10 Or states < lowCt Then
For i = 1 To states
Text1.Text = Text1.Text & hst(i) & crlf
showState (state(i))
Next
Text1.Text = Text1.Text & crlf
End If
If states < lowCt Then lowCt = states
ct = ct + 1
Else
If states <= lowCt Then
hotel2airport
End If
End If
airport = oldairport
hotel = oldhotel
states = states - 1
End If
End If
End If
carried = carried * 2
Next crd
End If
driver = driver * 2
Next d
End Sub
Sub hotel2airport()
driver = 8
For d = 0 To 2
If hotel And driver Then
carried = 1
For crd = 0 To 5
DoEvents
If hotel And carried Then
newairport = airport Or driver Or carried
newhotel = hotel And (Not driver) And (Not carried)
newstate = 64 * newhotel + newairport
If isOK(newairport) And isOK(newhotel) Then
good = 1
If driver = a And carried = blug Or driver = b And carried = clug Or driver = c And carried = alug Then good = 0
For i = 1 To states
If newstate = state(i) Then good = 0: Exit For
Next
If good Then
states = states + 1
state(states) = newstate
oldhotel = hotel
oldairport = airport
airport = newairport
hotel = newhotel
hist$ = ""
Select Case driver
Case 8
hist = "C"
Case 16
hist = "B"
Case 32
hist = "A"
End Select
If carried <> driver Then
Select Case carried
Case 1
hist = hist + "c"
Case 2
hist = hist + "b"
Case 42
hist = hist + "a"
Case 8
hist = hist + "C"
Case 16
hist = hist + "B"
Case 32
hist = hist + "A"
End Select
End If
hst(states) = hist + ">"
airport2hotel
airport = oldairport
hotel = oldhotel
states = states - 1
End If
End If
End If
carried = carried * 2
Next crd
End If
driver = driver * 2
Next d
End Sub
Function isOK(place)
apres = Abs((place And a) > 0)
bpres = Abs((place And b) > 0)
cpres = Abs((place And c) > 0)
pop = apres + bpres + cpres
good = 1
If pop = 1 Then
alpres = Abs((place And alug) > 0)
blpres = Abs((place And blug) > 0)
clpres = Abs((place And clug) > 0)
If apres And blpres Or bpres And clpres Or cpres And alpres Then good = 0
End If
isOK = good
End Function
Sub showState(s)
h = s \ 64
airp = s Mod 64
If h And a Then Text1.Text = Text1.Text & "A"
If h And b Then Text1.Text = Text1.Text & "B"
If h And c Then Text1.Text = Text1.Text & "C"
If h And alug Then Text1.Text = Text1.Text & "a"
If h And blug Then Text1.Text = Text1.Text & "b"
If h And clug Then Text1.Text = Text1.Text & "c"
Text1.Text = Text1.Text & " | "
If airp And a Then Text1.Text = Text1.Text & "A"
If airp And b Then Text1.Text = Text1.Text & "B"
If airp And c Then Text1.Text = Text1.Text & "C"
If airp And alug Then Text1.Text = Text1.Text & "a"
If airp And blug Then Text1.Text = Text1.Text & "b"
If airp And clug Then Text1.Text = Text1.Text & "c"
Text1.Text = Text1.Text & crlf
End Sub
|
|
Posted by Charlie
on 2016-12-15 10:38:16 |
computer solution (spoiler)
