Archived

This topic is now archived and is closed to further replies.

logic problem

This topic is 5015 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

ok i have this logic problem a friend of mine gave me and i was wondering how you would solve it (using c++) Sylvia and four other workers in Hamilton were unemployed for a short time last year when they decided to change their occupations (one was a telephone operator) and undergo retraining for new jobs. The five are now happily re employed (one is a mechanic). From the clues below, can you determine each worker's full name (one surname is Swanson), former job and present job? 1. The five workers are Tom, the former welder, the present arcade manager, Ms. Cortez, and the present Fitness instructor(who is not Mr. Bertram). 2. Ralph used to be a foreman. 3. Marie, who is neither Cortez nor Monroe, used to be a secretary. 4. Mr. Hampton is now a mail carrier. 5. The programmer, who is not Erica, used to repair TVs. plz post the an explanation of your methode. thanx. source would be nice too [edited by - Dransic on March 23, 2004 10:58:55 PM]

Share this post


Link to post
Share on other sites
Set up two matrices. Each one has five slots for names, and five slots for occupations. At start, ALL the intersections are empty, and ALL the names/occupation rows/columns are empty.

Now, use the information to fill out the matrices. All the kinds of occupations (old and new) are mentioned -- if they aren't, the problem isn't fully (uniquely) solvable. All the names are mentioned, too -- if they aren't, the problem isn't fully (uniquely) solvable.

As a bonus, there's only five names, so the row labels are the same in the two matrices. It might make it clearer to build one matrix that's five rows times ten columns; that's up to you.

In these matrices, mark in the knowledge you know from the direct clues. Now, remains to solve the unknowns, i e determining "yes" or "now" for each intersection of name/occupation that's not currently filled (blank == don't know yet). You also know that each person can only have one former and one current job; that's an important additional constraint.

Edit: There's a few extra details, like male/female and first/last name, which you can fill out the same way. Again, if you can't figure out all of the variables (not necessarily assignments) then the problem is under-constrained.

You can brute-force this using direct enumeration at this point, unless the direct rules are already enough to give you the solution. I e, for the first name for which you don't know the former occupation, pick one of the candidates that aren't already excluded, then work through the rules to arrive at everyone else. If you get an inconsistency, back-track and pick the next. Pretty soon, you'll have the solution (as the problem is well constrained).

What the actual solution is? Well, that wouldn't be sportsmanlike. Hint: it's pretty fast to write it up in prolog :-)


[edited by - hplus0603 on March 23, 2004 10:52:48 PM]

Share this post


Link to post
Share on other sites
Because no-one else posted, there is exactly one solution, and this is it:

[tom, hampton, male, telephoneoperator, mailcarrier]
[ralph, bertram, male, foreman, arcademanager]
[marie, swanson, female, secretary, fitnessinstructor]
[erica, monroe, female, welder, mechanic]
[sylvia, cortez, female, tvrepairman, programmer]

This is the output of the appropriate prolog program. Note that some of the rules are quite subtle -- like, the list of the five workers is an exclusion (i e you can't both have the name Tom and be a former welder). Also, cuts will make the program run lots faster, and generate the single solution.

Edit: Prolog code (with ugly top-level solution driver/printer) available for next 24 hours at:
rafb.net.

Just consult it, and execute the goal "solution".

[edited by - hplus0603 on March 23, 2004 12:37:02 AM]

Share this post


Link to post
Share on other sites