Re: Smarter algo, was Re: 03 digression by brute force

[jfong]

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

I am facing problem in saving my file.

[mallickaman2003]

Sent from Mail for Windows 10

-- 
https://mail.python.org/mailman/listinfo/python-list

RE: Smarter algo, was Re: 03 digression by brute force

[Avi Gross]

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

installing issue

[Akshay Ghugare]

 python uninstall problem.jpg


python is not working on my pc .after instaling 3.71 version appliction
showing above error .plz fix it as soon as possible..
-- 
https://mail.python.org/mailman/listinfo/python-list

No module named encodings

[Holley Jupiter]

Having an issue with this error. I have uninstalled and reinstalled several 
times but I cannot solve the problem. I googled my issue but non of the 
solutions have worked.

Sent from Mail for Windows 10

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: 03 digression by brute force

[BlindAnagram]

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

[asyncio] Suggestion for a major PEP

[Christophe Bailly]

Hello,

I copy paste the main idea from an article I have written:
contextual async


"

Imagine you have some code written for monothread. And you want to include
your code in a multithread environment.  Do you need to adapt all your code
which is what you do when you want to migrate to async code ? The answer is
no.

Functionnally these constraints are not justified neither technically

Do we have the tools to do this ? Yes because thanks to boost::context we
can switch context between tasks. When a task suspends, it just calls a
function (the event loop or reactor) to potentially switch to another task.
Just like threads switch contexts…

Async/Await logic has introduced a symetric relation wich introduces
unnecessary contraints. We should just the same logic as thread logic.

"

Read the examples in the article I have developped a prototype in C++ and
everything works perfectly.

My opinion is that sooner or later, it will have to switch to this logic
because chaining async/aswait is a huge contraints and does not make sense
in my opinion.

Maybe I am missing something,

Feel free to give me your feedback.

Regards,


Chris
-- 
https://mail.python.org/mailman/listinfo/python-list

error

[Prasanna kumar]

Sir/mam,
Fatal error in launcher: Unable to create process using   this is error which I 
am not getting clear with it . so, I request you to help me it.
-- 
https://mail.python.org/mailman/listinfo/python-list

No connection

[Vasilis Mytilinaios]

Hello,

I'm trying to open the interactive shell but it doesn't let me. It says
that IDLE's subprocess didn't make connection. I unistall and install
python again and still doesn't work.
I was using it properly until 2 days ago.
Any advice on how can I fix it?

Thank you,
Vasilis
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: No connection

[Igor Korot]

Hi,

On Sun, Dec 16, 2018 at 12:00 PM Vasilis Mytilinaios
 wrote:
>
> Hello,
>
> I'm trying to open the interactive shell but it doesn't let me. It says
> that IDLE's subprocess didn't make connection. I unistall and install
> python again and still doesn't work.
> I was using it properly until 2 days ago.
> Any advice on how can I fix it?

What is your version of python?
Did you upgrade it recently?
Was there an OS update recently applied?

Thank you.

>
> Thank you,
> Vasilis
> --
> https://mail.python.org/mailman/listinfo/python-list
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: I am facing problem in saving my file.

[Abdur-Rahmaan Janhangeer]

error message?

Abdur-Rahmaan Janhangeer
Mauritius
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: No connection

[Terry Reedy]

On 12/16/2018 9:40 AM, Vasilis Mytilinaios wrote:

Hello,

I'm trying to open the interactive shell but it doesn't let me. It says
that IDLE's subprocess didn't make connection. 


Read the doc section on possible reasons.
https://docs.python.org/3/library/idle.html#startup-failure


--
Terry Jan Reedy

--
https://mail.python.org/mailman/listinfo/python-list

Fastest first

[Avi Gross]

I have a serious question about what is already available out there in a
herpetologists dream  pythonland.

 

SHORT VERSION: a way to automatically run multiple algorithms in parallel
and kill the rest when one returns an answer.

 

I know I can write this by hand. But it looks like the kind of thing that
would come in handy.

 

MOTIVATION: I recently was discussing alternate GENERAL  ways to solve a
puzzle. Depending on the nature of the input, it seems likely that some
methods will run faster while for other scenarios another might win. It may
not be possible to determine easily which to use so I wonder why not use ALL
of them but stop when an answer arrives.

 

I know how to use all kinds of multitasking in python ranging from threads
running in the same process to multiple external processes that can
communicate with the parent or each other to processes running on different
machines over the internet. You can obviously start algorithm A then B and
as many more as you want in each case. When a (final) solution is reached,
you can send it back to the consolidator (such as a parent) and it can
presumably easily kill local threads by thread number or processes by
process ID. Remote executions might be handled by sending suicide messages
through sockets.

 

Since some algorithms may take orders of magnitude longer than others and
may not ever terminate, letting them continue might be wasteful. But even if
they all share the same CPU, the winner might be slowed down relative to
running alone but perhaps not by much. If they share the same process, the
slowdown for N running together might be I the neighborhood of taking N
times as long. It may be less or more.  If run as another independent
process on a machine which has many other processes running, it may degrade
performance by only a few percent. When running on other machines, no real
impact except the overhead of communications.

 

I am pretty sure there are already many variations out there. When google
searches what has to be a gigantic partially indexed mass of data, I think
it farms out bits of the work to multiple processes and probably processors
as no ONE of them can sift through much of that data in real time. Much of
the search may be done in computer memories. So a search may spawn a massive
attempt and results that come back are consolidated and displayed. Perhaps
after a second or two, no additional data is wanted. It will happily page
the first billion pages it found.

 

What would be nice is to load a module, give it a list of functions to call
and ask to be given an answer with a guarantee that no functions (or
processes)  are still in the running. In real life, this could be complex if
some of your functions invoked a similar method to farm out their work. You
would be killing trees.

 

An example is what happens if you ask for a translation from text written in
an unknown language (I mean Hungarian versus English versus French as an
example.) One solution is to try a list of translators in sequence and if
they return nonsense, try the next. But if you tried them in parallel and
one came back with a 98% probability that it recognized the language because
it found places with a “zs” combination and found characters like an o with
an umlaut and another o with single/double accents, and regognized a few
words like “születésnapot” you can pretty much rule out English and French.
You might have a similar approach with multiple variations on SPAM detectors
and call a halt when any one says it seems safe, or vice versa.

 

I would call this a KILL the stragglers survival of the fittest … strategy.

 

 

 

 

 

 

-- 
https://mail.python.org/mailman/listinfo/python-list