[The Original Shootout]   [NEWS]   [FAQ]   [Methodology]   [Platform Details]   [Acknowledgements]   [Scorecard]
All Source For python
Ackermann's Function
```#!/usr/local/bin/python
# \$Id: ackermann.python,v 1.7 2001/03/16 15:57:34 doug Exp \$
# http://www.bagley.org/~doug/shootout/

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()

```
Array Access
```#!/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()
```
Count Lines/Words/Chars
```#!/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
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()
```
Echo Client/Server
```#!/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.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)
for i in range(0,n):
sender(DATA)
while ans[-1] != "\n":
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
n = 0
while 1:
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()
```
Exception Mechanisms
```#!/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()
```
Fibonacci Numbers
```#!/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()
```
Hash (Associative Array) Access
```#!/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()
```
Hashes, Part II
```#!/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']

```
Heapsort
```#!/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()

```
Hello World
```#!/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"
```
List Operations
```#!/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()
```
Matrix Multiplication
```#!/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()
```
Method Calls
```#!/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()
```
Nested Loops
```#!/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()
```
Object Instantiation
```#!/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

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.start()
t2.start()
t1.join()
t2.join()
print produced, consumed

main(int(sys.argv[1]))

```
Random Number Generator
```#!/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()

```
Regular Expression Matching
```#!/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

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()
```
Reverse a File
```#!/usr/local/bin/python
# \$Id: reversefile.python,v 1.4 2001/05/09 00:47:40 doug Exp \$
# http://www.bagley.org/~doug/shootout/
# with help from Mark Baker

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

main()
```
Sieve of Erathostenes
```#!/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()
```
Spell Checker
```#!/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
word = line[:-1]
if word: dict[word] = 1

word = line[:-1]
if word:
if not dict_has_key(word): print word

main()
```
Statistical Moments
```#!/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

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()

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

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()
```
Sum a Column of Integers
```#!/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
count += int(line)
print count

main()
```
Word Frequency Count
```#!/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)

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()
```