#!/usr/local/bin/python
# $Id: ackermann.python,v 1.7 2001/03/16 15:57:34 doug Exp $
# http://www.bagley.org/~doug/shootout/
# from Brad Knotwell

import sys

def Ack(M, N):
    if (not M):
        return( N + 1 )
    if (not N):
        return( Ack(M-1, 1) )
    return( Ack(M-1, Ack(M, N-1)) )

def main():
    NUM = int(sys.argv[1])
    sys.setrecursionlimit(3000)
    print "Ack(3,%d): %d" % (NUM, Ack(3, NUM))

main()

#!/usr/local/bin/python
# $Id: ary3.python,v 1.1 2001/05/31 02:27:48 doug Exp $
# http://www.bagley.org/~doug/shootout/
# with help from Brad Knotwell

import sys

def main():
    n = int(sys.argv[1])
    x = n * [0]       
    y = n * [0]
    for i in xrange(0,n):
        x[i] = i + 1
    for k in xrange(0,1000):
        for i in xrange(n-1,-1,-1):
            y[i] += x[i]
    print y[0], y[-1]

main()

#!/usr/local/bin/python
# $Id: wc.python,v 1.2 2001/05/15 03:11:19 doug Exp $
# http://www.bagley.org/~doug/shootout/

import sys

def main():
    nl = nw = nc = 0
    rl = sys.stdin.readlines
    lines = rl(4096)
    while lines:
        for line in lines:
            nl += 1
            nc += len(line)
            nw += len(line.split())
        lines = rl(4096)

    print "%d %d %d" % (nl, nw, nc)

main()

#!/usr/local/bin/python
# $Id: echo.python,v 1.7 2001/05/06 22:21:26 doug Exp $
# http://www.bagley.org/~doug/shootout/
# with help from Brad Knotwell

import sys, os
from socket import *

DATA = "Hello there sailor\n"
bufferSize = len(DATA)

def server_sock():
    sock = socket(AF_INET, SOCK_STREAM)
    sock.setsockopt(SOL_SOCKET, SO_REUSEADDR, 1)
    sock.bind(('127.0.0.1', 0));
    sock.listen(2)
    return(sock)

def get_port(sock):
    host, port = sock.getsockname()
    return(port)

def client_sock(port):
    sock = socket(AF_INET, SOCK_STREAM)
    sock.connect(('127.0.0.1', port))
    return(sock)

def echo_client(n, port):
    sock = client_sock(port)
    sender,receiver = sock.send,sock.recv
    for i in range(0,n):
        sender(DATA)
        ans = receiver(bufferSize)
        while ans[-1] != "\n":
            ans += receiver(bufferSize - len(ans))
        if ans <> DATA:
            raise("client: \"%s\" ne \"%s\"" % (DATA, ans))
    sock.close()

def echo_server(n):
    ssock = server_sock()
    if os.fork() > 0:
        # parent is server
        csock, addr = ssock.accept()
        n = 0
        sender,receiver = csock.send,csock.recv
        while 1:
            dat = receiver(bufferSize)
            if not dat: break
            sender(dat)
            n += len(dat)
        print "server processed %d bytes" % n
        os.wait()
    else:
        # child is client
        echo_client(n, get_port(ssock))

def main():
    n = int(sys.argv[1])
    if n < 1:
        n = 1
    echo_server(n)

main()

#!/usr/local/bin/python
# http://www.bagley.org/~doug/shootout/

import sys

HI = 0
LO = 0


class Hi_exception:
    def __init__(self, value):
        self.value = value
    def __str__(self):
        return `self.value`


class Lo_exception:
    def __init__(self, value):
        self.value = value
    def __str__(self):
        return `self.value`


def some_function(num):
    try:
        hi_function(num)
    except:
        raise "We shouldn't get here (%s)" % sys.exc_info()[0]


def hi_function(num):
    global HI
    try:
        lo_function(num)
    except Hi_exception, ex:
        HI += 1
        #print 'Hi_exception occurred, value:', ex.value


