# QMUL Programming Competition 2016

Ryan Welch / January 30, 2016

11 min read • – views

Last week, I along with two friends, Marcello and Chris, competed in the Queen Mary University programming competition. We did quite well. In fact, we won!

The competition was made up of six challenging problems to which we had to think up a solution, implement the solution and submit it to be tested against a ruthless online judge. We were competing against 19 teams, from first year students to fourth year students. I thought it would be interesting to go through the problems as well as the approaches we took.

## The online judge

We incurred a *lot* of penalty time. Although we tested the entries our biggest problem was not handling all edge cases as well as strange bugs. Admittedly that was partly due to not reading the questions properly.

For each problem we also had to parse the input from standard input and parse the data to be able to solve it. I haven't included this in the solutions since it was specific to the competition.

## Problem 1

This was a relatively simple problem, the task was to parse some HTML input and extract all the links in a specified format (ignoring duplicates) and then print them out in alphabetical order.

Our algorithm worked something like this:

problem1.java

1String input = "<a href=\"B\"<a href=\"A\">"; // Test input23// Array of links found4ArrayList<String> links = new ArrayList<String>();56// Pattern to match any digit and any trailing zeroes7Pattern p = Pattern.compile("<a href=\"([^\"]+?)\">");89Matcher m = p.matcher(input);10while(m.find()) {11if(!links.contains(m.group(1))) {12links.add(m.group(1));13}14}1516Collections.sort(links);1718for(String s : links) {19System.out.println(s);20}21

The interesting part here is the regular expression which does all the heavy lifting by finding the links in the text. `([^"]+?)`

is our capture group, which captures the link it finds which must be inside the `a`

tag. The `[^"]`

means match any character that isn't a speech mark, the `+`

means at least 1 or more characters and the `?`

stops the regular expression from being greedy and matching everything between the first tag and the last tag.

## Problem 2

A little more complex than the last problem, it required taking a string of bits where each 8 bits formed a character in a secret string. Each 8 bits was XOR-ed against a given set of bits.

Here's a snippet of java code:

problem2.java

1String output = "";23int bit_mask = Integer.parseInt("01101110", 2); // Parse as base 245int position = 0;6while(position < message.length()) {7String bitStr = message.substring(position, position + 8);89int num = Integer.parseInt(bitStr, 2); // Parse as base 210num = num ^ bit_mask; // XOR1112output += (char) num;1314position += 8;15}1617System.out.println(output);18

We tried a few things to convert a string of binary into something we could work with in java before we found that `Integer.parseInt`

had a radix (base) parameter we could use.

## Problem 3

The classic, finding prime numbers but with a twist. In this case we had to find the nth prime number after a prime number which we were given.

For example if n is 2, and our starting prime number is 11, then the answer is 17 as it is the second prime number after 11.

Here's the relveant code:

problem3.java

