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
Search for all "self-describing" integers; integers
of a specified length, N, with the property that, when digit positions are
labeled 0 to N-1, the digit in each position is equal to the number of times
that digit occurs in the number.
Background & Techniques
There are a number of ways to define "self-describing" numbers or
sequences. This program searches for those meeting the above
conditions. For example 1210 is a four digit self describing
number because position "0" has value 1 and there is one 0 in the number;
position "1" has value 2 because there are two 1' s in the number, position "2"
has value 1 and there is one 2, and position "3" has value 0 and there are
zero 3's.
Searching for the maximum length, 10 digits, may take several hours, but you
should be able to recognize a pattern in the shorter results and "guess" the
10 digit answer! (Hint: Start by guessing the number of zeros and filling in
the rest of the digits from there.)
I wrote the original version of a program to solve this program several
years ago, but when a young student asked me about it the other day, I
couldn't find the program so I coded it again. yesterday When I saw
the results, I recalled why I had not posted the original version. The
coding was interesting, but the results are kind of boring. There are
only 7 of them and a pattern is clear in the last few. It would be
interesting to answer a couple of other questions though (see Further
Explorations section below.)
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 Programmer's
There are about 70 lines of user written code here so we'll call it
Intermediate level, but most of those lines perform "housekeeping".
The 25 lines that consume most of the search time work like this:
 | Initialize with the starting number then loop until the number
exceeds the maximum value for the length specified:
 | Convert number to a string so that we can check
individual digits |
| Zero out a array of 10 integers to hold counts of the 10
possible digit values, 0 through 9. |
| Examine the string and count the digit occurrences using
the digits as an index into the counts array. |
| Compare the counts left to right with the to the
digit values left to right. If they all match, then we have a
solution to display. |
| Increment the number to be tested. |
|
There are probably many rules that could be applied to reduce the "search
space" and let the program find solutions faster. So far, the program
uses these two:
| Solutions cannot have leading zeros. A zero in the 1st
position would imply that there is at least one zero in the number so
the leftmost digit must be 1 or greater. This means that we can
start the N digit search with 10N-1 (e.g. 4 digit search can
start at 1000). |
| The effective base of an N digit solution is N. That is, it
cannot contain any digit values larger than N-1. (The 4 digits of a 4
digit solution represent counts of values 0, 1, 2, and 3, so no
need to count and check any integer containing a digit greater than 3). |
Running/Exploring the Program
Suggestions for Further Explorations
 |
Out of 10
billion possibilities, why are there only 7 numbers that meet the
definition? Or did I miss some? |
|
|
Are there
additional rules that could shortcut the "brute force" approach so
that fewer numbers would require checking? |
|
|
The inner loop
of the program could no doubt be speeded up, but I was too lazy to
add the timing stuff right now. |
|
Original Date: August 19, 2007 |
Modified:
May 15, 2018 |
|
|
