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 ""
    else:
        base = list(gray_code(n-1))

        for code in base:
            yield "0"+code

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

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.

Example:
* (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.

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.

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

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)