what?
Originally posted by Greg Harris:
the german has the fish... houses from left to right.
Norwegian - Yellow - Water - Dunhill - Cat Dane - Blue - Tea - Blends - Horse Brit - Red - Milk - PallMall - Bird German - Green - Coffee - Prince - Fish Swede - White - Beer - BlueMaster - Dog
Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius - and a lot of courage - to move in the opposite direction. - Ernst F. Schumacher
Originally posted by Michael Morris:
... I'm not so sure this is a 98 percentile logic problem though...
what?
Originally posted by Greg Harris:
gosh... and i was starting to think that i was really smart.
Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius - and a lot of courage - to move in the opposite direction. - Ernst F. Schumacher
what?
Originally posted by Greg Harris:
hmmm... i am supposed to be working today... thanks, michael.
i was thinking of booleans like you said - maybe an adjacency matrix, but there are the pesky "maybe" situations you mentioned.
now i am thinking of using graph theory - but there are too many factors for a regular graph coloring.
the way i solved it manually was to figure out the houses first, and then fill in what i knew for certain. then, i put the men in five columns and filled in what i knew for certain about them. after that, the rest fell into place.
Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius - and a lot of courage - to move in the opposite direction. - Ernst F. Schumacher
MH
Originally posted by Tim Allen:
I *really* would like to see this worked out as a Java program. I think the algorithm for how to do this would really teach all of us a new way of thinking about problem solving-- anyone?
Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius - and a lot of courage - to move in the opposite direction. - Ernst F. Schumacher
Originally posted by Eugene Kononov:
This may be one of those problems that cannot be solved in polynomially bounded time. If you employ a brute search algorithm, it may take up to 1.45519E+25 iterations, if my calculations are right. Even if each iteration takes only 1 microsecond, it will take about 460 billion years to find a solution.
Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius - and a lot of courage - to move in the opposite direction. - Ernst F. Schumacher
Originally posted by Eugene Kononov:
Are you sure? If the set of data is conclusive it would seem that it is possible.
I don't have a formal proof, but I laid down the problem on paper and it is awefully simplar to those graphs problems, such as Hamiltonian Cycle and Traveling Salesmen, which are NP-complete. I'll do some search, maybe there is reference to this particular problem as an NP-complete, too.
Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius - and a lot of courage - to move in the opposite direction. - Ernst F. Schumacher
Originally posted by Eugene Kononov:
I've got the data structure down. My next step is to add the knowns into it and then write a solve method. When I get to that point, it should become obvious if we have a Traveling Salesmen dillema.
Go on, man. I did some search and found that people have written programs in Lisp, Prolog, and C++ to solve this problem in a very short computational time (order of seconds). So my guess about NP-completeness was wrong. I intentionally do not list the references to the solutions here, but you can easily find them on the web. Of course, creating your own solution is much more fun.
Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius - and a lot of courage - to move in the opposite direction. - Ernst F. Schumacher
Originally posted by Michael Morris:
Just like Elvis, I'll go out singin' "I did it my way".
Originally posted by Mark Herschberg:
AAARRRRGGGG! That's Frankie's song! Not Elvis'!
--Mark
Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius - and a lot of courage - to move in the opposite direction. - Ernst F. Schumacher
Thanks, leo
Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius - and a lot of courage - to move in the opposite direction. - Ernst F. Schumacher
Originally posted by Mark Herschberg:
AAARRRRGGGG! That's Frankie's song! Not Elvis'!
--Mark
Mark Herschberg wrote:It strikes me that this type of problem is ideal for a rule based language like Lisp or Prolog.
--Mark
Michael Morris wrote:
So Gregg, can you figure a generic way to solve this sort of problem programatically? I've been thinking of some sort of contrived data structure to do it but can't quite get a handle on it. At first you think booleans would handle it but you actually have tristate conditions: yes, no, maybe. You could probably create an object for each possible item with references to all the other items but that would seem inefficient.
Consider Paul's rocket mass heater. |