Esoteric Dissertations from a One-Track Mind

June 6, 2007

Letting the Machine do the Thinking

Filed under: programming — codesmithy @ 7:10 am

I came across a self-referential test today. As an exercise, I decided I wanted to try to write a computer program to solve it, with 20 multiple choice questions (A-E), that means there are 5^20 or 95,367,431,640,625 possibilities to churn through. My computer seems to be able to churn through about 100,000,000 of the possibilities per second, which unfortunately means we wouldn’t be guaranteed to get a result for about 11 days. This is longer than I want to wait. So, we’ll have to make some improvements over brute force.

The solver will follow the the same basic out line of the sudoku solver. We need to be able to enumerate all possibilities: AAAAAAAAAAAAAAAAAAAA – EEEEEEEEEEEEEEEEEEEE. In our convention, the first A will the answer to question 1, the next enumeration is B for question 1 until we pass E, which resets question 1 back to A and question 2 answer is now B. So, we get a progression of AAAA… BAAA…, CAAA… etc. The other half, is we need some code that will verify each rule to see if we have achieved the correct result. It is important that we give this section a few dry runs to make sure it is functioning correctly. The new piece that we didn’t need before is to skip whole chunks of the search range. This gets a little tricky because we don’t want to accidentally skip where the solution is.

But the basic idea is to take a question like question 16: the answer to question is 10 is (A)D, (B)C, (C)B, (D)A, (E)E. The skipper component looks at the possible solution

AAAAAAAAAAAAAAAAAAAA, because 16 is A, the answer to 10 must be D. So we might as well start searching from AAAAAAAAADAAAAAAAAAA. Note that the rule doesn’t work the other way, that is we can’t skip to AAAAAAAAAAAAAAADAAAA. Because that would pass over possibilities where the answer to question 16 is or B, or C. So, for our range skipper, later assignments can effect earlier assignments, but not vice-versa.

The other bug that we need to look out for is to make sure that we always progress. If we accidentally force the program to examine an earlier range, the program will be in an infinite loop.

With this design in mind, we can start implementing the following interface.

class Test{

public:

bool Advance(void);

void Skip(void);

bool Validate(void) const;

bool operator<(const Test& test) const;

};
Advertisements

1 Comment »

  1. Hi!, nice article. A bit too hi-fi for me, but yet interesting.
    even i have started a programming blog where i put my projects and articles.

    Comment by Abhishek Mishra — June 6, 2007 @ 7:34 am


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: