Tuesday, November 25, 2008

99 problems - python - 49

Gray codes.

An n-bit Gray code is a sequence of n-bit strings constructed according to certain rules. For example,

n = 1: C(1) = ['0','1'].
n = 2: C(2) = ['00','01','11','10'].
n = 3: C(3) = ['000','001','011','010',´110´,´111´,´101´,´100´].

Find out the construction rules and write a predicate with the following specification:

def gray(n):
if n == 0:
yield ""
base = list(gray_code(n-1))

for code in base:
yield "0"+code

for code in reversed(base):
yield "1"+code

Saturday, November 22, 2008

99 problems - python - 48

Truth tables for logical expressions (3).

Generalize problem P47 in such a way that the logical expression may contain any number of logical variables. Define table/2 in a way that table(List,Expr) prints the truth table for the expression Expr, which contains the logical variables enumerated in List.

* (table (A,B,C) (A and (B or C) equ A and B or A and C))
true true true true
true true fail true
true fail true true
true fail fail true
fail true true true
fail true fail true
fail fail true true
fail fail fail true

def int_to_bool_tuple(x,size):
result = []
while x:
result.insert(0, (x & 1) == 1)
x >>= 1
return ([False]*(size-len(result))) + result

def table2(var_count, func):
for x in range(2**var_count):
bools = int_to_bool_tuple(x,var_count)
for b in bools:
print "%-5s" % b,
print func(*bools)

As I was exploring ideas for this solution I noticed that python 2.6 has a bin() function which gives a string representation of a number as binary. Need to upgrade to 2.6 I guess. Of course if I'm going to upgrade, might as well wait for 3.0.

99 problems - python - 46

Define predicates and/2, or/2, nand/2, nor/2, xor/2, impl/2 and equ/2 (for logical equivalence) which succeed or fail according to the result of their respective operations; e.g. and(A,B) will succeed, if and only if both A and B succeed.

A logical expression in two variables can then be written as in the following example: and(or(A,B),nand(A,B)).

Now, write a predicate table/3 which prints the truth table of a given logical expression in two variables.

def and_(x,y): return x and y
def or_ (x,y): return x or y
def not_(x): return not x
def nand_(x,y): return not (x and y)
def nor_(x,y): return not (x or y)
def xor_(x,y): return x ^ y
def impl_(x,y):return not x or y
def equ_(x,y): return x == y

def bool_table(func):
inputs = [(x,y) for x in (True,False) for y in (True,False)]
for x,y in inputs:
print "%-5s %-5s %-5s" % (x,y,func(x,y))

Note: I'm just going to skip 47 since it's pretty much a noop based on how python already works, and how I solved this problem. Unless I'm missing something subtle.

Friday, November 21, 2008

100 Pushups: week 6 (8th try)

It just occurred to me that I've been doing this crazy 100 pushups thing since at least July. I'm still humorously far from my goal, but damn if I'm still making some progress. For instance this week after doing my various reps (150+ pushups in 20+ increments) I was able to get to 53 which is a new record for me.

But nevertheless it is still pretty funny that I've been doing the 6th week of a 6 week program for 8 weeks now. And it *only* took me 6 weeks or so to finish week 5. But I did finish.

The idea of doing 100 pushups seemed sort of comical to me when I started this bad boy, but now it's my mission. I just hope I finish this decade sometime.

Tuesday, November 18, 2008

Pragmatic Thinking and Learning

I've just started this book and while I think that I will get lots of interesting things out of it, it has already set off some alarm bells with me. The same alarm bell that goes off when I hear someone quote the "fact" that we only use 10% of out brains (well, maybe that's true for you...).

In any case the author seems to stick pretty close to the Betty (Drawing on the Right Side of the Brain) Edwards L/R distinction which I've grown skeptical of over the years. That was a low buzz no real alarm, just be wary.

But next came a reference to the"Unskilled and Unaware" paper. I've always thought that result sounded pretty reasonable, but today I came across this.

Hopefully the book doesn't continue to be full of too many debunked/sketchy studies.

I actually expect I will like the book and recommend it, but I just wish you could get a clear, unambiguous picture of state of the art learning/creativity techniques with minimal "woo".

Sunday, November 16, 2008

