Solutions for 2014

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 

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