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
Write a program which will resolve problem text and present the
solution for this problem (and other similar "digit position" problems):
Find a six-digit number in which the first digit is two
less than the fifth, the second digit is one more than the fourth, and the fifth
digit is four less than the last. The sum of the first and fourth digits equals
the second, the sum of the third and last digits equals the second, and the sum
of all the digits is 30."
Background & Techniques
This is another experiment in writing a program to convert a certain type of
story problem to algebraic equations. A previous "Age
Problem Solver" program solves
problems describing the relationship between the ages of two people. The current
project applies similar techniques to solving "digit relationship" problems like
the one above from my current "Mensa Puzzle-A-Day" calendar:
The syntax analysis is not very generalized but it is adequate to handle most of
the "digit position" problems in this year's calendar which were entered verbatim as
"Problem00.txt" through "Problem11.txt and included in the download file.
The problems are converted in several stages and using an initialization file, "DigitProblemTables.ini",containing
several word conversion sections. Briefly:
 | Un-needed words and delimiters are removed based on "UnNeededWords"
section. |
| Names for the digits are identified. Common initial capitalized words to
ignore are in "FirstWord" section. Digit position words ("first", "second",
etc. which are not normally capitalized, but should be treated as variable
names, are treated as such based on the "Capitalized" section. |
| Numbers are converted to a standard text form using the "Numbers"
section; "one" to "1", "twice" to "2*", etc. Similarly fraction denominator
words ("half", "third", "thirds", etc.) are identified based on the
"Denominators" section. |
| Sentences are converted to a "canonical" form replacing names with "&V",
whole numbers and fraction numerators with "&N", denominators with "&D".
Patterns in the "OpWords" section are tested against the canonical form and
matches are replaced with a corresponding text in equation form. |
| Numeric and name identifiers and then replaced with the original values
and the results displayed. |
There are some syntax/vocabulary problems which are solved by hard coding
rather than via table entries.
The word "last", for example must be treating differently depending on the
context. I.E. in the phrase "equals the first plus the last",
"last"
can be replaced by the position name of the rightmost digit (fifth or sixth).
But in the phrase "the sum of the last 3 digits" considerably more code is
required. Currently, parsing "sum", "same" and "product" are also hard
coded.
Unresolved parsing problems
There are some unresolved parsing problems. One is in identifying the
beginning and ending of phrases which define equations. The program currently
uses comma or decimal point (, or
.) as reliable separators, but humans frequently
omit the comma. So a phrase like "The first is the sum of the second and the
third and the fourth equals the fifth" will not be correctly parsed unless the
second "and" is preceded by a comma. We probably need code to look for
multiple equivalence indicator words (is, are, equals) in what is initially
identified as a sentence, and then try to identify where it should be split. Another problem is that, at least in English, we use position words like
"third" and "fourth" to indicate both position and as denominators in fractions.
So a phrase like "The fourth digit is one fourth of the fifth" is much harder
for a computer to understand than it is for a human.
For the restricted text forms represented by the included sample files, the
program works quite well. The resulting equations in N unknowns for N digit
numbers can solved algebraically. The program uses a trial and error
approach to find solutions.
Programmer's Notes:
From a programming point of view, there is nothing particularly clever or
innovative about the code. I had originally implemented our
Gaussian
Elimination class to
solve N equations in N unknowns, but it turns out that problems about N digit
numbers may have more or fewer than N equations. As a result,
I reverted to the same "Brute Force", exhaustive search procedure used in the
Age Problems program. It uses our
TEval
class which takes an expression and an array of variable names & values as
input, and returns the value of the expression when those variable values are
plugged into the expression. By assigning the N position variables
to all feasible integers (10,000 to 99,999 for 5 digit numbers, 100,000 to
999,999 for 6 digit numbers), we can find one or all solutions to the set
of equations by evaluating the left and right sides and comparing the results
for equality.
Running/Exploring the Program
Suggestions for Further Explorations
 |
Improved parsing to identify equation phrases
and the conflict between position words which may also be denominators in
fractions as described above. |
|
.I' convinced that
humans convert "words" to information using "local context analysis".
Perhaps our brains normally use "subroutines" to recognize and
understand words that we read or hear because they have been learned and
remembered (i.e. pre-programmed ), but we also have the ability to
probe deeper when necessary. How humans convert inputs to usable
information is an area worthy of attention by curious minds. J |
| |
|
| Original: July 16, 2008 |
Modified:
May 15, 2018
|
|
