Proposed Java Solution

From Beautifulcode

This is a Java solution to the challenge. There are a number of issues/trade-offs that are not considered in the original challenge, and proposals for handling those situations are included here.

(a) Why you believe your solution works ?

1) New characters are passed to a sufficiently-sized BlockingQueue (not created/controlled by the player, so it cannot be corrupted/extended). This ensure fast response to a new character by each Thread (as the Queue can hold all incremental characters without "add" blocking)

2) Each solution is validated in the user thread (penalizing only the individual user for slow Solution [interface] response code and submitting bad solutions), but in referee (thus not player-controlled) code. The user submitted Solution is also not trusted to return the proper character count (the validated count is returned by the validation method). Assumption: Validation is fast, to the point where extra validation is not considered an unreasonable penalty, yet it is still slower than producing a false solution object; thus Validation must remain in the Player Thread. (See Beautiful #7 and Potential Improvements #3 for effects of this assumption)

3) Good solutions are submitted by the referee code (but the Player Thread) through a BlockingQueue (thread safety is not an issue, because we have only one reader of the queue). Good solutions are then acted upon (trigger go or winner declaration) in the master Referee Thread

4) Calls to "go" in CompetitorThread and the "start()" of each thread are as tight as possible, to avoid any calculation overhead that takes place in the Referee code (and Referee Thread) from unreasonably impacting a participant

(b) What makes it beautiful ?

1) No explicit synchronization (controlled through queues)

2) Each player can control if they choose to ignore a new character event (there are algorithms that may wish to temporarily ignore new characters if they are building hashes/lookups or use incremental algorithms to attempt to place new characters).

3) There is a user penalty for doing excessive calculation when the dictionary is added (Since it is added while the competitive thread is running). However, dictionary addition is a separate method, so that it allows easy modification if such assumptions are changed (e.g. allow a set time to load the dictionary before the competition starts).

4) Separation without lookup. Items which are global to the referee are controlled in the Referee class, there is a "trusted" Class that controls master information for each participant (e.g. the character list) [CompetitorThread] and then the player code is in a third Class. The master information for each participant is not placed in the IPlayScrabble Class so that references & Objects passed during construction cannot be poached by child classes of IPlayScrabble. Since the Thread starts with a zero-argument call to run() that doesn't allow information to be passed, use of the separate Class avoids expensive or confusing callbacks to the referee (which would be using a Hashtable or other lookup to index Competitor-specific information).

5) Security. The methods that trigger "go", declaring a winner, passing character lists, etc. cannot be accessed by the player code to cause cheating. Additionally, while not implemented below, Security could be used to prevent reflection use that could result in more subtle corruption or cheating. The dictionary is shared, but unmodifiable and unsynchronized.

6) Character calculation is done "up front", which reduces excessive "go" processing delay, which could penalize some algorithms vs. others (the thread that called "go" is probably waiting for a character, but others may be performing work that is still relevant after a new character is provided)

7) The validation step is a separate method; thus it could easily be moved to the Referee Thread, if desired (though this is not advised, as submission of large numbers of false solutions could be used to delay calls to "go" in order to get extra time for indexing/preprocessing)

8) No assumptions are made about how the user wishes to store the board (arrays, Lists, etc. etc.), all queries are done through the Submission interface (not developed in this example)

Potential Improvements

(1) Beautification: Field/parameter names could be vastly improved for clarity, ditto adding comments.

(2) Ability to run more than one competition with one Referee

(3) Interrupting Validation: There is a potential pool of wasted processing due to the decision to make validation part of the user thread. The events are: Player 1 submits solution, solution is validated, solution is placed in good solution queue to trigger "go", Player 2 submits solution with same # of characters, go is actually triggered (passing new characters), player 2 solution is validated. Player 2 is penalized in this case, so a solution that allows two player threads (a management thread and a run thread) and a validation routine that could be interrupted by having a rescindSolution() in SolutionSubmitter may be able to overcome this issue if validation is considered or found to be excessively slow.

(4) Variable length games (partially implemented)

public interface Solution {
	// Methods for extracting character count, words & locations left as an exercise for the reader
}

public interface Referee {
	void submitSolution(CompetitorThread submitter, Solution solution);
	List<String> getMasterDictionary();
}

public interface SolutionSubmitter {
	void submitSolution(Solution s);
}

public class SpeedScabbleReferee implements Referee {

	private final Queue<Submission> goodSolutions = new LinkedBlockingQueue<Submission>();