def lo_function(num):
    global LO
    try:
        blowup(num)
    except Lo_exception, ex:
        LO += 1
        #print 'Lo_exception occurred, value:', ex.value


def blowup(num): 
    raise (((num & 1) and Lo_exception) or Hi_exception)(num)

def main():
    global LO, HI
    NUM = int(sys.argv[1])
    if NUM < 1:
        NUM = 1
    for i in xrange(NUM-1,-1,-1):
        some_function(i)
    print "Exceptions: HI=%d / LO=%d" % (HI, LO)


main()

#!/usr/local/bin/python
# $Id: fibo.python,v 1.2 2000/12/24 19:10:50 doug Exp $
# http://www.bagley.org/~doug/shootout/

import sys

def fib(n):
    if (n < 2):
        return(1)
    return( fib(n-2) + fib(n-1) )

def main():
    N = int(sys.argv[1])
    #sys.setrecursionlimit(3000)
    print fib(N)

main()

#!/usr/local/bin/python
# $Id: hash.python,v 1.4 2001/06/10 03:33:57 doug Exp $
# http://www.bagley.org/~doug/shootout/
# with help from from Gustavo Niemeyer

import sys
#sys.setcheckinterval(10000)

def main():
    n = int(sys.argv[1])
    X = {}
    myhex = hex
    for i in xrange(1,n+1):
        X[myhex(i)[2:]] = i
    c = 0
    has_key = X.has_key
    for i in xrange(n, 0, -1):
        c += has_key(`i`)
    print c

main()

#!/usr/local/bin/python
# $Id: hash2.python,v 1.2 2001/05/06 19:16:31 doug Exp $
# http://www.bagley.org/~doug/shootout/
# from Mark Baker

import sys

n = int(sys.argv[1])
hash1 = {}
for i in xrange(10000):
    hash1['foo_' + `i`] = i

hash2 = {}
for i in xrange(n):
    for k in hash1.keys():
        try:
            hash2[k] += hash1[k]
        except KeyError:
            hash2[k] = hash1[k]

print hash1['foo_1'], hash1['foo_9999'], hash2['foo_1'], hash2['foo_9999']

#!/usr/local/bin/python -O
# $Id: heapsort.python,v 1.10 2001/09/09 01:57:21 doug Exp $
# http://www.bagley.org/~doug/shootout/

import sys

IM = 139968
IA =   3877
IC =  29573

LAST = 42
def gen_random(max):
    global LAST
    LAST = (LAST * IA + IC) % IM
    return( (max * LAST) / IM )

def heapsort(n, ra):
    rra = i = j = 0
    l = (n >> 1) + 1
    ir = n

    while (1):
        if (l > 1):
            l -= 1
            rra = ra[l]
        else:
            rra = ra[ir]
            ra[ir] = ra[1]
            ir -= 1
            if (ir == 1):
                ra[1] = rra
                return
        i = l
        j = l << 1
        while (j <= ir):
            if ((j < ir) and (ra[j] < ra[j+1])):
                j += 1
            if (rra < ra[j]):
                ra[i] = ra[j]
                i = j
                j += i
            else:
                j = ir + 1
        ra[i] = rra

def main():
    N = int(sys.argv[1])
    if N < 1:
        N = 1

    ary = range(N+1)
    for i in xrange(1,N+1):
        ary[i] = gen_random(1.0)

    heapsort(N, ary)

    print "%.10f" % ary[N]

main()

#!/usr/local/bin/python
# $Id: hello.python,v 1.1 2001/06/17 22:00:34 doug Exp $
# http://www.bagley.org/~doug/shootout/

print "hello world"

#!/usr/local/bin/python
# $Id: lists.python,v 1.7 2001/05/09 01:09:04 doug Exp $
# http://www.bagley.org/~doug/shootout/
# with improvements from Mark Baker

import sys

SIZE = 10000