99 problems - python - 41

Given a range of integers by its lower and upper limit, print a list of all even numbers and their Goldbach composition.

In most cases, if an even number is written as the sum of two prime numbers, one of them is very small. Very rarely, the primes are both bigger than say 50. Try to find out how many such cases there are in the range 2..3000.

# using goldbach as defined previously
def goldbach_list(start,end,threshold=None):
start = max([start,4])
for n in range(start,end+1):
if n % 2 == 0:
i,j = goldbach(n)
if threshold == None or i > threshold:
print "%d = %d + %d" % (n, i, j)

99 problems - python - 40

Goldbach's conjecture. Goldbach's conjecture says that every positive even number greater than 2 is the sum of two prime numbers. Example: 28 = 5 + 23. It is one of the most famous facts in number theory that has not been proved to be correct in the general case. It has been numerically confirmed up to very large numbers (much larger than we can go with our Prolog system). Write a predicate to find the two prime numbers that sum up to a given even integer.

# using primes_range from previous problem
def goldbach(n):
assert n % 2 == 0

for i in primes_range(2, n):
for j in primes_range(i, n):
if i + j == n:
return (i,j)

Saturday, November 15, 2008

99 problems - python - 39

A list of prime numbers

# using is_prime from earlier problem
def primes_range(start,end):
return [n for n in range(start, end+1) if is_prime(n)]

99 problems - python - 37

Calculate Euler's totient function phi(m) (improved). See problem 34 for the definition of Euler's totient function. If the list of the prime factors of a number m is known in the form of problem 36 then the function phi(m) can be efficiently calculated as follows: Let ((p1 m1) (p2 m2) (p3 m3) ...) be the list of prime factors (and their multiplicities) of a given number m. Then phi(m) can be calculated with the following formula:

phi(m) = (p1 - 1) * p1 ** (m1 - 1) + (p2 - 1) * p2 ** (m2 - 1) + (p3 - 1) * p3 ** (m3 - 1) + ...

Note that a ** b stands for the b'th power of a. Note: Actually, the official problems show this as a sum, but it should be a product.

# using prime_factors_mult from earlier
def totient_phi2(n):
if n == 1:
return 1

def product(lst):
return reduce(lambda x,y: x*y, lst)
return product([((p-1)*(p**(m-1))) for (p, m) in prime_factors_mult(n)])

I'm pretty sure that "reduce" will be leaving python 3. We hardly knew ye. I don't understand that removal. Of course I'll just be adding it right the hell back in. And no one can stop me!

99 problems - python - 36

Determine the prime factors of a given positive integer.

Construct a list containing the prime factors and their multiplicity.


* (prime-factors-mult 315)
((3 2) (5 1) (7 1))

#using prime_factors from the previous problem
import itertools
def prime_factors_mult(n):
return [(x, len(list(y))) for x,y in itertools.groupby(prime_factors(n))]

99 problems - python - 35

Determine the prime factors of a given positive integer. Construct a flat list containing the prime factors in ascending order.

def prime_factors(n):
factor = 2
while n > 1:
if n % factor == 0:
yield factor
n = n / factor
factor += 1

This ended up being simpler and more beautiful than I was expecting. I think I'm falling in love with python all over again. *snif*

99 problems - python - 34

Calculate Euler's totient function phi(m). Euler's so-called totient function phi(m) is defined as the number of positive integers r (1 <= r < m) that are coprime to m. Example: m = 10: r = 1,3,7,9; thus phi(m) = 4. Note the special case: phi(1) = 1.

# using coprime defined previously
def totient_phi(m):
if m == 1:
return 1
return len([r for r in range(1,m) if coprime(r,m)])

emacs python mode from scratch: stage 12 - bicycle repair man

For this session we'll get bicycle repair man support working.

First let's see if we can get brm working by itself and then see how it integrates into emacs.

To start it I ran:

M-x python-setup-brm

It took a little googling and experimentation to figure out how to use this. But I finally figured out that if you select some text then the menus do their thing.

This is a strange little tool. I guess I'm so used to refactoring with global search and replaces that this seems overly constraining. But perhaps it's just unfamiliar. I suspect that if you got used to it then you could learn to like it, but I'm skeptical. One behavior that was very counter intuitive is that you can't use the normal emacs undo to revert the refactoring change. You have to do it via the menus (or presumably the brm console). In any case let's look at the code that runs brm.

