QMUL Programming Competition 2016

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:

String input = "<a href=\"B\"<a href=\"A\">"; // Test input

// Array of links found
ArrayList<String> links = new ArrayList<String>();

// Pattern to match any digit and any trailing zeroes
Pattern p = Pattern.compile("<a href=\"([^\"]+?)\">");

Matcher m = p.matcher(input);
while(m.find()) {
    if(!links.contains(m.group(1))) {
        links.add(m.group(1));
    }
}

Collections.sort(links);

for(String s : links) {
    System.out.println(s);
}

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:

String output = "";

int bit_mask = Integer.parseInt("01101110", 2); // Parse as base 2

int position = 0;
while(position < message.length()) {
    String bitStr = message.substring(position, position + 8);

    int num = Integer.parseInt(bitStr, 2); // Parse as base 2
    num = num ^ bit_mask; // XOR

    output += (char) num;

    position += 8;
}

System.out.println(output);

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:

public static void main(String[] args) {
  int n = 2; // Test values
  int m = 11;

  int count = 0;
  while(count < n) { // Keep going until we have enough primes
      if(checkPrime(++m)) count++; // Count the number of primes we find
  }

  System.out.println(m);
}

// Really simple prime check
public static boolean checkPrime(int num) {
    int sqrt = (int) Math.floor(Math.sqrt(num));

    for(int i = 2; i <= sqrt; i++) {
        if(num % i == 0) return false;
    }

    return true;
}

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:

String input = "310110"; // Test input

// Pattern to match any digit and any trailing zeroes
Pattern p = Pattern.compile("([0-9]0*)");

Matcher m = p.matcher(input);

float sum = 0;
float count = 0;
while(m.find()) {
    sum += Integer.parseInt(m.group(0));
    count++;
}

if(count != 0) System.out.printf("%.02f", sum / count);

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.

Example input and representation

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!

int[][] map = { // Test data
    { 3, 2, 2 },
    { 1, 3, 2 }
};

int rows = map.length;
int columns = map[0].length;

int total = 0;

// First: Add the EAST and WEST walls
// Iterate loop along rows
for(int i = 0; i < rows; i++) {
    // Get first and last cubes in the row
    total += map[i][0];
    total += map[i][columns - 1];
}

// Second: Add the NORTH and SOUTH walls
// Iterate loop along columns
for(int i = 0; i < columns; i++) {
    // Get top and bottom cubes in a column
    total += map[0][i];
    total += map[rows - 1][i];
}

// Third: Find all EAST to WEST inner walls
for(int i = 0; i < rows; i++) {
    for(int j = 0; j < columns - 1; j++) {
        if(map[i][j] > map[i][j + 1]) {
            total += map[i][j] - map[i][j + 1];
        } else {
            total += map[i][j + 1] - map[i][j];
        }
    }
}

// Fourth: Find all NORTH to SOUTH inner walls
for(int j = 0; j < columns; j++) {
    for(int i = 0; i < rows - 1; i++) {
        if(map[i][j] > map[i + 1][j]) {
            total += map[i][j] - map[i + 1][j];
        } else {
            total += map[i + 1][j] - map[i][j];
        }
    }
}

System.out.println(total);

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:

int[][] map = { // Test data
    { 3, 2, 2 },
    { 1, 3, 2 }
};

int rows = map.length;
int columns = map[0].length;

int total = 0;

for(int i = -1; i < rows; i++) {
    for(int j = -1; j < columns; j++) {

        // EAST to WEST
        if((j == -1 || j == columns - 1) && i != -1) {
            total += map[i][(j == -1 ? 0 : columns - 1)];
        } else if(i != -1) {
            total += Math.abs(map[i][j] - map[i][j + 1]);
        }

        // NORTH to SOUTH
        if((i == -1 || i == rows - 1) && j != -1) {
            total += map[(i == -1 ? 0 : rows - 1)][j];
        } else if(j != -1) {
            total += Math.abs(map[i][j] - map[i + 1][j]);
        }
    }
}

System.out.println(total);

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:

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:

class Main {
    // Number of rooms
    private int numColors = 3;
    // Number of people
    private int numNodes = 7;
    // People and who they cannot share a room with
    private int[][] nodes = {
            {2, 5, 7},
            {3, 4},
            {5, 6},
            {},
            {2, 3},
            {4},
            {2}
        };

    // Keep track of assigned colors, 0 means unassigned
    private int[] solution = new int[numNodes];

    public static void main(String[] args) {
        // Solve it
        if((new Main()).solve(0)) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }

    public boolean solve(int node) {
        // We solved all nodes!
        if(node == numNodes) {
            return true;
        }

        // Try all colors for this node
        for(int color = 1; color <= numColors; color++) {
            if(checkNode(node, color)) {
                // We found a possible solution for this node, lets check the rest...

                // Our possible color
                solution[node] = color;

                // Let's check the rest of the nodes
                if(solve(node + 1)) {
                    // If it works, then we have a solution
                    return true;
                } else {
                    // If not, let's reset our color and keep looking
                    solution[node] = 0;
                }
            }
        }

        return false; // No solution found
    }

    private boolean checkNode(int node, int color) {
        // Iterate over all connections to node
        for(int i = 0; i < nodes[node].length; i++) {
            int adjacent = nodes[node][i] - 1;
            // If connected node has the same color, it's not valid
            if(solution[adjacent] == color) return false;
        }

        // No clashes found, all good
        return true;
    }
}

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.