Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* 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" );
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement