BlindAnagram at 2018/12/15 UTC+8 PM 8:41:21 wrote: > On 15/12/2018 09:56, jf...@ms4.hinet.net wrote: > > Appreciate your thoughtfully analysis on this code. Before generalize it > > with arbitrary additions, as Peter suggested:-), a recursive version is > > needed. I may give it a try on this Sunday. > > > > > > Avi Gross at 2018/12/15 UTC+8 AM8:13:37 wrote: > >> REAL SUBJECT: Analysis of alternate algorithms. > >> > >> Peter & Jach and anyone interested, > >> > >> As Peter said in his altered subject line, Jack changed directions from > >> tweaking an algorithm to trying something quite different. > >> > >> Reminder of the problem. > >> > >> Horizontal View: > >> SEND + MORE = MONEY > >> > >> Vertical View: > >> SEND > >> +MORE > >> ........... > >> MONEY > >> > >> Hard to be precise as I am sticking to plain text in my message. The three > >> words above are meant to be right adjusted. > >> > >> When solving it horizontally, Jach and I used variants of a brute force > >> approach. Substitute all possible combinations. He did it in-line and used > >> eval. I did it by making lists of items on both sides and summing the > >> int() of each component and comparing. We tried both our algorithms and > >> his was slower and he profiled that the cause was that eval() was much > >> more expensive as were his use of regular expression functions. For > >> comparison, mine used int() and string manipulation functions and sets and > >> dictionaries. > >> > >> But the real puzzle is meant to be solved in a more vertical way by humans > >> using logic. I won't do that here but note we have 4 equations going down > >> but 8 unknowns. And the equations are not unique. > >> > >> The rightmost column (I will call it the first as our arithmetic proceeds > >> from right to left) is meant to represent ONES and provides the equation: > >> > >> (D+E== Y) or (D+E == Y + 10) > >> > >> Worse, for the next column, you either get a "1" carried from the previous > >> addition or not and either pass a "1" along to the next column or not. 4 > >> Possibilities. > >> > >> (N+R==E) or (N+R+1==E) or (N+R==E+10) or (N+R+1==E+10) > >> > >> Getting a headache yet? > >> > >> For a human, they need a way to come up with additional info in terms of > >> constraints. > >> > >> There is a guiding inequality that looks like this: > >> > >> S is not the same as any of the others. Anytime you solve for another, the > >> list of possible values for S shrinks. > >> Ditto for each other variable. > >> Or, since anything plus 0 is itself, then D and E adding up to Y (with no > >> possible carry) cannot be 0. > >> > >> But getting a computer to do this might be a bit harder than blunt-force > >> searches. So let's see why Jach's new algorithm was faster. > >> > >> The code I am analyzing can be viewed in the archives and will not be > >> entered again: > >> > >> https://mail.python.org/pipermail/python-list/2018-December/738454.html > >> > >> So what did Jach try in his newer version? It is what I call a vertical > >> approach but one a computer can do easier than a human can or would. I see > >> it is a very specific algorithm that hard codes in these variables as > >> global entities that are altered by a set of nested functions. S, E, N, D, > >> M, O, R, Y. There are approaches that might be better such as passing a > >> dictionary partially filled out from one function to the next as the only > >> one that prints the solution is the final function call. > >> > >> So his is not a general solution. > >> > >> What interests me as a probable reason this is faster is the number of > >> situations it tries. The earlier versions asked itertools.permutations() > >> to provide all unique combinations of ten tokens in eight positions. So > >> there were 10 choices for the first and 9 for the second and so on adding > >> up to 10!/2! or 1,814,400 different combinations tried. That approaches 2 > >> million. > >> > >> Jack broke the problem down into evaluating the units column with a loop > >> like this: > >> > >> itertools.permutations(range(10), 3) > >> > >> That is 720 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 <python-list-bounces+avigross=verizon....@python.org> 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
