[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