/* Fastermind
*  By COTO
*  Entry for the Mastermind Horse Battery Staple Challenge
*  Much code, and way too long spent on this. */

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;


public final class Fastermind {
	// Set to true to have a console printout of individual solutions.
	static final boolean SHOW_ALL_OUTPUTS = false;

	// Set to true to have the oracle declare its query strings, pausing for .5 seconds after each.
	static final boolean ORACLE_DECLARES_QUERIES = false;

	// The "full" oracle. This is my implementation. Identical to the reference version except for improvements in
	// efficiency and the option to declare queries.
	static final class FullOracle implements Oracle {
		final char[] chKeyChars;
		final char[] chSortedKeyChars;
		int iQueryCount = 0;

		FullOracle( String sKey ) {
			chKeyChars = sKey.toCharArray();
			chSortedKeyChars = sKey.toCharArray();
			Arrays.sort( chSortedKeyChars );
		}

		public Outcome query( QueryString qsCandidate ) {
			String sCandidate = qsCandidate.contents();

			iQueryCount++;
			if( Fastermind.ORACLE_DECLARES_QUERIES ) {
				System.out.println( "Key: \"" + new String( chKeyChars ) + "\"\nQry: \"" + sCandidate + "\"" );
				try {
					Thread.sleep( 250 );
				} catch( InterruptedException IEx ) { /* ignore */ }
			}

			char[] chCandChars = sCandidate.toCharArray();
			char[] chSortedCandChars = sCandidate.toCharArray();
			Arrays.sort( chSortedCandChars );

			int nMatch = 0;
			int iDomain = Math.min( chCandChars.length, chKeyChars.length );
			for( int i = 0; i < iDomain; i++ )
				if( chCandChars[i] == chKeyChars[i] )
					nMatch++;

			int nCoincide = 0;
			int i1 = 0, i2 = 0;
			while( i1 < chSortedCandChars.length && i2 < chSortedKeyChars.length ) {
				if( chSortedCandChars[i1] == chSortedKeyChars[i2] ) {
					nCoincide++;
					i1++;
					i2++;
				} else if( chSortedCandChars[i1] < chSortedKeyChars[i2] )
					i1++;
				else i2++;
			}
			if( nMatch == chKeyChars.length )
				return Outcome.VALID;

			return new Outcome( nMatch, nCoincide - nMatch );
		}
		int getQueryCount() {
			return iQueryCount;
		}
	}
	// END OF ORACLE ---- <


	static final int UNKNOWN_COUNT = -1;

	static final char ZERO_COUNT_PLACEHOLDER = '-';
	static final char RESOLVED_CHAR_PLACEHOLDER = '+';

	static char[] ALPHABET;
	static String ALPHABET_STRING;
	static List<Integer> ASCENDING_ORDER;

	public static void main( String[] sArgs ) {
		final SortedSet<String> sWords = readInDictionary( "./dict.txt" );

		// Compute the alphabet...
		final Map<Character,Integer> M_CharFrequencies = new HashMap<Character, Integer>( 32 );
		for( String sWord : sWords ) {
			for( char ch : sWord.toCharArray() ) {
				if( M_CharFrequencies.containsKey( ch ) )
					M_CharFrequencies.put( ch, M_CharFrequencies.get( ch ) + 1 );
				else M_CharFrequencies.put( ch, 1 );
			}
		}
		List<Character> chAlphabet = new ArrayList<Character>( M_CharFrequencies.keySet() );
		Collections.sort( chAlphabet, new Comparator<Character>() {
			public int compare( Character ch1, Character ch2 ) {
				return M_CharFrequencies.get( ch2 ) - M_CharFrequencies.get( ch1 );
			}
		});

		ALPHABET = new char[chAlphabet.size()];
		for( int i = 0; i < chAlphabet.size(); i++ )
			ALPHABET[i] = chAlphabet.get( i );

		ALPHABET_STRING = new String( ALPHABET );
		DictionaryDB DDb = new DictionaryDB( sWords.size() );

		// Compute all word metrics...
		final Map<Integer, SortedSet<String>> M_WordsByLength = new HashMap<Integer, SortedSet<String>>( 32 );
		for( String sWord : sWords ) {
			int nChars = sWord.length();
			SortedSet<String> sEnCharWords = M_WordsByLength.get( nChars );
			if( sEnCharWords == null ) {
				sEnCharWords = new TreeSet<String>();
				M_WordsByLength.put( nChars, sEnCharWords );
			}
			sEnCharWords.add( sWord );
			DDb.registerWord( sWord );
		}

		ASCENDING_ORDER = new ArrayList<Integer>( DDb.iMaxWordLength );
		for( int i = 0; i < DDb.iMaxWordLength; i++ )
			ASCENDING_ORDER.add( i );

		// Read in the codes...
		final List<String> sCodes = readInCodesToCrack( "./codes.txt" );
		int nTotalQueries = 0;
		int nDecoded = 0;
		int nMinQueries = Integer.MAX_VALUE;
		int nMaxQueries = 0;
		long iStartTime = System.currentTimeMillis();

		// Main loop. Gets a code, creates full oracle for code, identifies code, moves on.
		for( String sCode : sCodes ) {
			final FullOracle Or = new FullOracle( sCode );
			final int[] iFullCounts = new int[ALPHABET.length],
				iUsedCounts = new int[ALPHABET.length];

			Arrays.fill( iFullCounts, UNKNOWN_COUNT );

			final CharCounter CC = new CharCounter( iFullCounts, iUsedCounts, DDb );

			// Identify location of spaces...
			final int[] iSpaceLocations = getSpaceLocations( Or, CC, DDb.iMaxWordLength );

			CC.setSpaceLocations( iSpaceLocations );

			// Sort words in terms of decreasing length. Solving larger words first works best.
			final String[] sCodeWords = new String[3];
			List<Integer> iToResolve = Arrays.asList( 0, 1, 2 );
			Collections.sort( iToResolve, new Comparator<Integer>() {
				public int compare( Integer I1, Integer I2 ) {
					return CC.iWordLengths[I2] - CC.iWordLengths[I1];
				}
			} );

			for( int iResolveIndex = 0; iResolveIndex < iToResolve.size(); iResolveIndex++ ) {
				int iResolveWord = iToResolve.get( iResolveIndex );
				SortedSet<String> sCodeWordPotentials = M_WordsByLength.get( CC.iWordLengths[iResolveWord] );
				Oracle OrMasked = WordMaskOracle.forCodeWord( Or, CC.iWordLengths, iResolveWord );

				// We clone the full set of potential code words for each word we're resolving. This is a huge waste
				// of time and memory, but c'est la vie.
				sCodeWords[iResolveWord] = resolveCodeWord( new TreeSet<String>( sCodeWordPotentials ), CC, OrMasked,
					iToResolve.subList( iResolveIndex + 1, 3 ) );
			}

			// Check that we've done it correctly...
			if( Or.query( new QueryString( sCodeWords[0] +" "+ sCodeWords[1] +" "+ sCodeWords[2] ) ).isExactMatch ) {
				nTotalQueries += Or.getQueryCount();
				nDecoded++;
				nMinQueries = Math.min( Or.getQueryCount(), nMinQueries );
				nMaxQueries = Math.max( Or.getQueryCount(), nMaxQueries );

				if( SHOW_ALL_OUTPUTS )
					System.out.println( sCode + " OK: " + Or.getQueryCount() + " queries (" + nTotalQueries + " in " +
						nDecoded + " = " + Math.round( nTotalQueries/(double)nDecoded*100. )/100. + ")" );
			} else {
				System.err.println( "Failed to decode: " + sCode );
				System.exit( 1 );
			}
		}

		// Output the only metrics that matter...
		System.out.println( "Decoded " + nDecoded + " items in " + nTotalQueries + " queries (" +
				Math.round( nTotalQueries/(double)nDecoded*100. )/100. + " queries per item).\n" +
			"Time to complete: " + (System.currentTimeMillis() - iStartTime) + " msec\n" );

		System.out.println( "Min queries: " + nMinQueries );
		System.out.println( "Max queries: " + nMaxQueries );
	}

