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

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:

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

  [Feedback]   [Newsletters (subscribe/view)] [About me]

Copyright © 2000-2013, Gary Darby    All rights reserved.