Smarter algo, was Re: 03 digression by brute force
Avi Gross
avigross at verizon.net
Sat Dec 15 12:47:15 EST 2018
I appreciate the information by " BlindAnagram <blindanagram at nowhere.com>" 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 <python-list-bounces+avigross=verizon.net at python.org> On Behalf Of BlindAnagram
Sent: Saturday, December 15, 2018 7:41 AM
To: python-list at python.org
Subject: Re: Smarter algo, was Re: 03 digression by brute force
<<<snipped>>>
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/
More information about the Python-list
mailing list