	static SortedSet<String> readInDictionary( String sDictFile ) {
		SortedSet<String> sWords = new TreeSet<String>();
		try {
			BufferedReader BR = new BufferedReader( new FileReader( sDictFile ) );
			String sWord;
			while( (sWord = BR.readLine()) != null )
				sWords.add( sWord );

			BR.close();
		} catch( IOException ioe ) {
			throw new RuntimeException( "could not read contents of dictionary file: " + sDictFile );
		}
		return sWords;
	}

	static List<String> readInCodesToCrack( String sCodesFile ) {
		List<String> sCodes = new LinkedList<String>();
		try {
			BufferedReader BR = new BufferedReader( new FileReader( sCodesFile ) );
			String sCode;
			while( (sCode = BR.readLine()) != null )
				if( !sCode.isEmpty() )
					sCodes.add( sCode );

			BR.close();
		} catch( IOException ioe ) {
			throw new RuntimeException( "could not read contents of codes file: " + sCodesFile );
		}
		return sCodes;
	}

	static String resolveCodeWord( SortedSet<String> sCodeWordPotentials, final CharCounter CC, Oracle Or,
		List<Integer> iOutstandingWords )
	{
		CC.filterByExclusion( sCodeWordPotentials );
		if( sCodeWordPotentials.size() == 1 ) {
			String sCodeWord = sCodeWordPotentials.first();

			CC.commitUsedChars( sCodeWord );
			return sCodeWord;
		}
		CC.filterByNecessity( sCodeWordPotentials, iOutstandingWords );
		if( sCodeWordPotentials.size() == 1 ) {
			String sCodeWord = sCodeWordPotentials.first();

			CC.commitUsedChars( sCodeWord );
			return sCodeWord;
		}

		MappingOracle MOr = new MappingOracle( new OracleWithTackedOnCharCounter( Or, sCodeWordPotentials, CC ),
			sCodeWordPotentials.first().length() );

		FilterFrame FF = new FilterFrame( sCodeWordPotentials, MOr, Or, CC );

		while( true ) {
			FF.queryToResolve();
			if( FF.isResolved() )
				return FF.codeWord();

			int iMatchChar = FF.getOutstandingChar();
			WordSearchType WSTy = WordSearchType.FULL;
			Outcome Oc, Oc2;

			FF.i0 = 0;
			while( FF.i0 < FF.n ) {
				switch( WSTy ) {
				case FULL:
					int nCharsToMatch = Math.min( FF.n - FF.i0, 4 );
					if( !FF.queryIsEfficient( iMatchChar, nCharsToMatch ) ) {
						FF.i0 += nCharsToMatch;
						continue;
					}
					Oc = FF.query( iMatchChar, nCharsToMatch );
					if( FF.isResolved() )
						return FF.codeWord();

					switch( nCharsToMatch ) {
					case 4:
						if( Oc.nMatch == 4 )
							WSTy = WordSearchType.FOUR_MATCHES_IN_NEXT_FOUR;
						else if( Oc.nMatch == 3 )
							WSTy = WordSearchType.THREE_MATCHES_IN_NEXT_FOUR;
						else if( Oc.nMatch == 2 )
							WSTy = WordSearchType.TWO_MATCHES_IN_NEXT_FOUR;
						else if( Oc.nMatch == 1 )
							WSTy = WordSearchType.ONE_MATCH_IN_NEXT_FOUR;
						else FF.filterBy( iMatchChar, false, false, false, false );
						break;

					case 3:
						if( Oc.nMatch == 3 )
							WSTy = WordSearchType.THREE_MATCHES_IN_NEXT_THREE;
						else if( Oc.nMatch == 2 )
							WSTy = WordSearchType.TWO_MATCHES_IN_NEXT_THREE;
						else if( Oc.nMatch == 1 )
							WSTy = WordSearchType.ONE_MATCH_IN_NEXT_THREE;
						else FF.filterBy( iMatchChar, false, false, false );
						break;

					case 2:
						if( Oc.nMatch == 2 )
							WSTy = WordSearchType.TWO_MATCHES_IN_NEXT_TWO;
						else if( Oc.nMatch == 1 )
							WSTy = WordSearchType.ONE_MATCH_IN_NEXT_TWO;
						else FF.filterBy( iMatchChar, false, false );
						break;

					case 1:
						if( Oc.nMatch == 1 )
							WSTy = WordSearchType.ONE_MATCH_IN_NEXT_ONE;
						else FF.filterBy( iMatchChar, false );
						break;
					}
					break;

				case FOUR_MATCHES_IN_NEXT_FOUR:
				case THREE_MATCHES_IN_NEXT_THREE:
					throw new InternalError( "didn't expect this with standard dictionary" );

				case THREE_MATCHES_IN_NEXT_FOUR:
					WSTy = WordSearchType.FULL;
					if( FF.pare( new String[] { "+++-", "++-+", "+-++", "-+++" }, iMatchChar, true ) )
						return FF.codeWord();
					if( !FF.queryIsEfficient( iMatchChar, 2 ) ) {
						FF.i0 += 4;
						break;
					}
					Oc = FF.query( iMatchChar, 2 );
					if( FF.isResolved() )
						return FF.codeWord();

					if( Oc.nMatch == 1 ) {
						if( FF.pare( new String[] { "+-", "-+" }, iMatchChar ) )
							return FF.codeWord();
						if( !FF.queryIsEfficient( iMatchChar, 1 ) ) {
							FF.i0 += 4;
							break;
						}
						Oc = FF.query( iMatchChar, 1 );
						if( FF.isResolved() )
							return FF.codeWord();
						if( Oc.nMatch == 1 )
							FF.filterBy( iMatchChar, true, false, true, true );
						else FF.filterBy( iMatchChar, false, true, true, true );
					} else {
						if( FF.pare( new String[] { "+++-", "++-+" }, iMatchChar ) )
							return FF.codeWord();
						if( !FF.queryIsEfficient( iMatchChar, 3 ) ) {
							FF.i0 += 4;
							break;
						}
						Oc = FF.query( iMatchChar, 3 );
						if( FF.isResolved() )
							return FF.codeWord();
						if( Oc.nMatch == 3 )
							FF.filterBy( iMatchChar, true, true, true, false );
						else FF.filterBy( iMatchChar, true, true, false, true );
					}
					break;

				case TWO_MATCHES_IN_NEXT_FOUR:
					WSTy = WordSearchType.FULL;
					if( FF.pare( new String[] { "++--", "+-+-", "+--+", "-++-", "-+-+", "--++" }, iMatchChar ) )
						return FF.codeWord();
					if( !FF.queryIsEfficient( iMatchChar, 2 ) ) {
						FF.i0 += 4;
						break;
					}

					Oc = FF.query( iMatchChar, 2 );
					if( FF.isResolved() )
						return FF.codeWord();

					if( Oc.nMatch == 2 )
						FF.filterBy( iMatchChar, true, true, false, false );
					else if( Oc.nMatch == 0 )
						FF.filterBy( iMatchChar, false, false, true, true );
					else {
						if( FF.pare( new String[] { "+-+-", "-++-", "+--+", "-+-+" }, iMatchChar ) )
							return FF.codeWord();
						if( !FF.queryIsEfficient( iMatchChar, 1 ) ) {
							FF.i0 += 4;
							break;
						}
						Oc = FF.query( iMatchChar, 1 );
						if( FF.isResolved() )
							return FF.codeWord();

						if( FF.pare( Oc.nMatch == 1 ? new String[] { "+" } : new String[] { "-" }, iMatchChar ) )
							return FF.codeWord();
						if( !FF.queryIsEfficient( iMatchChar, 3 ) ) {
							FF.i0 += 4;
							break;
						}
						Oc2 = FF.query( iMatchChar, 3 );
						if( FF.isResolved() )
							return FF.codeWord();

						if( Oc.nMatch == 1 && Oc2.nMatch == 2 )
							FF.filterBy( iMatchChar, true, false, true, false );
						else if( Oc.nMatch == 1 )
							FF.filterBy( iMatchChar, true, false, false, true );
						else if( Oc2.nMatch == 2 )
							FF.filterBy( iMatchChar, false, true, true, false );
						else FF.filterBy( iMatchChar, false, true, false, true );
					}
					break;

				case ONE_MATCH_IN_NEXT_FOUR:
					WSTy = WordSearchType.FULL;
					if( FF.pare( new String[] { "+---", "-+--", "--+-", "---+" }, iMatchChar ) )
						return FF.codeWord();
					if( !FF.queryIsEfficient( iMatchChar, 2 ) ) {
						FF.i0 += 4;
						break;
					}
					Oc = FF.query( iMatchChar, 2 );
					if( FF.isResolved() )
						return FF.codeWord();

					if( Oc.nMatch == 1 ) {
						if( FF.pare( new String[] { "+-", "-+" }, iMatchChar ) )
							return FF.codeWord();
						if( !FF.queryIsEfficient( iMatchChar, 1 ) ) {
							FF.i0 += 4;
							break;
						}
						Oc = FF.query( iMatchChar, 1 );
						if( FF.isResolved() )
							return FF.codeWord();
						if( Oc.nMatch == 1 )
							FF.filterBy( iMatchChar, true, false, false, false );
						else FF.filterBy( iMatchChar, false, true, false, false );
					} else {
						if( FF.pare( new String[] { "--+-", "---+" }, iMatchChar ) )
							return FF.codeWord();
						if( !FF.queryIsEfficient( iMatchChar, 3 ) ) {
							FF.i0 += 4;
							break;
						}
						Oc = FF.query( iMatchChar, 3 );
						if( FF.isResolved() )
							return FF.codeWord();
						if( Oc.nMatch == 1 )
							FF.filterBy( iMatchChar, false, false, true, false );
						else FF.filterBy( iMatchChar, false, false, false, true );
					}
					break;

				case TWO_MATCHES_IN_NEXT_THREE:
					WSTy = WordSearchType.FULL;
					if( FF.pare( new String[] { "++-", "+-+", "-++" }, iMatchChar ) )
						return FF.codeWord();
					if( !FF.queryIsEfficient( iMatchChar, 2 ) ) {
						FF.i0 += 3;
						break;
					}
					Oc = FF.query( iMatchChar, 2 );
					if( FF.isResolved() )
						return FF.codeWord();

					if( Oc.nMatch == 2 )
						FF.filterBy( iMatchChar, true, true, false );
					else {
						if( FF.pare( new String[] { "+-+", "-++" }, iMatchChar ) )
							return FF.codeWord();
						if( !FF.queryIsEfficient( iMatchChar, 1 ) ) {
							FF.i0 += 3;
							break;
						}
						Oc = FF.query( iMatchChar, 1 );
						if( FF.isResolved() )
							return FF.codeWord();

						if( Oc.nMatch == 1 )
							FF.filterBy( iMatchChar, true, false, true );
						else FF.filterBy( iMatchChar, false, true, true );
					}
					break;

				case ONE_MATCH_IN_NEXT_THREE:
					WSTy = WordSearchType.FULL;
					if( FF.pare( new String[] { "+--", "-+-", "--+" }, iMatchChar ) )
						return FF.codeWord();
					if( !FF.queryIsEfficient( iMatchChar, 1 ) ) {
						FF.i0 += 3;
						break;
					}
					Oc = FF.query( iMatchChar, 1 );
					if( FF.isResolved() )
						return FF.codeWord();

					if( Oc.nMatch == 1 )
						FF.filterBy( iMatchChar, true, false, false );
					else {
						if( FF.pare( new String[] { "-+-", "--+" }, iMatchChar ) )
							return FF.codeWord();
						if( !FF.queryIsEfficient( iMatchChar, 2 ) ) {
							FF.i0 += 3;
							break;
						}
						Oc = FF.query( iMatchChar, 2 );
						if( FF.isResolved() )
							return FF.codeWord();

						if( Oc.nMatch == 1 )
							FF.filterBy( iMatchChar, false, true, false );
						else FF.filterBy( iMatchChar, false, false, true );
					}
					break;

				case TWO_MATCHES_IN_NEXT_TWO:
					WSTy = WordSearchType.FULL;
					FF.filterBy( iMatchChar, true, true );
					break;

				case ONE_MATCH_IN_NEXT_TWO:
					WSTy = WordSearchType.FULL;
					if( FF.pare( new String[] { "+-", "-+" }, iMatchChar ) )
						return FF.codeWord();
					if( !FF.queryIsEfficient( iMatchChar, 1 ) ) {
						FF.i0 += 2;
						break;
					}
					Oc = FF.query( iMatchChar, 1 );
					if( FF.isResolved() )
						return FF.codeWord();

					if( Oc.nMatch == 1 )
						FF.filterBy( iMatchChar, true, false );
					else FF.filterBy( iMatchChar, false, true );
					break;

				case ONE_MATCH_IN_NEXT_ONE:
					WSTy = WordSearchType.FULL;
					FF.filterBy( iMatchChar, true );
				}
				FF.queryToResolve();
				if( FF.isResolved() )
					return FF.codeWord();
			}
			FF.iResolvedChars.add( iMatchChar );
		}
	}

