[triangle-zpug] Python challenge

Chris Calloway cbc at unc.edu
Wed Jun 1 17:28:03 CEST 2005


Geoff Davis wrote:
> http://plope.com/Members/chrism/python_challenge
> Python Challenge

This was on slashdot on May 21. I almost posted it here. But as noted on
slashdot, nothing about the Python Challenge is python specific. It is
just a collection of general riddles which might have some application
to programming. Someone was even solving the riddles with shell code.

http://developers.slashdot.org/article.pl?sid=05/05/21/1826239

Could make a good project to add to the pile: a collection of
instructional python problems. TriZPUG Python Challenge: can you come up 
with some? If there's really good participation, we could post the 
collection on trizpug.org.

Here's a few. They range from trivial to impossible, not necessarily in 
that order. One of them has a "valuable prize" for solving it. The 
important thing is that they are all instructional about Python. 
Spoiler: I've included the solutions to a few. Don't look until you try 
first.

1) A fibonacci series starts with 0 and 1. Each term in the series
thereafter is the sum of the two prior terms. Create a function which
returns a fibonacci series of arbitrary length using a generator, a
lambda, and a list comprehension.

def genFibIter():
     a, b = 0, 1
     while 1:
         yield a
         a, b = b, a+b

fi = genFibIter()

f = lambda x: [fi.next() for y in xrange(x)]

f(100)

2) Do the above without using a generator, lambda, or list
comprehension. Use slices.

def f(x):
     if x < 1:
         return []
     a, b = 0, 1
     if x < 2:
         return [a,]
     result = [a, b,]
     if x < 3:
         pass
     else:
         for y in xrange(x-2):
             result.append(result[-2]+result[-1])
     return result

f(100)

3) Which of the above solutions is recallable? What happens when the
non-recallble version is recalled? Why does it not really matter that 
the non-recallable version can't be recalled? What does this say about a 
certain Python language feature?

4) Why can't the fibonacci problem be solved easily with just a list 
comprehension? (Hint: irrational numbers, recursion, state machines, 
computability.) Try to solve the fibonacci series *exactly* (i.e., no 
floating point) as a list comprehension *without* a generator or other 
user defined function. (You can skip this one if you get stuck. It is 
exceedingly difficult. I will buy lunch for the first local TriZPUGer 
who can perform this stunt and post it into the public domain on this 
list.) Is it possible using Pascal's Triangle?

http://goldennumber.net/pascal.htm

5) Did you know, for-clauses, in list comprehensions and otherwise, can 
have mulitple targets and iterators? Check it out:

 >>> f=lambda n: [[x,y] for x,y in [xrange(n-1,n+1), xrange(n,n+2)]]
 >>> f(7)
[[6, 7], [7, 8]]

Could this be useful for solving problem (4)?

6) A golden section is the ratio of two successive fibonacci numbers.
Golden sections which use larger and larger fibonacci numbers approach a
limit. This limit is called a golden mean. Define a function which
computes a golden mean to within an arbitrary precision. Brute force is 
OK as python's floating point implementation will rapidly exceed its 
precision.

def g(e):
     x = [0, 1, 1, 2,]
     y, z = 1.0, 2.0
     while abs(z-y) > e:
         x.append(x[-1]+x[-2])
         y = float(x[-2])/x[-3]
         z = float(x[-1])/x[-2]
     return z

g(.5)
g(.02)
g(.0001)

7) Why wouldn't the golden mean solution above use our fibonacci function?

8) What is the maximum precision to which your python implementation can
compute the golden mean using the solution above?

9) Python, like most languages, implements floating point as double 
precision IEEE 754 binary mantissa and exponent. Python 2.4.1 introduces 
a new module called decimal which implements IEEE 854 decimal floating 
point (c.f. Mike Colishaw at IBM and the REXX IEEE 854 implementation). 
The decimal module allows for *exact* representation (i.e., accuracy) of 
floating point numbers with *user definable precision*. Install python 
2.4.1 and define a function which computes a golden mean to within a 
within an arbitrary precision without limits on the precision.

http://python.org/doc/2.4.1/lib/module-decimal.html

10) Remember, Decimal objects are immutable. Your decimal module golden 
mean function will consume more memory, spend more time in garbage 
collection, and run considerably slower than your stock binary floating 
point version. Such is the cost of accuracy. Find what precision causes 
your decimal golden mean function to take longer than one hour to run on 
your hardware. Use the time module to automate this search. Using brute 
force, this search might take a couple of hours.

http://python.org/doc/2.4.1/lib/module-time.html

-- 
Sincerely,

Chris Calloway
http://www.seacoos.org
office: 17-6 Venable Hall   phone: (919) 962-4323
mail: Campus Box #3300, UNC-CH, Chapel Hill, NC 27599





More information about the triangle-zpug mailing list