Coolest Python recipe of all time

[Raymond Hettinger]

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/

What are your favorites?


Raymond
twitter: @Raymondh

 

[David Monaghan]

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]

Really cool, but wrong. x = 3234.667, not 3236.0

Nope, I get 3236. Maybe you made a mistake somewhere.

 

[David Monaghan]

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!

DaveM

 

[Stefan Behnel]

David Monaghan, 02.05.2011 23:45:

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).

 

[Stefan Behnel]

Terry Reedy, 03.05.2011 08:00:

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).

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?

 

[Terry Reedy]

Hmmm... so if we used quaternions, could we solve systems
of linear equations in 3 variables?

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.

 

[Raymond Hettinger]

Hmmm... so if we used quaternions, could we solve systems
of linear equations in 3 variables?

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]

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.

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]

a += b   # Adds b to a in-place. Polymorphic - works on a wide variety of types.

Too surprising to qualify. For some types it modifies a, while for
others it replaces a.

 

[Raymond Hettinger]

Terry Reedy, 03.05.2011 08:00:



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.

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:
.... 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)
........ 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.

 

[geremy condra]

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:
...     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)
......     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.

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]

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