	static String getEnCharMatchString( int iMatchChar, int iCharsToMatch ) {
		char[] chs = new char[iCharsToMatch];

		Arrays.fill( chs, ALPHABET[iMatchChar] );
		return new String( chs );
	}

	static String getSpaceAt( int iSpace ) {
		char[] chs = getPlaceholders( iSpace+1 );
		chs[iSpace] = ' ';
		return new String( chs );
	}

	static char[] getPlaceholders( int iCount ) {
		char[] ch = new char[iCount];

		Arrays.fill( ch, ZERO_COUNT_PLACEHOLDER );
		return ch;
	}

	static List<Integer> getSpaceOneSearchProfile( final int iCodeLength, final boolean in1HE, final boolean in1HO,
		final boolean in2HE, final boolean in2HO )
	{
		final List<Integer> iSites = new LinkedList<Integer>();
		class Vetter {
			void add( int i ) {
				if( i > 0 && i < iCodeLength-1 && (
					(in1HE && (i &1) == 0 && i <= iCodeLength/2) ||
					(in1HO && (i &1) == 1 && i <= iCodeLength/2) ||
					(in2HE && (i &1) == 0 && i > iCodeLength/2) ||
					(in2HO && (i &1) == 1 && i > iCodeLength/2) ) )
				{
					iSites.add( i );
				}
			}
		}

		Vetter V = new Vetter();
		int iSiteM1 = (iCodeLength + 1)/3 - 1,
			iSiteP1 = iSiteM1;

		while( iSiteM1 > 0 || iSiteP1 < iCodeLength-1 ) {
			V.add( iSiteM1-- );
			V.add( ++iSiteP1 );
		}
		return iSites;
	}