Firstly it does an autoload of pymacs.

I've never really played with this before but you can see that it is loaded correctly and working by doing the following in *scratch*:

(pymacs-eval "2 + 2")

The second prep step is to get the bicycle repair man module itself loaded:

(autoload 'brm-init "bikemacs")

Which I'm assuming works since I was able to do a refactoring

  • python-setup-brm

    This code is mostly just busy work to set up of menus.

    Strangely this code ends with an (error ... ) embedded in an (error ...).
    Not sure what that is about.

Interestingly in the comments the author of python.el expresses doubts that brm is useful.
Note to self, I should also look at ropemacs. Looks like rope has more features and if I recall an earlier experiment correctly does autocomplete of python variables/modules as well.

Any way, onward and upward. Next stop, context sensitive help.

99 problems - python - 33

Determine whether two positive integer numbers are coprime. Two numbers are coprime if their greatest common divisor equals 1.

Using gcd as defined in the previous problem:

def coprime(m,n):
return gcd(m,n) == 1

Wednesday, November 12, 2008

99 problems - python - 32

Determine the greatest common divisor of two positive integer numbers.

def gcd(m,n):
m,n = sorted([m,n])

while m != 0:
m, n = (n % m), m

return n

Humorously, I resisted using a recursive algorithm. I don't know why, but it just seemed more reasonable to use a straight iterative one. Also I really like how m,n = (n%m), m saves us from having to declare a temporary variable.

emacs python mode from scratch: stage 11 - skeleton

We are actually getting to the point where this mode would actually be useful for developing with.

Next let's get skeleton support working now.

Here are the new functions I've copied over:

def-python-skeleton if
define-skeleton python-else
def-python-skeleton while
def-python-skeleton for
def-python-skeleton try/except
define-skeleton python-target
def-python-skeleton try/finally
def-python-skeleton def
def-python-skeleton class
python-default-template "if"

  • python-use-skeletons

    This controls whether or not skeleton functions are added to the python-mode-abbrev-table

  • python-skeletons

    A list of all the skeletons. apparently used when working on compound statements.

  • python-mode-abbrev-table

    This is where the actual abbrevs are stored

  • def-python-skeleton

    A macro for getting a skeletons "registered" in the abbrev system. First it creates a name for the skeleton of the form: python-insert-foo. Then if adds this name to the pyton-mode-abbrev-table. Finally it calls define-skeleton and creates the skeleton.

  • Each of the following create the appropriate skeleton by name

    def-python-skeleton if
    def-python-skeleton while
    def-python-skeleton for
    def-python-skeleton try/except
    def-python-skeleton try/finally
    def-python-skeleton def
    def-python-skeleton class
  • define-skeleton python-else

    else clause used by if and other else-able statements. One reason I would find it hard to get excited about using this particular skeleton/template system is that it seems sort of ridiculous to be prompted after a for loop or a while loop, etc for an else clause. I can count on 1 hand how many times i've ever used an else clause other than part of an if cascade. It seems like an unnecessary burden to make the user consider this case every time they are writing a for loop.

  • define-skeleton python-target

    Helper used by try/except

  • python-default-template

    Variable that defines what template to use by default in python-expand-template

  • python-expand-template

    This function is for allowing a skeleton to be used directly as a key sequence rather than as an abbrev. Interestingly if defaults to the "if" template but then let's you update what the default is.

I'm not totally sold on the value of skeletons for python. The syntax is already so minimal that the distraction of writing code through the minibuffer doesn't seem like a big win but it's something i'd like to explore in detail sometime and see if it works for me if i give it a chance.

Next let's get bicycle repair man support working.

Saturday, November 8, 2008

99 problems - python - 31

Determine whether a given integer number is prime.

import math
def is_prime(n):
for test in range(2, int(math.sqrt(n) + 1)):
if n % test == 0:
return False

return True

(no, I'm not skipping problems, the original set skips too)

BTW, below is the prime number generator function in Haskell in case you haven't seen it before. For my money it's about the most beautiful line (or 2) of code I've ever seen. It almost gives me goose bumps when I see it.

It's deceptively simple looking, but the more you look at it the more your mind is guaranteed to be blown as it sinks in how subtly cool this is

primes = sieve [2..]
where sieve (p:xs) = p : sieve [x | x<-xs, x `mod` p /= 0]

* (guarantee not binding any where)

99 problems - python - 28

Sorting a list of lists according to length of sublists

a) We suppose that a list contains elements that are lists themselves. The objective is to sort the elements of this list according to their length. E.g. short lists first, longer lists later, or vice versa.

* (lsort '((a b c) (d e) (f g h) (d e) (i j k l) (m n) (o)))
((O) (D E) (D E) (M N) (A B C) (F G H) (I J K L))

b) Again, we suppose that a list contains elements that are lists themselves. But this time the objective is to sort the elements of this list according to their length frequency; i.e., in the default, where sorting is done ascendingly, lists with rare lengths are placed first, others with a more frequent length come later.

* (lfsort '((a b c) (d e) (f g h) (d e) (i j k l) (m n) (o)))
((i j k l) (o) (a b c) (f g h) (d e) (d e) (m n))

(a) it should be enough to do
sorted(lst_of_lsts, key=lambda x: len(x))

If you want the lists of same length to be alphabetically sorted as well then you could do:
sorted(sorted(lst_of_lsts), key=lambda x: len(x))


def length_frequency_sort(lst_of_lists):
freqs = {}

for lst in lst_of_lists:
freqs.setdefault(len(lst), 0)
freqs[len(lst)] += 1

return sorted(lst_of_lists, key=lambda x: freqs[len(x)])

99 problems - python - 27

Group the elements of a set into disjoint subsets.

a) In how many ways can a group of 9 people work in 3 disjoint subgroups of 2, 3 and 4 persons? Write a function that generates all the possibilities and returns them in a list.

* (group3 '(aldo beat carla david evi flip gary hugo ida))
... )

b) Generalize the above predicate in a way that we can specify a list of group sizes and the predicate will return a list of groups.

