## Question 1 - Primes

```        #
# Sieve of Eratosthenes in Python
# Runs "forwards", thus uses a lot of memory
# Andrew Turpin
# April 2014
#
import sys
import math

n = int(sys.argv)
sqrt_n = int(math.floor(math.sqrt(n)))

flags = [True for x in range(0, n+1)]
flags = flags = False

for i in range(2, sqrt_n+1):
if flags[i]:
isq = i * i
for j in range(0,n):
kill = isq + j*i
if kill > n:
break
flags[kill] = False

print(sum(flags))
```
```        #
# Sieve of Eratosthenes in Python
# Runs "backwards"
# Andrew Turpin
# April 2014
#
import sys

n = int(sys.argv)

primes = 
for i in range(3, n):
#if i % 100000 == 0: print "... {0}".format(i)   # progress reporter
i_is_prime = True
for j in primes:
if j*j > i:
break
if i % j == 0:
i_is_prime = False
break
if i_is_prime:
primes.append(i)

print(len(primes))
```
```        // Forward in C++
// April 24th 2014
// Author: Simon Gog
#include
#include
#include

using namespace std;

int main(){
uint32_t n;
while ( cin>>n ){
vector b(n+1, true);
b=b=false;
for ( uint32_t i=2; i*i <= n; ++i){
for (uint32_t j=2*i; j<=n; j+=i){
b[j]=false;
}
}
uint32_t res=0;
for(uint32_t i=0; i
```

## Question 2 - Anagrams

```        #
# Python
# Tony Wirth, April 2014
#
for i in range(1,6):
f = open('anagram'+str(i)+'.txt','r')

dict = {}
for line in f:
w = line.split()
#print w
lw = list(w)
lw.sort()
lws = ''.join(lw)
if lws not in dict:
dict[lws] = []
dict[lws].append(w)

print(len(dict))
```
```        // C++
// Author: Simon Gog, April 24th 2014
#include
#include
#include
#include

using namespace std;

int main(){
vector vs;
string s;
while ( cin>>s ){
sort(s.begin(),s.end());
vs.push_back(s);
}
sort(vs.begin(),vs.end());
auto it = std::unique (vs.begin(), vs.end());
cout << it-vs.begin() << endl;
}
```

## Question 3 - Voting

```        // C++
// Author: Simon Gog, April 24th 2014
#include
#include
#include

using namespace std;

int main(){
string pre, sur;
map m;
map mss;
while ( cin >> pre >> sur ){
auto s=sur+pre;
mss[s] = pre+" "+sur;
m[s]++;
}
string best;
for(auto x : m ){
if ( x.second >= m[best] ){
best=x.first;
}
}
cout << mss[best] << endl;
}
```

## Question 4 - Postcodes

```        #
# In R
# Read students*.txt and postcodes, join on suburb
# Print most popular postcode, break ties alphabetically.
#
# Andrew Turpin
# Sun 23 Mar 2014 06:36:30 EST
#

pcs  <- read.csv("postcodes.txt", strings=FALSE)

for(f in 1:5) {
stus <- read.csv(paste0("students",f,".csv"), strings=FALSE)

# find postcodes for students
z <- sapply(stus\$Suburb, function(s) which(pcs\$Suburb == s) )
p <- as.numeric(pcs[z,"PostCode"])

#k <- cbind(stus, p)

t <- table(p)    # count frequencies of postcodes
freq <- max(t)   # find max freq

ps <- which(t == freq) # get all postcodes with max freq
ps <- as.numeric(names(ps))
print(ps[order(ps)])
}
```
```        # In awk
#
# Read students on stdin and postcodes, join on suburb
# Print most popular postcode, break ties alphabetically.
#
# Andrew Turpin
# Sun 23 Mar 2014 07:39:03 EST
#

BEGIN {
FS = ","
while ((getline < "postcodes.txt") == 1) {
pc[\$1] = \$2               # each sub has only one pc
ns[\$2]++                  # num suburbs with this postcode
suburb[\$2":"ns[\$2]] = \$1  # a postcode can have multi subs
}
}

NR==1 { next}

{ count[pc[\$2]]++ }   # freq count of postcodes

END {
# find max freq
max = 0
for(postcode in count)
if (count[postcode] > max)
max = count[postcode]

# put all names of suburbs with max freq postcode in
# candidates[]. Note one pc could have mulitple PCs
for(postcode in count)
if (count[postcode] == max) {
for (i=1;i<=ns[postcode];i++)
candidates[suburb[postcode":"i]] = postcode
}

print "################## candidates"
for (sb in candidates)
print sb " "candidates[sb]
}
```

## Question 5 - Overlap

```        // C++
// Author: Simon Gog, 24th April 2014
#include
#include
#include

using namespace std;

int main(){
map m; // map
size_t call=0;
size_t s,e;
while ( cin>>s>>e ){
m[2*e]++;
m[2*s+1]++;
++call;
}
size_t active = 0;
size_t max_active = 0;
for ( auto x : m ){
size_t time = x.first/2;
if ( x.first % 2 == 0 ){ // end call
active -= x.second;
} else { // start call
active += x.second;
if ( active > max_active )
max_active = active;
}
}
cout << max_active << endl;
}

```

## Question 6 - Histogram

```        # Python using "extend left and right" method
# Andrew Turpin, April 2014
import sys

hist = []
with open(sys.argv) as file:
for line in file:
hist += [int(line.strip())]

n = len(hist)
max_so_far = hist
for i in range(0, n):
current = hist[i]

# go right as far as possible
j = i+1
while j < n and hist[j] >= hist[i]:
current += hist[i]
j += 1

# go left as far as possible
j = i-1
while j >= 0 and hist[j] >= hist[i]:
current += hist[i]
j -= 1

if current > max_so_far:
max_so_far = current

print(max_so_far)
```
```        # Python using "divide and conquer" method
# Andrew Turpin, April 2014
import sys

hist = []
with open(sys.argv) as file:
for line in file:
hist += [int(line.strip())]

def minR(left, right):
if left > right:
return 0

global hist
if left == right:
return(hist[left])

lowI = left
low = hist[left]
for i in range(left+1, right+1):
if hist[i] < low:
low = hist[i]
lowI = i

h0 = (right-left+1)  * low
h1 = minR(left, lowI-1)
h2 = minR(lowI+1, right)

return(max(h0,h1,h2))

print (minR(0,len(hist)-1))
```

## Question 7 - Pocket Money

```        # Python
# Dynamic Programming
# Andrew Turpin, April 2014
import sys

def maximise(e):
if len(e) == 1:
return(int(e))

max = -1
for i in range(1,len(e), 2):
left = e[:i]
right = e[i+1:]
if e[i] == '+':
temp = maximise(left) + maximise(right)
else:
temp = maximise(left) * maximise(right)
if temp > max:
max = temp

return(max)

with open(sys.argv) as votes_file:
for line in votes_file:
expression = line.strip()
print maximise(expression)

```