	static List<Integer> getSpaceTwoSearchProfile( List<Integer> iSpaceOneProfile, final int iSpace1Location,
		final int iCodeLength, final boolean in1HE, final boolean in1HO, final boolean in2HE, final boolean in2HO )
	{
		final List<Integer> iSites = new LinkedList<Integer>();
		final List<Integer> iSearchedSites = iSpaceOneProfile.subList( 0, iSpaceOneProfile.indexOf( iSpace1Location ) );
		class Vetter {
			void add( int i ) {
				if( i > 0 && i < iCodeLength-1 && !iSearchedSites.contains( i ) &&
					Math.abs( i - iSpace1Location ) > 1 && (
					(in1HE && (i &1) == 0 && i <= iCodeLength/2) ||
					(in1HO && (i &1) == 1 && i <= iCodeLength/2) ||
					(in2HE && (i &1) == 0 && i > iCodeLength/2) ||
					(in2HO && (i &1) == 1 && i > iCodeLength/2) ) )
				{
					iSites.add( i );
				}
			}
		}

		Vetter V = new Vetter();
		int iSiteM1 = iSpace1Location > iCodeLength/2 ? (iSpace1Location + 1)/2 - 1 :
				(iSpace1Location + iCodeLength)/2,
			iSiteP1 = iSiteM1;

		while( iSiteM1 > 0 || iSiteP1 < iCodeLength-1 ) {
			V.add( iSiteM1-- );
			V.add( ++iSiteP1 );
		}
		return iSites;
	}

	static int[] getSpaceLocations( Oracle Or, final CharCounter CC, final int iMaxWordLength ) {
		final int[] iLocations = new int[3];

		StringBuilder SBu = new StringBuilder( ALPHABET.length*iMaxWordLength );
		for( int i = 0; i < iMaxWordLength; i++ )
			SBu.append( new String( ALPHABET ) );

		Outcome Oc = Or.query( new QueryString( createEvenSpaceSieve( iMaxWordLength*3 + 2 ) + SBu.toString() ) );
		int iLength = Oc.nMatch + Oc.nCoincide;

		iLocations[2] = iLength;

		SpaceOracle SOr = new SpaceOracle( Or, CC );
		boolean in1HE = false,
			in1HO = false,
			in2HE = false,
			in2HO = false;

		if( Oc.nMatch == 0 ) {
			in1HO = true;
			in2HO = true;
		} else if( Oc.nMatch == 2 ) {
			in1HE = true;
			in2HE = true;
		} else {
			Oc = SOr.query( new QueryString( createFullSpaceSieve( iLength/2 + 1 ) ) );
			if( Oc.nMatch == 2 ) {
				in1HE = true;
				in1HO = true;
			} else if( Oc.nMatch == 0 ) {
				in2HE = true;
				in2HO = true;
			} else {
				Oc = SOr.query( new QueryString( createEvenSpaceSieve( iLength/2 + 1 ) ) );
				if( Oc.nMatch == 0 ) {
					in1HO = true;
					in2HE = true;
				} else {
					in1HE = true;
					in2HO = true;
				}
			}
		}
		List<Integer> iSpaceOneSearchProfile = getSpaceOneSearchProfile( iLength, in1HE, in1HO, in2HE, in2HO );
		for( int iSite : iSpaceOneSearchProfile ) {
			Oc = SOr.query( new QueryString( getSpaceAt( iSite ), 0, 0 ) );
			if( Oc.nMatch == 1 ) {
				iLocations[0] = iSite;
				break;
			}
		}

		List<Integer> iSpaceTwoSearchProfile = getSpaceTwoSearchProfile( iSpaceOneSearchProfile, iLocations[0],
			iLength, in1HE, in1HO, in2HE, in2HO );

		for( int iSite : iSpaceTwoSearchProfile ) {
			Oc = SOr.query( new QueryString( getSpaceAt( iSite ), 0, 0 ) );
			if( Oc.nMatch == 1 ) {
				iLocations[1] = iSite;
				break;
			}
		}
		if( iLocations[1] < iLocations[0] ) {
			int i = iLocations[1];
			iLocations[1] = iLocations[0];
			iLocations[0] = i;
		}
		return iLocations;
	}

	static String createFullSpaceSieve( int iLength ) {
		char[] chs = new char[iLength];
		Arrays.fill( chs, ' ' );
		return new String( chs );
	}

	static String createEvenSpaceSieve( int iLength ) {
		char[] chs = new char[iLength];
		for( int i = 0; i < iLength; i++ )
			chs[i] = (i &1) == 0 ? ' ' : ZERO_COUNT_PLACEHOLDER;

		return new String( chs );
	}
}


// Enumerated type for the main routine. Makes the code easier to follow.
enum WordSearchType {
	FULL,
	ONE_MATCH_IN_NEXT_ONE,
	ONE_MATCH_IN_NEXT_TWO,
	TWO_MATCHES_IN_NEXT_TWO,
	ONE_MATCH_IN_NEXT_THREE,
	TWO_MATCHES_IN_NEXT_THREE,
	THREE_MATCHES_IN_NEXT_THREE,
	ONE_MATCH_IN_NEXT_FOUR,
	TWO_MATCHES_IN_NEXT_FOUR,
	THREE_MATCHES_IN_NEXT_FOUR,
	FOUR_MATCHES_IN_NEXT_FOUR
}


// Class for computing various relevant word metrics.
class DictionaryDB {
	Map<String,DBEntry> M_Data;
	Map<Integer,int[]> M_MaxCharCountsByWordLength;
	int iMaxWordLength;
	String sDisplacer = null;

	DictionaryDB( int nWords ) {
		M_Data = new HashMap<String, DBEntry>( nWords );
		M_MaxCharCountsByWordLength = new TreeMap<Integer, int[]>();
		iMaxWordLength = 0;
	}

	void registerWord( String sWord ) {
		int iLength = sWord.length();
		int[] iMaxCharCounts;
		iMaxWordLength = Math.max( iMaxWordLength, iLength );

		Map<Integer,Integer> iCharCounts = computeCharCountsForWord( sWord );

		M_Data.put( sWord, new DBEntry( iCharCounts ) );
		iMaxCharCounts = M_MaxCharCountsByWordLength.get( iLength );
		if( iMaxCharCounts == null ) {
			iMaxCharCounts = new int[Fastermind.ALPHABET.length];
			M_MaxCharCountsByWordLength.put( iLength, iMaxCharCounts );
		}
		for( Map.Entry<Integer,Integer> E : iCharCounts.entrySet() ) {
			int iCharIndex = E.getKey();

			iMaxCharCounts[iCharIndex] = Math.max( iMaxCharCounts[iCharIndex], E.getValue() );
		}
	}

	Map<Integer,Integer> charCountsForWord( String sWord ) {
		return M_Data.get( sWord ).M_CharCounts;
	}

	int[] maxCharCountsForWordLength( int iWordLength ) {
		return M_MaxCharCountsByWordLength.get( iWordLength );
	}

	int maxPossibleInstancesOfChar( int[] iWordLengths, int iCharIndex ) {
		if( iWordLengths == null )
			return iMaxWordLength*3;

		int iMaxInstances = 0;
		for( int iWordLength : iWordLengths )
			iMaxInstances += maxCharCountsForWordLength( iWordLength )[iCharIndex];

		return iMaxInstances;
	}

	String displacer() {
		if( sDisplacer == null )
			sDisplacer = new String( Fastermind.getPlaceholders( iMaxWordLength * 3 ) );

		return sDisplacer;
	}

