API tools faq
paste
Advertisement
Guest User

COTO Mastermind Java Code

a guest
Aug 29th, 2014
400
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 47.60 KB | None | 0 0
raw download clone embed print report
  1. /* Fastermind
  2. *  By COTO
  3. *  Entry for the Mastermind Horse Battery Staple Challenge
  4. *  Much code, and way too long spent on this. */
  5.  
  6. import java.io.BufferedReader;
  7. import java.io.FileReader;
  8. import java.io.IOException;
  9. import java.util.*;
  10.  
  11.  
  12. public final class Fastermind {
  13.     // Set to true to have a console printout of individual solutions.
  14.     static final boolean SHOW_ALL_OUTPUTS = false;
  15.  
  16.     // Set to true to have the oracle declare its query strings, pausing for .5 seconds after each.
  17.     static final boolean ORACLE_DECLARES_QUERIES = false;
  18.  
  19.     // The "full" oracle. This is my implementation. Identical to the reference version except for improvements in
  20.     // efficiency and the option to declare queries.
  21.     static final class FullOracle implements Oracle {
  22.         final char[] chKeyChars;
  23.         final char[] chSortedKeyChars;
  24.         int iQueryCount = 0;
  25.  
  26.         FullOracle( String sKey ) {
  27.             chKeyChars = sKey.toCharArray();
  28.             chSortedKeyChars = sKey.toCharArray();
  29.             Arrays.sort( chSortedKeyChars );
  30.         }
  31.  
  32.         public Outcome query( QueryString qsCandidate ) {
  33.             String sCandidate = qsCandidate.contents();
  34.  
  35.             iQueryCount++;
  36.             if( Fastermind.ORACLE_DECLARES_QUERIES ) {
  37.                 System.out.println( "Key: \"" + new String( chKeyChars ) + "\"\nQry: \"" + sCandidate + "\"" );
  38.                 try {
  39.                     Thread.sleep( 500 );
  40.                 } catch( InterruptedException IEx ) { /* ignore */ }
  41.             }
  42.  
  43.             char[] chCandChars = sCandidate.toCharArray();
  44.             char[] chSortedCandChars = sCandidate.toCharArray();
  45.             Arrays.sort( chSortedCandChars );
  46.  
  47.             int nMatch = 0;
  48.             int iDomain = Math.min( chCandChars.length, chKeyChars.length );
  49.             for( int i = 0; i < iDomain; i++ )
  50.                 if( chCandChars[i] == chKeyChars[i] )
  51.                     nMatch++;
  52.  
  53.             int nCoincide = 0;
  54.             int i1 = 0, i2 = 0;
  55.             while( i1 < chSortedCandChars.length && i2 < chSortedKeyChars.length ) {
  56.                 if( chSortedCandChars[i1] == chSortedKeyChars[i2] ) {
  57.                     nCoincide++;
  58.                     i1++;
  59.                     i2++;
  60.                 } else if( chSortedCandChars[i1] < chSortedKeyChars[i2] )
  61.                     i1++;
  62.                 else i2++;
  63.             }
  64.             return new Outcome( nMatch, nCoincide - nMatch );
  65.         }
  66.         int getQueryCount() {
  67.             return iQueryCount;
  68.         }
  69.     }
  70.     // END OF ORACLE ---- <
  71.  
  72.  
  73.     static final int UNKNOWN_COUNT = -1;
  74.  
  75.     static final char ZERO_COUNT_PLACEHOLDER = '-';
  76.     static final char RESOLVED_CHAR_PLACEHOLDER = '+';
  77.  
  78.     static char[] ALPHABET;
  79.     static String ALPHABET_STRING;
  80.     static List<Integer> ASCENDING_ORDER;
  81.  
  82.     public static void main( String[] sArgs ) {
  83.         final SortedSet<String> sWords = readInDictionary( "./dict.txt" );
  84.  
  85.         // Compute the alphabet...
  86.         final Map<Character,Integer> M_CharFrequencies = new HashMap<Character, Integer>( 32 );
  87.         for( String sWord : sWords ) {
  88.             for( char ch : sWord.toCharArray() ) {
  89.                 if( M_CharFrequencies.containsKey( ch ) )
  90.                     M_CharFrequencies.put( ch, M_CharFrequencies.get( ch ) + 1 );
  91.                 else M_CharFrequencies.put( ch, 1 );
  92.             }
  93.         }
  94.         List<Character> chAlphabet = new ArrayList<Character>( M_CharFrequencies.keySet() );
  95.         Collections.sort( chAlphabet, new Comparator<Character>() {
  96.             public int compare( Character ch1, Character ch2 ) {
  97.                 return M_CharFrequencies.get( ch2 ) - M_CharFrequencies.get( ch1 );
  98.             }
  99.         });
  100.  
  101.         ALPHABET = new char[chAlphabet.size()];
  102.         for( int i = 0; i < chAlphabet.size(); i++ )
  103.             ALPHABET[i] = chAlphabet.get( i );
  104.  
  105.         ALPHABET_STRING = new String( ALPHABET );
  106.         DictionaryDB DDb = new DictionaryDB( sWords.size() );
  107.  
  108.         // Compute all word metrics...
  109.         final Map<Integer, SortedSet<String>> M_WordsByLength = new HashMap<Integer, SortedSet<String>>( 32 );
  110.         for( String sWord : sWords ) {
  111.             int nChars = sWord.length();
  112.             SortedSet<String> sEnCharWords = M_WordsByLength.get( nChars );
  113.             if( sEnCharWords == null ) {
  114.                 sEnCharWords = new TreeSet<String>();
  115.                 M_WordsByLength.put( nChars, sEnCharWords );
  116.             }
  117.             sEnCharWords.add( sWord );
  118.             DDb.registerWord( sWord );
  119.         }
  120.  
  121.         ASCENDING_ORDER = new ArrayList<Integer>( DDb.iMaxWordLength );
  122.         for( int i = 0; i < DDb.iMaxWordLength; i++ )
  123.             ASCENDING_ORDER.add( i );
  124.  
  125.         // Read in the codes...
  126.         final List<String> sCodes = readInCodesToCrack( "./codes.txt" );
  127.         int nTotalQueries = 0;
  128.         int nDecoded = 0;
  129.         int nMinQueries = Integer.MAX_VALUE;
  130.         int nMaxQueries = 0;
  131.         long iStartTime = System.currentTimeMillis();
  132.  
  133.         // Main loop. Gets a code, creates full oracle for code, identifies code, moves on.
  134.         for( String sCode : sCodes ) {
  135.             final FullOracle Or = new FullOracle( sCode );
  136.             final int[] iFullCounts = new int[ALPHABET.length],
  137.                 iUsedCounts = new int[ALPHABET.length];
  138.  
  139.             Arrays.fill( iFullCounts, UNKNOWN_COUNT );
  140.  
  141.             final CharCounter CC = new CharCounter( iFullCounts, iUsedCounts, DDb );
  142.  
  143.             // Identify location of spaces...
  144.             final int[] iSpaceLocations = getSpaceLocations( Or, CC, DDb.iMaxWordLength );
  145.  
  146.             CC.setSpaceLocations( iSpaceLocations );
  147.  
  148.             // Sort words in terms of decreasing length. Solving larger words first works best.
  149.             final String[] sCodeWords = new String[3];
  150.             List<Integer> iToResolve = Arrays.asList( 0, 1, 2 );
  151.             Collections.sort( iToResolve, new Comparator<Integer>() {
  152.                 public int compare( Integer I1, Integer I2 ) {
  153.                     return CC.iWordLengths[I2] - CC.iWordLengths[I1];
  154.                 }
  155.             } );
  156.  
  157.             for( int iResolveIndex = 0; iResolveIndex < iToResolve.size(); iResolveIndex++ ) {
  158.                 int iResolveWord = iToResolve.get( iResolveIndex );
  159.                 SortedSet<String> sCodeWordPotentials = M_WordsByLength.get( CC.iWordLengths[iResolveWord] );
  160.                 Oracle OrMasked = WordMaskOracle.forCodeWord( Or, CC.iWordLengths, iResolveWord );
  161.  
  162.                 // We clone the full set of potential code words for each word we're resolving. This is a huge waste
  163.                 // of time and memory, but c'est la vie.
  164.                 sCodeWords[iResolveWord] = resolveCodeWord( new TreeSet<String>( sCodeWordPotentials ), CC, OrMasked,
  165.                     iToResolve.subList( iResolveIndex + 1, 3 ) );
  166.             }
  167.  
  168.             // Check that we've done it correctly...
  169.             if( sCode.equals( sCodeWords[0] + " " + sCodeWords[1] + " " + sCodeWords[2] ) ) {
  170.                 nTotalQueries += Or.getQueryCount();
  171.                 nDecoded++;
  172.                 nMinQueries = Math.min( Or.getQueryCount(), nMinQueries );
  173.                 nMaxQueries = Math.max( Or.getQueryCount(), nMaxQueries );
  174.  
  175.                 if( SHOW_ALL_OUTPUTS )
  176.                     System.out.println( sCode + " OK: " + Or.getQueryCount() + " queries (" + nTotalQueries + " in " +
  177.                         nDecoded + " = " + Math.round( nTotalQueries/(double)nDecoded*100. )/100. + ")" );
  178.             } else {
  179.                 System.err.println( "Failed to decode: " + sCode );
  180.                 System.exit( 1 );
  181.             }
  182.         }
  183.  
  184.         // Output the only metrics that matter...
  185.         System.out.println( "Decoded " + nDecoded + " items in " + nTotalQueries + " queries (" +
  186.                 Math.round( nTotalQueries/(double)nDecoded*100. )/100. + " queries per item).\n" +
  187.             "Time to complete: " + (System.currentTimeMillis() - iStartTime) + " msec\n" );
  188.  
  189.         System.out.println( "Min queries: " + nMinQueries );
  190.         System.out.println( "Max queries: " + nMaxQueries );
  191.     }
  192.  
  193.     static SortedSet<String> readInDictionary( String sDictFile ) {
  194.         SortedSet<String> sWords = new TreeSet<String>();
  195.         try {
  196.             BufferedReader BR = new BufferedReader( new FileReader( sDictFile ) );
  197.             String sWord;
  198.             while( (sWord = BR.readLine()) != null )
  199.                 sWords.add( sWord );
  200.  
  201.             BR.close();
  202.         } catch( IOException ioe ) {
  203.             throw new RuntimeException( "could not read contents of dictionary file: " + sDictFile );
  204.         }
  205.         return sWords;
  206.     }
  207.  
  208.     static List<String> readInCodesToCrack( String sCodesFile ) {
  209.         List<String> sCodes = new LinkedList<String>();
  210.         try {
  211.             BufferedReader BR = new BufferedReader( new FileReader( sCodesFile ) );
  212.             String sCode;
  213.             while( (sCode = BR.readLine()) != null )
  214.                 if( !sCode.isEmpty() )
  215.                     sCodes.add( sCode );
  216.  
  217.             BR.close();
  218.         } catch( IOException ioe ) {
  219.             throw new RuntimeException( "could not read contents of codes file: " + sCodesFile );
  220.         }
  221.         return sCodes;
  222.     }
  223.  
  224.     static String resolveCodeWord( SortedSet<String> sCodeWordPotentials, final CharCounter CC, Oracle Or,
  225.         List<Integer> iOutstandingWords )
  226.     {
  227.         CC.filterByExclusion( sCodeWordPotentials );
  228.         if( sCodeWordPotentials.size() == 1 ) {
  229.             String sCodeWord = sCodeWordPotentials.first();
  230.  
  231.             CC.commitUsedChars( sCodeWord );
  232.             return sCodeWord;
  233.         }
  234.         CC.filterByNecessity( sCodeWordPotentials, iOutstandingWords );
  235.         if( sCodeWordPotentials.size() == 1 ) {
  236.             String sCodeWord = sCodeWordPotentials.first();
  237.  
  238.             CC.commitUsedChars( sCodeWord );
  239.             return sCodeWord;
  240.         }
  241.  
  242.         MappingOracle MOr = new MappingOracle( new OracleWithTackedOnCharCounter( Or, sCodeWordPotentials, CC ),
  243.             sCodeWordPotentials.first().length() );
  244.  
  245.         FilterFrame FF = new FilterFrame( sCodeWordPotentials, MOr, Or, CC );
  246.  
  247.         while( true ) {
  248.             FF.queryToResolve();
  249.             if( FF.isResolved() )
  250.                 return FF.codeWord();
  251.  
  252.             int iMatchChar = FF.getOutstandingChar();
  253.             WordSearchType WSTy = WordSearchType.FULL;
  254.             Outcome Oc, Oc2;
  255.  
  256.             FF.i0 = 0;
  257.             while( FF.i0 < FF.n ) {
  258.                 switch( WSTy ) {
  259.                 case FULL:
  260.                     int nCharsToMatch = Math.min( FF.n - FF.i0, 4 );
  261.                     if( !FF.queryIsEfficient( iMatchChar, nCharsToMatch ) ) {
  262.                         FF.i0 += nCharsToMatch;
  263.                         continue;
  264.                     }
  265.                     Oc = FF.query( iMatchChar, nCharsToMatch );
  266.                     if( FF.isResolved() )
  267.                         return FF.codeWord();
  268.  
  269.                     switch( nCharsToMatch ) {
  270.                     case 4:
  271.                         if( Oc.nMatch == 4 )
  272.                             WSTy = WordSearchType.FOUR_MATCHES_IN_NEXT_FOUR;
  273.                         else if( Oc.nMatch == 3 )
  274.                             WSTy = WordSearchType.THREE_MATCHES_IN_NEXT_FOUR;
  275.                         else if( Oc.nMatch == 2 )
  276.                             WSTy = WordSearchType.TWO_MATCHES_IN_NEXT_FOUR;
  277.                         else if( Oc.nMatch == 1 )
  278.                             WSTy = WordSearchType.ONE_MATCH_IN_NEXT_FOUR;
  279.                         else FF.filterBy( iMatchChar, false, false, false, false );
  280.                         break;
  281.  
  282.                     case 3:
  283.                         if( Oc.nMatch == 3 )
  284.                             WSTy = WordSearchType.THREE_MATCHES_IN_NEXT_THREE;
  285.                         else if( Oc.nMatch == 2 )
  286.                             WSTy = WordSearchType.TWO_MATCHES_IN_NEXT_THREE;
  287.                         else if( Oc.nMatch == 1 )
  288.                             WSTy = WordSearchType.ONE_MATCH_IN_NEXT_THREE;
  289.                         else FF.filterBy( iMatchChar, false, false, false );
  290.                         break;
  291.  
  292.                     case 2:
  293.                         if( Oc.nMatch == 2 )
  294.                             WSTy = WordSearchType.TWO_MATCHES_IN_NEXT_TWO;
  295.                         else if( Oc.nMatch == 1 )
  296.                             WSTy = WordSearchType.ONE_MATCH_IN_NEXT_TWO;
  297.                         else FF.filterBy( iMatchChar, false, false );
  298.                         break;
  299.  
  300.                     case 1:
  301.                         if( Oc.nMatch == 1 )
  302.                             WSTy = WordSearchType.ONE_MATCH_IN_NEXT_ONE;
  303.                         else FF.filterBy( iMatchChar, false );
  304.                         break;
  305.                     }
  306.                     break;
  307.  
  308.                 case FOUR_MATCHES_IN_NEXT_FOUR:
  309.                 case THREE_MATCHES_IN_NEXT_THREE:
  310.                     throw new InternalError( "didn't expect this with standard dictionary" );
  311.  
  312.                 case THREE_MATCHES_IN_NEXT_FOUR:
  313.                     WSTy = WordSearchType.FULL;
  314.                     if( FF.pare( new String[] { "+++-", "++-+", "+-++", "-+++" }, iMatchChar, true ) )
  315.                         return FF.codeWord();
  316.                     if( !FF.queryIsEfficient( iMatchChar, 2 ) ) {
  317.                         FF.i0 += 4;
  318.                         break;
  319.                     }
  320.                     Oc = FF.query( iMatchChar, 2 );
  321.                     if( FF.isResolved() )
  322.                         return FF.codeWord();
  323.  
  324.                     if( Oc.nMatch == 1 ) {
  325.                         if( FF.pare( new String[] { "+-", "-+" }, iMatchChar ) )
  326.                             return FF.codeWord();
  327.                         if( !FF.queryIsEfficient( iMatchChar, 1 ) ) {
  328.                             FF.i0 += 4;
  329.                             break;
  330.                         }
  331.                         Oc = FF.query( iMatchChar, 1 );
  332.                         if( FF.isResolved() )
  333.                             return FF.codeWord();
  334.                         if( Oc.nMatch == 1 )
  335.                             FF.filterBy( iMatchChar, true, false, true, true );
  336.                         else FF.filterBy( iMatchChar, false, true, true, true );
  337.                     } else {
  338.                         if( FF.pare( new String[] { "+++-", "++-+" }, iMatchChar ) )
  339.                             return FF.codeWord();
  340.                         if( !FF.queryIsEfficient( iMatchChar, 3 ) ) {
  341.                             FF.i0 += 4;
  342.                             break;
  343.                         }
  344.                         Oc = FF.query( iMatchChar, 3 );
  345.                         if( FF.isResolved() )
  346.                             return FF.codeWord();
  347.                         if( Oc.nMatch == 3 )
  348.                             FF.filterBy( iMatchChar, true, true, true, false );
  349.                         else FF.filterBy( iMatchChar, true, true, false, true );
  350.                     }
  351.                     break;
  352.  
  353.                 case TWO_MATCHES_IN_NEXT_FOUR:
  354.                     WSTy = WordSearchType.FULL;
  355.                     if( FF.pare( new String[] { "++--", "+-+-", "+--+", "-++-", "-+-+", "--++" }, iMatchChar ) )
  356.                         return FF.codeWord();
  357.                     if( !FF.queryIsEfficient( iMatchChar, 2 ) ) {
  358.                         FF.i0 += 4;
  359.                         break;
  360.                     }
  361.  
  362.                     Oc = FF.query( iMatchChar, 2 );
  363.                     if( FF.isResolved() )
  364.                         return FF.codeWord();
  365.  
  366.                     if( Oc.nMatch == 2 )
  367.                         FF.filterBy( iMatchChar, true, true, false, false );
  368.                     else if( Oc.nMatch == 0 )
  369.                         FF.filterBy( iMatchChar, false, false, true, true );
  370.                     else {
  371.                         if( FF.pare( new String[] { "+-+-", "-++-", "+--+", "-+-+" }, iMatchChar ) )
  372.                             return FF.codeWord();
  373.                         if( !FF.queryIsEfficient( iMatchChar, 1 ) ) {
  374.                             FF.i0 += 4;
  375.                             break;
  376.                         }
  377.                         Oc = FF.query( iMatchChar, 1 );
  378.                         if( FF.isResolved() )
  379.                             return FF.codeWord();
  380.  
  381.                         if( FF.pare( Oc.nMatch == 1 ? new String[] { "+" } : new String[] { "-" }, iMatchChar ) )
  382.                             return FF.codeWord();
  383.                         if( !FF.queryIsEfficient( iMatchChar, 3 ) ) {
  384.                             FF.i0 += 4;
  385.                             break;
  386.                         }
  387.                         Oc2 = FF.query( iMatchChar, 3 );
  388.                         if( FF.isResolved() )
  389.                             return FF.codeWord();
  390.  
  391.                         if( Oc.nMatch == 1 && Oc2.nMatch == 2 )
  392.                             FF.filterBy( iMatchChar, true, false, true, false );
  393.                         else if( Oc.nMatch == 1 )
  394.                             FF.filterBy( iMatchChar, true, false, false, true );
  395.                         else if( Oc2.nMatch == 2 )
  396.                             FF.filterBy( iMatchChar, false, true, true, false );
  397.                         else FF.filterBy( iMatchChar, false, true, false, true );
  398.                     }
  399.                     break;
  400.  
  401.                 case ONE_MATCH_IN_NEXT_FOUR:
  402.                     WSTy = WordSearchType.FULL;
  403.                     if( FF.pare( new String[] { "+---", "-+--", "--+-", "---+" }, iMatchChar ) )
  404.                         return FF.codeWord();
  405.                     if( !FF.queryIsEfficient( iMatchChar, 2 ) ) {
  406.                         FF.i0 += 4;
  407.                         break;
  408.                     }
  409.                     Oc = FF.query( iMatchChar, 2 );
  410.                     if( FF.isResolved() )
  411.                         return FF.codeWord();
  412.  
  413.                     if( Oc.nMatch == 1 ) {
  414.                         if( FF.pare( new String[] { "+-", "-+" }, iMatchChar ) )
  415.                             return FF.codeWord();
  416.                         if( !FF.queryIsEfficient( iMatchChar, 1 ) ) {
  417.                             FF.i0 += 4;
  418.                             break;
  419.                         }
  420.                         Oc = FF.query( iMatchChar, 1 );
  421.                         if( FF.isResolved() )
  422.                             return FF.codeWord();
  423.                         if( Oc.nMatch == 1 )
  424.                             FF.filterBy( iMatchChar, true, false, false, false );
  425.                         else FF.filterBy( iMatchChar, false, true, false, false );
  426.                     } else {
  427.                         if( FF.pare( new String[] { "--+-", "---+" }, iMatchChar ) )
  428.                             return FF.codeWord();
  429.                         if( !FF.queryIsEfficient( iMatchChar, 3 ) ) {
  430.                             FF.i0 += 4;
  431.                             break;
  432.                         }
  433.                         Oc = FF.query( iMatchChar, 3 );
  434.                         if( FF.isResolved() )
  435.                             return FF.codeWord();
  436.                         if( Oc.nMatch == 1 )
  437.                             FF.filterBy( iMatchChar, false, false, true, false );
  438.                         else FF.filterBy( iMatchChar, false, false, false, true );
  439.                     }
  440.                     break;
  441.  
  442.                 case TWO_MATCHES_IN_NEXT_THREE:
  443.                     WSTy = WordSearchType.FULL;
  444.                     if( FF.pare( new String[] { "++-", "+-+", "-++" }, iMatchChar ) )
  445.                         return FF.codeWord();
  446.                     if( !FF.queryIsEfficient( iMatchChar, 2 ) ) {
  447.                         FF.i0 += 3;
  448.                         break;
  449.                     }
  450.                     Oc = FF.query( iMatchChar, 2 );
  451.                     if( FF.isResolved() )
  452.                         return FF.codeWord();
  453.  
  454.                     if( Oc.nMatch == 2 )
  455.                         FF.filterBy( iMatchChar, true, true, false );
  456.                     else {
  457.                         if( FF.pare( new String[] { "+-+", "-++" }, iMatchChar ) )
  458.                             return FF.codeWord();
  459.                         if( !FF.queryIsEfficient( iMatchChar, 1 ) ) {
  460.                             FF.i0 += 3;
  461.                             break;
  462.                         }
  463.                         Oc = FF.query( iMatchChar, 1 );
  464.                         if( FF.isResolved() )
  465.                             return FF.codeWord();
  466.  
  467.                         if( Oc.nMatch == 1 )
  468.                             FF.filterBy( iMatchChar, true, false, true );
  469.                         else FF.filterBy( iMatchChar, false, true, true );
  470.                     }
  471.                     break;
  472.  
  473.                 case ONE_MATCH_IN_NEXT_THREE:
  474.                     WSTy = WordSearchType.FULL;
  475.                     if( FF.pare( new String[] { "+--", "-+-", "--+" }, iMatchChar ) )
  476.                         return FF.codeWord();
  477.                     if( !FF.queryIsEfficient( iMatchChar, 1 ) ) {
  478.                         FF.i0 += 3;
  479.                         break;
  480.                     }
  481.                     Oc = FF.query( iMatchChar, 1 );
  482.                     if( FF.isResolved() )
  483.                         return FF.codeWord();
  484.  
  485.                     if( Oc.nMatch == 1 )
  486.                         FF.filterBy( iMatchChar, true, false, false );
  487.                     else {
  488.                         if( FF.pare( new String[] { "-+-", "--+" }, iMatchChar ) )
  489.                             return FF.codeWord();
  490.                         if( !FF.queryIsEfficient( iMatchChar, 2 ) ) {
  491.                             FF.i0 += 3;
  492.                             break;
  493.                         }
  494.                         Oc = FF.query( iMatchChar, 2 );
  495.                         if( FF.isResolved() )
  496.                             return FF.codeWord();
  497.  
  498.                         if( Oc.nMatch == 1 )
  499.                             FF.filterBy( iMatchChar, false, true, false );
  500.                         else FF.filterBy( iMatchChar, false, false, true );
  501.                     }
  502.                     break;
  503.  
  504.                 case TWO_MATCHES_IN_NEXT_TWO:
  505.                     WSTy = WordSearchType.FULL;
  506.                     FF.filterBy( iMatchChar, true, true );
  507.                     break;
  508.  
  509.                 case ONE_MATCH_IN_NEXT_TWO:
  510.                     WSTy = WordSearchType.FULL;
  511.                     if( FF.pare( new String[] { "+-", "-+" }, iMatchChar ) )
  512.                         return FF.codeWord();
  513.                     if( !FF.queryIsEfficient( iMatchChar, 1 ) ) {
  514.                         FF.i0 += 2;
  515.                         break;
  516.                     }
  517.                     Oc = FF.query( iMatchChar, 1 );
  518.                     if( FF.isResolved() )
  519.                         return FF.codeWord();
  520.  
  521.                     if( Oc.nMatch == 1 )
  522.                         FF.filterBy( iMatchChar, true, false );
  523.                     else FF.filterBy( iMatchChar, false, true );
  524.                     break;
  525.  
  526.                 case ONE_MATCH_IN_NEXT_ONE:
  527.                     WSTy = WordSearchType.FULL;
  528.                     FF.filterBy( iMatchChar, true );
  529.                 }
  530.                 FF.queryToResolve();
  531.                 if( FF.isResolved() )
  532.                     return FF.codeWord();
  533.             }
  534.             FF.iResolvedChars.add( iMatchChar );
  535.         }
  536.     }
  537.  
  538.     static String getEnCharMatchString( int iMatchChar, int iCharsToMatch ) {
  539.         char[] chs = new char[iCharsToMatch];
  540.  
  541.         Arrays.fill( chs, ALPHABET[iMatchChar] );
  542.         return new String( chs );
  543.     }
  544.  
  545.     static String getSpaceAt( int iSpace ) {
  546.         char[] chs = getPlaceholders( iSpace+1 );
  547.         chs[iSpace] = ' ';
  548.         return new String( chs );
  549.     }
  550.  
  551.     static char[] getPlaceholders( int iCount ) {
  552.         char[] ch = new char[iCount];
  553.  
  554.         Arrays.fill( ch, ZERO_COUNT_PLACEHOLDER );
  555.         return ch;
  556.     }
  557.  
  558.     static List<Integer> getSpaceOneSearchProfile( final int iCodeLength, final boolean in1HE, final boolean in1HO,
  559.         final boolean in2HE, final boolean in2HO )
  560.     {
  561.         final List<Integer> iSites = new LinkedList<Integer>();
  562.         class Vetter {
  563.             void add( int i ) {
  564.                 if( i > 0 && i < iCodeLength-1 && (
  565.                     (in1HE && (i &1) == 0 && i <= iCodeLength/2) ||
  566.                     (in1HO && (i &1) == 1 && i <= iCodeLength/2) ||
  567.                     (in2HE && (i &1) == 0 && i > iCodeLength/2) ||
  568.                     (in2HO && (i &1) == 1 && i > iCodeLength/2) ) )
  569.                 {
  570.                     iSites.add( i );
  571.                 }
  572.             }
  573.         }
  574.  
  575.         Vetter V = new Vetter();
  576.         int iSiteM1 = (iCodeLength + 1)/3 - 1,
  577.             iSiteP1 = iSiteM1;
  578.  
  579.         while( iSiteM1 > 0 || iSiteP1 < iCodeLength-1 ) {
  580.             V.add( iSiteM1-- );
  581.             V.add( ++iSiteP1 );
  582.         }
  583.         return iSites;
  584.     }
  585.  
  586.     static List<Integer> getSpaceTwoSearchProfile( List<Integer> iSpaceOneProfile, final int iSpace1Location,
  587.         final int iCodeLength, final boolean in1HE, final boolean in1HO, final boolean in2HE, final boolean in2HO )
  588.     {
  589.         final List<Integer> iSites = new LinkedList<Integer>();
  590.         final List<Integer> iSearchedSites = iSpaceOneProfile.subList( 0, iSpaceOneProfile.indexOf( iSpace1Location ) );
  591.         class Vetter {
  592.             void add( int i ) {
  593.                 if( i > 0 && i < iCodeLength-1 && !iSearchedSites.contains( i ) &&
  594.                     Math.abs( i - iSpace1Location ) > 1 && (
  595.                     (in1HE && (i &1) == 0 && i <= iCodeLength/2) ||
  596.                     (in1HO && (i &1) == 1 && i <= iCodeLength/2) ||
  597.                     (in2HE && (i &1) == 0 && i > iCodeLength/2) ||
  598.                     (in2HO && (i &1) == 1 && i > iCodeLength/2) ) )
  599.                 {
  600.                     iSites.add( i );
  601.                 }
  602.             }
  603.         }
  604.  
  605.         Vetter V = new Vetter();
  606.         int iSiteM1 = iSpace1Location > iCodeLength/2 ? (iSpace1Location + 1)/2 - 1 :
  607.                 (iSpace1Location + iCodeLength)/2,
  608.             iSiteP1 = iSiteM1;
  609.  
  610.         while( iSiteM1 > 0 || iSiteP1 < iCodeLength-1 ) {
  611.             V.add( iSiteM1-- );
  612.             V.add( ++iSiteP1 );
  613.         }
  614.         return iSites;
  615.     }
  616.  
  617.     static int[] getSpaceLocations( Oracle Or, final CharCounter CC, final int iMaxWordLength ) {
  618.         final int[] iLocations = new int[3];
  619.  
  620.         StringBuilder SBu = new StringBuilder( ALPHABET.length*iMaxWordLength );
  621.         for( int i = 0; i < iMaxWordLength; i++ )
  622.             SBu.append( new String( ALPHABET ) );
  623.  
  624.         Outcome Oc = Or.query( new QueryString( createEvenSpaceSieve( iMaxWordLength*3 + 2 ) + SBu.toString() ) );
  625.         int iLength = Oc.nMatch + Oc.nCoincide;
  626.  
  627.         iLocations[2] = iLength;
  628.  
  629.         SpaceOracle SOr = new SpaceOracle( Or, CC );
  630.         boolean in1HE = false,
  631.             in1HO = false,
  632.             in2HE = false,
  633.             in2HO = false;
  634.  
  635.         if( Oc.nMatch == 0 ) {
  636.             in1HO = true;
  637.             in2HO = true;
  638.         } else if( Oc.nMatch == 2 ) {
  639.             in1HE = true;
  640.             in2HE = true;
  641.         } else {
  642.             Oc = SOr.query( new QueryString( createFullSpaceSieve( iLength/2 + 1 ) ) );
  643.             if( Oc.nMatch == 2 ) {
  644.                 in1HE = true;
  645.                 in1HO = true;
  646.             } else if( Oc.nMatch == 0 ) {
  647.                 in2HE = true;
  648.                 in2HO = true;
  649.             } else {
  650.                 Oc = SOr.query( new QueryString( createEvenSpaceSieve( iLength/2 + 1 ) ) );
  651.                 if( Oc.nMatch == 0 ) {
  652.                     in1HO = true;
  653.                     in2HE = true;
  654.                 } else {
  655.                     in1HE = true;
  656.                     in2HO = true;
  657.                 }
  658.             }
  659.         }
  660.         List<Integer> iSpaceOneSearchProfile = getSpaceOneSearchProfile( iLength, in1HE, in1HO, in2HE, in2HO );
  661.         for( int iSite : iSpaceOneSearchProfile ) {
  662.             Oc = SOr.query( new QueryString( getSpaceAt( iSite ), 0, 0 ) );
  663.             if( Oc.nMatch == 1 ) {
  664.                 iLocations[0] = iSite;
  665.                 break;
  666.             }
  667.         }
  668.  
  669.         List<Integer> iSpaceTwoSearchProfile = getSpaceTwoSearchProfile( iSpaceOneSearchProfile, iLocations[0],
  670.             iLength, in1HE, in1HO, in2HE, in2HO );
  671.  
  672.         for( int iSite : iSpaceTwoSearchProfile ) {
  673.             Oc = SOr.query( new QueryString( getSpaceAt( iSite ), 0, 0 ) );
  674.             if( Oc.nMatch == 1 ) {
  675.                 iLocations[1] = iSite;
  676.                 break;
  677.             }
  678.         }
  679.         if( iLocations[1] < iLocations[0] ) {
  680.             int i = iLocations[1];
  681.             iLocations[1] = iLocations[0];
  682.             iLocations[0] = i;
  683.         }
  684.         return iLocations;
  685.     }
  686.  
  687.     static String createFullSpaceSieve( int iLength ) {
  688.         char[] chs = new char[iLength];
  689.         Arrays.fill( chs, ' ' );
  690.         return new String( chs );
  691.     }
  692.  
  693.     static String createEvenSpaceSieve( int iLength ) {
  694.         char[] chs = new char[iLength];
  695.         for( int i = 0; i < iLength; i++ )
  696.             chs[i] = (i &1) == 0 ? ' ' : ZERO_COUNT_PLACEHOLDER;
  697.  
  698.         return new String( chs );
  699.     }
  700. }
  701.  
  702.  
  703. // Enumerated type for the main routine. Makes the code easier to follow.
  704. enum WordSearchType {
  705.     FULL,
  706.     ONE_MATCH_IN_NEXT_ONE,
  707.     ONE_MATCH_IN_NEXT_TWO,
  708.     TWO_MATCHES_IN_NEXT_TWO,
  709.     ONE_MATCH_IN_NEXT_THREE,
  710.     TWO_MATCHES_IN_NEXT_THREE,
  711.     THREE_MATCHES_IN_NEXT_THREE,
  712.     ONE_MATCH_IN_NEXT_FOUR,
  713.     TWO_MATCHES_IN_NEXT_FOUR,
  714.     THREE_MATCHES_IN_NEXT_FOUR,
  715.     FOUR_MATCHES_IN_NEXT_FOUR
  716. }
  717.  
  718.  
  719. // Class for computing various relevant word metrics.
  720. class DictionaryDB {
  721.     Map<String,DBEntry> M_Data;
  722.     Map<Integer,int[]> M_MaxCharCountsByWordLength;
  723.     int iMaxWordLength;
  724.     String sDisplacer = null;
  725.  
  726.     DictionaryDB( int nWords ) {
  727.         M_Data = new HashMap<String, DBEntry>( nWords );
  728.         M_MaxCharCountsByWordLength = new TreeMap<Integer, int[]>();
  729.         iMaxWordLength = 0;
  730.     }
  731.  
  732.     void registerWord( String sWord ) {
  733.         int iLength = sWord.length();
  734.         int[] iMaxCharCounts;
  735.         iMaxWordLength = Math.max( iMaxWordLength, iLength );
  736.  
  737.         Map<Integer,Integer> iCharCounts = computeCharCountsForWord( sWord );
  738.  
  739.         M_Data.put( sWord, new DBEntry( iCharCounts ) );
  740.         iMaxCharCounts = M_MaxCharCountsByWordLength.get( iLength );
  741.         if( iMaxCharCounts == null ) {
  742.             iMaxCharCounts = new int[Fastermind.ALPHABET.length];
  743.             M_MaxCharCountsByWordLength.put( iLength, iMaxCharCounts );
  744.         }
  745.         for( Map.Entry<Integer,Integer> E : iCharCounts.entrySet() ) {
  746.             int iCharIndex = E.getKey();
  747.  
  748.             iMaxCharCounts[iCharIndex] = Math.max( iMaxCharCounts[iCharIndex], E.getValue() );
  749.         }
  750.     }
  751.  
  752.     Map<Integer,Integer> charCountsForWord( String sWord ) {
  753.         return M_Data.get( sWord ).M_CharCounts;
  754.     }
  755.  
  756.     int[] maxCharCountsForWordLength( int iWordLength ) {
  757.         return M_MaxCharCountsByWordLength.get( iWordLength );
  758.     }
  759.  
  760.     int maxPossibleInstancesOfChar( int[] iWordLengths, int iCharIndex ) {
  761.         if( iWordLengths == null )
  762.             return iMaxWordLength*3;
  763.  
  764.         int iMaxInstances = 0;
  765.         for( int iWordLength : iWordLengths )
  766.             iMaxInstances += maxCharCountsForWordLength( iWordLength )[iCharIndex];
  767.  
  768.         return iMaxInstances;
  769.     }
  770.  
  771.     String displacer() {
  772.         if( sDisplacer == null )
  773.             sDisplacer = new String( Fastermind.getPlaceholders( iMaxWordLength * 3 ) );
  774.  
  775.         return sDisplacer;
  776.     }
  777.  
  778.     static class DBEntry {
  779.         final Map<Integer,Integer> M_CharCounts;
  780.  
  781.         DBEntry( Map<Integer,Integer> M_CharCounts_ ) {
  782.             M_CharCounts = M_CharCounts_;
  783.         }
  784.     }
  785.  
  786.     static Map<Integer,Integer> computeCharCountsForWord( String sWord ) {
  787.         Map<Integer,Integer> iCounts = new HashMap<Integer, Integer>( sWord.length() );
  788.         for( char ch : sWord.toCharArray() ) {
  789.             int iCharIndex = Fastermind.ALPHABET_STRING.indexOf( ch );
  790.  
  791.             Integer I = iCounts.get( iCharIndex );
  792.             int iCount = 1;
  793.             if( I != null )
  794.                 iCount = I + 1;
  795.  
  796.             iCounts.put( iCharIndex, iCount );
  797.         }
  798.         return iCounts;
  799.     }
  800. }
  801.  
  802.  
  803. // Class for storing known character counts and used character counts, and filtering based on them. Also stores some
  804. // other random data since it's passed around a lot.
  805. class CharCounter {
  806.     int[] iWordLengths;
  807.     final int[] iUsedCounts;
  808.     final int[] iFullCounts;
  809.     final DictionaryDB DDb;
  810.  
  811.     CharCounter( int[] iFullCounts_, int[] iUsedCounts_, DictionaryDB DDb_ ) {
  812.         iFullCounts = iFullCounts_;
  813.         iUsedCounts = iUsedCounts_;
  814.         DDb = DDb_;
  815.     }
  816.  
  817.     void setSpaceLocations( int[] iSpaceLocations ) {
  818.         iWordLengths = new int[iSpaceLocations.length];
  819.         for( int iSub = 0, i = 0; i < iWordLengths.length; i++ ) {
  820.             iWordLengths[i] = iSpaceLocations[i] - iSub;
  821.             iSub = iSpaceLocations[i] + 1;
  822.         }
  823.     }
  824.  
  825.     void commitUsedChars( String sCodeStub ) {
  826.         for( char ch : sCodeStub.toCharArray() )
  827.             iUsedCounts[Fastermind.ALPHABET_STRING.indexOf( ch )]++;
  828.     }
  829.  
  830.     void commitUsedChars( int iMatchChar, int iUseCount ) {
  831.         iUsedCounts[iMatchChar] += iUseCount;
  832.     }
  833.  
  834.     void filterByExclusion( SortedSet<String> sCodeWordPotentials ) {
  835.         Iterator<String> ItCodeWordPotentials = sCodeWordPotentials.iterator();
  836.         while( ItCodeWordPotentials.hasNext() ) {
  837.             for( Map.Entry<Integer,Integer> E : DDb.charCountsForWord( ItCodeWordPotentials.next() ).entrySet() ) {
  838.                 int iCharIndex = E.getKey();
  839.                 if( iFullCounts[iCharIndex] != Fastermind.UNKNOWN_COUNT && E.getValue() > iFullCounts[iCharIndex] -
  840.                     iUsedCounts[iCharIndex] )
  841.                 {
  842.                     ItCodeWordPotentials.remove();
  843.                     break;
  844.                 }
  845.             }
  846.         }
  847.     }
  848.  
  849.     void filterByNecessity( SortedSet<String> sCodeWordPotentials, List<Integer> iOutstandingWords ) {
  850.         int[] iFutureSlacks = new int[Fastermind.ALPHABET.length];
  851.         for( int iOutstandingWord : iOutstandingWords ) {
  852.             int[] iCounts = DDb.maxCharCountsForWordLength( iWordLengths[iOutstandingWord] );
  853.             for( int j = 0; j < iCounts.length; j++ )
  854.                 iFutureSlacks[j] += iCounts[j];
  855.         }
  856.  
  857.         List<Integer> I_Deficits = new LinkedList<Integer>();
  858.         for( int i = 0; i < Fastermind.ALPHABET.length; i++ )
  859.             if( iFullCounts[i] != Fastermind.UNKNOWN_COUNT && iFullCounts[i] - iFutureSlacks[i] - iUsedCounts[i] > 0 )
  860.                 I_Deficits.add( i );
  861.  
  862.         if( I_Deficits.isEmpty() )
  863.             return;
  864.  
  865.         Iterator<String> ItCodeWordPotentials = sCodeWordPotentials.iterator();
  866.         while( ItCodeWordPotentials.hasNext() ) {
  867.             Map<Integer,Integer> M_CharCounts = DDb.charCountsForWord( ItCodeWordPotentials.next() );
  868.             for( Integer I_Deficit : I_Deficits ) {
  869.                 int iCount = 0,
  870.                     iDeficit = I_Deficit;
  871.  
  872.                 Integer I_Count = M_CharCounts.get( I_Deficit );
  873.                 if( I_Count != null )
  874.                     iCount = I_Count;
  875.  
  876.                 if( iCount + iUsedCounts[iDeficit] + iFutureSlacks[iDeficit] < iFullCounts[iDeficit] ) {
  877.                     ItCodeWordPotentials.remove();
  878.                     break;
  879.                 }
  880.             }
  881.         }
  882.     }
  883. }
  884.  
  885.  
  886. // Class handling most of the complex filtering and querying by the main routine.
  887. class FilterFrame {
  888.     static final int MAX_POTENTIALS_FOR_SPECIFIC_DISCRIMINANT = 150;
  889.     static final int GLOBAL_INEFFICIENCY_DISCOUNT = 3;
  890.     static final double MIN_EFFICIENT_QUERY_POWER = 0.45;
  891.  
  892.     int i0;
  893.     int n;
  894.     MappingOracle MOr;
  895.     final Oracle OrResolver;
  896.     SortedSet<String> sCodeWordPotentials;
  897.     final List<Integer> iResolvedChars;
  898.     final CharCounter CC;
  899.     int nInefficient = 0;
  900.  
  901.     FilterFrame( SortedSet<String> sCodeWordPotentials_, MappingOracle MOr_, Oracle OrResolver_, CharCounter CC_ ) {
  902.         i0 = 0;
  903.         sCodeWordPotentials = sCodeWordPotentials_;
  904.         MOr = MOr_;
  905.         OrResolver = OrResolver_;
  906.         CC = CC_;
  907.         n = sCodeWordPotentials.first().length();
  908.         iResolvedChars = new LinkedList<Integer>();
  909.     }
  910.  
  911.     Outcome query( int iMatchChar, int iMatchCount ) {
  912.         String s = Fastermind.getEnCharMatchString( iMatchChar, iMatchCount );
  913.         QueryString qs = new QueryString( i0 > 0 ? (new String(Fastermind.getPlaceholders( i0 )) + s) : s,
  914.             iMatchChar, iMatchCount );
  915.  
  916.         Outcome Oc = MOr.query( qs );
  917.  
  918.         nInefficient = 0;
  919.         checkForExhaustion( iMatchChar );
  920.         commitOutstanding();
  921.  
  922.         return Oc;
  923.     }
  924.  
  925.     boolean queryIsEfficient( int iMatchChar, int nMatchCount ) {
  926.         if( sCodeWordPotentials.size() > MAX_POTENTIALS_FOR_SPECIFIC_DISCRIMINANT )
  927.             return true;
  928.  
  929.         boolean isEfficient = powerOfQuery( iMatchChar, nMatchCount ) >=
  930.             (int)(sCodeWordPotentials.size()*MIN_EFFICIENT_QUERY_POWER) - nInefficient*GLOBAL_INEFFICIENCY_DISCOUNT;
  931.  
  932.         if( !isEfficient )
  933.             nInefficient++;
  934.         else nInefficient = 0;
  935.         return isEfficient;
  936.     }
  937.  
  938.     int powerOfQuery( int iMatchChar, int nMatchCount ) {
  939.         Integer[] iIndicesArray = nextEnIndices( nMatchCount );
  940.         char[] chMatchMask = new char[nMatchCount];
  941.         char chMatch = Fastermind.ALPHABET[iMatchChar];
  942.  
  943.         Map<String,Integer> M_OutcomePowers = new TreeMap<String, Integer>();
  944.         for( String sWord : sCodeWordPotentials ) {
  945.             for( int i = 0; i < nMatchCount; i++ )
  946.                 chMatchMask[i] = sWord.charAt( iIndicesArray[i] ) == chMatch ? '+' : '-';
  947.  
  948.             String sMask = new String( chMatchMask );
  949.             if( M_OutcomePowers.containsKey( sMask ) )
  950.                 M_OutcomePowers.put( sMask, M_OutcomePowers.get( sMask ) + 1 );
  951.             else M_OutcomePowers.put( sMask, 1 );
  952.         }
  953.         return sCodeWordPotentials.size() - Collections.max( M_OutcomePowers.values() );
  954.     }
  955.  
  956.     boolean pare( String[] sMasksArray, int iMatchChar ) {
  957.         return pare( sMasksArray, iMatchChar, false );
  958.     }
  959.  
  960.     boolean pare( String[] sMasksArray, int iMatchChar, boolean isForce ) {
  961.         if( !isForce && sCodeWordPotentials.size() > MAX_POTENTIALS_FOR_SPECIFIC_DISCRIMINANT )
  962.             return false;
  963.  
  964.         int nMatchCount = sMasksArray[0].length();
  965.         Integer[] iIndicesArray = nextEnIndices( nMatchCount );
  966.         char[] chMatchMask = new char[nMatchCount];
  967.         char chMatch = Fastermind.ALPHABET[iMatchChar];
  968.         List<String> sMasks = Arrays.asList( sMasksArray );
  969.         Iterator<String> It = sCodeWordPotentials.iterator();
  970.         while( It.hasNext() ) {
  971.             String sWord = It.next();
  972.             for( int i = 0; i < nMatchCount; i++ )
  973.                 chMatchMask[i] = sWord.charAt( iIndicesArray[i] ) == chMatch ? '+' : '-';
  974.  
  975.             if( !sMasks.contains( new String( chMatchMask ) ) )
  976.                 It.remove();
  977.         }
  978.  
  979.         if( sCodeWordPotentials.size() == 1 )
  980.             commitOutstanding();
  981.         else queryToResolve();
  982.  
  983.         return sCodeWordPotentials.size() == 1;
  984.     }
  985.  
  986.     Integer[] nextEnIndices( int n_ ) {
  987.         List<Integer> iIndices = new LinkedList<Integer>();
  988.         for( int i = 0; i < n_; i++ )
  989.             iIndices.add( i0 + i );
  990.  
  991.         return MOr.map( iIndices ).toArray( new Integer[n_] );
  992.     }
  993.  
  994.     void commitOutstanding() {
  995.         if( sCodeWordPotentials.size() == 1 )
  996.             CC.commitUsedChars( MOr.substring( sCodeWordPotentials.first() ) );
  997.     }
  998.  
  999.     static final int[][] PERMS3_MODULO_12ORDER = {
  1000.         { 0, 1, 2 }, { 0, 2, 1 }, { 1, 2, 0 }
  1001.     };
  1002.  
  1003.     static final int[][] PERMS4_MODULO_12ORDER = {
  1004.         { 0, 1, 2, 3 }, { 0, 1, 3, 2 }, { 0, 2, 1, 3 }, { 0, 2, 3, 1 }, { 0, 3, 1, 2 }, { 0, 2, 2, 1 },
  1005.         { 1, 2, 0, 3 }, { 1, 2, 3, 0 }, { 1, 3, 0, 2 }, { 1, 3, 2, 0 }, { 2, 3, 0, 1 }, { 2, 3, 1, 0 }
  1006.     };
  1007.  
  1008.     void queryToResolve() {
  1009.         char[] ch;
  1010.         String[] sWords;
  1011.  
  1012.         if( sCodeWordPotentials.first().length() == 1 ) {
  1013.             String sCodeWord = sCodeWordPotentials.last();
  1014.  
  1015.             sCodeWordPotentials.remove( sCodeWord );
  1016.             for( String sWord : sCodeWordPotentials ) {
  1017.                 if( OrResolver.query( new QueryString( sWord ) ).nMatch == 1 ) {
  1018.                     sCodeWord = sWord;
  1019.                     break;
  1020.                 }
  1021.             }
  1022.             sCodeWordPotentials.clear();
  1023.             sCodeWordPotentials.add( sCodeWord );
  1024.             commitOutstanding();
  1025.             return;
  1026.         }
  1027.  
  1028.         switch( sCodeWordPotentials.size() ) {
  1029.         case 2:
  1030.             sWords = sCodeWordPotentials.toArray( new String[2] );
  1031.             ch = Fastermind.getPlaceholders( sWords[0].length() );
  1032.             for( int i = 0; i < sWords[0].length(); i++ )
  1033.                 if( sWords[0].charAt( i ) != sWords[1].charAt( i ) ) {
  1034.                     ch[i] = sWords[0].charAt( i );
  1035.                     break;
  1036.                 }
  1037.  
  1038.             sCodeWordPotentials.remove( OrResolver.query(new QueryString( ch )).nMatch == 1 ? sWords[1] : sWords[0] );
  1039.             commitOutstanding();
  1040.             break;
  1041.  
  1042.         case 3:
  1043.         case 4:
  1044.             final int nWords = sCodeWordPotentials.size();
  1045.  
  1046.             sWords = sCodeWordPotentials.toArray( new String[nWords] );
  1047.             for( int[] iWords : nWords == 3 ? PERMS3_MODULO_12ORDER : PERMS4_MODULO_12ORDER ) {
  1048.                 int[] iMeet = { -1, -1, -1 };
  1049.  
  1050.                 for( int i = 0; i < sWords[0].length(); i++ ) {
  1051.                     char ch0 = sWords[iWords[0]].charAt( i ),
  1052.                         ch1 = sWords[iWords[1]].charAt( i ),
  1053.                         ch2 = sWords[iWords[2]].charAt( i );
  1054.  
  1055.                     if( nWords == 3 ) {
  1056.                         if( ch0 != ch2 )
  1057.                             iMeet[ch0 == ch1 ? 1 : 0] = i;
  1058.                     } else {
  1059.                         char ch3 = sWords[iWords[3]].charAt( i );
  1060.                         if( ch0 != ch3 ) {
  1061.                             if( ch0 == ch1 && ch0 == ch2 )
  1062.                                 iMeet[2] = i;
  1063.                             else if( ch0 == ch1 )
  1064.                                 iMeet[1] = i;
  1065.                             else if( ch0 != ch2 )
  1066.                                 iMeet[0] = i;
  1067.                         }
  1068.                     }
  1069.                 }
  1070.                 if( iMeet[0] != -1 && iMeet[1] != -1 && (nWords == 3 || iMeet[2] != -1) ) {
  1071.                     ch = Fastermind.getPlaceholders( sWords[0].length() );
  1072.                     ch[iMeet[0]] = sWords[iWords[0]].charAt( iMeet[0] );
  1073.                     ch[iMeet[1]] = sWords[iWords[1]].charAt( iMeet[1] );
  1074.                     if( nWords == 4 )
  1075.                         ch[iMeet[2]] = sWords[iWords[2]].charAt( iMeet[2] );
  1076.  
  1077.                     int nMatch = nWords - 1 - OrResolver.query( new QueryString( ch ) ).nMatch;
  1078.  
  1079.                     sCodeWordPotentials.clear();
  1080.                     sCodeWordPotentials.add( sWords[iWords[nMatch]] );
  1081.                     commitOutstanding();
  1082.                     return;
  1083.                 }
  1084.             }
  1085.         }
  1086.     }
  1087.  
  1088.     int nResetsDueToExhaustedPool = 0;
  1089.  
  1090.     int getOutstandingChar() {
  1091.         int nChars = Fastermind.ALPHABET.length;
  1092.         if( sCodeWordPotentials.size() <= MAX_POTENTIALS_FOR_SPECIFIC_DISCRIMINANT ) {
  1093.             int[] iOutstandingCharCounts = new int[nChars];
  1094.             for( String sWord : sCodeWordPotentials )
  1095.                 for( Map.Entry<Integer,Integer> E : CC.DDb.charCountsForWord( sWord ).entrySet() )
  1096.                     iOutstandingCharCounts[E.getKey()] += E.getValue();
  1097.  
  1098.             List<IndexedInteger> II_OutstandingCharCounts = new ArrayList<IndexedInteger>( nChars );
  1099.             for( int i = 0; i < nChars; i++ )
  1100.                 if( iOutstandingCharCounts[i] > 0 )
  1101.                     II_OutstandingCharCounts.add( new IndexedInteger( iOutstandingCharCounts[i], i ) );
  1102.  
  1103.             Collections.sort( II_OutstandingCharCounts, new Comparator<IndexedInteger>() {
  1104.                 public int compare( IndexedInteger II1, IndexedInteger II2 ) {
  1105.                     return II2.i - II1.i;
  1106.                 }
  1107.             } );
  1108.  
  1109.             for( IndexedInteger II : II_OutstandingCharCounts ) {
  1110.                 if( !iResolvedChars.contains( II.iIndex ) &&
  1111.                     CC.iUsedCounts[II.iIndex] != CC.iFullCounts[II.iIndex] &&
  1112.                     CC.iFullCounts[II.iIndex] != Fastermind.UNKNOWN_COUNT )
  1113.                 {
  1114.                     return II.iIndex;
  1115.                 }
  1116.             }
  1117.         } else {
  1118.             for( int iIndex = 0; iIndex < nChars; iIndex++ )
  1119.                 if( !iResolvedChars.contains( iIndex ) &&
  1120.                     CC.iUsedCounts[iIndex] != CC.iFullCounts[iIndex] &&
  1121.                     CC.iFullCounts[iIndex] != Fastermind.UNKNOWN_COUNT )
  1122.                 {
  1123.                     return iIndex;
  1124.                 }
  1125.         }
  1126.         if( iResolvedChars.isEmpty() ) {
  1127.             MOr.query( new QueryString( Fastermind.ALPHABET_STRING.substring( 0, 1 ), 0, 1 ) );
  1128.             nResetsDueToExhaustedPool++;
  1129.             if( nResetsDueToExhaustedPool > 10 )
  1130.                 throw new InternalError( "perpetually exhausting pool" );
  1131.         } else {
  1132.             iResolvedChars.remove( 0 );
  1133.         }
  1134.         return getOutstandingChar();
  1135.     }
  1136.  
  1137.     void filterBy( int iMatchChar, boolean... isAt ) {
  1138.         List<Integer> iOns = new LinkedList<Integer>(),
  1139.             iOffs = new LinkedList<Integer>();
  1140.  
  1141.         for( int i = 0; i < isAt.length; i++ ) {
  1142.             if( isAt[i] )
  1143.                 iOns.add( i0 + i );
  1144.             else iOffs.add( i0 + i );
  1145.         }
  1146.         if( !iOffs.isEmpty() )
  1147.             filterByCharExclusion( iMatchChar, iOffs );
  1148.         if( !isResolved() && !iOns.isEmpty() )
  1149.             filterByCharInclusion( iMatchChar, iOns );
  1150.  
  1151.         if( isResolved() ) {
  1152.             commitOutstanding();
  1153.             n = i0 = 0;
  1154.         } else {
  1155.             CC.commitUsedChars( iMatchChar, iOns.size() );
  1156.             i0 += iOffs.size();
  1157.             if( !iOns.isEmpty() ) {
  1158.                 n -= iOns.size();
  1159.                 MOr = MappingOracle.oracleForResolvedCharsAt( MOr, iOns );
  1160.             }
  1161.             checkForExhaustion( iMatchChar );
  1162.             if( isResolved() ) {
  1163.                 commitOutstanding();
  1164.                 n = i0 = 0;
  1165.             }
  1166.         }
  1167.     }
  1168.  
  1169.     void filterByCharExclusion( int iMatchChar, List<Integer> iCharIndices ) {
  1170.         filterByCharWhateverclusion( iMatchChar, iCharIndices, false );
  1171.     }
  1172.  
  1173.     void filterByCharInclusion( int iMatchChar, List<Integer> iCharIndices ) {
  1174.         filterByCharWhateverclusion( iMatchChar, iCharIndices, true );
  1175.     }
  1176.  
  1177.     void filterByCharWhateverclusion( int iMatchChar, List<Integer> iCharIndices, boolean isInclusion ) {
  1178.         char chMatch = Fastermind.ALPHABET[iMatchChar];
  1179.         Iterator<String> ItCodeWordPotentials = sCodeWordPotentials.iterator();
  1180.  
  1181.         iCharIndices = MOr.map( iCharIndices );
  1182.  
  1183.         while( ItCodeWordPotentials.hasNext() ) {
  1184.             String sCodeWord = ItCodeWordPotentials.next();
  1185.  
  1186.             for( int iCharIndex : iCharIndices )
  1187.                 if( (sCodeWord.charAt( iCharIndex ) == chMatch) != isInclusion ) {
  1188.                     ItCodeWordPotentials.remove();
  1189.                     break;
  1190.                 }
  1191.         }
  1192.     }
  1193.  
  1194.     void checkForExhaustion( int iMatchChar ) {
  1195.         if( CC.iUsedCounts[iMatchChar] == CC.iFullCounts[iMatchChar] )
  1196.             filterByCharExclusion( iMatchChar, Fastermind.ASCENDING_ORDER.subList( 0, MOr.getUnresolvedIndexCount() ) );
  1197.     }
  1198.  
  1199.     boolean isResolved() {
  1200.         assert !sCodeWordPotentials.isEmpty();
  1201.         return sCodeWordPotentials.size() == 1;
  1202.     }
  1203.  
  1204.     String codeWord() {
  1205.         return sCodeWordPotentials.first();
  1206.     }
  1207.  
  1208.     static final class IndexedInteger {
  1209.         int i;
  1210.         int iIndex;
  1211.  
  1212.         IndexedInteger( int i_, int iIndex_ ) {
  1213.             i = i_;
  1214.             iIndex = iIndex_;
  1215.         }
  1216.     }
  1217. }
  1218.  
  1219.  
  1220. // Class encapsulates an outcome by the oracle: number of matches, number of "coincidences" (characters present in
  1221. // both strings but not in matching locations).
  1222. class Outcome implements Comparable<Outcome> {
  1223.     final int nMatch;
  1224.     final int nCoincide;
  1225.  
  1226.     Outcome( int nMatch_, int nCoincide_ ) {
  1227.         nMatch = nMatch_;
  1228.         nCoincide = nCoincide_;
  1229.     }
  1230.  
  1231.     public int compareTo( Outcome Oc ) {
  1232.         return nMatch < Oc.nMatch ? -1 : (nMatch > Oc.nMatch ? 1 : (nCoincide < Oc.nCoincide ? -1 :
  1233.             (nCoincide > Oc.nCoincide ? 1 : 0)));
  1234.     }
  1235.  
  1236.     public boolean equals( Object o ) {
  1237.         if( !(o instanceof Outcome) )
  1238.             return false;
  1239.  
  1240.         Outcome Oc = (Outcome)o;
  1241.         return Oc.nMatch == nMatch && Oc.nCoincide == nCoincide;
  1242.     }
  1243.  
  1244.     public int hashCode() {
  1245.         return nMatch*37 + nCoincide;
  1246.     }
  1247. }
  1248.  
  1249.  
  1250. // Oracle interface. An oracle is the machine that spits out the relevant match data when queried with a specific
  1251. // string.
  1252. interface Oracle {
  1253.     Outcome query( QueryString qsCandidate );
  1254. }
  1255.  
  1256.  
  1257. // A string with extra data attached. Needed to avoid headaches in passing data between the many nested oracles. Not
  1258. // elegant, but gets the job done.
  1259. class QueryString {
  1260.     final String s;
  1261.     final int iIndex;
  1262.     final int nCount;
  1263.  
  1264.     QueryString( String s_ )
  1265.         { this( s_, -1, -1 ); }
  1266.     QueryString( char[] chs )
  1267.         { this( new String( chs ), -1, -1 ); }
  1268.     QueryString( char[] chs, int iIndex_, int nCount_ )
  1269.         { this( new String( chs ), iIndex_, nCount_ ); }
  1270.     QueryString( String s_, int iIndex_, int nCount_ ) {
  1271.         s = s_;
  1272.         iIndex = iIndex_;
  1273.         nCount = nCount_;
  1274.     }
  1275.  
  1276.     String contents() {
  1277.         return s;
  1278.     }
  1279.  
  1280.     QueryString append( String s_ ) {
  1281.         return s_.isEmpty() ? this : new QueryString( s + s_, iIndex, nCount );
  1282.     }
  1283.  
  1284.     QueryString prepend( String s_ ) {
  1285.         return s_.isEmpty() ? this : new QueryString( s_ + s, iIndex, nCount );
  1286.     }
  1287. }
  1288.  
  1289.  
  1290. // Simple hook on the input and output to an oracle.
  1291. abstract class FilteredOracle implements Oracle {
  1292.     final Oracle Or;
  1293.  
  1294.     FilteredOracle( Oracle Or_ ) {
  1295.         Or = Or_;
  1296.     }
  1297.  
  1298.     abstract QueryString localStringToOracleString( QueryString qsLocal );
  1299.  
  1300.     abstract Outcome oracleOutcomeToLocalOutcome( Outcome Oc );
  1301.  
  1302.     public Outcome query( QueryString qsCandidate ) {
  1303.         return oracleOutcomeToLocalOutcome( Or.query( localStringToOracleString( qsCandidate ) ) );
  1304.     }
  1305. }
  1306.  
  1307.  
  1308. // Simple oracle shifts test characters into the position of a specific word.
  1309. class WordMaskOracle extends FilteredOracle {
  1310.     final String sPrefix;
  1311.     final Outcome OcBaseline;
  1312.  
  1313.     WordMaskOracle( Oracle Or_, String sPrefix_, Outcome OcBaseline_ ) {
  1314.         super( Or_ );
  1315.         sPrefix = sPrefix_;
  1316.         OcBaseline = OcBaseline_;
  1317.     }
  1318.  
  1319.     @Override QueryString localStringToOracleString( QueryString qsLocal ) {
  1320.         return qsLocal.prepend( sPrefix );
  1321.     }
  1322.  
  1323.     @Override Outcome oracleOutcomeToLocalOutcome( Outcome Oc ) {
  1324.         return new Outcome( Oc.nMatch - OcBaseline.nMatch, Oc.nCoincide - OcBaseline.nCoincide );
  1325.     }
  1326.  
  1327.     static Oracle forCodeWord( Oracle Or_, int[] iWordLengths, int iCodeWord ) {
  1328.         switch( iCodeWord ) {
  1329.         case 0:
  1330.             return Or_;
  1331.         case 1:
  1332.             return new WordMaskOracle( Or_, new String( Fastermind.getPlaceholders( iWordLengths[0] + 1 ) ),
  1333.                 new Outcome( 0, 0 ) );
  1334.         case 2:
  1335.             return new WordMaskOracle( Or_, new String( Fastermind.getPlaceholders( iWordLengths[0] +
  1336.                 iWordLengths[1] + 2 ) ), new Outcome( 0, 0 ) );
  1337.         }
  1338.         throw new InternalError();
  1339.     }
  1340. }
  1341.  
  1342.  
  1343. // Simpler version of the OracleWithTackedOnCharCounter. This one also tacks on a character counter, but is
  1344. // sufficiently different to warrant its own class.
  1345. final class SpaceOracle extends FilteredOracle {
  1346.     final CharCounter CC;
  1347.     int iFullQueryCharIndex;
  1348.     boolean areAllCharsQueried;
  1349.     QueryString qsStored;
  1350.  
  1351.     SpaceOracle( Oracle Or_, CharCounter CC_ ) {
  1352.         super( Or_ );
  1353.         CC = CC_;
  1354.     }
  1355.  
  1356.     @Override QueryString localStringToOracleString( QueryString qsLocal ) {
  1357.         if( areAllCharsQueried )
  1358.             return qsLocal;
  1359.  
  1360.         qsStored = qsLocal;
  1361.         for( iFullQueryCharIndex = 0; iFullQueryCharIndex < Fastermind.ALPHABET.length; iFullQueryCharIndex++ ) {
  1362.             if( CC.iFullCounts[iFullQueryCharIndex] == Fastermind.UNKNOWN_COUNT )
  1363.                 return qsLocal.append( CC.DDb.displacer() + Fastermind.getEnCharMatchString( iFullQueryCharIndex,
  1364.                     CC.DDb.maxPossibleInstancesOfChar( null, iFullQueryCharIndex ) ) );
  1365.         }
  1366.         areAllCharsQueried = true;
  1367.         return qsLocal;
  1368.     }
  1369.  
  1370.     @Override Outcome oracleOutcomeToLocalOutcome( Outcome Oc ) {
  1371.         if( areAllCharsQueried )
  1372.             return Oc;
  1373.  
  1374.         CC.iFullCounts[iFullQueryCharIndex] = Oc.nMatch + Oc.nCoincide - 1 + qsStored.nCount;
  1375.         return new Outcome( Oc.nMatch, 1 - Oc.nMatch );
  1376.     }
  1377. }
  1378.  
  1379.  
  1380. // Oracle with a tacked on character counter. The name says it all. ;)
  1381. final class OracleWithTackedOnCharCounter extends FilteredOracle {
  1382.     final CharCounter CC;
  1383.     final SortedSet<String> sCodeWordPotentials;
  1384.     int iFullQueryCharIndex;
  1385.     boolean areAllCharsQueried;
  1386.     QueryString qsStoredLocal;
  1387.  
  1388.     OracleWithTackedOnCharCounter( Oracle Or_, SortedSet<String> sCodeWordPotentials_, CharCounter CC_ ) {
  1389.         super( Or_ );
  1390.         sCodeWordPotentials = sCodeWordPotentials_;
  1391.         CC = CC_;
  1392.         iFullQueryCharIndex = 0;
  1393.     }
  1394.  
  1395.     @Override QueryString localStringToOracleString( QueryString qsLocal ) {
  1396.         if( areAllCharsQueried )
  1397.             return qsLocal;
  1398.  
  1399.         qsStoredLocal = qsLocal;
  1400.         for( ; iFullQueryCharIndex < Fastermind.ALPHABET.length; iFullQueryCharIndex++ ) {
  1401.             if( CC.iFullCounts[iFullQueryCharIndex] == Fastermind.UNKNOWN_COUNT ) {
  1402.                 assert iFullQueryCharIndex > 0;
  1403.                 return qsLocal.append( CC.DDb.displacer() + Fastermind.getEnCharMatchString( iFullQueryCharIndex,
  1404.                     CC.DDb.maxPossibleInstancesOfChar( CC.iWordLengths, iFullQueryCharIndex ) ) );
  1405.             }
  1406.         }
  1407.         areAllCharsQueried = true;
  1408.         return qsLocal;
  1409.     }
  1410.  
  1411.     @Override Outcome oracleOutcomeToLocalOutcome( Outcome Oc ) {
  1412.         if( areAllCharsQueried )
  1413.             return Oc;
  1414.  
  1415.         int iImpliedCount = Oc.nMatch + Oc.nCoincide;
  1416.         int iCharIndex = qsStoredLocal.iIndex;
  1417.  
  1418.         assert CC.iFullCounts[iCharIndex] != Fastermind.UNKNOWN_COUNT;
  1419.         iImpliedCount -= Math.min( CC.iFullCounts[iCharIndex], qsStoredLocal.nCount );
  1420.  
  1421.         CC.iFullCounts[iFullQueryCharIndex] = iImpliedCount;
  1422.         if( iImpliedCount == 0 )
  1423.             filterByTotalCharExclusion( iFullQueryCharIndex );
  1424.  
  1425.         return new Outcome( Oc.nMatch, iImpliedCount - CC.iUsedCounts[iFullQueryCharIndex] );
  1426.     }
  1427.  
  1428.     void filterByTotalCharExclusion( int iMatchChar ) {
  1429.         char chMatch = Fastermind.ALPHABET[iMatchChar];
  1430.         Iterator<String> ItCodeWordPotentials = sCodeWordPotentials.iterator();
  1431.  
  1432.         while( ItCodeWordPotentials.hasNext() ) {
  1433.             if( ItCodeWordPotentials.next().indexOf( chMatch ) != -1 )
  1434.                 ItCodeWordPotentials.remove();
  1435.         }
  1436.     }
  1437. }
  1438.  
  1439.  
  1440. // Oracle that handles mapping characters around "gaps" formed by resolved characters from prior guesses.
  1441. final class MappingOracle extends FilteredOracle {
  1442.     static final int[] NO_OFFSETS = new int[0];
  1443.  
  1444.     final int[] iOffsets;
  1445.     final char[] chMapped;
  1446.     final int iMaxMapLength;
  1447.     final int nResolved;
  1448.  
  1449.     MappingOracle( Oracle Or_, int iMaxMapLength_ ) {
  1450.         super( Or_ );
  1451.         iOffsets = NO_OFFSETS;
  1452.         nResolved = 0;
  1453.         chMapped = Fastermind.getPlaceholders( iMaxMapLength_ );
  1454.         iMaxMapLength = iMaxMapLength_;
  1455.     }
  1456.  
  1457.     MappingOracle( Oracle Or_, int[] iOffsets_, char[] chMapped_, int nResolved_ ) {
  1458.         super( Or_ );
  1459.         iOffsets = iOffsets_;
  1460.         chMapped = chMapped_;
  1461.         nResolved = nResolved_;
  1462.         iMaxMapLength = chMapped_.length;
  1463.     }
  1464.  
  1465.     List<Integer> map( List<Integer> iCharIndices ) {
  1466.         if( iOffsets == NO_OFFSETS )
  1467.             return iCharIndices;
  1468.  
  1469.         List<Integer> iMappedIndices = new ArrayList<Integer>( iCharIndices.size() );
  1470.  
  1471.         for( int iIndex : iCharIndices )
  1472.             iMappedIndices.add( map( iIndex ) );
  1473.  
  1474.         return iMappedIndices;
  1475.     }
  1476.  
  1477.     int map( int iIndex ) {
  1478.         if( iOffsets == NO_OFFSETS )
  1479.             return iIndex;
  1480.  
  1481.         return iIndex >= iOffsets.length ? (iIndex + iOffsets[iOffsets.length-1] - (iOffsets.length-1)) :
  1482.             iOffsets[iIndex];
  1483.     }
  1484.  
  1485.     String substring( String sWord ) {
  1486.         if( iOffsets == NO_OFFSETS )
  1487.             return sWord;
  1488.  
  1489.         StringBuilder SBu = new StringBuilder( sWord.length() );
  1490.  
  1491.         int iSub = 0,
  1492.             iMapped = map( iSub );
  1493.  
  1494.         while( iMapped < sWord.length() ) {
  1495.             SBu.append( sWord.charAt( iMapped ) );
  1496.             iMapped = map( ++iSub );
  1497.         }
  1498.         return SBu.toString();
  1499.     }
  1500.  
  1501.     int getUnresolvedIndexCount() {
  1502.         return iMaxMapLength - nResolved;
  1503.     }
  1504.  
  1505.     @Override QueryString localStringToOracleString( QueryString qsLocal ) {
  1506.         if( iOffsets == NO_OFFSETS )
  1507.             return qsLocal;
  1508.  
  1509.         char[] chOracle = new char[iMaxMapLength];
  1510.         String sLocal = qsLocal.contents();
  1511.  
  1512.         System.arraycopy( chMapped, 0, chOracle, 0, iMaxMapLength );
  1513.         for( int i = 0; i < sLocal.length(); i++ )
  1514.             chOracle[map( i )] = sLocal.charAt( i );
  1515.  
  1516.         return new QueryString( chOracle, qsLocal.iIndex, qsLocal.nCount );
  1517.     }
  1518.  
  1519.     @Override Outcome oracleOutcomeToLocalOutcome( Outcome Oc ) {
  1520.         return Oc;
  1521.     }
  1522.  
  1523.     static MappingOracle oracleForResolvedCharsAt( Oracle Or_, List<Integer> iResolvedChars ) {
  1524.         if( Or_ instanceof MappingOracle ) {
  1525.             MappingOracle MOr = (MappingOracle)Or_;
  1526.             iResolvedChars = MOr.map( iResolvedChars );
  1527.  
  1528.             char[] chMappedNew;
  1529.  
  1530.             chMappedNew = new char[MOr.iMaxMapLength];
  1531.             System.arraycopy( MOr.chMapped, 0, chMappedNew, 0, MOr.iMaxMapLength );
  1532.             for( int iResolvedChar : iResolvedChars )
  1533.                 chMappedNew[iResolvedChar] = Fastermind.RESOLVED_CHAR_PLACEHOLDER;
  1534.  
  1535.             List<Integer> iOffsetsNew = new LinkedList<Integer>();
  1536.             int iTo = 0;
  1537.             for( ; iTo < chMappedNew.length; iTo++ )
  1538.                 if( chMappedNew[iTo] == Fastermind.ZERO_COUNT_PLACEHOLDER ) {
  1539.                     iOffsetsNew.add( iTo );
  1540.                 }
  1541.  
  1542.             iOffsetsNew.add( iTo );
  1543.             int[] iOffsetsNewArray = new int[iOffsetsNew.size()];
  1544.             int i = 0;
  1545.             for( int iOffset : iOffsetsNew )
  1546.                 iOffsetsNewArray[i++] = iOffset;
  1547.  
  1548.             return new MappingOracle( MOr.Or, iOffsetsNewArray, chMappedNew, MOr.nResolved + iResolvedChars.size() );
  1549.         }
  1550.         throw new InternalError( "didn't expect this" );
  1551.     }
  1552. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!