Coolest Python recipe of all time
Raymond Hettinger
and very cool recipes in ActiveState's python cookbook.
My vote for the coolest recipe of all time is:
http://code.activestate.com/recipes/365013-linear-equations-solver-in-3-lines/
What are your favorites?
Raymond
twitter: @raymondh
David Monaghan
wrote:
>I think it is time to give some visibility to some of the instructive
>and very cool recipes in ActiveState's python cookbook.
>
>My vote for the coolest recipe of all time is:
>
> http://code.activestate.com/recipes/365013-linear-equations-solver-in-3-lines/
Really cool, but wrong. x = 3234.667, not 3236.0
DaveM
Ian Kelly
Nope, I get 3236. Maybe you made a mistake somewhere.
David Monaghan
Oops. What a plonker .Three times I checked and got the same result each
time. Now it works fine. Sorry!
DaveM
Stefan Behnel
> On Mon, 2 May 2011 14:58:50 -0600, Ian Kelly wrote:
>
>> On Mon, May 2, 2011 at 2:48 PM, David Monaghan wrote:
>>> On Mon, 2 May 2011 10:33:31 -0700 (PDT), Raymond Hettinger wrote:
>>>
>>>> I think it is time to give some visibility to some of the instructive
>>>> and very cool recipes in ActiveState's python cookbook.
>>>>
>>>> My vote for the coolest recipe of all time is:
>>>>
>>>> http://code.activestate.com/recipes/365013-linear-equations-solver-in-3-lines/
>>>
>>> Really cool, but wrong. x = 3234.667, not 3236.0
>>
>> Nope, I get 3236. Maybe you made a mistake somewhere.
>
> Oops. What a plonker .Three times I checked and got the same result each
> time. Now it works fine. Sorry!
The bad thing about this recipe is that it requires quite a bit of
background knowledge in order to infer that the code the developer is
looking at is actually correct. At first sight, it looks like an evil hack,
and the lack of documentation doesn't help either.
Stefan
Ian Kelly
> The bad thing about this recipe is that it requires quite a bit of
> background knowledge in order to infer that the code the developer is
> looking at is actually correct. At first sight, it looks like an evil hack,
> and the lack of documentation doesn't help either.
What do you mean, "looks like"? For crying out loud, it abuses
complex numbers to represent 2-element vectors, and it passes
unvalidated input to eval(). It is *absolutely* an evil hack! Albeit
a clever one...
Terry Reedy
> The bad thing about this recipe is that it requires quite a bit of
> background knowledge in order to infer that the code the developer is
> looking at is actually correct.
The main math knowledge needed is the trivial fact that if a*x + b = 0,
then x = -b/a. The other math knowledge needed is that complex numbers
add componentwise. The trick is that replacing x with j and evaluating
therefore causes (in Python) all the coefficients of x (now j) to be
added together separately from all the constant terms to reduce the
linear equation to a*x+b (= 0 implied).
--
Terry Jan Reedy
Stefan Behnel
As your above paragraph proves, it's the kind of implementation that
requires three lines of executing code and at least 6 lines of additional
comment. Hopefully accompanied by an excuse of the developer.
Stefan
Gregory Ewing
> The trick is that replacing x with j and evaluating
> therefore causes (in Python) all the coefficients of x (now j) to be
> added together separately from all the constant terms to reduce the
> linear equation to a*x+b (= 0 implied).
Hmmm... so if we used quaternions, could we solve systems
of linear equations in 3 variables?
--
Greg
Terry Reedy
Yes and no. The use of 1*j merely collected and added together all the
multipliers of 'x' (and all the constant terms). That is a fairly
trivial matter of constant folding. Systems of linear equations are
usually presented in that form already. The actual solution to the
simple equation is in the formula x = -a/b (where a and b are the sums).
The solution formula for three variables would be far more complex.
--
Terry Jan Reedy
Raymond Hettinger
Yes :-)
The implementation of a Quanternion class and the Quartic equation is
left as an exercise for the reader ;-)
Raymond
@raymondh
Raymond Hettinger
> The bad thing about this recipe is that it requires quite a bit of
> background knowledge in order to infer that the code the developer is
> looking at is actually correct. At first sight, it looks like an evil hack,
> and the lack of documentation doesn't help either.
The recipe is cool in the same way that a magic trick is cool.
A practical recipe would use a more general purpose method (perhaps
using finite differences or continued fractions); it would have
documentation and tests; it would accept a regular python function
instead of a string; and it would avoid an unsanitized eval(). But
then it would completely lose its panache, its flourish, and the
pleasant gratification that you get when solving the riddle of how it
works.
We should have a separate thread for the most practical, best
documented, least surprising, and most boring recipe ;-)
Raymond
geremy condra
> On 5/3/2011 2:29 AM, Gregory Ewing wrote:
>>
> multipliers of 'x' (and all the constant terms). That is a fairly trivial
> matter of constant folding. Systems of linear equations are usually
> presented in that form already. The actual solution to the simple equation
> is in the formula x = -a/b (where a and b are the sums). The solution
> formula for three variables would be far more complex.
Or just use a gauss-jordan solver, which has the advantage of being
easy to explain and possible to verify by hand on small instances.
Geremy Condra
Chris Angelico
> We should have a separate thread for the most practical, best
> documented, least surprising, and most boring recipe ;-)
a += b # Adds b to a in-place. Polymorphic - works on a wide variety of types.
You didn't say it had to be complicated...
Chris Angelico
Ian Kelly
> On Wed, May 4, 2011 at 2:43 AM, Raymond Hettinger <pyt...@rcn.com> wrote:
>> documented, least surprising, and most boring recipe ;-)
>
Too surprising to qualify. For some types it modifies a, while for
others it replaces a.
Raymond Hettinger
If you found nothing educational, interesting, or amusing about the
three-line linear equation solver, then you're *really* going to hate
this one:
http://groups.google.com/group/comp.lang.python/browse_frm/thread/e46de4596e93188b/
Raymond
@raymondh
Steven D'Aprano
> I think it is time to give some visibility to some of the instructive
> and very cool recipes in ActiveState's python cookbook.
[...]
> What are your favorites?
I'm not sure if favourite is the right word, but I'm amazed by this one:
McCarthy's "amb" (ambiguous) operator.
http://code.activestate.com/recipes/577368
Here's how I might use it to solve the problem if making change. In
Australian currency, I have 5, 10, 20, 50 cent and $1 and $2 coins.
Ignoring the dollar coins, how can I make up change for any multiple of
five cents up to a dollar?
Suppose I have more 5 cent coins that I can deal with, and I want to make
sure I hand out at least three of them. Here's how to make 45 cents worth
of change:
>>> amb = Amb()
>>> a = amb(range(3, 21)) # number of 5 cent coins
>>> b = amb(range(11)) # number of 10 cent coins
>>> c = amb(range(6)) # number of 20 cent coins
>>> d = amb(range(3)) # number of 50 cent coins
>>> for _ in amb(lambda a,b,c,d: 5*a+10*b+20*c+50*d == 45):
... print a, b, c, d
...
3 1 1 0
3 3 0 0
5 0 1 0
5 2 0 0
7 1 0 0
9 0 0 0
Suppose I have some words, and want to put them together so that there
are a certain number of vowels:
>>> amb = Amb()
>>> a = amb(['quick', 'slow', 'hungry', 'wise-old'])
>>> b = amb(['fox', 'hare', 'turtle', 'kangaroo'])
>>> c = amb(['lazy', 'stupid', 'sleepy', 'confused'])
>>> d = amb(['dog', 'aardvark', 'sloth', 'wombat'])
>>>
>>> def test(a, b, c, d):
... s = "The %s brown %s jumped over the %s %s." % (a, b, c, d)
... num_vowels = sum(s.count(c) for c in 'aeiou')
... return num_vowels in (12, 18, 19)
...
>>> for _ in amb(test):
... print a, b, c, d
...
quick fox lazy sloth
quick fox lazy dog
quick kangaroo stupid aardvark
[...more solutions cut for brevity]
hungry kangaroo confused aardvark
As written, amb is just a brute-force solver using more magic than is
good for any code, but it's fun to play with.
--
Steven
geremy condra
I use a similar technique *a lot* for various kinds of constraint
solvers, but I have yet to come up with a really satisfying spelling
for it. Have you looked at the way this is done in Sage?
Geremy Condra
Ian Kelly
<steve+comp....@pearwood.info> wrote:
> As written, amb is just a brute-force solver using more magic than is
> good for any code, but it's fun to play with.
This isn't really amb; as you said it's just a brute-force solver with
some weird syntax. The whole point of amb is to enable
non-deterministic programming, such as this:
def find_values():
a = amb(1, 3, 5)
b = amb(2, 4, 8)
if a + b <= 5:
fail()
if not is_prime(a * b + 1):
fail()
c = amb(a, b, None)
if c is not None and c < 5:
fail()
return a, b, c
The amb engine would conceptually execute this function for every
possible combination of a, b, and c, pruning away the combinations
that fail at some point, and arbitrarily returning one of the
remaining combinations. So find_values() here might return (3, 4,
None) after failing at one point or another on (1, 2); (1, 4); (1, 8);
(3, 2); (3, 4, 3); and (3; 4; 4).
Note in particular that the declaration of c is not easily expressible
using the Python recipe.
This is typically implemented using continuations, and I'm not sure
whether a true amb could actually be achieved in Python without adding
continuations or flow-control macros to the language.
Ian Kelly
> This is typically implemented using continuations, and I'm not sure
> whether a true amb could actually be achieved in Python without adding
> continuations or flow-control macros to the language.
I stand corrected. After poking around a bit more I found this recipe
that is designed for unit-testing but implements amb beautifully.
http://lackingrhoticity.blogspot.com/2009/08/how-to-do-model-checking-of-python-code.html
My code from the previous post using this recipe:
def find_values(chooser):
def amb(*choices):
return chooser.choose(choices)
def require(x):
if not x:
amb()
a = amb(1, 3, 5)
b = amb(2, 4, 8)
require(a + b > 5)
require(is_prime(a * b + 1))
c = amb(a, b, None)
require(c is None or c >= 5)
return a, b, c
check(find_values)
The one downside is that the check function (again, designed for
unit-testing) does not provide any way to retrieve the returned
values, but that is easily solved by rewriting as a generator.
Cheers,
Ian
Raymond Hettinger
> As written, amb is just a brute-force solver using more magic than is
> good for any code, but it's fun to play with.
With a small change in API, much of the magic isn't needed.
from itertools import product
def amb(func, *argument_ranges):
for args in product(*argument_ranges):
if func(*args):
print(args)
amb(lambda a,b,c,d: 5*a+10*b+20*c+50*d == 45,
range(3, 21), # number of 5 cent coins
range(11), # number of 10 cent coins
range(6), # number of 20 cent coins
range(3), # number of 50 cent coins
)
def test(a, b, c, d):
s = "The %s brown %s jumped over the %s %s." % (a, b, c, d)
num_vowels = sum(s.count(c) for c in 'aeiou')
return num_vowels in (12, 18, 19)
amb(test,
['quick', 'slow', 'hungry', 'wise-old'],
['fox', 'hare', 'turtle', 'kangaroo'],
['lazy', 'stupid', 'sleepy', 'confused'],
['dog', 'aardvark', 'sloth', 'wombat'],
)
amb(lambda x, y, z: x*x + y*y == z*z,
range(1, 11),
range(1, 11),
range(1, 11),
)
Raymond
------------
follow my recipes and tips on twitter: @raymondh
Steven D'Aprano
> On Fri, May 6, 2011 at 10:59 AM, Steven D'Aprano
> <steve+comp....@pearwood.info> wrote:
>> As written, amb is just a brute-force solver using more magic than is
>> good for any code, but it's fun to play with.
>
> This isn't really amb; as you said it's just a brute-force solver with
> some weird syntax. The whole point of amb is to enable
> non-deterministic programming, such as this:
[...]
> The amb engine would conceptually execute this function for every
> possible combination of a, b, and c,
Which pretty much is the definition of "brute-force solver", no?
--
Steven
Ian Kelly
<steve+comp....@pearwood.info> wrote:
>> This isn't really amb; as you said it's just a brute-force solver with
>> some weird syntax. The whole point of amb is to enable
>> non-deterministic programming, such as this:
> [...]
>> The amb engine would conceptually execute this function for every
>> possible combination of a, b, and c,
>
> Which pretty much is the definition of "brute-force solver", no?
The "execute the function for every possible combination" part, yes.
The "non-deterministic programming" part, no.
Raymond Hettinger
FWIW, here's one of my favorite brute-force solvers:
http://code.activestate.com/recipes/576615-alphametics-solver/
Raymond
Trent Nelson
I think I've posted this before, but I love my 3-lines-if-you-ignore-the-scaffolding language translator. Not because it's clever code -- quite the opposite, the code is dead simple -- but because it encompasses one of the things I love about Python the most: it gets shit done.
In [1]: from translate import *
In [2]: translate('French', 'The quick brown fox jumped over the lazy dog.')
Le renard brun rapide a sauté par-dessus le chien paresseux.
In [3]: translate('German', 'The quick brown fox jumped over the lazy dog.')
Der schnelle braune Fuchs sprang über den faulen Hund.
In [4]: translate('Spanish', 'The quick brown fox jumped over the lazy dog.')
El zorro marrón rápido saltó sobre el perro perezoso.
translate.py:
import sys
from urllib import urlopen, urlencode
from BeautifulSoup import BeautifulSoup
url = 'http://babelfish.altavista.com/tr'
languages = {
'French' : 'en_fr',
'German' : 'en_de',
'Italian' : 'en_it',
'Spanish' : 'en_es',
'Russian' : 'en_ru',
'Portuguese': 'en_pt',
'Dutch' : 'en_nl',
'Japanese' : 'en_ja',
}
def translate(lang, text):
kwds = { 'trtext' : text, 'lp' : languages[lang]}
soup = BeautifulSoup(urlopen(url, urlencode(kwds)))
print soup.find('div', style='padding:10px;').string
if __name__ == '__main__':
translate(sys.argv[1], sys.argv[2])
Raymond Hettinger
That completely rocks! Thanks for the recipe.
Raymond
----------