	static class DBEntry {
		final Map<Integer,Integer> M_CharCounts;

		DBEntry( Map<Integer,Integer> M_CharCounts_ ) {
			M_CharCounts = M_CharCounts_;
		}
	}

	static Map<Integer,Integer> computeCharCountsForWord( String sWord ) {
		Map<Integer,Integer> iCounts = new HashMap<Integer, Integer>( sWord.length() );
		for( char ch : sWord.toCharArray() ) {
			int iCharIndex = Fastermind.ALPHABET_STRING.indexOf( ch );

			Integer I = iCounts.get( iCharIndex );
			int iCount = 1;
			if( I != null )
				iCount = I + 1;

			iCounts.put( iCharIndex, iCount );
		}
		return iCounts;
	}
}


// Class for storing known character counts and used character counts, and filtering based on them. Also stores some
// other random data since it's passed around a lot.
class CharCounter {
	int[] iWordLengths;
	final int[] iUsedCounts;
	final int[] iFullCounts;
	final DictionaryDB DDb;

	CharCounter( int[] iFullCounts_, int[] iUsedCounts_, DictionaryDB DDb_ ) {
		iFullCounts = iFullCounts_;
		iUsedCounts = iUsedCounts_;
		DDb = DDb_;
	}

	void setSpaceLocations( int[] iSpaceLocations ) {
		iWordLengths = new int[iSpaceLocations.length];
		for( int iSub = 0, i = 0; i < iWordLengths.length; i++ ) {
			iWordLengths[i] = iSpaceLocations[i] - iSub;
			iSub = iSpaceLocations[i] + 1;
		}
	}

	void commitUsedChars( String sCodeStub ) {
		for( char ch : sCodeStub.toCharArray() )
			iUsedCounts[Fastermind.ALPHABET_STRING.indexOf( ch )]++;
	}

	void commitUsedChars( int iMatchChar, int iUseCount ) {
		iUsedCounts[iMatchChar] += iUseCount;
	}

	void filterByExclusion( SortedSet<String> sCodeWordPotentials ) {
		Iterator<String> ItCodeWordPotentials = sCodeWordPotentials.iterator();
		while( ItCodeWordPotentials.hasNext() ) {
			for( Map.Entry<Integer,Integer> E : DDb.charCountsForWord( ItCodeWordPotentials.next() ).entrySet() ) {
				int iCharIndex = E.getKey();
				if( iFullCounts[iCharIndex] != Fastermind.UNKNOWN_COUNT && E.getValue() > iFullCounts[iCharIndex] -
					iUsedCounts[iCharIndex] )
				{
					ItCodeWordPotentials.remove();
					break;
				}
			}
		}
	}

	void filterByNecessity( SortedSet<String> sCodeWordPotentials, List<Integer> iOutstandingWords ) {
		int[] iFutureSlacks = new int[Fastermind.ALPHABET.length];
		for( int iOutstandingWord : iOutstandingWords ) {
			int[] iCounts = DDb.maxCharCountsForWordLength( iWordLengths[iOutstandingWord] );
			for( int j = 0; j < iCounts.length; j++ )
				iFutureSlacks[j] += iCounts[j];
		}

		List<Integer> I_Deficits = new LinkedList<Integer>();
		for( int i = 0; i < Fastermind.ALPHABET.length; i++ )
			if( iFullCounts[i] != Fastermind.UNKNOWN_COUNT && iFullCounts[i] - iFutureSlacks[i] - iUsedCounts[i] > 0 )
				I_Deficits.add( i );

		if( I_Deficits.isEmpty() )
			return;

		Iterator<String> ItCodeWordPotentials = sCodeWordPotentials.iterator();
		while( ItCodeWordPotentials.hasNext() ) {
			Map<Integer,Integer> M_CharCounts = DDb.charCountsForWord( ItCodeWordPotentials.next() );
			for( Integer I_Deficit : I_Deficits ) {
				int iCount = 0,
					iDeficit = I_Deficit;

				Integer I_Count = M_CharCounts.get( I_Deficit );
				if( I_Count != null )
					iCount = I_Count;

				if( iCount + iUsedCounts[iDeficit] + iFutureSlacks[iDeficit] < iFullCounts[iDeficit] ) {
					ItCodeWordPotentials.remove();
					break;
				}
			}
		}
	}
}


// Class handling most of the complex filtering and querying by the main routine.
class FilterFrame {
	static final int MAX_POTENTIALS_FOR_SPECIFIC_DISCRIMINANT = 150;
	static final int GLOBAL_INEFFICIENCY_DISCOUNT = 3;
	static final double MIN_EFFICIENT_QUERY_POWER = 0.45;

	int i0;
	int n;
	MappingOracle MOr;
	final Oracle OrResolver;
	SortedSet<String> sCodeWordPotentials;
	final List<Integer> iResolvedChars;
	final CharCounter CC;
	int nInefficient = 0;

	FilterFrame( SortedSet<String> sCodeWordPotentials_, MappingOracle MOr_, Oracle OrResolver_, CharCounter CC_ ) {
		i0 = 0;
		sCodeWordPotentials = sCodeWordPotentials_;
		MOr = MOr_;
		OrResolver = OrResolver_;
		CC = CC_;
		n = sCodeWordPotentials.first().length();
		iResolvedChars = new LinkedList<Integer>();
	}

	Outcome query( int iMatchChar, int iMatchCount ) {
		String s = Fastermind.getEnCharMatchString( iMatchChar, iMatchCount );
		QueryString qs = new QueryString( i0 > 0 ? (new String(Fastermind.getPlaceholders( i0 )) + s) : s,
			iMatchChar, iMatchCount );

		Outcome Oc = MOr.query( qs );

		nInefficient = 0;
		checkForExhaustion( iMatchChar );
		commitOutstanding();

		return Oc;
	}

	boolean queryIsEfficient( int iMatchChar, int nMatchCount ) {
		if( sCodeWordPotentials.size() > MAX_POTENTIALS_FOR_SPECIFIC_DISCRIMINANT )
			return true;

		boolean isEfficient = powerOfQuery( iMatchChar, nMatchCount ) >=
			(int)(sCodeWordPotentials.size()*MIN_EFFICIENT_QUERY_POWER) - nInefficient*GLOBAL_INEFFICIENCY_DISCOUNT;

		if( !isEfficient )
			nInefficient++;
		else nInefficient = 0;
		return isEfficient;
	}

	int powerOfQuery( int iMatchChar, int nMatchCount ) {
		Integer[] iIndicesArray = nextEnIndices( nMatchCount );
		char[] chMatchMask = new char[nMatchCount];
		char chMatch = Fastermind.ALPHABET[iMatchChar];

		Map<String,Integer> M_OutcomePowers = new TreeMap<String, Integer>();
		for( String sWord : sCodeWordPotentials ) {
			for( int i = 0; i < nMatchCount; i++ )
				chMatchMask[i] = sWord.charAt( iIndicesArray[i] ) == chMatch ? '+' : '-';

			String sMask = new String( chMatchMask );
			if( M_OutcomePowers.containsKey( sMask ) )
				M_OutcomePowers.put( sMask, M_OutcomePowers.get( sMask ) + 1 );
			else M_OutcomePowers.put( sMask, 1 );
		}
		return sCodeWordPotentials.size() - Collections.max( M_OutcomePowers.values() );
	}

	boolean pare( String[] sMasksArray, int iMatchChar ) {
		return pare( sMasksArray, iMatchChar, false );
	}