1public static void main(String[] args) {2int n = 2; // Test values3int m = 11;45int count = 0;6while(count < n) { // Keep going until we have enough primes7if(checkPrime(++m)) count++; // Count the number of primes we find8}910System.out.println(m);11}1213// Really simple prime check14public static boolean checkPrime(int num) {15int sqrt = (int) Math.floor(Math.sqrt(num));1617for(int i = 2; i <= sqrt; i++) {18if(num % i == 0) return false;19}2021return true;22}23

The prime checking algorithm could probably be improved on, but since we had limited time we were just focused on getting the problems done.

## Problem 4

The challenge for this problem was to split a string of digits into numbers where each numbers is between 1 and 10. Therefore each digit is a number unless it has a trailing 0, in which case it is the digit plus the 0.

For example, given the input "310110", the output would be "3 10 1 10". Then we had to calculate the average of these numbers and return the result to two decimal places.

You guessed it, here's the code:

problem4.java

1String input = "310110"; // Test input23// Pattern to match any digit and any trailing zeroes4Pattern p = Pattern.compile("([0-9]0*)");56Matcher m = p.matcher(input);78float sum = 0;9float count = 0;10while(m.find()) {11sum += Integer.parseInt(m.group(0));12count++;13}1415if(count != 0) System.out.printf("%.02f", sum / count);16

The regex again is the most important part, in this case it would be trivial to use a loop and check if the next digit is a zero since the only number possible with two digits is a "10". However since we had already used regex in problem 1, I chose to go with the above solution also using regex. This solution also has the added bonus of being more flexible against longer inputs of trailing 0s.

The built-in java formatting in `printf`

was very useful and definitely worthwhile knowing how to use.

## Problem 5

We spent a while working on the algorithm for this problem, longer than the others, and it took some trial and error. We had some annoying bugs in our code which took a while to track down. In this problem we are asked to calculate the surface area of the walls in a 3d arrangement of cubes. Our input consists of a 2d matrix which contains height data for each position.

Here's the java solution similar to the one we submitted, it's very rough but it works which is what's important when you're under pressure!

problem5.java

1int[][] map = { // Test data2{ 3, 2, 2 },3{ 1, 3, 2 }4};56int rows = map.length;7int columns = map[0].length;89int total = 0;1011// First: Add the EAST and WEST walls12// Iterate loop along rows13for(int i = 0; i < rows; i++) {14// Get first and last cubes in the row15total += map[i][0];16total += map[i][columns - 1];17}1819// Second: Add the NORTH and SOUTH walls20// Iterate loop along columns21for(int i = 0; i < columns; i++) {22// Get top and bottom cubes in a column23total += map[0][i];24total += map[rows - 1][i];25}2627// Third: Find all EAST to WEST inner walls28for(int i = 0; i < rows; i++) {29for(int j = 0; j < columns - 1; j++) {30if(map[i][j] > map[i][j + 1]) {31total += map[i][j] - map[i][j + 1];32} else {33total += map[i][j + 1] - map[i][j];34}35}36}3738// Fourth: Find all NORTH to SOUTH inner walls39for(int j = 0; j < columns; j++) {40for(int i = 0; i < rows - 1; i++) {41if(map[i][j] > map[i + 1][j]) {42total += map[i][j] - map[i + 1][j];43} else {44total += map[i + 1][j] - map[i][j];45}46}47}4849System.out.println(total);50

There's plenty of room for improvement in this code, and after playing about with it now, I came up with the following improved code:

problem5.java

1int[][] map = { // Test data2{ 3, 2, 2 },3{ 1, 3, 2 }4};56int rows = map.length;7int columns = map[0].length;89int total = 0;1011for(int i = -1; i < rows; i++) {12for(int j = -1; j < columns; j++) {1314// EAST to WEST15if((j == -1 || j == columns - 1) && i != -1) {16total += map[i][(j == -1 ? 0 : columns - 1)];17} else if(i != -1) {18total += Math.abs(map[i][j] - map[i][j + 1]);19}2021// NORTH to SOUTH22if((i == -1 || i == rows - 1) && j != -1) {23total += map[(i == -1 ? 0 : rows - 1)][j];24} else if(j != -1) {25total += Math.abs(map[i][j] - map[i + 1][j]);26}27}28}2930System.out.println(total);31

The code is a bit obscure and certainly some of the expressions and in-line if statements make it hard to follow however it's much smaller than the previous code. While it's hard to come up with this code straight away, it would certainly be much faster to write.

## Problem 6

Unfortunately we did not get time to implement the solution to this during the competition, however for the sake of completion I've decided to write a solution for it. In my opinion this is the most interesting question in the programming competition, it is based on a NP complete problem, specifically the question is a graph colouring problem.

We are given two variables, M and N, where the former is the number of rooms and the latter is the number of people. Then we are given a series of lines with lists of numerical IDs, each line corresponds to one person and the numerical IDs in the line are the people that they cannot be in a room with.

For example:

```
13
27
32 5 7
43 4
55 6
6
72 3
84
92
10
```

Means that there are 3 rooms and 7 people. Person 1 cannot share a room with person 2, 5 or 7. Person 2 cannot share a room with person 3 or 4, and so on.

This is a graph colouring problem, we create a graph where each person is a node and each line connecting the nodes is a relationship where those two people cannot be in the same room. We then attempt to colour the graph so that two connected nodes do not have the same colour using only a certain amount of colours. The amount of colours we can use are the number of rooms in the problem.

Below is a commented example program that will solve the above problem:

problem6.java

1class Main {2// Number of rooms3private int numColors = 3;4// Number of people5private int numNodes = 7;6// People and who they cannot share a room with7private int[][] nodes = {8{2, 5, 7},9{3, 4},10{5, 6},11{},12{2, 3},13{4},14{2}15};1617// Keep track of assigned colors, 0 means unassigned18private int[] solution = new int[numNodes];1920public static void main(String[] args) {21// Solve it22if((new Main()).solve(0)) {23System.out.println("YES");24} else {25System.out.println("NO");26}27}2829public boolean solve(int node) {30// We solved all nodes!31if(node == numNodes) {32return true;33}3435// Try all colors for this node36for(int color = 1; color <= numColors; color++) {37if(checkNode(node, color)) {38// We found a possible solution for this node, lets check the rest...3940// Our possible color41solution[node] = color;4243// Let's check the rest of the nodes44if(solve(node + 1)) {45// If it works, then we have a solution46return true;47} else {48// If not, let's reset our color and keep looking49solution[node] = 0;50}51}52}5354return false; // No solution found55}5657private boolean checkNode(int node, int color) {58// Iterate over all connections to node59for(int i = 0; i < nodes[node].length; i++) {60int adjacent = nodes[node][i] - 1;61// If connected node has the same color, it's not valid62if(solution[adjacent] == color) return false;63}6465// No clashes found, all good66return true;67}68}69

This solution can be applied to any graph coloring problem. During the competition we did not realise that the problem was a graph colouring problem and so we spent time trying to think of efficient solutions to no avail.

That was it, all 6 problems. We never thought we would do so well, but we proved ourselves wrong, it was a fun experience and I hope to enter more competitions in the future. Feel free to use any of the solutions from this post.