## Question 1 - Square Roots

```# Newton Raphson
# Andrew Turpin
def s(k, ii):
'''Return the ii'th approximation of square root of k.'''
k = float(k)
x = k
print("{1:2} {0}".format(x, 1))
for i in range(ii+1):
x = x/2.0 + k/x/2.0
print("{1:2} {0:4.4}".format(x, i+2))

s(1000, 9)

s(1234.56789, 100)
```
```# Newton Raphson
# Bernie Pope

def root(k, i):
n = 1
x = k
while n <= i:
#print((n, x))
x = (x + k / x) / 2
n += 1
return x

def main():
k = input("k: ")
i = input("i: ")
result = root(float(k), int(i))
print("%.2f" % result)

if __name__ == '__main__':
main()

```

## Question 2 - Water Pools

```###############################
# Brute Force on a 2d grid!
# Andrew Turpin
###############################
def brute(filename):
data = [int(x.strip()) for x in open(filename).readlines()]

highest = max(data)

# Scan each row left to right
# If we hit a rock begin counting water
# If we hit another rock, add the count to running total
# If we don't hit another rock, then chuck count

total = 0
for row in range(highest, 0, -1):
counting = False
for col in range(len(data)):
if data[col] >= row and not counting:
counting = True
count = -1
elif data[col] >= row and counting:
total += count
count = -1

if counting:
count += 1

return(total)
```
```# Repeated filling, O(n^2)
# Andrew Turpin
def lowDC(filename):
'''
Solve water problem with repeated filling.
Find the lowest point, low.
Find first higher rock to the right of low.
Find first higher rock to the left of low.
Find the smallest of data[left] and data[right], min.
Count the water in (min-data[low])*(right-left-1).
Raise all left:right to min and go again
'''
data = [int(x.strip()) for x in open(filename).readlines()]
total_so_far = 0

while True:
low = data.index(min(data))

left  = low - 1
while left >= 0 and data[left] == data[low]:
left -= 1

right  = low + 1
while right < len(data) and data[right] == data[low]:
right += 1

if left < 0 and right >= len(data):       # nothing left
return(total_so_far)
else:
if left >= 0 and right < len(data):       # left and right
lowest_end = min((data[left], data[right]))
total_so_far += (lowest_end - data[low]) * (right-left-1)
fill = (left+1, right, lowest_end)
else:
if left >= 0 and right >= len(data):   # left only
fill = (left+1, len(data), data[left])
elif left < 0 and right < len(data):  # right only
fill = (0, right, data[right])

for i in range(fill[0], fill[1]):
data[i] = fill[2]

```
```# Efficient version, O(n)
# Bernie Pope
def water_columns(columns):
prev_pos = -1
prev_col = 0
stack = []
area = 0
for pos, this_column in enumerate(columns):
if this_column < prev_col:
# height is decreasing
# push this column on the stack
stack.append((prev_pos, prev_col))
elif this_column > prev_col:
# height is increasing
bottom_height = prev_col
while stack:
stack_pos, stack_col = stack[-1]
if this_column >= stack_col:
new_area = (stack_col - bottom_height) * (prev_pos - stack_pos)
area += new_area
bottom_height = stack_col
stack.pop()
else: # this_column < top_col
new_area = (this_column - bottom_height) * (prev_pos - stack_pos)
area += new_area
break
prev_pos = pos
prev_col = this_column
return area

```

## Question 3 - Langton's Ant

```# Langton's Ant
# Andrew Turpin
import numpy as np

'''
Facing N = 0, E = 1,  S = 2, W = 3
'''
def ant(nrow, ncol, row, col, facing, n):

a = np.zeros((nrow, ncol))

for i in range(n):
if a[row,col] == 0:
a[row,col] = 1
facing = (facing + 1) % 4
else:
a[row,col] = 0
facing = (facing - 1) if facing > 0 else 3

if facing == 0:
row = (row - 1) if row > 0 else (nrow - 1)
elif facing == 2:
row = (row + 1) if row < nrow-1 else 0
elif facing == 1:
col = (col + 1) if col < ncol-1 else 0
else:
col = (col - 1) if col > 0 else (ncol - 1)

return( (row, col))

f_dict = {'N':0, 'E':1, 'S':2, 'W':3}

for i in (1,2,3,4,5):

nrow = int(data[0])
ncol = int(data[1])
row = int(data[2])
col = int(data[3])
facing = f_dict[data[4].strip()]
n = int(data[5])
a = ant(nrow, ncol, row, col, facing, n)
print("{0} {1} sum = {2}".format(i, a, sum(a)))

```

## Question 4 - Melbourne Tram Network

