in reply to Words that equal numbers

In essence what one wants to do is to allocate the numbers 0 - 9 over 10 or less letters. To make it easier we will allocate the figures 0 to 9 over exactly 10 letters (we will make up the missing letters and drop them when appropriate).

Of course we may allocate each letter only once, but I think that using a clever algorithm to make sure that each letter is not used more than once will take more time than using real brute force and dropping "wrong" solutions afterwards.

So I would set up a for loop starting with '0123456789' till '9876543210' with a step of 1 and directly allocating the first digit to the (alphabetically) first letter used in your equation and so on. (Perhaps it is easier to start with the last digit in order not to involuntarily shift the whole pattern if it starts with a zero)

Then checking if the equation holds and if it holds checking if no digit has been used more than once.

Thus you delay at lot of "expensive" tests and logic until they are really necessary.

If you optimise the allocation of the digits to the letters and you hard code the testing of the equation, it should be possible.

CountZero

"If you have four groups working on a compiler, you'll get a 4-pass compiler." - Conway's Law

Replies are listed 'Best First'.
Re: Re: Words that equal numbers
by tall_man (Parson) on Jan 18, 2003 at 14:35 UTC
    I really wouldn't do it that way, because now you are dealing in billions of combinations (9,753,086,421 to be exact) which is worse than the 10! count for every possible permutation with no repeated digits.

    Suppose the program could check a combination every .001 seconds. Then for an unsolvable problem where it had to try all 9.7 billion combinations, it would take about 112 days.

    If you have to use brute-force rather than an AI-style search, at least use a permutation generator like Algorithm::Permute. If you don't need all 10 digits in the problem, then Algorithm::ChooseSubsets would also help.

[reply]

      Well to make my solution a little less "brute" and a bit more smart, only check the combinations where the sum of all digits is equal to 45, which is the sum of the digits one to nine.

      This should save some time.

      I really wonder if using a permutation engine would be that much faster as it takes time to generate the 10! combinations as well.

      In any case my proposed solution woudl work equally well (and probably even better) with the generated list of allowable permutations.

      I have a feeling that hardcoding the problem into a PERL script with all constraints will take much longer. At least my solution is more general.

      CountZero

      "If you have four groups working on a compiler, you'll get a 4-pass compiler." - Conway's Law

[reply]
        There's a large enough difference between 9.7 billion and 3,628,800 that there's no contest, even if the permutation engine was slow. And there are optimized ones around, like Algorithm::FastPermute.

        But check out the hawtin solution below, which generates a combination one letter at a time, eliminating large batches of cases with early constraint testing. And all the constraint checks are simple concatenations and arithmetic.

        It's not a completely general solution as it stands, but it could be the basis for one, by using generated code.

        Update: It could also be generalized fairly easily by a looping program that pushed the current state onto a stack, or by a recursive program.

        Update 2: I just noticed that your idea to test only combinations that sum to 45 means you could count by 9's. Only multiples of 9 have a digital sum that is a multiple of 9. That cuts your number from 9 billion to about 1 billion... still too many to be worth doing it that way, IMHO.

[reply]

In Section Seekers of Perl Wisdom