Code Masters 2020

2015 Solutions lecture (mp4)

---

2015 Solutions lecture (pdf)

---

2015 Answers

---

Solution code

Q1 Square Roots

---

Q2 Water Pools

---

Q3 Langton's Ant

---

Q4 Melbourne Tram Network

---

Q5 Perfect Shuffle

---

Q6 Jumping Stairs

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

        

###############################
# 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

        

# 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):
    data = open('../data/ant'+str(i)+'.txt').readlines()

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

        

# With two dictionaries in Python
# Andrew Turpin

data = open('trams.txt').readlines()

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

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

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