```# With two dictionaries in Python
# Andrew Turpin

import collections
d_r = collections.defaultdict(list)
d_s = collections.defaultdict(list)

for line in data:
s,r = line.split()
d_s[s] += [r]
d_r[r] += [s]

print("Num unique routes     {0}".format(len(set(d_r.keys()))))
print("Num unique stops      {0}".format(len(set(d_s.keys()))))

m = max([len(r) for s,r in d_s.items()])
for s,r in d_s.items():
if len(r) == m:
print("Stop with most routes {0} ({1} routes)".format(s, len(r)))

m = max([len(s) for r,s in d_r.items()])
for r,s in d_r.items():
if len(s) == m:
print("Route with most stops {0} ({1} routes)".format(r, len(s)))

d_rr = collections.defaultdict(list)
for r1 in d_r.keys():
for r2 in d_r.keys():
if r1 != r2:
d_rr[len(set(d_r[r1]) & set(d_r[r2]))] += [[r1, r2]]

m = max(d_rr.keys())

for rr in d_rr[m]:
print("Routes {0} share {1} stops".format(rr, m))
```

## Question 5 - Perfect Shuffle

```# Python
# Bernie Pope
suits = "CDHS"
faces = "A23456789TJQK"

def deck():
return [face + suit for suit in suits for face in faces]

def shuffle(d1, d2):
return [item for index in range(len(d1)) for item in [d1[index], d2[index]]]

def find_lowest(card, deck):
return deck.index(card) + 1

def q1():
return find_lowest('JH', shuffle(deck(), deck()))

def q2():
return find_lowest('4D', shuffle(deck(), deck()))

def shuffle_split(d1, d2):
shuf = shuffle(d1, d2)
return(shuf[:52], shuf[52:])

def q3():
return find_lowest('KD', shuffle(*shuffle_split(deck(), deck())))

def q4():
d1, d2 = deck(), deck()
for _count in range(5):
d1, d2 = shuffle_split(d1, d2)
return find_lowest('QC', d1 + d2)

def q5():
d1, d2 = deck(), deck()
count = 0 # don't count the first shuffle for some reason.
while True:
d1, d2 = shuffle_split(d1, d2)
if (d1 + d2)[51] == 'KS':
return count
count += 1

print(q1())
print(q2())
print(q3())
print(q4())
print(q5())
```

## Question 6 - Jumping Stairs

```# Brute force
# Andrew Turpin
import time
def brute_force():
def comb(n):
'''
Return list of all combs of (1,2,3) of length n
'''
if n > 1:
a1 = [ [1] + x for x in comb(n-1) ]
a2 = [ [2] + x for x in comb(n-1) ]
a3 = [ [3] + x for x in comb(n-1) ]
return(a1 + a2 + a3)
else:
return([[1], [2], [3]])

for N in range(1, 31):
count = 0
start = time()
for n in range(1,N+1):
for a in comb(n):
if sum(a) == N:
#print(a)
count += 1

print("{0:2d} {1:>8} {2}".format(N,count, time() - start))
```
```# Dynamic programming
# Andrew Turpin
import time
def dp():
MAX = 40
required = [0] * (MAX+1)   # require[i] is number of ways to climb i stairs

def climb(target):
if target >= 3:
required[target] += required[target-3]
if target >= 2:
required[target] += required[target-2]
if target >= 1:
required[target] += required[target-1]

return(required[target])

required[0] = 1
for N in range(1, MAX+1):
start = time()
print("{0:2d} {1:>15} {2}".format(N, climb(N), time() - start))

```
```'''
Ferdinand likes to skip up stair cases.

With each skip he can choose to jump 1, 2 or 3 steps at a time.

Ferdinand wonders how many different ways he can ascend a stair case with
N steps such that he starts at the bottom and always lands exactly on the top
step.

Memoisation
Bernie Pope
'''

class Steps(object):
def __init__(self):
self.memo = {}

def steps(self, n):
if n in self.memo:
return self.memo[n]
else:
if n < 0:
result = 0
elif n == 0:
result = 1
else:
result = self.steps(n - 1) + self.steps(n - 2) + self.steps(n - 3)
self.memo[n] = result
return result

s = Steps()
print(" 1 {0}".format(s.steps(1)))
print(" 2 {0}".format(s.steps(2)))
print(" 3 {0}".format(s.steps(3)))
print(" 4 {0}".format(s.steps(4)))
print(" 5 {0}".format(s.steps(5)))
print(" 6 {0}".format(s.steps(6)))
print("10 {0}".format(s.steps(10)))
print("29 {0}".format(s.steps(29)))
print("35 {0}".format(s.steps(35)))

```