* (group '(aldo beat carla david evi flip gary hugo ida) '(2 2 5))
... )

def combination(lst, size):
#defined as in previous problem

def grouped_combos(lst, sizes):
assert len(lst) == sum(sizes)

if not sizes:
yield []
for combo in combinations(lst, sizes[0]):
rest = sorted(list(set(lst) - set(combo)))
for rest_combo in grouped_combos(rest, sizes[1:]):
yield [combo] + rest_combo

I have a sorted thrown in since using set gave unreliable ordering after the set difference. I really love recursion. It seems like the above would be quite annoying without it.

99 problems - python - 26

Generate the combinations of K distinct objects chosen from the N elements of a list In how many ways can a committee of 3 be chosen from a group of 12 people? We all know that there are C(12,3) = 220 possibilities (C(N,K) denotes the well-known binomial coefficients). For pure mathematicians, this result may be great. But we want to really generate all the possibilities in a list.

def combinations(lst, size):
if len(lst) < size:
elif size == 0:
yield []
# keep first
for combo in combinations(lst[1:], size-1):
yield [lst[0]] + combo
# skip first
for combo in combinations(lst[1:], size):
yield combo

After I wrote this I remembered that python's test/test_generators.py also had an implementation of this:

>>> def gcomb(x, k):
... "Generate all combinations of k elements from list x."
... if k > len(x):
... return
... if k == 0:
... yield []
... else:
... first, rest = x[0], x[1:]
... # A combination does or doesn't contain first.
... # If it does, the remainder is a k-1 comb of rest.
... for c in gcomb(rest, k-1):
... c.insert(0, first)
... yield c
... # If it doesn't contain first, it's a k comb of rest.
... for c in gcomb(rest, k):
... yield c

Which is amazingly similar. I guess in python there really is OBWTDI (one best way to do it).

So anyway I think from here on out the questions will continue to be less and less "trivial".

99 problems - python - 25

Generate a random permutation of the elements of a list.

Once again python provides us with a solution, so we don't have to code at all.


Since this works in place you may want to copy your list first before operating on.

Keep your shirt on, these do get interesting after a while. But it is nice to see how many "problems" are already solved for us.