def test_lists():
    Li1 = range(1, SIZE + 1)
    Li2 = Li1[:]
    Li3 = []

    # remove each individual item from left side of Li2 and
    # append to right side of Li3 (preserving order)
    # 
    # popping the first element is *expensive*
    #
    #while Li2:
    #    Li3.append(Li2.pop(0))   
    Li2.reverse()
    while Li2:
        Li3.append(Li2.pop())
    while Li3:
        Li2.append(Li3.pop())
    Li1.reverse()
    if Li1[0] != SIZE:
        return 0
    if Li1 == Li2:
        return len(Li1)
    else:
        return 0

def main():
    NUM = int(sys.argv[1])
    if NUM < 1:
        NUM = 1
    while NUM > 0:
        result = test_lists()
        NUM = NUM - 1
    print result

main()

#!/usr/local/bin/python
# $Id: matrix.python,v 1.5 2001/05/09 01:24:52 doug Exp $
# http://www.bagley.org/~doug/shootout/

# This program based on the original from:
# "The What, Why, Who, and Where of Python" By Aaron R. Watters
# http://www.networkcomputing.com/unixworld/tutorial/005/005.html

# modified to pass rows and cols, and avoid matrix size checks
# and added one optimization to reduce subscripted references in
# inner loop.

import sys

size = 30

def mkmatrix(rows, cols):
    count = 1
    mx = [ None ] * rows
    for i in range(rows):
        mx[i] = [0] * cols
        for j in range(cols):
            mx[i][j] = count
            count += 1
    return mx

def mmult(rows, cols, m1, m2):
    m3 = [ None ] * rows
    for i in range( rows ):
        m3[i] = [0] * cols
        for j in range( cols ):
            val = 0
            for k in range( cols ):
                val += m1[i][k] * m2[k][j]
            m3[i][j] = val
    return m3

def mxprint(m):
    for i in range(size):
        for j in range(size):
            print m[i][j],
        print ""

def main():
    iter = int(sys.argv[1])
    m1 = mkmatrix(size, size)
    m2 = mkmatrix(size, size)
    for i in xrange(iter):
        mm = mmult(size, size, m1, m2)
    print mm[0][0], mm[2][3], mm[3][2], mm[4][4]

main()

#!/usr/local/bin/python
# http://www.bagley.org/~doug/shootout/

import sys

class Toggle:
    def __init__(self, start_state):
        self.bool = start_state
    def value(self):
        return(self.bool)
    def activate(self):
        self.bool = not self.bool
        return(self)

class NthToggle(Toggle):
    def __init__(self, start_state, max_counter):
        Toggle.__init__(self, start_state)
        self.count_max = max_counter
        self.counter = 0
    def activate(self):
        self.counter += 1
        if (self.counter >= self.count_max):
            self.bool = not self.bool
            self.counter = 0
        return(self)


def main():
    NUM = int(sys.argv[1])
    if NUM < 1:
        NUM = 1

    val = 1
    toggle = Toggle(val)
    for i in xrange(0,NUM):
    val = toggle.activate().value()
    if val:
        print "true"
    else:
        print "false"

    val = 1
    ntoggle = NthToggle(val, 3)
    for i in xrange(0,NUM):
        val = ntoggle.activate().value()
    if val:
        print "true"
    else:
        print "false"

main()

#!/usr/local/bin/python
# $Id: nestedloop.python,v 1.3 2001/05/09 00:35:52 doug Exp $
# http://www.bagley.org/~doug/shootout/
# with help from Mark Baker

import sys

def main():
    x = 0
    iter = int(sys.argv[1])
    if iter < 1:
        iter = 1
    
    i_r = range(iter)
    for a in i_r:
        for b in i_r:
            for c in i_r:
                for d in i_r:
                    for e in i_r:
                        for f in i_r:
                            x += 1
    print x

main()

#!/usr/local/bin/python
# http://www.bagley.org/~doug/shootout/

import sys

class Toggle:
    def __init__(self, start_state):
        self.bool = start_state
    def value(self):
        return(self.bool)
    def activate(self):
        self.bool = not self.bool
        return(self)

class NthToggle(Toggle):
    def __init__(self, start_state, max_counter):
        Toggle.__init__(self, start_state)
        self.count_max = max_counter
        self.counter = 0
    def activate(self):
        self.counter += 1
        if (self.counter >= self.count_max):
            self.bool = not self.bool
            self.counter = 0
        return(self)