	boolean pare( String[] sMasksArray, int iMatchChar, boolean isForce ) {
		if( !isForce && sCodeWordPotentials.size() > MAX_POTENTIALS_FOR_SPECIFIC_DISCRIMINANT )
			return false;

		int nMatchCount = sMasksArray[0].length();
		Integer[] iIndicesArray = nextEnIndices( nMatchCount );
		char[] chMatchMask = new char[nMatchCount];
		char chMatch = Fastermind.ALPHABET[iMatchChar];
		List<String> sMasks = Arrays.asList( sMasksArray );
		Iterator<String> It = sCodeWordPotentials.iterator();
		while( It.hasNext() ) {
			String sWord = It.next();
			for( int i = 0; i < nMatchCount; i++ )
				chMatchMask[i] = sWord.charAt( iIndicesArray[i] ) == chMatch ? '+' : '-';

			if( !sMasks.contains( new String( chMatchMask ) ) )
				It.remove();
		}

		if( sCodeWordPotentials.size() == 1 )
			commitOutstanding();
		else queryToResolve();

		return sCodeWordPotentials.size() == 1;
	}

	Integer[] nextEnIndices( int n_ ) {
		List<Integer> iIndices = new LinkedList<Integer>();
		for( int i = 0; i < n_; i++ )
			iIndices.add( i0 + i );

		return MOr.map( iIndices ).toArray( new Integer[n_] );
	}

	void commitOutstanding() {
		if( sCodeWordPotentials.size() == 1 )
			CC.commitUsedChars( MOr.substring( sCodeWordPotentials.first() ) );
	}

	static final int[][] PERMS3_MODULO_12ORDER = {
		{ 0, 1, 2 }, { 0, 2, 1 }, { 1, 2, 0 }
	};

	static final int[][] PERMS4_MODULO_12ORDER = {
		{ 0, 1, 2, 3 }, { 0, 1, 3, 2 }, { 0, 2, 1, 3 }, { 0, 2, 3, 1 }, { 0, 3, 1, 2 }, { 0, 2, 2, 1 },
		{ 1, 2, 0, 3 }, { 1, 2, 3, 0 }, { 1, 3, 0, 2 }, { 1, 3, 2, 0 }, { 2, 3, 0, 1 }, { 2, 3, 1, 0 }
	};

	void queryToResolve() {
		char[] ch;
		String[] sWords;

		if( sCodeWordPotentials.first().length() == 1 ) {
			String sCodeWord = sCodeWordPotentials.last();

			sCodeWordPotentials.remove( sCodeWord );
			for( String sWord : sCodeWordPotentials ) {
				if( OrResolver.query( new QueryString( sWord ) ).nMatch == 1 ) {
					sCodeWord = sWord;
					break;
				}
			}
			sCodeWordPotentials.clear();
			sCodeWordPotentials.add( sCodeWord );
			commitOutstanding();
			return;
		}

		switch( sCodeWordPotentials.size() ) {
		case 2:
			sWords = sCodeWordPotentials.toArray( new String[2] );
			ch = Fastermind.getPlaceholders( sWords[0].length() );
			for( int i = 0; i < sWords[0].length(); i++ )
				if( sWords[0].charAt( i ) != sWords[1].charAt( i ) ) {
					ch[i] = sWords[0].charAt( i );
					break;
				}

			sCodeWordPotentials.remove( OrResolver.query(new QueryString( ch )).nMatch == 1 ? sWords[1] : sWords[0] );
			commitOutstanding();
			break;

		case 3:
		case 4:
			final int nWords = sCodeWordPotentials.size();

			sWords = sCodeWordPotentials.toArray( new String[nWords] );
			for( int[] iWords : nWords == 3 ? PERMS3_MODULO_12ORDER : PERMS4_MODULO_12ORDER ) {
				int[] iMeet = { -1, -1, -1 };

				for( int i = 0; i < sWords[0].length(); i++ ) {
					char ch0 = sWords[iWords[0]].charAt( i ),
						ch1 = sWords[iWords[1]].charAt( i ),
						ch2 = sWords[iWords[2]].charAt( i );

					if( nWords == 3 ) {
						if( ch0 != ch2 )
							iMeet[ch0 == ch1 ? 1 : 0] = i;
					} else {
						char ch3 = sWords[iWords[3]].charAt( i );
						if( ch0 != ch3 ) {
							if( ch0 == ch1 && ch0 == ch2 )
								iMeet[2] = i;
							else if( ch0 == ch1 )
								iMeet[1] = i;
							else if( ch0 != ch2 )
								iMeet[0] = i;
						}
					}
				}
				if( iMeet[0] != -1 && iMeet[1] != -1 && (nWords == 3 || iMeet[2] != -1) ) {
					ch = Fastermind.getPlaceholders( sWords[0].length() );
					ch[iMeet[0]] = sWords[iWords[0]].charAt( iMeet[0] );
					ch[iMeet[1]] = sWords[iWords[1]].charAt( iMeet[1] );
					if( nWords == 4 )
						ch[iMeet[2]] = sWords[iWords[2]].charAt( iMeet[2] );

					int nMatch = nWords - 1 - OrResolver.query( new QueryString( ch ) ).nMatch;

					sCodeWordPotentials.clear();
					sCodeWordPotentials.add( sWords[iWords[nMatch]] );
					commitOutstanding();
					return;
				}
			}
		}
	}

	int nResetsDueToExhaustedPool = 0;

	int getOutstandingChar() {
		int nChars = Fastermind.ALPHABET.length;
		if( sCodeWordPotentials.size() <= MAX_POTENTIALS_FOR_SPECIFIC_DISCRIMINANT ) {
			int[] iOutstandingCharCounts = new int[nChars];
			for( String sWord : sCodeWordPotentials )
				for( Map.Entry<Integer,Integer> E : CC.DDb.charCountsForWord( sWord ).entrySet() )
					iOutstandingCharCounts[E.getKey()] += E.getValue();

			List<IndexedInteger> II_OutstandingCharCounts = new ArrayList<IndexedInteger>( nChars );
			for( int i = 0; i < nChars; i++ )
				if( iOutstandingCharCounts[i] > 0 )
					II_OutstandingCharCounts.add( new IndexedInteger( iOutstandingCharCounts[i], i ) );

			Collections.sort( II_OutstandingCharCounts, new Comparator<IndexedInteger>() {
				public int compare( IndexedInteger II1, IndexedInteger II2 ) {
					return II2.i - II1.i;
				}
			} );

			for( IndexedInteger II : II_OutstandingCharCounts ) {
				if( !iResolvedChars.contains( II.iIndex ) &&
					CC.iUsedCounts[II.iIndex] != CC.iFullCounts[II.iIndex] &&
					CC.iFullCounts[II.iIndex] != Fastermind.UNKNOWN_COUNT )
				{
					return II.iIndex;
				}
			}
		} else {
			for( int iIndex = 0; iIndex < nChars; iIndex++ )
				if( !iResolvedChars.contains( iIndex ) &&
					CC.iUsedCounts[iIndex] != CC.iFullCounts[iIndex] &&
					CC.iFullCounts[iIndex] != Fastermind.UNKNOWN_COUNT )
				{
					return iIndex;
				}
		}
		if( iResolvedChars.isEmpty() ) {
			MOr.query( new QueryString( Fastermind.ALPHABET_STRING.substring( 0, 1 ), 0, 1 ) );
			nResetsDueToExhaustedPool++;
			if( nResetsDueToExhaustedPool > 10 )
				throw new InternalError( "perpetually exhausting pool" );
		} else {
			iResolvedChars.remove( 0 );
		}
		return getOutstandingChar();
	}