Friday, November 7, 2008

99 problems - python - 24

Lotto: Draw N different random numbers from the set 1..M.

No reason to use anything other than random.sample(population, count)

emacs python mode from scratch: stage 10 - pychecker

My next step is to get pychecker working. Turns out it's not much code. Here are the functions:

  • python-check-command

    the default string to use as the command for running pychecker

  • python-saved-check-command

    a cache of the command above and the name of the file we are
    currently working with

  • python-check

    Pretty straightforward but a couple of things to note.

    I wasn't aware that the "interactive" command took straight elisp as an argument. I had just assumed you had to use the magic argument strings.

    It's a little strange that they use an old school emacs lisp regular expression ("(\\([^,]+\\), line \\([0-9]+\\))") rather than the rx style they seemed to use everywhere else.

A note on pychecker. I find this utility fascinating. For good and bad reasons. It's really quite useful. C-c C-w is reflexively typed after saving a file. And the fact that it is so useful makes it extra confusing that it it seems sort of abandoned (at least last I checked).

As a future project I'd like to look at it (or one of it's cohorts, pylint, pyflakes, etc) and see how it works and perhaps complain less and help more,but it seems strangely abandoned now. I did start to take a look at one point and it seemed very complex so I ran away with my tail between my legs. But fortunately I have a short memory for scary things and I'll likely return to it someday.

Getting pychecker working required less code than I suspected.

Next I'll do skeleton support which if nothing else is a lot more lines of code.

Wednesday, November 5, 2008

99 problems - python - 23

Extract a given number of randomly selected elements from a list.

import random
def random_select(lst, n):
for x in range(n):
yield random.choice(lst)

Depending on how you interpret the problem you may just want to use random.sample

99 problems - python - 22

Create a list containing all integers within a given range.

OK, just use range(). Anything else would be silly. Depending on how you interpret this problem you may need to add one to the second parameter.

Monday, November 3, 2008

99 problems - python - 21

Insert an element at a given position into a list.

def insert_at(x, lst, n):
return lst[:n-1] + [x] + lst[n-1:]

Sunday, November 2, 2008

99 problems - python - 20

Remove the K'th element from a list.

def remove_at(lst, n):
return lst[:(n-1)] + lst[n:]

The simplest thing to do would be to just use .pop(), but I assuming that a non-destructive operation would be preferred in this case.

99 problems - python - 19

Rotate a list N places to the left.

def rotate(lst, n):
n = n % len(lst)
x, y = lst[:n], lst[n:]
return y + x

99 problems - python - 18

Extract a slice from a list.

Given two indices, i and k, the slice is the list containing the elements between the i'th and k'th element of the original list (both limits included). Start counting the elements with 1

def slice(lst, i, k):
return lst[i-1:k]

99 problems - python - 17

Split a list into two parts; the length of the first part is given.

def split(lst, n):
return (lst[:n], lst[n:])

Trust me, these problems do get more challenging after a while. But it is a nice testament to the beauty of python how straightforward something like this is.

99 problems - python - 16

Drop every N'th element from a list.

def drop(lst, n):
for i,x in enumerate(lst):
if (i+1) % n != 0:
yield x

99 problems - python - 15

Replicate the elements of a list a given number of times.

def replicate_elements(lst, n):
for x in lst:
for y in range(n):
yield x

Saturday, November 1, 2008

99 problems - python - 14

Duplicate the elements of a list.

def duplicate_elements(lst):
for x in lst:
yield x
yield x

real age

I had set a goal to get to a certain weight (210) and then get a physical and blood profile (cholesterol, etc). As it happens I received my results just as it was my 40th birthday.

One of my objectives of getting the blood profile was so I could complete the realage survey in excruciating detail. So I finally filled it in today and was pretty pleased with my results.

physical age = 40
"real age" = 27.9

Of course that is an absurdly precise number, but I'm still proud of my result. And my wife was part jealous and part suspicious. So she went over all my answers with me and helped me adjust them to less fantasy based answers. And my score went from 26.7 to 27.9.

Now we are in serious competition mode. She will be getting a blood profile done later this week.

Any way, I have the body of a 27.9 year old. I can do 50 pushups (and working towards 100). Things could be worse.