RE: Smarter algo, was Re: 03 digression by brute force
I appreciate the information by " BlindAnagram "
below. I myself claim to be from erehwon at times.
But to be clear, there are issues raised here where someone wants an easy
solution for the real world like "I have to build a webserver that searches a
database" and they would prefer an answer telling them of a set of modules they
can import that can do 90% of the work once you fill in some things on your own.
I am not clear on why Jach is working on this. Personally, I just like solving
puzzles and consider it fun (in moderation) to think about the ideas behind a
solution, alternates, ways to improve, and so on.
So I wanted to balance the wasteful brute force aspects of a solution with
ways to cut down the expense per iteration. In particular, I chose not to use
the regular expression routines or eval. The first reference you supplied is a
nice solution but does use those. It needs minor changes as it is written in an
enhanced python 2.6 and I choose not to look back
And best, it offers an oodle of similar puzzles. The weirdest perhaps was this:
('AN + ACCELERATING + INFERENTIAL + ENGINEERING + TALE + ' +
'ELITE + GRANT + FEE + ET + CETERA == ARTIFICIAL + INTELLIGENCE')
I mention that for a reason. In a private exchange with Jach, I noted that a
generalization of his method would need to allow for more possible carries than
just 0 and 1 that rise with the number of items being added. In the above,
there are 10 numbers being added on the left and two on the right. Granted the
rules do not allow all the letters to be 9. So the maximum addition is not
usually 90 + carry. But it can be in the 40's or even higher depending on the
specific digits involved. In the worst case, you might have 10 copies in a
column of the same letter whose value might be 9. So the algorithm would need
to plan on a larger set of carry choices just in case. At some point, it might
be less efficient than the horizontal solutions such as the ones Jach and I
made first or the one you shared below.
-Original Message-
From: Python-list On
Behalf Of BlindAnagram
Sent: Saturday, December 15, 2018 7:41 AM
To: python-list@python.org
Subject: Re: Smarter algo, was Re: 03 digression by brute force
<<>>
There are quite a few Python based solvers for alphametics around on the net,
for example:
http://code.activestate.com/recipes/576615-alphametics-solver/
There is also a long discussion here on ways of doing this:
https://enigmaticcode.wordpress.com/2016/06/22/solving-alphametics-with-python/
--
https://mail.python.org/mailman/listinfo/python-list
Re: Smarter algo, was Re: 03 digression by brute force
20 possibilities. He then doubled that to 1,440 to consider a
> >> carry. Only if the selected values for the three variables in contention
> >> (plus a carry) does he go on to call to evaluate the tens column.
> >>
> >> It then shrinks a bit more as he no longer gets the permutations of all 10
> >> digits. He subtracts the three values that might work for the units, so he
> >> is asking for permutations of 7 digits, two at a time. That is 42, doubled
> >> again to 84 for carry purposes. And this function is not called 1,440
> >> times, but quite a bit fewer.
> >>
> >> So, similarly, of those 84 loops for tens, he only sometimes calls to
> >> evaluate hundreds. As mentioned, the set of 10 digits shrinks some more
> >> and this continues upward to functions that evaluate hundreds and
> >> thousands and finally the one evaluating ten thousands pretty much prints
> >> out an answer it finds.
> >>
> >> So overall iterations can be shown to drop. We could add code to measure
> >> how many times each function is called and come up with an exact value for
> >> this built-in problem. I did and the functions were called this many times:
> >>
> >>>>> counting
> >> {'unit': 1, 'ten': 72, 'hundred': 290, 'thou': 183, '10thou': 196}
> >>>>> sum(counting.values())
> >> 742
> >>
> >> But I also see the permutation function was called 542 times. Most of
> >> those runs though were fairly trivial as the combined number of items
> >> issued back were only 7,390 as compared to nearly two million in the
> >> earlier version. Overall, this is much faster.
> >>
> >> Range() is probably a highly efficient built-in written in C, but it can
> >> totally be eliminated in this code as it is a constant. You can write
> >> {1,2,2,3,4,5,6,7,8,9} or [0,1] instead of calculating ranges.
> >>
> >> Naturally, this code does not scale up to finding the two solutions for:
> >>
> >> HAWAII + IDAHO +IOWA + OHIO = STATES
> >>
> >> The horizontal versions solved that easily.
> >>
> >> The carry issues get more complex here even if a general solution is
> >> written. One approach might be to make a matrix as wide as the widest term
> >> and place all entries in it as characters, right justified. You can then
> >> work on any number of columns by extracting columns backwards from the
> >> right and applying whatever logic, perhaps recursively. The possible carry
> >> amounts need to be estimated as no more than about the number of items
> >> being added minus one.
> >>
> >> But, I am ready to do other things so I leave it as an exercise for the
> >> reader
> >>
> >> -Original Message-
> >> From: Python-list On
> >> Behalf Of Peter Otten
> >> Sent: Friday, December 14, 2018 3:21 AM
> >> To: python-list@python.org
> >> Subject: Smarter algo, was Re: 03 digression by brute force
> >>
> >> jf...@ms4.hinet.net wrote:
> >>
> >>> Just for fun:-) On my ooold PC, it takes 0.047 seconds to run the
> >>> following algorithm on the problem 'SNED + MORE == MONEY".
> >>
> >>> def tenThousand(u, Cin): # Cin == M
> >>> global n
> >>> if Cin == M:
> >>> print(S, E, N, D, '+', M, O, R, E, '==', M, O, N, E, Y)
> >>> n += 1
> >>
> >> And it probably took under two minutes with the brute force approach.
> >> So if you were only interested in the result the code below were efficient
> >> only if it took at most two more minutes to write it;)
> >>
> >> But seriously, the next step is to generalize this to work with arbitrary
> >> additions...
> >> More fun!
>
> There are quite a few Python based solvers for alphametics around on the
> net, for example:
>
> http://code.activestate.com/recipes/576615-alphametics-solver/
>
> There is also a long discussion here on ways of doing this:
>
> https://enigmaticcode.wordpress.com/2016/06/22/solving-alphametics-with-python/
I was shocked when I saw this link! Must take my hat off to its author:-)
--
https://mail.python.org/mailman/listinfo/python-list
Re: Smarter algo, was Re: 03 digression by brute force
lled 1,440 times,
>> but quite a bit fewer.
>>
>> So, similarly, of those 84 loops for tens, he only sometimes calls to
>> evaluate hundreds. As mentioned, the set of 10 digits shrinks some more and
>> this continues upward to functions that evaluate hundreds and thousands and
>> finally the one evaluating ten thousands pretty much prints out an answer it
>> finds.
>>
>> So overall iterations can be shown to drop. We could add code to measure how
>> many times each function is called and come up with an exact value for this
>> built-in problem. I did and the functions were called this many times:
>>
>>>>> counting
>> {'unit': 1, 'ten': 72, 'hundred': 290, 'thou': 183, '10thou': 196}
>>>>> sum(counting.values())
>> 742
>>
>> But I also see the permutation function was called 542 times. Most of those
>> runs though were fairly trivial as the combined number of items issued back
>> were only 7,390 as compared to nearly two million in the earlier version.
>> Overall, this is much faster.
>>
>> Range() is probably a highly efficient built-in written in C, but it can
>> totally be eliminated in this code as it is a constant. You can write
>> {1,2,2,3,4,5,6,7,8,9} or [0,1] instead of calculating ranges.
>>
>> Naturally, this code does not scale up to finding the two solutions for:
>>
>> HAWAII + IDAHO +IOWA + OHIO = STATES
>>
>> The horizontal versions solved that easily.
>>
>> The carry issues get more complex here even if a general solution is
>> written. One approach might be to make a matrix as wide as the widest term
>> and place all entries in it as characters, right justified. You can then
>> work on any number of columns by extracting columns backwards from the right
>> and applying whatever logic, perhaps recursively. The possible carry amounts
>> need to be estimated as no more than about the number of items being added
>> minus one.
>>
>> But, I am ready to do other things so I leave it as an exercise for the
>> reader
>>
>> -Original Message-
>> From: Python-list On
>> Behalf Of Peter Otten
>> Sent: Friday, December 14, 2018 3:21 AM
>> To: python-list@python.org
>> Subject: Smarter algo, was Re: 03 digression by brute force
>>
>> jf...@ms4.hinet.net wrote:
>>
>>> Just for fun:-) On my ooold PC, it takes 0.047 seconds to run the
>>> following algorithm on the problem 'SNED + MORE == MONEY".
>>
>>> def tenThousand(u, Cin): # Cin == M
>>> global n
>>> if Cin == M:
>>> print(S, E, N, D, '+', M, O, R, E, '==', M, O, N, E, Y)
>>> n += 1
>>
>> And it probably took under two minutes with the brute force approach.
>> So if you were only interested in the result the code below were efficient
>> only if it took at most two more minutes to write it;)
>>
>> But seriously, the next step is to generalize this to work with arbitrary
>> additions...
>> More fun!
There are quite a few Python based solvers for alphametics around on the
net, for example:
http://code.activestate.com/recipes/576615-alphametics-solver/
There is also a long discussion here on ways of doing this:
https://enigmaticcode.wordpress.com/2016/06/22/solving-alphametics-with-python/
--
https://mail.python.org/mailman/listinfo/python-list
Re: Smarter algo, was Re: 03 digression by brute force
shown to drop. We could add code to measure how
> many times each function is called and come up with an exact value for this
> built-in problem. I did and the functions were called this many times:
>
> >>> counting
> {'unit': 1, 'ten': 72, 'hundred': 290, 'thou': 183, '10thou': 196}
> >>> sum(counting.values())
> 742
>
> But I also see the permutation function was called 542 times. Most of those
> runs though were fairly trivial as the combined number of items issued back
> were only 7,390 as compared to nearly two million in the earlier version.
> Overall, this is much faster.
>
> Range() is probably a highly efficient built-in written in C, but it can
> totally be eliminated in this code as it is a constant. You can write
> {1,2,2,3,4,5,6,7,8,9} or [0,1] instead of calculating ranges.
>
> Naturally, this code does not scale up to finding the two solutions for:
>
> HAWAII + IDAHO +IOWA + OHIO = STATES
>
> The horizontal versions solved that easily.
>
> The carry issues get more complex here even if a general solution is written.
> One approach might be to make a matrix as wide as the widest term and place
> all entries in it as characters, right justified. You can then work on any
> number of columns by extracting columns backwards from the right and applying
> whatever logic, perhaps recursively. The possible carry amounts need to be
> estimated as no more than about the number of items being added minus one.
>
> But, I am ready to do other things so I leave it as an exercise for the
> reader
>
> -Original Message-
> From: Python-list On
> Behalf Of Peter Otten
> Sent: Friday, December 14, 2018 3:21 AM
> To: python-list@python.org
> Subject: Smarter algo, was Re: 03 digression by brute force
>
> jf...@ms4.hinet.net wrote:
>
> > Just for fun:-) On my ooold PC, it takes 0.047 seconds to run the
> > following algorithm on the problem 'SNED + MORE == MONEY".
>
> > def tenThousand(u, Cin): # Cin == M
> > global n
> > if Cin == M:
> > print(S, E, N, D, '+', M, O, R, E, '==', M, O, N, E, Y)
> > n += 1
>
> And it probably took under two minutes with the brute force approach.
> So if you were only interested in the result the code below were efficient
> only if it took at most two more minutes to write it;)
>
> But seriously, the next step is to generalize this to work with arbitrary
> additions...
> More fun!
>
>
> --
> https://mail.python.org/mailman/listinfo/python-list
--
https://mail.python.org/mailman/listinfo/python-list
RE: Smarter algo, was Re: 03 digression by brute force
,9} or [0,1] instead of calculating ranges. Naturally, this code does not scale up to finding the two solutions for: HAWAII + IDAHO +IOWA + OHIO = STATES The horizontal versions solved that easily. The carry issues get more complex here even if a general solution is written. One approach might be to make a matrix as wide as the widest term and place all entries in it as characters, right justified. You can then work on any number of columns by extracting columns backwards from the right and applying whatever logic, perhaps recursively. The possible carry amounts need to be estimated as no more than about the number of items being added minus one. But, I am ready to do other things so I leave it as an exercise for the reader -Original Message- From: Python-list On Behalf Of Peter Otten Sent: Friday, December 14, 2018 3:21 AM To: python-list@python.org Subject: Smarter algo, was Re: 03 digression by brute force jf...@ms4.hinet.net wrote: > Just for fun:-) On my ooold PC, it takes 0.047 seconds to run the > following algorithm on the problem 'SNED + MORE == MONEY". > def tenThousand(u, Cin): # Cin == M > global n > if Cin == M: > print(S, E, N, D, '+', M, O, R, E, '==', M, O, N, E, Y) > n += 1 And it probably took under two minutes with the brute force approach. So if you were only interested in the result the code below were efficient only if it took at most two more minutes to write it;) But seriously, the next step is to generalize this to work with arbitrary additions... More fun! -- https://mail.python.org/mailman/listinfo/python-list -- https://mail.python.org/mailman/listinfo/python-list
Smarter algo, was Re: 03 digression by brute force
jf...@ms4.hinet.net wrote: > Just for fun:-) On my ooold PC, it takes 0.047 seconds to run the > following algorithm on the problem 'SNED + MORE == MONEY". > def tenThousand(u, Cin): # Cin == M > global n > if Cin == M: > print(S, E, N, D, '+', M, O, R, E, '==', M, O, N, E, Y) > n += 1 And it probably took under two minutes with the brute force approach. So if you were only interested in the result the code below were efficient only if it took at most two more minutes to write it;) But seriously, the next step is to generalize this to work with arbitrary additions... More fun! -- https://mail.python.org/mailman/listinfo/python-list