	void filterBy( int iMatchChar, boolean... isAt ) {
		List<Integer> iOns = new LinkedList<Integer>(),
			iOffs = new LinkedList<Integer>();

		for( int i = 0; i < isAt.length; i++ ) {
			if( isAt[i] )
				iOns.add( i0 + i );
			else iOffs.add( i0 + i );
		}
		if( !iOffs.isEmpty() )
			filterByCharExclusion( iMatchChar, iOffs );
		if( !isResolved() && !iOns.isEmpty() )
			filterByCharInclusion( iMatchChar, iOns );

		if( isResolved() ) {
			commitOutstanding();
			n = i0 = 0;
		} else {
			CC.commitUsedChars( iMatchChar, iOns.size() );
			i0 += iOffs.size();
			if( !iOns.isEmpty() ) {
				n -= iOns.size();
				MOr = MappingOracle.oracleForResolvedCharsAt( MOr, iOns );
			}
			checkForExhaustion( iMatchChar );
			if( isResolved() ) {
				commitOutstanding();
				n = i0 = 0;
			}
		}
	}

	void filterByCharExclusion( int iMatchChar, List<Integer> iCharIndices ) {
		filterByCharWhateverclusion( iMatchChar, iCharIndices, false );
	}

	void filterByCharInclusion( int iMatchChar, List<Integer> iCharIndices ) {
		filterByCharWhateverclusion( iMatchChar, iCharIndices, true );
	}

	void filterByCharWhateverclusion( int iMatchChar, List<Integer> iCharIndices, boolean isInclusion ) {
		char chMatch = Fastermind.ALPHABET[iMatchChar];
		Iterator<String> ItCodeWordPotentials = sCodeWordPotentials.iterator();

		iCharIndices = MOr.map( iCharIndices );

		while( ItCodeWordPotentials.hasNext() ) {
			String sCodeWord = ItCodeWordPotentials.next();

			for( int iCharIndex : iCharIndices )
				if( (sCodeWord.charAt( iCharIndex ) == chMatch) != isInclusion ) {
					ItCodeWordPotentials.remove();
					break;
				}
		}
	}

	void checkForExhaustion( int iMatchChar ) {
		if( CC.iUsedCounts[iMatchChar] == CC.iFullCounts[iMatchChar] )
			filterByCharExclusion( iMatchChar, Fastermind.ASCENDING_ORDER.subList( 0, MOr.getUnresolvedIndexCount() ) );
	}

	boolean isResolved() {
		assert !sCodeWordPotentials.isEmpty();
		return sCodeWordPotentials.size() == 1;
	}

	String codeWord() {
		return sCodeWordPotentials.first();
	}

	static final class IndexedInteger {
		int i;
		int iIndex;

		IndexedInteger( int i_, int iIndex_ ) {
			i = i_;
			iIndex = iIndex_;
		}
	}
}


// Class encapsulates an outcome by the oracle: number of matches, number of "coincidences" (characters present in
// both strings but not in matching locations).
class Outcome implements Comparable<Outcome> {
	final int nMatch;
	final int nCoincide;
	final boolean isExactMatch;

	static final Outcome VALID = new Outcome();

	private Outcome() {
		nMatch = -1;
		nCoincide = -1;
		isExactMatch = true;
	}

	Outcome( int nMatch_, int nCoincide_ ) {
		nMatch = nMatch_;
		nCoincide = nCoincide_;
		isExactMatch = false;
	}

	public int compareTo( Outcome Oc ) {
		return nMatch < Oc.nMatch ? -1 : (nMatch > Oc.nMatch ? 1 : (nCoincide < Oc.nCoincide ? -1 :
			(nCoincide > Oc.nCoincide ? 1 : 0)));
	}

	public boolean equals( Object o ) {
		if( !(o instanceof Outcome) )
			return false;

		Outcome Oc = (Outcome)o;
		return Oc.nMatch == nMatch && Oc.nCoincide == nCoincide;
	}

	public int hashCode() {
		return nMatch*37 + nCoincide;
	}
}


// Oracle interface. An oracle is the machine that spits out the relevant match data when queried with a specific
// string.
interface Oracle {
	Outcome query( QueryString qsCandidate );
}


// A string with extra data attached. Needed to avoid headaches in passing data between the many nested oracles. Not
// elegant, but gets the job done.
class QueryString {
	final String s;
	final int iIndex;
	final int nCount;

	QueryString( String s_ )
		{ this( s_, -1, -1 ); }
	QueryString( char[] chs )
		{ this( new String( chs ), -1, -1 ); }
	QueryString( char[] chs, int iIndex_, int nCount_ )
		{ this( new String( chs ), iIndex_, nCount_ ); }
	QueryString( String s_, int iIndex_, int nCount_ ) {
		s = s_;
		iIndex = iIndex_;
		nCount = nCount_;
	}

	String contents() {
		return s;
	}

	QueryString append( String s_ ) {
		return s_.isEmpty() ? this : new QueryString( s + s_, iIndex, nCount );
	}

	QueryString prepend( String s_ ) {
		return s_.isEmpty() ? this : new QueryString( s_ + s, iIndex, nCount );
	}
}


// Simple hook on the input and output to an oracle.
abstract class FilteredOracle implements Oracle {
	final Oracle Or;

	FilteredOracle( Oracle Or_ ) {
		Or = Or_;
	}

	abstract QueryString localStringToOracleString( QueryString qsLocal );

	abstract Outcome oracleOutcomeToLocalOutcome( Outcome Oc );

	public Outcome query( QueryString qsCandidate ) {
		return oracleOutcomeToLocalOutcome( Or.query( localStringToOracleString( qsCandidate ) ) );
	}
}


// Simple oracle shifts test characters into the position of a specific word.
class WordMaskOracle extends FilteredOracle {
	final String sPrefix;
	final Outcome OcBaseline;

	WordMaskOracle( Oracle Or_, String sPrefix_, Outcome OcBaseline_ ) {
		super( Or_ );
		sPrefix = sPrefix_;
		OcBaseline = OcBaseline_;
	}

	@Override QueryString localStringToOracleString( QueryString qsLocal ) {
		return qsLocal.prepend( sPrefix );
	}

	@Override Outcome oracleOutcomeToLocalOutcome( Outcome Oc ) {
		return new Outcome( Oc.nMatch - OcBaseline.nMatch, Oc.nCoincide - OcBaseline.nCoincide );
	}

	static Oracle forCodeWord( Oracle Or_, int[] iWordLengths, int iCodeWord ) {
		switch( iCodeWord ) {
		case 0:
			return Or_;
		case 1:
			return new WordMaskOracle( Or_, new String( Fastermind.getPlaceholders( iWordLengths[0] + 1 ) ),
				new Outcome( 0, 0 ) );
		case 2:
			return new WordMaskOracle( Or_, new String( Fastermind.getPlaceholders( iWordLengths[0] +
				iWordLengths[1] + 2 ) ), new Outcome( 0, 0 ) );
		}
		throw new InternalError();
	}
}


// Simpler version of the OracleWithTackedOnCharCounter. This one also tacks on a character counter, but is
// sufficiently different to warrant its own class.
final class SpaceOracle extends FilteredOracle {
	final CharCounter CC;
	int iFullQueryCharIndex;
	boolean areAllCharsQueried;
	QueryString qsStored;

	SpaceOracle( Oracle Or_, CharCounter CC_ ) {
		super( Or_ );
		CC = CC_;
	}

