Traveling Men Problem

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.

 

Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

Problem Description

 Mr. Barclay and five of his friends, each of whom works in a different field, just returned from business trips.  Each man used two different methods of transportation during his trip.  All six traveled by either plane or train, but not both, and all six also traveled by bus, boat, or trolley.  No two used the same two methods of transportation.  From the information provided, determine the first and last names of each man, his field (one deals in precious gems), and the two methods of travel he used on his business trip.

  1.  Mr. Rogers, who is not Vince or Russ, and Mr. Whitman together, used four different methods of transportation.

  2.  Mr. Potter traveled by bus.  The oil company executive visited an area that can only be  reached by a boat from the mainland.

  3.  Neither Myron, nor Russ, nor Mr. Henley, nor the mining engineer traveled by trolley.

  4.  Neither Leroy, who traveled by bus, nor Jeremy is the manufacturer.

  5.  The agricultural representative did not fly to his destination.

  6.  Vince, who is not Mr. Henley, traveled by boat.

  7.  Dennis and Mr. Rogers traveled by train.  Mr. Strong traveled by plane.

  8.  Both Mr. Whitman and the research scientist traveled by trolley.

Background & Techniques

I called this problem "stupid" for several days before resorting to a program to prove it.  Now that I've solved it, I'll modify the adjective from "stupid" to "less than clear".   If you work on it, I'll tell you that Clue #1 says that 2 people used the 4 modes of transportation, not 4 people as I originally interpreted it.

I  posted a logic problem solver several years ago which an excellent logic engine but cumbersome input procedures.  I may rewrite it one day to fix that.  It also is not flexible enough to handle this problem, particularly the compound travel mode characteristics where each man travels by "Plane & Boat", "Plane & Bus", Plane & Trolley", Train & Boat", "Train & Bus",  or "Train & Trolley" .  The clues partially specify travel by such statements as "traveled by train", etc.

The alternative approach posted here has the facts and rules hard coded into the program.  More  flexible for the programmer but not of much use to the non-programmer. The program uses "exhaustive search with pruning"   to find the solution quickly.   There are 373,248,000 possible solutions which might take an hour for the computer to check    But if we start by generating all possible assignments of Travel Mode to First names,  there are 720 possibilities.   (Dennis has  one of 6 modes, Jeremy, has one of the remaining 5, etc. and 6x5x4x3x2x1 = 720).   Each of these 720 will have 720 ways to assign last names and each of those will have 720 ways to assign occupations.  The large total stated above is this product 720x720x720. 

But back to the point, from Clue #7 we know that Dennis traveled by Train.  Since 1/2 the possibilities have him traveling  by Train and 1/2 by Plane, then half the time we can stop checking after this test  and we have "pruned" our search space by 50%.  If Dennis did travel by train for a specific permutation, we can check to see if Vince traveled by boat (Clue #6).  He only does this in 1/3 of the outcomes, so we have eliminated another 2/3 of the cases by this second test and only 1/6 of the 373 million will need to be checked further.   Each successive rule will eliminate 5/6, 2/3, 1/2,  1/3,  or at least 1/6 of the remaining cases to be checked which if we are applying several rules, quickly prunes the space to those possible solutions that pass all of the test applied.   

For the non-programmer, I have made a table in plain English (there are 29 of them in their current form) which the user can select or ignore for any test run.   And of course, selecting all of them will be the spoiler and give you the final solution, so do not run that choice unless you have given up on solving it manually.         

Non-programmers are welcome to read on, but may want to skip to the bottom of this page to download executable version of the program.

Notes for Programmers

I assumed permutations of the 6 Last names, 6 Travel modes and 6 Occupations, represented the 6 First names in alphabetical order.  Here are the actual Delphi statements that assign names to the various numeric values

{We will assume we are checking first names in this order}
Dennis=1; Jeremy=2; Leroy=3; Myron=4; Russ=5; Vince=6;

{Then we will permute these 6 travel mode combinations, filtering as we go}
PlaneBoat=1; PlaneBus=2; PlaneTrolley=3; TrainBoat=4; TrainBus=5; TrainTrolley=6;


{Any that pass First name-travel mode rules will get checked against last name
rules with names permuted in this order}
Barclay=1; Henley=2; Potter=3; Rogers=4; Strong=5;Whitman=6;

{Finally remaining possibilities will get checked against rules that involve
occupations in this  order}
Ag=1; Gems=2; Mfg=3; Mining=4; Oil=5; Research=6;

So a solution like  

Dennis, Rogers, Mining, Train/Trolley
Jeremy, Henley, Research, Plane/Trolley
Leroy, Strong, Gems, Plane/Bus
Myron, Whitman, Mfg., Plane/Boat
Russ, Potter, Agriculture, Train/Bus
Vince, Barclay, Oil, Train/Boat

is represented  by permutation 425631  for Last Names, 462315 for Occupations and 632154 for Travel Modes.

Special functions were written to identify rules which specified only half of one of the travel modes  (e.g. N represents a Train if N>3,;  N is a Bus if N=2 or N=5, etc.).

Permutations are generated for travel modes first, since those seemed to do the most pruning early on;  even negative rules (..is not ...), eliminate 1/3 or 1/2 of the remaining choices.  .   Permutations that pass the Fist-name vs. Travel Mode tests move to to the Last Name permutations, where we apply all of the tests for First Name vs. Last Name and Travel Mode vs. Last name.   Finally those that pass those filters get to Occupation permutations which check Occupation vs. everything else.  And, if all works correctly a single possibility will fall out the bottom as the unique solution. 

Running/Exploring the Program 

Suggestions for Further Explorations

Perhaps a visual based logic rule generator, which generates Delphi code for inclusion in a compile and run mode?

 

Original Date: May 13, 2006

Modified: February 18, 2016

 

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.