Search
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.
Mensa®
Daily Puzzlers
For over 15 years
Mensa Page-A-Day calendars have provided several puzzles a year
for my programming pleasure. Coding "solvers" is most fun,
but many programs also allow user solving, convenient for "fill
in the blanks" type. Below are Amazon links to the
two most recent years.
Mensa®
365 Puzzlers Calendar 2017
Mensa®
365 Puzzlers Calendar 2018
(Hint: If you can
wait, current year calendars are usually on sale in January.)
Contact
Feedback:
Send an
e-mail with your comments about this program (or anything else).
|
| |
Problem Description
The teacher on a Halloween
field trip with her small class, asked the students to guess the number of
pumpkins in a pile. Monica guessed 26, Nicole guessed 24, Oleg guessed 25,
Paige guessed 22, and Quentin guessed 22. Two were off by 3, two were off by
1, and one guessed the exact number. How many pumpkins were in the pile?
Background & Techniques
The above is an example of a class of puzzle which appears quite often in
my Mensa Puzzle-A-Day calendar.
Solutions to these puzzles may be easier to find manually that it was to
write the program to find them automatically. It took several starts
before I came up with the algorithm (algorithm = technique or method) to solve them.
Aristotle said "Well begun is half done" and in programming, the data
structure chosen to represent the real world conditions defines that beginning. The
one I ended up with represents the puzzle in a grid with guesses as columns
and errors as rows. The cell at the intersection of each guess and
error contains the answers which could reflect that combination. So
for example if one of the guesses was 26 and one of the errors conditions
was "off by 3", then that intersection would contain the values 23 and 29.
When the grid is filled in, one of the numbers in the
first column must be the correct answer and that same value must appear in a
unique row in each of the other columns. Here is the grid for
the above problem from which we can find by inspection that 25 is a
correct answer.
Errors↓ |
Guesses |
|
26 |
24 |
25 |
22 |
22 |
±3 |
(23,29) |
(21,27) |
(22,28) |
(19,25) |
(19,25) |
±3 |
(23,29) |
(21,27) |
(22,28) |
(19,25) |
(19,25) |
±1 |
(25,27) |
(23,25) |
(24,26) |
(21,23) |
(21,23) |
±1 |
(25,27) |
(23,25) |
(24,26) |
(21,23) |
(21,23) |
0 |
(26) |
(24) |
(25) |
(22) |
(22) |
The program follows this procedure, although it takes more
code than one would think to do something that is quite simple for a human.
For example when checking column 5 for the guess value 25, we need to make sure
not to check row 1 (even though it contains a 25 in column 5) since we have already used that row.
Humans can do this without setting up a nested loop to check all of the
columns ahead of the current column. (Or maybe we do without being
aware of it. Anyway, it seemed like being a human was a big advantage
when solving the first puzzle of this type. For all future puzzles
however, the computer has a definite advantage!)
In addition to a "Solve" button, there is a "Change" button that lets
the user change or define new problems, to load any of several sample
problems that are to included, and to save any changes made to a file.
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
To implement the above method, I defined a
TErrType record type to keep the error value and the direction,
too high (+), too low (-) or "off by" (±). An array of
these records represents the error values for the rows in the grid. A
TGuessRec defines the possible actual values for each guess and error
value combination (as integers Upval and Downval).
A two dimensional array of these records is the internal representation of
the data displayed in the TStringGrid that the user sees (and the
grid displayed above).
All the good stuff happens in the SolutionBtnClick procedure. It
runs through all the unique possible actual values for the first guess ( the
first column). For each, it calls a local function, Goodval,
which checks whether the potential actual value is a solution. and returns
Boolean value "True" if it is, "False" otherwise
The value is a solution if, for each column after the first, the value
appears in some unused row as an Upval or Downval for
this column. Failing to find a value for nay column causes the
function to return "false". When Goodval returns true, local procedure
ShowSolution displays the result.
The other button on the main program form , Change, moves the puzzle data to three
TMemos in Editform named GuessData, ErrorData, and
StoryData and calls
ShowModal to display the form. The user may replace any or
all of this data. When he clicks the OK button, the data is
validated before returning to the main form with a return code of MROK.
If an error is found, a message is displayed and the return code is set to
MRNone which prevents the exit. Save and Load buttons use the
CommaText property of Tmemo.Lines stringlists to save and restore the data,
preserving line structure.
Running/Exploring the Program
Suggestions for Further Explorations
There are probably smarter ways to solve the
puzzle (for example, if we are told that one of the guesses is correct, the
number of possible correct values to check could be reduced to the given
guess values.) Or perhaps pass the guesses against the errors instead
of the current method which passes errors against the guesses.
A game generator make a good project add-on.
I suspect that puzzles more difficult than the current sample set could be
developed. I would make a file of proper names for the guessers
and a file of container/object pairs to randomly select from.
Then the program could specify the number of guessers, their accuracy (10%,
20%, etc. maximum error), and the correct answer. We could then
generate the guesses, the errors, and even the story text with the
help of Delphi's random number generator.
Original Date: May 19,2007 |
Modified:
May 11, 2018 |
|
|