All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Logic
Traveling with Luggage (Posted on 2016-12-15) Difficulty: 3 of 5
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?

No Solution Yet Submitted by Brian Smith    
Rating: 3.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution computer solution (spoiler) | Comment 1 of 2
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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information