in reply to Re: Re: Words that equal numbers
in thread Words that equal numbers

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

Replies are listed 'Best First'.
Re: Re: Re: Re: Words that equal numbers
by tall_man (Parson) on Jan 19, 2003 at 01:29 UTC
    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]

      tall man ++
      You are totally right.

      CountZero

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

[reply]

In Section Seekers of Perl Wisdom