def main():
    NUM = int(sys.argv[1])
    if NUM < 1:
        NUM = 1

    toggle = Toggle(1)
    for i in xrange(0,5):
        if toggle.activate().value():
            print "true"
        else:
            print "false"
    for i in xrange(0,NUM):
        toggle = Toggle(1)

    print ""

    ntoggle = NthToggle(1, 3)
    for i in xrange(0,8):
        if ntoggle.activate().value():
            print "true"
        else:
            print "false"
    for i in xrange(0,NUM):
        ntoggle = NthToggle(1, 3)

main()

#!/usr/local/bin/python
# $Id: prodcons.python,v 1.1 2000/12/20 04:33:20 doug Exp $
# http://www.bagley.org/~doug/shootout/

import sys
from threading import * 

access = Condition()
count = 0
consumed = 0
produced = 0
data = 0

def consumer(n):
    global count, data, consumed
    while 1:
        access.acquire()
        while count == 0:
            access.wait()
        i = data
        count = 0
        access.notify()
        access.release()
        consumed += 1
        if i == n:
            break

def producer(n):
    global count, data, produced
    for i in xrange(1,n+1):
        access.acquire()
        while count == 1:
            access.wait()
        data = i
        count = 1
        access.notify()
        access.release()
        produced += 1

def main(n):
    t1 = Thread(target=producer, args=(n,))
    t2 = Thread(target=consumer, args=(n,))
    t1.start()
    t2.start()
    t1.join()
    t2.join()
    print produced, consumed
    
main(int(sys.argv[1]))

#!/usr/local/bin/python
# $Id: random.python,v 1.17 2001/07/31 16:38:37 doug Exp $
# http://www.bagley.org/~doug/shootout/
# with help from Brent Burley

import sys

IM = 139968
IA = 3877
IC = 29573

LAST = 42
def gen_random(max):
    global LAST
    LAST = (LAST * IA + IC) % IM
    return( (max * LAST) / IM )

def main():
    N = int(sys.argv[1])
    if N < 1:
        N = 1
    gr = gen_random
    for i in xrange(1,N):
        gr(100.0)
    print "%.9f" % gr(100.0)

main()

#!/usr/pkg/bin/python
# $Id: regexmatch.python,v 1.9 2001/02/05 19:02:37 doug Exp $
# http://www.bagley.org/~doug/shootout/

import sys, re

def main():
    NUM = int(sys.argv[1])
    if NUM < 1:
        NUM = 1

    phones = sys.stdin.readlines()

    rx = re.compile(
        r'(?:^|[^\d\(])'
        r'(?:\((\d\d\d)\)|(\d\d\d))'
        r'[ ]'
        r'(\d\d\d)'
        r'[ -]'
        r'(\d\d\d\d)'
        r'\D'
        )

    findIt = rx.search
    count = 0
    for i in xrange(0,NUM):
        for line in phones:
            m = findIt(line)
            if m:
                g = m.group
                num = "(" + (g(1) or g(2)) + ") " + g(3) + "-" + g(4)
                if 0 == i:
                    count = count + 1
                    print "%d: %s" % (count, num)

main()

#!/usr/local/bin/python
# $Id: reversefile.python,v 1.4 2001/05/09 00:47:40 doug Exp $
# http://www.bagley.org/~doug/shootout/
# from Brad Knotwell
# with help from Mark Baker

def main():
    from sys import stdin, stdout
    w = stdin.readlines()
    w.reverse()
    stdout.writelines(w)

main()

#!/usr/local/bin/python 
# $Id: sieve.python,v 1.10 2001/05/06 04:37:45 doug Exp $
# http://www.bagley.org/~doug/shootout/
# with help from Brad Knotwell

import sys

def main():
    NUM = int(sys.argv[1])
    for foo in xrange(0,NUM):
    flags = (8192+1) * [1]
    count = 0
        for i in xrange(2,8192+1):
        if flags[i]:
                # remove all multiples of prime: i
            k = i + i
        while k <= 8192:
            flags[k] = 0
            k = k + i
        count = count + 1    
    print "Count:", count

