Max runnning time is 10! Given any set letters could only be assigned
values of {0,1,...9}.
thanks
Arun prasath NOn Nov 2, 9:43 pm, "Lego Haryanto" <[EMAIL PROTECTED]> wrote: > A "quicker" brute force (not the one with 10! complexity) is by doing a > recursion starting from the rightmost digit. > > The number of levels in the recursion is the same as the longest digits (in > the sample case: 5, which is length of MONEY). After we processed 5 levels, > we know we got a solution. > > The idea follows: > In the first level, we are faced with D + E = Y (or possibly: D + E = 1Y). > Brute force the D and E (since we have no idea what they are ...), and for > each possible combination of D and E, we automatically knows Y. Make sure > that this Y is never assigned a value, OR if it is assigned, it should match > the result of D+E. Also make sure that whatever Y is, the digit is never > used by another letter. Up to this point, we'd know whether or not there's > a "carry". > > When the D+E=Y is valid, then we should recurse deeper to the second level > N+R=E (propagating the carry information). This one here, we also look for > combination of N and R, ... but, whichever combination it is, it should > match the E (since we already have the tentative answer for E in the > previous level). > > The same process goes on until we processed 5 levels (for this example) at > which we know we have a valid solution. > > You need to take care of little details such as whether leading zeroes is > allowed. Also, when the operands have lesser digits, it should be clear > that we can just assume we can pad the left digit with constant 0. > > Best, > -Lego > > On 11/2/06, Rave Hanker <[EMAIL PROTECTED]> wrote: > > > > > > > > > Hello, > > I was asked this in my ICPC qualifiers. Are there any good algorithms to > > solve Cryptarithmetic > > problemshttp://en.wikipedia.org/wiki/Send%2Bmore%3Dmoney > > like > > SEND > > +MORE > > ------------ > > MONEY > > > where each character should be assigned a unique digit. > > > One more constraint i got was to sort the answer by the value of the first > > operand > > > -- > > Well," said Owl, "the customary procedure in such cases is as follows." > > "What does Crustimoney Proseedcake mean?" said Pooh. "For I am a Bear of > > Very Little Brain, and long words Bother me." > > "It means the Thing to Do." > > "As long as it means that, I don't mind," said Pooh humbly.-- > Fear of the LORD is the beginning of knowledge (Proverbs 1:7)- Hide quoted > text -- Show quoted text - --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
