Solutions for 2014
2014 Solutions lecture (Quicktime)
Solution code
Q1 PrimesQ2 Anagrams
Q3 Voting
Q4 Postcode
Q5 Overlap
Q6 Histogram
Q7 Pocket Money
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[1])
sqrt_n = int(math.floor(math.sqrt(n)))
flags = [True for x in range(0, n+1)]
flags[0] = flags[1] = 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[1])
primes = [2]
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[0]=b[1]=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()[0]
#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
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
Question 6 - Histogram
# Python using "extend left and right" method
# Andrew Turpin, April 2014
import sys
hist = []
with open(sys.argv[1]) as file:
for line in file:
hist += [int(line.strip())]
n = len(hist)
max_so_far = hist[0]
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[1]) 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[1]) as votes_file:
for line in votes_file:
expression = line.strip()
print maximise(expression)