Re: 03 digression by brute force
On 14/12/2018 02:24, 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".
>
> -
> import time
> import itertools
>
> #S, E, N, D, M, O, R, Y
> n = 0
> digits = {x for x in range(10)}
>
> 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
>
> def thousand(u, Cin): # Cin + S + M == 10 * Cout + O
> global S, M, n
> rest = digits - set(u)
> for g in itertools.permutations(rest, 2):
> for Cout in range(2):
> if Cin + g[0] + g[1] == 10 * Cout + O:
> S = g[0]; M = g[1]
> tenThousand(u + g, Cout)
>
> def hundred(u, Cin): # Cin + E + O == 10 * Cout + N
> global O, n
> rest = digits - set(u)
> for g in itertools.permutations(rest, 1):
> for Cout in range(2):
> if Cin + E + g[0] == 10 * Cout + N:
> O = g[0]
> thousand(u + g, Cout)
>
> def ten(u, Cin): # Cin + N + R == 10 * Cout + E
> global N, R, n
> rest = digits - set(u)
> for g in itertools.permutations(rest, 2):
> for Cout in range(2):
> if Cin + g[0] + g[1] == 10 * Cout + E:
> N = g[0]; R = g[1]
> hundred(u + g, Cout)
>
> def unit(): # D + E == 10 * Cout + Y
> global D, E, Y, n
> n = 0
> for g in itertools.permutations(range(10), 3): # g is a tuple
> for Cout in range(2): # add two items so Cout is 0 or 1
> if g[0] + g[1] == 10 * Cout + g[2]:
> D = g[0]; E = g[1]; Y = g[2]
> ten(g, Cout)
> print(n)
>
> if __name__ == '__main__':
> start = time.time()
> unit()
> print(time.time() - start)
> -
>
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
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
Re: 03 digression by brute force
Just for fun:-) On my ooold PC, it takes 0.047 seconds to run the following
algorithm on the problem 'SNED + MORE == MONEY".
-
import time
import itertools
#S, E, N, D, M, O, R, Y
n = 0
digits = {x for x in range(10)}
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
def thousand(u, Cin): # Cin + S + M == 10 * Cout + O
global S, M, n
rest = digits - set(u)
for g in itertools.permutations(rest, 2):
for Cout in range(2):
if Cin + g[0] + g[1] == 10 * Cout + O:
S = g[0]; M = g[1]
tenThousand(u + g, Cout)
def hundred(u, Cin): # Cin + E + O == 10 * Cout + N
global O, n
rest = digits - set(u)
for g in itertools.permutations(rest, 1):
for Cout in range(2):
if Cin + E + g[0] == 10 * Cout + N:
O = g[0]
thousand(u + g, Cout)
def ten(u, Cin): # Cin + N + R == 10 * Cout + E
global N, R, n
rest = digits - set(u)
for g in itertools.permutations(rest, 2):
for Cout in range(2):
if Cin + g[0] + g[1] == 10 * Cout + E:
N = g[0]; R = g[1]
hundred(u + g, Cout)
def unit(): # D + E == 10 * Cout + Y
global D, E, Y, n
n = 0
for g in itertools.permutations(range(10), 3): # g is a tuple
for Cout in range(2): # add two items so Cout is 0 or 1
if g[0] + g[1] == 10 * Cout + g[2]:
D = g[0]; E = g[1]; Y = g[2]
ten(g, Cout)
print(n)
if __name__ == '__main__':
start = time.time()
unit()
print(time.time() - start)
-
--Jach
--
https://mail.python.org/mailman/listinfo/python-list
Re: 03 digression by brute force
"Avi Gross" writes: > SYNOPSIS: One way to solve math puzzle by brute force. (message sent earlier > disappeared) > > > > Quick note. Jack started by asking why python does not like decimal > numbers with leading zeroes. When asked to explain, he said he was > trying to solve word problems using python. Someone mentioned problems > like solving SEND + MORE = MONEY and I decided to quickly write a > function that would solve anything of that sort that only has addition > on either side of the equals. > > > > What amused me was that I had 25 solutions to the above when I was > told there would be one. Closer examination showed that 24 of those > had the ‘M’ in MONEY set to zero which the logicians claimed was not a > sensible solution. What amuses me is the solution to the problem that started the whole thread had at least one number with a leading 0. -- https://mail.python.org/mailman/listinfo/python-list
Re: 03 digression by brute force
On 2018-12-12 02:06, Avi Gross wrote: [snip] My main point though is that a leading zero can appear including in bank account numbers, social security numbers and so on. But I accept that historically python is as it is. As I mentioned, some functions like int() can deal with them. Bank account numbers, etc, are not really numbers, but are, instead, identifiers. You wouldn't do arithmetic with such a number, nor should you store one in a integer field in a database. Dropping a leading digit would be like dropping a leading letter of a name. -- https://mail.python.org/mailman/listinfo/python-list
03 digression by brute force
SYNOPSIS: One way to solve math puzzle by brute force. (message sent earlier
disappeared)
Quick note. Jack started by asking why python does not like decimal numbers
with leading zeroes. When asked to explain, he said he was trying to solve word
problems using python. Someone mentioned problems like solving SEND + MORE =
MONEY and I decided to quickly write a function that would solve anything of
that sort that only has addition on either side of the equals.
What amused me was that I had 25 solutions to the above when I was told there
would be one. Closer examination showed that 24 of those had the ‘M’ in MONEY
set to zero which the logicians claimed was not a sensible solution.
This solution is one of a list of 25 dictionaries returned, printed with
pprint.print:
{' SYNOPSIS': 'PUZZLE: SEND+MORE=MONEY with SOLUTION #1: 7429+0814=08243',
'D': '9',
'E': '4',
'M': '0',
'N': '2',
'O': '8',
'R': '1',
'S': '7',
'Y': '3'}
Note M == 0
The lone normal answer is:
{' SYNOPSIS': 'PUZZLE: SEND+MORE=MONEY with SOLUTION #25: 9567+1085=10652',
'D': '7',
'E': '5',
'M': '1',
'N': '6',
'O': '0',
'R': '8',
'S': '9',
'Y': '2'}
Apparently, unless you tell the program to skip any attempts where M is not 1,
it finds these. I will spare the rest but include the code if you wish to try
it. I called the function this (perhaps odd) way:
puzzle = "SeND+ MoRe =MoNeY???"
solution25 = math_word_puzzle_solver(puzzle)
And it returned a list of the 25 dicts.
So I tried this puzzle:
puzzle = "SeND + MoRe = oNeY"
I guessed (wrongly) that by removing the offending M in MONEY, it would find
only the other 24 solutions with the M in MORE being 0.
Not quite. That got 108 solutions! M was just about anything:
[d['M'] for d in solution108 ]
['6', '2', '5', '3', '6', '2', '5', '3', '7', '1', '6', '2', '7', '6', '2',
'1', '5', '3', '7', '1', '5', '2', '5', '2', '7', '0', '7', '0', '4', '3', '7',
'0', '8', '0', '4', '3', '8', '0', '8', '0', '6', '2', '5', '1', '6', '0', '5',
'1', '6', '0', '5', '1', '7', '0', '4', '3', '7', '0', '7', '6', '1', '0', '7',
'0', '4', '1', '5', '0', '6', '4', '2', '0', '6', '0', '6', '0', '3', '1', '5',
'0', '5', '0', '3', '2', '2', '1', '2', '1', '2', '1', '3', '0', '2', '1', '3',
'0', '3', '1', '2', '0', '2', '0', '3', '0', '3', '0', '2', '1']
My main point though is that a leading zero can appear including in bank
account numbers, social security numbers and so on. But I accept that
historically python is as it is. As I mentioned, some functions like int() can
deal with them.
I attach my code in case anyone is interested in seeing the whole output or
trying it on other puzzles. The code uses no exec() or eval() and should be
safe
CODE
# Module created to solve a specific kind of math word problem.
# FIND all solutions to a puzzle by systematically
# replacing LETTERS with NUMERALS till an equation is True
# Accepts string like "SEND + MORE = MONEY"
# Measure time elapsed, optional:
def math_word_puzzle_solver(puzzle):
"""USAGE: math_word_puzzle_solver(puzzle)"""
"""Solve a puzzle by brute force"""
"""of the form SEND + MORE = MONEY"""
"""with arbitrary sums on either side of"""
"""the equation."""
# NOTE: comments illustrate what happens to the test case only.
# Assuming the user typed in garbage, will restrict characters and
normalize.
# Remove whitespace and most other things except +/=, make uppercase, etc.
puzzle = puzzle.upper()
retain = set('ABCDEFGHIJKLMNOPQRSTUVWXYZ=+')
puzzle = ''.join(filter(retain.__contains__, puzzle))
# puzzle := 'SEND+MORE=money'
# Split into left/right on the equals sign:
left_text, right_text = puzzle.split('=')
# left_text := 'SEND+MORE'
# right_text := 'MONEY' (or 'ONEY')
# Split each side into a list on "+" and in the test case
# only the left side has more than one:
left_list = left_text.split('+')
right_list = right_text.split('+')
# At this point we have:
# left_list: ['SEND', 'MORE']
# right_list: ['MONEY']
# Combine everything in both lists to make a set with unique letters.
letter_set = { letter
for word in (left_list + right_list)
for letter in word }
# Letter_set := {'M', 'O', 'R', 'Y', 'N', 'S', 'E', 'D'}
letter_count = len(letter_set)
# letter_count := 8
# Make an iterator to deliver one combination at a time
# of the n-tuple of n digits at a time from 0-9 with no replacement
# and luckily that problem is solved by using the itertools module:
import itertools
# We want all permutations taken letter_count at a time
# so the iterator will return an 8-tuple in this example looking like:
#