	private final List<String> masterDictionary;

	private int currentMaximumSolved;

	private List<CompetitorThread> threadList;

	public SpeedScabbleReferee(List<String> dictionary) {
		masterDictionary = Collections.unmodifiableList(new ArrayList<String>(
				dictionary));
	}

	public void startCompetition(IPlayScrabble... ipsarray) {
		if (currentMaximumSolved != -1) {
			throw new IllegalStateException();
		}
		currentMaximumSolved = 6;
		threadList = new ArrayList<CompetitorThread>(ipsarray.length);
		for (IPlayScrabble competitor : ipsarray) {
			CompetitorThread competitorThread = new CompetitorThread(this,
					competitor, getRandomCharacterList(15));
			threadList.add(competitorThread);
		}
		goodSolutions.clear();
		for (CompetitorThread thread : threadList) {
			thread.start();
		}
		runCompetition(15);
		currentMaximumSolved = -1;
	}

	private void runCompetition(int max) {
		while (true) {
			Submission submission = goodSolutions.poll();
			int charCount = submission.getCharacterCount();
			if (charCount == max) {
				declareWinner(submission.getCompetitorThread(), submission.getSolution());
				break;
			} else {
				if (charCount > currentMaximumSolved) {
					int newCount = charCount + 1;
					if (newCount == currentMaximumSolved) {
						currentMaximumSolved = newCount;
						for (CompetitorThread thread1 : threadList) {
							thread1.go(currentMaximumSolved);
						}
					} else {
						// Serious error, left as an exercise for the reader
					}
				}
			}
		}
	}

	private List<Character> getRandomCharacterList(int max) {
		// Solution left as an exercise for the reader
		return null;
	}

	private int validateSolution(CompetitorThread submitter, Solution s) {
		// Solution left as an exercise for the reader
		return 0;
	}

	public void submitSolution(CompetitorThread submitter, Solution solution) {
		int solutionCount = validateSolution(submitter, solution);
		if (solutionCount > 0) {
			goodSolutions
					.add(new Submission(submitter, solution, solutionCount));
		}
	}

	private void declareWinner(CompetitorThread ips2, Solution s) {
		// Solution left as an exercise for the reader
	}

	public List<String> getMasterDictionary() {
		return masterDictionary;
	}

	private static class Submission {

		private final CompetitorThread ct;

		private final Solution s;

		private final int charCount;

		public Submission(CompetitorThread submitter, Solution solution,
				int count) {
			ct = submitter;
			s = solution;
			charCount = count;
		}

		public CompetitorThread getCompetitorThread() {
			return ct;
		}

		public Solution getSolution() {
			return s;
		}

		public int getCharacterCount() {
			return charCount;
		}
	}
}

class CompetitorThread extends Thread implements SolutionSubmitter {

	private final IPlayScrabble ips;

	private final List<Character> characterList;

	private final Referee referee;

	public CompetitorThread(Referee ref, IPlayScrabble competitor, List<Character> chars) {
		if (competitor == null) {
			throw new IllegalArgumentException();
		}
		if (ref == null) {
			throw new IllegalArgumentException();
		}
		if (chars == null) {
			throw new IllegalArgumentException();
		}
		characterList = new ArrayList<Character>(chars);
		ips = competitor;
		referee = ref;
	}

	public void go(int newCount) {
		ips.getQueue().add(characterList.get(newCount));
	}

	@Override
	public void run() {
		ips.setDictionary(referee.getMasterDictionary());
		ips.startCompetition(Collections.unmodifiableList(characterList.subList(0, 7)));
	}

	public void submitSolution(Solution s) {
		referee.submitSolution(this, s);
	}

	public List<Character> getCharacterList() {
		return characterList;
	}

}

public abstract class IPlayScrabble {

	private final BlockingQueue<Character> queue = new ArrayBlockingQueue<Character>(8);

	private final SolutionSubmitter acceptor;

	public IPlayScrabble(SolutionSubmitter ssr) {
		if (ssr == null) {
			throw new IllegalArgumentException();
		}
		acceptor = ssr;
	}

	public final void addCharacter(Character c) {
		queue.add(c);
	}

	public final void submitSolution(Solution s) {
		acceptor.submitSolution(s);
	}

	public abstract void setDictionary(List<String> dictionary);

	public abstract void startCompetition(List<Character> startingCharacters);

	public abstract void stopPlaying();

	public final BlockingQueue<Character> getQueue() {
		return queue;
	}

}