	@Override QueryString localStringToOracleString( QueryString qsLocal ) {
		if( areAllCharsQueried )
			return qsLocal;

		qsStored = qsLocal;
		for( iFullQueryCharIndex = 0; iFullQueryCharIndex < Fastermind.ALPHABET.length; iFullQueryCharIndex++ ) {
			if( CC.iFullCounts[iFullQueryCharIndex] == Fastermind.UNKNOWN_COUNT )
				return qsLocal.append( CC.DDb.displacer() + Fastermind.getEnCharMatchString( iFullQueryCharIndex,
					CC.DDb.maxPossibleInstancesOfChar( null, iFullQueryCharIndex ) ) );
		}
		areAllCharsQueried = true;
		return qsLocal;
	}

	@Override Outcome oracleOutcomeToLocalOutcome( Outcome Oc ) {
		if( areAllCharsQueried )
			return Oc;

		CC.iFullCounts[iFullQueryCharIndex] = Oc.nMatch + Oc.nCoincide - 1 + qsStored.nCount;
		return new Outcome( Oc.nMatch, 1 - Oc.nMatch );
	}
}


// Oracle with a tacked on character counter. The name says it all. ;)
final class OracleWithTackedOnCharCounter extends FilteredOracle {
	final CharCounter CC;
	final SortedSet<String> sCodeWordPotentials;
	int iFullQueryCharIndex;
	boolean areAllCharsQueried;
	QueryString qsStoredLocal;

	OracleWithTackedOnCharCounter( Oracle Or_, SortedSet<String> sCodeWordPotentials_, CharCounter CC_ ) {
		super( Or_ );
		sCodeWordPotentials = sCodeWordPotentials_;
		CC = CC_;
		iFullQueryCharIndex = 0;
	}

	@Override QueryString localStringToOracleString( QueryString qsLocal ) {
		if( areAllCharsQueried )
			return qsLocal;

		qsStoredLocal = qsLocal;
		for( ; iFullQueryCharIndex < Fastermind.ALPHABET.length; iFullQueryCharIndex++ ) {
			if( CC.iFullCounts[iFullQueryCharIndex] == Fastermind.UNKNOWN_COUNT ) {
				assert iFullQueryCharIndex > 0;
				return qsLocal.append( CC.DDb.displacer() + Fastermind.getEnCharMatchString( iFullQueryCharIndex,
					CC.DDb.maxPossibleInstancesOfChar( CC.iWordLengths, iFullQueryCharIndex ) ) );
			}
		}
		areAllCharsQueried = true;
		return qsLocal;
	}

	@Override Outcome oracleOutcomeToLocalOutcome( Outcome Oc ) {
		if( areAllCharsQueried )
			return Oc;

		int iImpliedCount = Oc.nMatch + Oc.nCoincide;
		int iCharIndex = qsStoredLocal.iIndex;

		assert CC.iFullCounts[iCharIndex] != Fastermind.UNKNOWN_COUNT;
		iImpliedCount -= Math.min( CC.iFullCounts[iCharIndex], qsStoredLocal.nCount );

		CC.iFullCounts[iFullQueryCharIndex] = iImpliedCount;
		if( iImpliedCount == 0 )
			filterByTotalCharExclusion( iFullQueryCharIndex );

		return new Outcome( Oc.nMatch, iImpliedCount - CC.iUsedCounts[iFullQueryCharIndex] );
	}

	void filterByTotalCharExclusion( int iMatchChar ) {
		char chMatch = Fastermind.ALPHABET[iMatchChar];
		Iterator<String> ItCodeWordPotentials = sCodeWordPotentials.iterator();

		while( ItCodeWordPotentials.hasNext() ) {
			if( ItCodeWordPotentials.next().indexOf( chMatch ) != -1 )
				ItCodeWordPotentials.remove();
		}
	}
}


// Oracle that handles mapping characters around "gaps" formed by resolved characters from prior guesses.
final class MappingOracle extends FilteredOracle {
	static final int[] NO_OFFSETS = new int[0];

	final int[] iOffsets;
	final char[] chMapped;
	final int iMaxMapLength;
	final int nResolved;

	MappingOracle( Oracle Or_, int iMaxMapLength_ ) {
		super( Or_ );
		iOffsets = NO_OFFSETS;
		nResolved = 0;
		chMapped = Fastermind.getPlaceholders( iMaxMapLength_ );
		iMaxMapLength = iMaxMapLength_;
	}

	MappingOracle( Oracle Or_, int[] iOffsets_, char[] chMapped_, int nResolved_ ) {
		super( Or_ );
		iOffsets = iOffsets_;
		chMapped = chMapped_;
		nResolved = nResolved_;
		iMaxMapLength = chMapped_.length;
	}

	List<Integer> map( List<Integer> iCharIndices ) {
		if( iOffsets == NO_OFFSETS )
			return iCharIndices;

		List<Integer> iMappedIndices = new ArrayList<Integer>( iCharIndices.size() );

		for( int iIndex : iCharIndices )
			iMappedIndices.add( map( iIndex ) );

		return iMappedIndices;
	}

	int map( int iIndex ) {
		if( iOffsets == NO_OFFSETS )
			return iIndex;

		return iIndex >= iOffsets.length ? (iIndex + iOffsets[iOffsets.length-1] - (iOffsets.length-1)) :
			iOffsets[iIndex];
	}

	String substring( String sWord ) {
		if( iOffsets == NO_OFFSETS )
			return sWord;

		StringBuilder SBu = new StringBuilder( sWord.length() );

		int iSub = 0,
			iMapped = map( iSub );

		while( iMapped < sWord.length() ) {
			SBu.append( sWord.charAt( iMapped ) );
			iMapped = map( ++iSub );
		}
		return SBu.toString();
	}

	int getUnresolvedIndexCount() {
		return iMaxMapLength - nResolved;
	}

	@Override QueryString localStringToOracleString( QueryString qsLocal ) {
		if( iOffsets == NO_OFFSETS )
			return qsLocal;

		char[] chOracle = new char[iMaxMapLength];
		String sLocal = qsLocal.contents();

		System.arraycopy( chMapped, 0, chOracle, 0, iMaxMapLength );
		for( int i = 0; i < sLocal.length(); i++ )
			chOracle[map( i )] = sLocal.charAt( i );

		return new QueryString( chOracle, qsLocal.iIndex, qsLocal.nCount );
	}

	@Override Outcome oracleOutcomeToLocalOutcome( Outcome Oc ) {
		return Oc;
	}

	static MappingOracle oracleForResolvedCharsAt( Oracle Or_, List<Integer> iResolvedChars ) {
		if( Or_ instanceof MappingOracle ) {
			MappingOracle MOr = (MappingOracle)Or_;
			iResolvedChars = MOr.map( iResolvedChars );

			char[] chMappedNew;

			chMappedNew = new char[MOr.iMaxMapLength];
			System.arraycopy( MOr.chMapped, 0, chMappedNew, 0, MOr.iMaxMapLength );
			for( int iResolvedChar : iResolvedChars )
				chMappedNew[iResolvedChar] = Fastermind.RESOLVED_CHAR_PLACEHOLDER;

			List<Integer> iOffsetsNew = new LinkedList<Integer>();
			int iTo = 0;
			for( ; iTo < chMappedNew.length; iTo++ )
				if( chMappedNew[iTo] == Fastermind.ZERO_COUNT_PLACEHOLDER ) {
					iOffsetsNew.add( iTo );
				}

			iOffsetsNew.add( iTo );
			int[] iOffsetsNewArray = new int[iOffsetsNew.size()];
			int i = 0;
			for( int iOffset : iOffsetsNew )
				iOffsetsNewArray[i++] = iOffset;

			return new MappingOracle( MOr.Or, iOffsetsNewArray, chMappedNew, MOr.nResolved + iResolvedChars.size() );
		}
		throw new InternalError( "didn't expect this" );
	}
}