Top coder open (TCO) 2014 – 500 problem

Elly is playing Scrabble with her family. The exact rules of the game are not important for this problem. You only need to know that Elly has a holder that contains a row of N tiles, and that there is a single letter on each of those tiles. (Tiles are small square pieces of wood. A holder is a tiny wooden shelf with room for precisely N tiles placed in a row.)… [More...]

As many others I came up with a simple greedy heuristic. We can simply find the characters one by one starting from the left. Suppose we want to find the i-th character. We just look at maxDistance characters on the left and maxDistance on the right and we take the smallest letter. We loop through all the letters and we get the whole sequence.

There are however two caveats. First, we need to make sure that we use all letters. Imagine maxDistance = 2 and letters ZAAA. With the algorithm described above we have a problem while choosing the last character. Lets look what happens

  • Iteration 1: Candidates ZAA, we choose A, the string so far is just A
  • Iteration 2: Candidates ZAA (one A is gone), we choose A, the string so far is just AA
  • Iteration 3: Candidates ZA (two As are gone), we choose A, the string so far is just AAA
  • Iteration 4: ERROR! We ran out of candidates!

To avoid this situation we simply need to use the first character of the list when it is the last chance to use it. Then the last to iterations are

  • Iteration 3: Candidates ZA (two As are gone), we must choose Z, the string so far is just AAZ
  • Iteration 4: Candidates A, we choose A, the string so far is just AAZA

The second caveat is that, whenever there is more than one smallest letter than we take the one from the left. This will give us more possibilities later on.

It’s quite easy to prove that this strategy gives the optimal solution.

My sub-optimal and sub-pretty Java

import java.util.Arrays;

public class EllysScrabble {
	public String getMin(String letters, int maxDistance) {
		StringBuilder newstring = new StringBuilder(letters);
		StringBuilder oldstring = new StringBuilder(letters);

		for (int i = 0; i < letters.length(); i++){
			int start = Math.max(i - maxDistance, 0);
			int end = Math.min(i + maxDistance + 1, letters.length());
			char[] candidates = new char[end - start];
			oldstring.getChars(start, end, candidates, 0);

			if ((start == i - maxDistance) && candidates[0] != '['){
				newstring.setCharAt(i, candidates[0]);
				continue;
			}

			Arrays.sort(candidates);
			newstring.setCharAt(i, candidates[0]);
			
			for (int j = start; j < end; j++){
				if (oldstring.charAt(j) == candidates[0]){
					oldstring.setCharAt(j, '[');
					break;
				}
			}
		}
		return newstring.toString();
	}
}

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>