Digit Position Problem Solver

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math Topics]   [Library]   [Utilities]

 

Search

 

Search DelphiForFun.org only

Support DFF

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.

In Association with Amazon.com

 

Support DFF

 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.

 

 

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

 

Search DelphiForFun.org only

 

 

 

 

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:

bulletUn-needed words and delimiters are removed based on "UnNeededWords" section.
bulletNames 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.
bulletNumbers 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.
bulletSentences 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.
bulletNumeric 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 

bulletDownload source
bulletDownload  executable

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 18, 2009

 

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2014, Gary Darby    All rights reserved.