main()

#!/usr/local/bin/python
# $Id: spellcheck.python,v 1.6 2001/05/15 22:22:37 doug Exp $
# http://www.bagley.org/~doug/shootout/
# From Fred Bremmer

import sys

def main():
    dict = {}
    dict_has_key = dict.has_key
    for line in open("Usr.Dict.Words").xreadlines():
        word = line[:-1]
        if word: dict[word] = 1

    for line in sys.stdin.xreadlines():
        word = line[:-1]
        if word:
            if not dict_has_key(word): print word

main()

#!/usr/local/bin/python
# $Id: moments.python,v 1.4 2001/05/09 00:58:40 doug Exp $
# http://www.bagley.org/~doug/shootout/

import sys, string, math, operator

def main():
    sum = 0
    nums = []
    atof = string.atof

    nums = map(atof, sys.stdin.readlines())
    sum = reduce(operator.add, nums)

    n = len(nums)
    mean = sum/n
    average_deviation = 0
    standard_deviation = 0
    variance = 0
    skew = 0
    kurtosis = 0

    for num in nums:
        deviation = num - mean
        average_deviation += abs(deviation)
        variance += deviation**2;
        skew += deviation**3;
        kurtosis += deviation**4

    average_deviation /= n
    variance /= (n - 1)
    standard_deviation = math.sqrt(variance)

    if variance > 0.0:
        skew /= (n * variance * standard_deviation)
        kurtosis = kurtosis/(n * variance * variance) - 3.0

    nums.sort()
    mid = n / 2

    if (n % 2) == 0:
        median = (nums[mid] + nums[mid-1])/2
    else:
        median = nums[mid]

    print "n:                  %d" % n
    print "median:             %f" % median
    print "mean:               %f" % mean
    print "average_deviation:  %f" % average_deviation
    print "standard_deviation: %f" % standard_deviation
    print "variance:           %f" % variance
    print "skew:               %f" % skew
    print "kurtosis:           %f" % kurtosis

main()

#!/usr/local/bin/python
# $Id: strcat.python,v 1.5 2001/06/12 02:40:03 doug Exp $
# http://www.bagley.org/~doug/shootout/
# from Brad Knotwell

import sys,cStringIO

def main():
    n = int(sys.argv[1])
    str = cStringIO.StringIO()
    for i in xrange(0,n):
        str.write('hello\n')

    print str.tell()

main()

#!/usr/local/bin/python
# $Id: sumcol.python,v 1.7 2001/05/09 00:45:50 doug Exp $
# http://www.bagley.org/~doug/shootout/
# with help from Mark Baker

import sys

def main():
    count = 0
    for line in sys.stdin.xreadlines():
        count += int(line)
    print count

main()

#!/usr/local/bin/python
# $Id: wordfreq.python,v 1.9 2001/05/11 17:44:00 doug Exp $
# http://www.bagley.org/~doug/shootout/
#
# adapted from Bill Lear's original python word frequency counter
#
# Joel Rosdahl suggested using translate table to speed up
# word splitting.  That change alone sped this program up by
# at least a factor of 3.
#
# with further speedups from Mark Baker

import sys

def main():
    count = {}
    i_r = map(chr, range(256))

    trans = [' '] * 256
    o_a, o_z = ord('a'), (ord('z')+1)
    trans[ord('A'):(ord('Z')+1)] = i_r[o_a:o_z]
    trans[o_a:o_z] = i_r[o_a:o_z]
    trans = ''.join(trans)

    rl = sys.stdin.readlines

    lines = rl(4095)
    while lines:
        for line in lines:
            for word in line.translate(trans).split():
                try:
                    count[word] += 1
                except KeyError:
                    count[word] = 1
        lines = rl(4095)

    l = zip(count.values(), count.keys())
    l.sort()
    l.reverse()

    print '\n'.join(["%7s\t%s" % (count, word) for (count, word) in l])

main()