API tools faq
paste
Advertisement
Guest User

COTO Mastermind Java Code Rev. 2

a guest
Sep 5th, 2014
383
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 37.64 KB | None | 0 0
raw download clone embed print report
  1. import java.io.BufferedReader;
  2. import java.io.FileReader;
  3. import java.io.IOException;
  4. import java.util.*;
  5.  
  6. public final class Revenant {
  7.  
  8.     // Set to true to have a console printout of individual solutions.
  9.     static final boolean SHOW_ALL_OUTPUTS = false;
  10.  
  11.     // Set to true to have the oracle declare its query strings, pausing for .25 seconds after each.
  12.     static final boolean ORACLE_DECLARES_QUERIES = false;
  13.  
  14.     // The "full" oracle. In this version of the software, to save on code, the full oracle
  15.     // is built on top of a "mock oracle" class, which provides most of the functionality. Mock oracles are used to
  16.     // compute outcomes based on hypothetical keys elsewhere in the program. The only functional difference between
  17.     // the mock oracle and the full oracle is that the full oracle maintains its query count, declares its queries (if
  18.     // flagged to do so), and (of course) is the only oracle that counts with respect to actual number of queries.
  19.     static class MockOracle implements RevOracle {
  20.         final char[] chKeyChars;
  21.         final char[] chSortedKeyChars;
  22.  
  23.         MockOracle( String sKey ) {
  24.             chKeyChars = sKey.toCharArray();
  25.             chSortedKeyChars = sKey.toCharArray();
  26.             Arrays.sort( chSortedKeyChars );
  27.         }
  28.  
  29.         @Override public RevOutcome query( String sCandidate ) {
  30.             char[] chCandChars = sCandidate.toCharArray();
  31.             char[] chSortedCandChars = sCandidate.toCharArray();
  32.             Arrays.sort( chSortedCandChars );
  33.  
  34.             int nMatch = 0;
  35.             int iDomain = Math.min( chCandChars.length, chKeyChars.length );
  36.             for( int i = 0; i < iDomain; i++ )
  37.                 if( chCandChars[i] == chKeyChars[i] )
  38.                     nMatch++;
  39.  
  40.             int nCoincide = 0;
  41.             int i1 = 0, i2 = 0;
  42.             while( i1 < chSortedCandChars.length && i2 < chSortedKeyChars.length ) {
  43.                 if( chSortedCandChars[i1] == chSortedKeyChars[i2] ) {
  44.                     nCoincide++;
  45.                     i1++;
  46.                     i2++;
  47.                 } else if( chSortedCandChars[i1] < chSortedKeyChars[i2] )
  48.                     i1++;
  49.                 else i2++;
  50.             }
  51.             if( nMatch == chKeyChars.length )
  52.                 return RevOutcome.VALID;
  53.  
  54.             return new RevOutcome( nMatch, nCoincide - nMatch );
  55.         }
  56.  
  57.         public String toString() {
  58.             return "Key: " + (new String( chKeyChars ));
  59.         }
  60.     }
  61.  
  62.     static final class FullOracle extends MockOracle {
  63.         int iQueryCount = 0;
  64.  
  65.         FullOracle( String sKey ) {
  66.             super( sKey );
  67.         }
  68.  
  69.         @Override
  70.         public RevOutcome query( String sCandidate ) {
  71.             iQueryCount++;
  72.             if( ORACLE_DECLARES_QUERIES ) {
  73.                 System.out.println( "Key: \"" + new String( chKeyChars ) + "\"\nQry: \"" + sCandidate + "\"\n" );
  74.                 try {
  75.                     Thread.sleep( 250 );
  76.                 } catch( InterruptedException IEx ) { /* ignore */ }
  77.             }
  78.  
  79.             return super.query( sCandidate );
  80.         }
  81.  
  82.         int getQueryCount() {
  83.             return iQueryCount;
  84.         }
  85.     }
  86.     // END OF ORACLE ---- <
  87.  
  88.     static final char ZERO_COUNT_PLACEHOLDER = '-';
  89.  
  90.     static char[] ALPHABET;
  91.     static char[] ALPHABET_WITH_SPACE;
  92.     static String ALPHABET_STRING;
  93.     static String ALPHABET_WITH_SPACE_STRING;
  94.  
  95.     public static void main( String[] sArgs ) {
  96.         final SortedSet<String> sWords = readInDictionary( "./dict.txt" );
  97.  
  98.         // Compute the alphabet...
  99.         final Map<Character,Integer> M_CharFrequencies = new HashMap<>( 32 );
  100.         for( String sWord : sWords ) {
  101.             for( char ch : sWord.toCharArray() ) {
  102.                 if( M_CharFrequencies.containsKey( ch ) )
  103.                     M_CharFrequencies.put( ch, M_CharFrequencies.get( ch ) + 1 );
  104.                 else M_CharFrequencies.put( ch, 1 );
  105.             }
  106.         }
  107.         List<Character> chAlphabet = new ArrayList<>( M_CharFrequencies.keySet() );
  108.         Collections.sort( chAlphabet, ( ch1, ch2 ) -> M_CharFrequencies.get( ch2 ) - M_CharFrequencies.get( ch1 ) );
  109.  
  110.         ALPHABET = new char[chAlphabet.size()];
  111.         ALPHABET_WITH_SPACE = new char[chAlphabet.size()+1];
  112.         for( int i = 0; i < chAlphabet.size(); i++ )
  113.             ALPHABET_WITH_SPACE[i] = ALPHABET[i] = chAlphabet.get( i );
  114.  
  115.         ALPHABET_WITH_SPACE[chAlphabet.size()] = ' ';
  116.         ALPHABET_STRING = new String( ALPHABET );
  117.         ALPHABET_WITH_SPACE_STRING = new String( ALPHABET_WITH_SPACE );
  118.         RevDictionaryDB DDb = new RevDictionaryDB( sWords.size() );
  119.  
  120.         // Compute all word metrics...
  121.         for( String sWord : sWords )
  122.             DDb.registerWord( sWord );
  123.  
  124.         // Read in the codes...
  125.         final List<String> sCodes = readInCodesToCrack( "./codes.txt" );
  126.         int nTotalQueries = 0;
  127.         int nDecoded = 0;
  128.         int nMinQueries = Integer.MAX_VALUE;
  129.         int nMaxQueries = 0;
  130.         long iStartTime = System.currentTimeMillis();
  131.  
  132.         // Main loop. Gets a code, creates full oracle for code, identifies code, moves on.
  133.         for( String sCode : sCodes ) {
  134.             final FullOracle Or = new FullOracle( sCode );
  135.  
  136.             List<Long> L_Candidates = generatePrincipalCandidateList( Or, sWords, DDb );
  137.             String sCodeWord = resolveCodeWord( Or, L_Candidates, DDb );
  138.  
  139.             // If the resolved code word is returned with a leading asterisk, it means the filtering routine has
  140.             // already, by good fortune, executed the precise query needed for a positive identification.
  141.             RevOutcome Oc = sCodeWord.startsWith( "*" ) ? RevOutcome.VALID : Or.query( sCodeWord );
  142.  
  143.             // Check that we've done it correctly...
  144.             if( Oc.isExactMatch ) {
  145.                 nTotalQueries += Or.getQueryCount();
  146.                 nDecoded++;
  147.  
  148.                 // Necessary to avoid problems with the heap.
  149.                 if( nDecoded %20 == 0 )
  150.                     M_MultipointWords.clear();
  151.  
  152.                 nMinQueries = Math.min( Or.getQueryCount(), nMinQueries );
  153.                 nMaxQueries = Math.max( Or.getQueryCount(), nMaxQueries );
  154.  
  155.                 if( SHOW_ALL_OUTPUTS )
  156.                     System.out.println( sCode + " OK: " + Or.getQueryCount() + " queries (" + nTotalQueries + " in " +
  157.                         nDecoded + " = " + Math.round( nTotalQueries/(double)nDecoded*100. )/100. + ")" );
  158.             } else {
  159.                 System.err.println( "Failed to decode: " + sCode );
  160.                 System.exit( 1 );
  161.             }
  162.         }
  163.  
  164.         // Output the only metrics that matter...
  165.         System.out.println( "Decoded " + nDecoded + " items in " + nTotalQueries + " queries (" +
  166.                 Math.round( nTotalQueries/(double)nDecoded*100. )/100. + " queries per item).\n" +
  167.             "Time to complete: " + (System.currentTimeMillis() - iStartTime) + " msec\n" );
  168.  
  169.         System.out.println( "Min queries: " + nMinQueries );
  170.         System.out.println( "Max queries: " + nMaxQueries );
  171.     }
  172.  
  173.     static SortedSet<String> readInDictionary( String sDictFile ) {
  174.         SortedSet<String> sWords = new TreeSet<>();
  175.         try {
  176.             BufferedReader BR = new BufferedReader( new FileReader( sDictFile ) );
  177.             String sWord;
  178.             while( (sWord = BR.readLine()) != null )
  179.                 sWords.add( sWord );
  180.  
  181.             BR.close();
  182.         } catch( IOException ioe ) {
  183.             throw new RuntimeException( "could not read contents of dictionary file: " + sDictFile );
  184.         }
  185.         return sWords;
  186.     }
  187.  
  188.     static List<String> readInCodesToCrack( String sCodesFile ) {
  189.         List<String> sCodes = new LinkedList<>();
  190.         try {
  191.             BufferedReader BR = new BufferedReader( new FileReader( sCodesFile ) );
  192.             String sCode;
  193.             while( (sCode = BR.readLine()) != null )
  194.                 if( !sCode.isEmpty() )
  195.                     sCodes.add( sCode );
  196.  
  197.             BR.close();
  198.         } catch( IOException ioe ) {
  199.             throw new RuntimeException( "could not read contents of codes file: " + sCodesFile );
  200.         }
  201.         return sCodes;
  202.     }
  203.  
  204.     static List<Long> generatePrincipalCandidateList( RevOracle Or, SortedSet<String> sWords, RevDictionaryDB DDb ) {
  205.         final char CH0 = ALPHABET[0],
  206.             CH1 = ALPHABET[1],
  207.             CH2 = ALPHABET[2],
  208.             CH3 = ALPHABET[3],
  209.             CH4 = ALPHABET[4];
  210.  
  211.         StringBuilder SBu = new StringBuilder( DDb.iMaxWordLength*3*(1 + ALPHABET.length) + 2 );
  212.  
  213.         SBu.append( generateBitEmSieve( ' ', 0, DDb ) );
  214.         for( int i = 0; i < DDb.iMaxWordLength; i++ )
  215.             SBu.append( ALPHABET_STRING );
  216.  
  217.         RevOutcome Oc = Or.query( SBu.toString() );
  218.         final int nTotalChars = Oc.nCoincide + Oc.nMatch,
  219.             iSieveZeroBitCount = Oc.nMatch;
  220.  
  221.         Oc = Or.query( generateBitEmSieve( ' ', 1, DDb ) + generateEnCharString( CH0, DDb.iMaxWordLength ) );
  222.  
  223.         final int iSieveOneBitCount = Oc.nMatch,
  224.             nChar0 = Oc.nMatch + Oc.nCoincide - 2;
  225.  
  226.         Oc = Or.query( generateBitEmSieve( CH0, 0, DDb ) + generateEnCharString( CH1, DDb.iMaxWordLength ) );
  227.  
  228.         final int nEvenChar0 = Oc.nMatch,
  229.             nOddChar0 = nChar0 - nEvenChar0,
  230.             nChar1 = Oc.nMatch + Oc.nCoincide - nChar0;
  231.  
  232.         Oc = Or.query( generateBitEmSieve( CH1, 0, DDb ) + generateEnCharString( CH2, DDb.iMaxWordLength ) );
  233.  
  234.         final int nEvenChar1 = Oc.nMatch,
  235.             nOddChar1 = nChar1 - nEvenChar1,
  236.             nChar2 = Oc.nMatch + Oc.nCoincide - nChar1;
  237.  
  238.         Oc = Or.query( generateBitEmSieve( CH2, 0, DDb ) + generateEnCharString( CH3, DDb.iMaxWordLength ) );
  239.  
  240.         final int nEvenChar2 = Oc.nMatch,
  241.             nOddChar2 = nChar2 - nEvenChar2,
  242.             nChar3 = Oc.nMatch + Oc.nCoincide - nChar2;
  243.  
  244.         Oc = Or.query( generateBitEmSieve( CH3, 0, DDb ) + generateEnCharString( CH4, DDb.iMaxWordLength ) );
  245.  
  246.         final int nEvenChar3 = Oc.nMatch,
  247.             nOddChar3 = nChar3 - nEvenChar3,
  248.             nChar4 = Oc.nMatch + Oc.nCoincide - nChar3;
  249.  
  250.         List<CodeWordProfile> CWPs = getCodeWordProfilesFor( nTotalChars, iSieveZeroBitCount, iSieveOneBitCount, DDb );
  251.  
  252.         final int[] iEvenCharCounts = { nEvenChar0, nEvenChar1, nEvenChar2, nEvenChar3 },
  253.             iOddCharCounts = { nOddChar0, nOddChar1, nOddChar2, nOddChar3 };
  254.  
  255.         final Map<Alignment,int[]> M_PostW0Counts = new EnumMap<>( Alignment.class ),
  256.             M_PostW1Counts = new EnumMap<>( Alignment.class );
  257.         final int[] iPostW0EvenCharCounts = new int[4],
  258.             iPostW0OddCharCounts = new int[4],
  259.             iPostW1EvenCharCounts = new int[4],
  260.             iPostW1OddCharCounts = new int[4];
  261.  
  262.         M_PostW0Counts.put( Alignment.EVEN, iPostW0EvenCharCounts );
  263.         M_PostW0Counts.put( Alignment.ODD, iPostW0OddCharCounts );
  264.         M_PostW1Counts.put( Alignment.EVEN, iPostW1EvenCharCounts );
  265.         M_PostW1Counts.put( Alignment.ODD, iPostW1OddCharCounts );
  266.  
  267.         List<Long> L_Candidates = new LinkedList<>();
  268.  
  269.         for( CodeWordProfile CWP : CWPs ) {
  270.             FivePointDiscriminant FpD1W0 = new FivePointDiscriminant( CWP.wordLength( 0 ), 0, nEvenChar0, nOddChar0,
  271.                     1, nEvenChar1, nOddChar1 ),
  272.                 FpD2W0 = new FivePointDiscriminant( CWP.wordLength( 0 ), 2, nEvenChar2, nOddChar2, 3, nEvenChar3,
  273.                     nOddChar3 );
  274.  
  275.             TwoPointDiscriminant TpD3W0 = new TwoPointDiscriminant( CWP.wordLength( 0 ), 4, nChar4 );
  276.             SortedSet<String> sWord0s = getMultipointWords( sWords, FpD1W0, FpD2W0, TpD3W0, DDb,
  277.                 SelectType.UPPER_BOUND );
  278.  
  279.             for( String sWord0 : sWord0s ) {
  280.                 Map<Integer,Integer> M_EvenCharCounts = DDb.charCountsForWord( sWord0, Alignment.EVEN ),
  281.                     M_OddCharCounts = DDb.charCountsForWord( sWord0, Alignment.ODD );
  282.  
  283.                 for( int iChar = 0; iChar < 4; iChar++ ) {
  284.                     iPostW0EvenCharCounts[iChar] = iEvenCharCounts[iChar] - M_EvenCharCounts.getOrDefault( iChar, 0 );
  285.                     iPostW0OddCharCounts[iChar] = iOddCharCounts[iChar] - M_OddCharCounts.getOrDefault( iChar, 0 );
  286.                 }
  287.  
  288.                 Map<Integer,Integer> M_CharCounts = DDb.charCountsForWord( sWord0, null );
  289.                 int nPostW0Char4 = nChar4 - M_CharCounts.getOrDefault( 4, 0 );
  290.  
  291.                 Alignment A1 = CWP.wordAlignment( 1 );
  292.  
  293.                 FivePointDiscriminant FpD1W1 = new FivePointDiscriminant( CWP.wordLength( 1 ), 0,
  294.                         M_PostW0Counts.get( Alignment.EVEN.onWord( A1 ) )[0],
  295.                         M_PostW0Counts.get( Alignment.ODD.onWord( A1 ) )[0], 1,
  296.                         M_PostW0Counts.get( Alignment.EVEN.onWord( A1 ) )[1],
  297.                         M_PostW0Counts.get( Alignment.ODD.onWord( A1 ) )[1] ),
  298.                     FpD2W1 = new FivePointDiscriminant( CWP.wordLength( 1 ), 2,
  299.                         M_PostW0Counts.get( Alignment.EVEN.onWord( A1 ) )[2],
  300.                         M_PostW0Counts.get( Alignment.ODD.onWord( A1 ) )[2], 3,
  301.                         M_PostW0Counts.get( Alignment.EVEN.onWord( A1 ) )[3],
  302.                         M_PostW0Counts.get( Alignment.ODD.onWord( A1 ) )[3] );
  303.  
  304.                 TwoPointDiscriminant TpD3W1 = new TwoPointDiscriminant( CWP.wordLength( 1 ), 4, nPostW0Char4 );
  305.                 SortedSet<String> sWord1s = getMultipointWords( sWords, FpD1W1, FpD2W1, TpD3W1, DDb,
  306.                     SelectType.UPPER_BOUND );
  307.  
  308.                 for( String sWord1 : sWord1s ) {
  309.                     M_EvenCharCounts = DDb.charCountsForWord( sWord1, Alignment.EVEN.onWord( A1 ) );
  310.                     M_OddCharCounts = DDb.charCountsForWord( sWord1, Alignment.ODD.onWord( A1 ) );
  311.                     for( int iChar = 0; iChar < 4; iChar++ ) {
  312.                         iPostW1EvenCharCounts[iChar] = iPostW0EvenCharCounts[iChar] -
  313.                             M_EvenCharCounts.getOrDefault( iChar, 0 );
  314.                         iPostW1OddCharCounts[iChar] = iPostW0OddCharCounts[iChar] -
  315.                             M_OddCharCounts.getOrDefault( iChar, 0 );
  316.                     }
  317.  
  318.                     M_CharCounts = DDb.charCountsForWord( sWord1, null );
  319.                     int nPostW1Char4 = nPostW0Char4 - M_CharCounts.getOrDefault( 4, 0 );
  320.  
  321.                     Alignment A2 = CWP.wordAlignment( 2 );
  322.  
  323.                     FivePointDiscriminant FpD1W2 = new FivePointDiscriminant( CWP.wordLength( 2 ), 0,
  324.                             M_PostW1Counts.get( Alignment.EVEN.onWord( A2 ) )[0],
  325.                             M_PostW1Counts.get( Alignment.ODD.onWord( A2 ) )[0], 1,
  326.                             M_PostW1Counts.get( Alignment.EVEN.onWord( A2 ) )[1],
  327.                             M_PostW1Counts.get( Alignment.ODD.onWord( A2 ) )[1] ),
  328.                         FpD2W2 = new FivePointDiscriminant( CWP.wordLength( 2 ), 2,
  329.                             M_PostW1Counts.get( Alignment.EVEN.onWord( A2 ) )[2],
  330.                             M_PostW1Counts.get( Alignment.ODD.onWord( A2 ) )[2], 3,
  331.                             M_PostW1Counts.get( Alignment.EVEN.onWord( A2 ) )[3],
  332.                             M_PostW1Counts.get( Alignment.ODD.onWord( A2 ) )[3] );
  333.  
  334.                     TwoPointDiscriminant TpD3W2 = new TwoPointDiscriminant( CWP.wordLength( 2 ), 4, nPostW1Char4 );
  335.                     SortedSet<String> sWord2s = getMultipointWords( sWords, FpD1W2, FpD2W2, TpD3W2, DDb,
  336.                         SelectType.EXACT_MATCH );
  337.  
  338.                     for( String sWord2 : sWord2s )
  339.                         L_Candidates.add( DDb.wordTripletToLong( sWord0, sWord1, sWord2 ) );
  340.                 }
  341.             }
  342.         }
  343.         return L_Candidates;
  344.     }
  345.  
  346.     static final int FOUR_WAY_FILTERING_MAX_CANDIDATES = 80000;
  347.     static final int TWENTY_SEVEN_WAY_FILTERING_MAX_CANDIDATES = 4800;
  348.     static final int SIXTY_FOUR_WAY_FILTERING_MAX_CANDIDATES = 320;
  349.  
  350.     static String resolveCodeWord( RevOracle Or, List<Long> L_Candidates, RevDictionaryDB DDb ) {
  351.         while( L_Candidates.size() > 1 ) {
  352.             int nCand = L_Candidates.size();
  353.             if( nCand > 4e6 ) {
  354.                 L_Candidates = takeAShotInTheDark( Or, L_Candidates, DDb );
  355.                 continue;
  356.             }
  357.             if( nCand <= 4 ) {
  358.                 String sCodeWord = queryToResolve( Or, L_Candidates, DDb );
  359.                 if( sCodeWord != null )
  360.                     return sCodeWord;
  361.             }
  362.  
  363.             CharMatrix CMx = new CharMatrix( L_Candidates, DDb );
  364.             String[] sQueries =
  365.                 nCand <= SIXTY_FOUR_WAY_FILTERING_MAX_CANDIDATES ? CMx.getSixtyFourWayOptimalQueryStrings() : (
  366.                 nCand <= TWENTY_SEVEN_WAY_FILTERING_MAX_CANDIDATES ? CMx.getTwentySevenWayOptimalQueryStrings() : (
  367.                 nCand <= FOUR_WAY_FILTERING_MAX_CANDIDATES ? CMx.getFourWayOptimalQueryStrings() :
  368.                 CMx.getOneWayOptimalQueryStrings()) );
  369.  
  370.             QueryProfile QPrOpt = null;
  371.             for( String sQuery : sQueries ) {
  372.                 QueryProfile QPr = new QueryProfile( sQuery, L_Candidates, DDb );
  373.  
  374.                 if( QPrOpt == null || QPr.isBetterThan( QPrOpt ) )
  375.                     QPrOpt = QPr;
  376.             }
  377.             if( QPrOpt.iPower < L_Candidates.size()/2 && nCand > TWENTY_SEVEN_WAY_FILTERING_MAX_CANDIDATES ) {
  378.                 for( String sQuery : CMx.getTwentySevenWayOptimalQueryStrings() ) {
  379.                     QueryProfile QPr = new QueryProfile( sQuery, L_Candidates, DDb );
  380.  
  381.                     if( QPr.isBetterThan( QPrOpt ) )
  382.                         QPrOpt = QPr;
  383.                 }
  384.             }
  385.  
  386.             assert QPrOpt != null;
  387.             RevOutcome Oc = Or.query( QPrOpt.getQueryString() );
  388.  
  389.             L_Candidates = QPrOpt.getCandidateListForOutcome( Oc );
  390.         }
  391.         return DDb.longToWordTriplet( L_Candidates.get( 0 ) );
  392.     }
  393.  
  394.     static String queryToResolve( RevOracle Or, List<Long> L_Candidates, RevDictionaryDB DDb ) {
  395.         switch( L_Candidates.size() ) {
  396.         case 2:
  397.             return Or.query( DDb.longToWordTriplet( L_Candidates.get( 0 ) ) ).isExactMatch ?
  398.                 ('*' + DDb.longToWordTriplet( L_Candidates.get( 0 ) )) :
  399.                 DDb.longToWordTriplet( L_Candidates.get( 1 ) );
  400.  
  401.         case 3:
  402.         case 4:
  403.             for( Long L_Pivot : L_Candidates ) {
  404.                 String sPivot = DDb.longToWordTriplet( L_Pivot );
  405.                 QueryProfile QPr = new QueryProfile( sPivot, L_Candidates, DDb );
  406.  
  407.                 if( QPr.iPower == L_Candidates.size() - 1 ) {
  408.                     RevOutcome Oc = Or.query( sPivot );
  409.                     return Oc.isExactMatch ? ('*' + sPivot) :
  410.                         DDb.longToWordTriplet( QPr.getCandidateListForOutcome( Oc ).get( 0 ) );
  411.                 }
  412.             }
  413.             return null;
  414.  
  415.         default:
  416.             throw new InternalError();
  417.         }
  418.     }
  419.  
  420.     static final int[] SHOT_IN_THE_DARK_QUERY = { 0, 2, 3, 0, 4, 1, 5, 2, 9, 0, 7, 3, 1, 2, 4, 5, 5, 0, 0, 6, 10, 2,
  421.         3, 3, 7, 0, 4, 9, 15, 2, 22, 1, 9, 3, 0, 4, 7, 10, 0, 2, 4, 6, 0, 2, 1, 1, 8, 0, 7, 19, 3, 0, 2, 17, 8, 0, 1,
  422.         5, 9, 11, 2, 4, 8, 0, 0, 3, 2, 4, 16, 14, 0 };
  423.  
  424.     static List<Long> takeAShotInTheDark( RevOracle Or, List<Long> L_Candidates, RevDictionaryDB DDb ) {
  425.         int nChar = DDb.longToWordTriplet( L_Candidates.get( 0 ) ).length(),
  426.             i0 = L_Candidates.size() %(SHOT_IN_THE_DARK_QUERY.length + 1 - nChar);
  427.  
  428.         char[] chsQuery = new char[nChar];
  429.         final int[] i = {0};
  430.         Arrays.stream( SHOT_IN_THE_DARK_QUERY, i0, i0 + nChar ).forEach( (int iChar) -> {
  431.             chsQuery[i[0]++] = ALPHABET[iChar];
  432.         } );
  433.  
  434.         String sQuery = new String( chsQuery );
  435.         RevOutcome OcRef = Or.query( sQuery );
  436.         MockOracle MOr = new MockOracle( sQuery );
  437.  
  438.         Iterator<Long> I = L_Candidates.iterator();
  439.         while( I.hasNext() ) {
  440.             RevOutcome Oc = MOr.query( DDb.longToWordTriplet( I.next() ) );
  441.             if( !Oc.equals( OcRef ) )
  442.                 I.remove();
  443.         }
  444.         return L_Candidates;
  445.     }
  446.  
  447.  
  448.     static final class CharMatrix {
  449.         final int[][] iCounts;
  450.         final int nChar;
  451.  
  452.         CharMatrix( List<Long> L_Candidates, RevDictionaryDB DDb ) {
  453.             nChar = DDb.longToWordTriplet( L_Candidates.get( 0 ) ).length();
  454.             iCounts = new int[nChar][ALPHABET_WITH_SPACE.length];
  455.  
  456.             for( Long L_Candidate : L_Candidates ) {
  457.                 char[] chsCandidate = DDb.longToWordTriplet( L_Candidate ).toCharArray();
  458.                 for( int iChar = 0; iChar < nChar; iChar++ )
  459.                     iCounts[iChar][ALPHABET_WITH_SPACE_STRING.indexOf( chsCandidate[iChar] )]++;
  460.             }
  461.         }
  462.  
  463.         String[] getOneWayOptimalQueryStrings() {
  464.             char[] chs = new char[nChar];
  465.             for( int iChar = 0; iChar < nChar; iChar++ )
  466.                 chs[iChar] = maxCharAtPosition( iChar );
  467.  
  468.             return new String[] { new String( chs ) };
  469.         }
  470.  
  471.         String[] getFourWayOptimalQueryStrings() {
  472.             char[] chs = new char[nChar];
  473.             char[][] chMaxes = new char[nChar][];
  474.  
  475.             for( int iChar = 0; iChar < nChar; iChar++ )
  476.                 chMaxes[iChar] = maxCharsAtPosition( iChar, 2 );
  477.  
  478.             String[] sQueries = new String[4];
  479.             for( int iQuery = 0; iQuery < 4; iQuery++ ) {
  480.                 for( int iChar = 0; iChar < nChar; iChar += 2 ) {
  481.                     chs[iChar] = chMaxes[iChar][iQuery &1];
  482.                     if( iChar < nChar-1 )
  483.                         chs[iChar+1] = chMaxes[iChar+1][(iQuery &2) >> 1];
  484.                 }
  485.                 sQueries[iQuery] = new String( chs );
  486.             }
  487.             return sQueries;
  488.         }
  489.  
  490.         String[] getTwentySevenWayOptimalQueryStrings() {
  491.             char[] chs = new char[nChar];
  492.             char[][] chMaxes = new char[nChar][];
  493.  
  494.             for( int iChar = 0; iChar < nChar; iChar++ )
  495.                 chMaxes[iChar] = maxCharsAtPosition( iChar, 3 );
  496.  
  497.             String[] sQueries = new String[27];
  498.             for( int iQuery = 0; iQuery < 27; iQuery++ ) {
  499.                 for( int iChar = 0; iChar < nChar; iChar += 3 ) {
  500.                     chs[iChar] = chMaxes[iChar][iQuery %3];
  501.                     if( iChar < nChar-1 )
  502.                         chs[iChar+1] = chMaxes[iChar+1][(iQuery/3) %3];
  503.                     if( iChar < nChar-2 )
  504.                         chs[iChar+2] = chMaxes[iChar+2][(iQuery/9) %3];
  505.                 }
  506.                 sQueries[iQuery] = new String( chs );
  507.             }
  508.             return sQueries;
  509.         }
  510.  
  511.         String[] getSixtyFourWayOptimalQueryStrings() {
  512.             char[] chs = new char[nChar];
  513.             char[][] chMaxes = new char[nChar][];
  514.  
  515.             for( int iChar = 0; iChar < nChar; iChar++ )
  516.                 chMaxes[iChar] = maxCharsAtPosition( iChar, 4 );
  517.  
  518.             String[] sQueries = new String[64];
  519.             for( int iQuery = 0; iQuery < 64; iQuery++ ) {
  520.                 for( int iChar = 0; iChar < nChar; iChar += 3 ) {
  521.                     chs[iChar] = chMaxes[iChar][iQuery &3];
  522.                     if( iChar < nChar-1 )
  523.                         chs[iChar+1] = chMaxes[iChar+1][(iQuery >> 2) &3];
  524.                     if( iChar < nChar-2 )
  525.                         chs[iChar+2] = chMaxes[iChar+2][(iQuery >> 4) &3];
  526.                 }
  527.                 sQueries[iQuery] = new String( chs );
  528.             }
  529.             return sQueries;
  530.         }
  531.  
  532.         char maxCharAtPosition( int iChar ) {
  533.             int[] iPositionCounts = iCounts[iChar];
  534.             int iMaxCount = 0;
  535.             char chMax = '\0';
  536.             for( int i = 0; i < iPositionCounts.length; i++ ) {
  537.                 int iCount = iPositionCounts[i];
  538.  
  539.                 if( iCount > iMaxCount ) {
  540.                     chMax = ALPHABET_WITH_SPACE[i];
  541.                     iMaxCount = iCount;
  542.                 }
  543.             }
  544.             return chMax;
  545.         }
  546.  
  547.         char[] maxCharsAtPosition( int iChar, int nToReturn ) {
  548.             int[] iPositionCounts = iCounts[iChar];
  549.             int[] iMaxCounts = new int[nToReturn];
  550.             char[] chMaxes = new char[nToReturn];
  551.  
  552.             for( int i = 0; i < iPositionCounts.length; i++ ) {
  553.                 int iCount = (iPositionCounts[i] << 8) + i;
  554.  
  555.                 if( iCount > iMaxCounts[0] ) {
  556.                     iMaxCounts[0] = iCount;
  557.                     Arrays.sort( iMaxCounts );
  558.                 }
  559.             }
  560.             for( int i = 0; i < nToReturn; i++ )
  561.                 chMaxes[i] = ALPHABET_WITH_SPACE[iMaxCounts[nToReturn-1-i] &0xFF];
  562.  
  563.             return chMaxes;
  564.         }
  565.     }
  566.  
  567.     static final class QueryProfile {
  568.         final Map<RevOutcome,List<Long>> M_Oc2CandLists;
  569.         final int iPower;
  570.         final String sQuery;
  571.  
  572.         QueryProfile( String sQuery_, List<Long> L_Candidates, RevDictionaryDB DDb ) {
  573.             sQuery = sQuery_;
  574.             M_Oc2CandLists = new HashMap<>( 32 );
  575.  
  576.             MockOracle MOr = new MockOracle( sQuery );
  577.             for( Long L_Candidate : L_Candidates ) {
  578.                 RevOutcome Oc = MOr.query( DDb.longToWordTriplet( L_Candidate ) );
  579.                 List<Long> LAtOcs = M_Oc2CandLists.get( Oc );
  580.                 if( LAtOcs == null ) {
  581.                     LAtOcs = new LinkedList<>();
  582.                     M_Oc2CandLists.put( Oc, LAtOcs );
  583.                 }
  584.                 LAtOcs.add( L_Candidate );
  585.             }
  586.             iPower = L_Candidates.size() - M_Oc2CandLists.values().parallelStream().
  587.                 mapToInt( (List<Long> LAtOcs) -> LAtOcs.size() ).max().getAsInt();
  588.         }
  589.  
  590.         String getQueryString() {
  591.             return sQuery;
  592.         }
  593.  
  594.         List<Long> getCandidateListForOutcome( RevOutcome Oc ) {
  595.             return M_Oc2CandLists.get( Oc );
  596.         }
  597.  
  598.         boolean isBetterThan( QueryProfile QPr ) {
  599.             return iPower == QPr.iPower ? (M_Oc2CandLists.size() > QPr.M_Oc2CandLists.size()) : (iPower > QPr.iPower);
  600.         }
  601.  
  602.         public String toString() {
  603.             return "Query: \"" + sQuery + "\", Power: " + iPower + ", Fragments: " + M_Oc2CandLists.size();
  604.         }
  605.     }
  606.  
  607.     static String generateEnCharString( char ch, int n ) {
  608.         char[] chs = new char[n];
  609.  
  610.         Arrays.fill( chs, ch );
  611.         return new String( chs );
  612.     }
  613.  
  614.     static String generateBitEmSieve( char ch, int m, RevDictionaryDB DDb ) {
  615.         char[] chs = new char[DDb.iMaxWordLength*3 + 2];
  616.         int iMask = 1 << m;
  617.         for( int i = 0; i < chs.length; i++ )
  618.             chs[i] = (i &iMask) == 0 ? ch : ZERO_COUNT_PLACEHOLDER;
  619.  
  620.         return new String( chs );
  621.     }
  622.  
  623.  
  624.     static final Map<TwoPointDiscriminant, SortedSet<String>> M_TwoPointWords_UpperBound = new HashMap<>( 2000 ),
  625.         M_TwoPointWords_ExactMatch = new HashMap<>( 2000 );
  626.  
  627.     static SortedSet<String> selectTwoPointWords( SortedSet<String> sWords, TwoPointDiscriminant TpD,
  628.         RevDictionaryDB DDb, SelectType STy )
  629.     {
  630.         Map<TwoPointDiscriminant, SortedSet<String>> M_TwoPointWords = STy == SelectType.UPPER_BOUND ?
  631.             M_TwoPointWords_UpperBound : M_TwoPointWords_ExactMatch;
  632.  
  633.         SortedSet<String> sCandidates = M_TwoPointWords.get( TpD );
  634.  
  635.         if( sCandidates != null )
  636.             return sCandidates;
  637.  
  638.         SortedSet<String> sMatches = new TreeSet<>();
  639.         for( String sWord : sWords ) {
  640.             if( sWord.length() != TpD.nCharCount )
  641.                 continue;
  642.  
  643.             Map<Integer,Integer> M_CharCounts = DDb.charCountsForWord( sWord, null );
  644.             int iCount = M_CharCounts.getOrDefault( TpD.iCharA, 0 );
  645.  
  646.             if( (STy == SelectType.EXACT_MATCH && iCount == TpD.nCharA) ||
  647.                 (STy == SelectType.UPPER_BOUND && iCount <= TpD.nCharA) )
  648.             {
  649.                 sMatches.add( sWord );
  650.             }
  651.         }
  652.         M_TwoPointWords.put( TpD, sMatches );
  653.  
  654.         return sMatches;
  655.     }
  656.  
  657.     static final Map<FivePointDiscriminant, SortedSet<String>> M_FivePointWords_UpperBound = new HashMap<>( 2000 ),
  658.         M_FivePointWords_ExactMatch = new HashMap<>( 2000 );
  659.  
  660.     static SortedSet<String> selectFivePointWords( SortedSet<String> sWords, FivePointDiscriminant FpD,
  661.         RevDictionaryDB DDb, SelectType STy )
  662.     {
  663.         Map<FivePointDiscriminant, SortedSet<String>> M_FivePointWords = STy == SelectType.UPPER_BOUND ?
  664.             M_FivePointWords_UpperBound : M_FivePointWords_ExactMatch;
  665.  
  666.         SortedSet<String> sCandidates = M_FivePointWords.get( FpD );
  667.  
  668.         if( sCandidates != null )
  669.             return sCandidates;
  670.  
  671.         SortedSet<String> sMatches = new TreeSet<>();
  672.         for( String sWord : sWords ) {
  673.             if( sWord.length() != FpD.nCharCount )
  674.                 continue;
  675.  
  676.             Map<Integer,Integer> M_EvenCharCounts = DDb.charCountsForWord( sWord, Alignment.EVEN ),
  677.                 M_OddCharCounts = DDb.charCountsForWord( sWord, Alignment.ODD );
  678.  
  679.             int iCountEvenA = M_EvenCharCounts.getOrDefault( FpD.iCharA, 0 ),
  680.                 iCountOddA = M_OddCharCounts.getOrDefault( FpD.iCharA, 0 ),
  681.                 iCountEvenB = M_EvenCharCounts.getOrDefault( FpD.iCharB, 0 ),
  682.                 iCountOddB = M_OddCharCounts.getOrDefault( FpD.iCharB, 0 );
  683.  
  684.             if( STy == SelectType.EXACT_MATCH ) {
  685.                 if( iCountEvenA == FpD.nEvenCharA && iCountOddA == FpD.nOddCharA &&
  686.                     iCountEvenB == FpD.nEvenCharB && iCountOddB == FpD.nOddCharB )
  687.                 {
  688.                     sMatches.add( sWord );
  689.                 }
  690.             } else {
  691.                 if( iCountEvenA <= FpD.nEvenCharA && iCountOddA <= FpD.nOddCharA &&
  692.                     iCountEvenB <= FpD.nEvenCharB && iCountOddB <= FpD.nOddCharB )
  693.                 {
  694.                     sMatches.add( sWord );
  695.                 }
  696.             }
  697.         }
  698.         M_FivePointWords.put( FpD, sMatches );
  699.  
  700.         return sMatches;
  701.     }
  702.  
  703.  
  704.  
  705.     static final Map<MultipointDiscriminant, SortedSet<String>> M_MultipointWords = new HashMap<>( 15800 );
  706.  
  707.     static SortedSet<String> getMultipointWords( SortedSet<String> sWords, FivePointDiscriminant FpD1,
  708.         FivePointDiscriminant FpD2, TwoPointDiscriminant TpD3, RevDictionaryDB DDb,
  709.         SelectType STy )
  710.     {
  711.         MultipointDiscriminant MpD = new MultipointDiscriminant( FpD1, FpD2, TpD3, STy );
  712.         SortedSet<String> sCandidates = M_MultipointWords.get( MpD );
  713.  
  714.         if( sCandidates != null )
  715.             return sCandidates;
  716.  
  717.         SortedSet<String> sWordD1 = new TreeSet<>( selectFivePointWords( sWords, FpD1, DDb, STy ) ),
  718.             sWordD2 = selectFivePointWords( sWords, FpD2, DDb, STy ),
  719.             sWordD3 = selectTwoPointWords( sWords, TpD3, DDb, STy );
  720.  
  721.         if( sWordD1.isEmpty() || sWordD2.isEmpty() || sWordD3.isEmpty() ) {
  722.             sCandidates = Collections.emptySortedSet();
  723.             M_MultipointWords.put( MpD, sCandidates );
  724.  
  725.             return sCandidates;
  726.         }
  727.  
  728.         Iterator<String> I1 = sWordD1.iterator(),
  729.             I2 = sWordD2.iterator(),
  730.             I3 = sWordD3.iterator();
  731.  
  732.         String sWord2 = I2.next(),
  733.             sWord3 = I3.next();
  734.  
  735.         merger: while( I1.hasNext() ) {
  736.             String sWord1 = I1.next();
  737.             int iResult1, iResult2;
  738.  
  739.             while( (iResult1 = sWord1.compareTo( sWord2 )) > 0 ) {
  740.                 if( !I2.hasNext() )
  741.                     break merger;
  742.  
  743.                 sWord2 = I2.next();
  744.             }
  745.             while( (iResult2 = sWord1.compareTo( sWord3 )) > 0 ) {
  746.                 if( !I3.hasNext() )
  747.                     break merger;
  748.  
  749.                 sWord3 = I3.next();
  750.             }
  751.             if( iResult1 != 0 || iResult2 != 0 )
  752.                 I1.remove();
  753.         }
  754.         M_MultipointWords.put( MpD, sWordD1 );
  755.  
  756.         return sWordD1;
  757.     }
  758.  
  759.     static final Map<CodeWordProfileSetIndex, List<CodeWordProfile>> M_CStsRegistry = new HashMap<>( 128 );
  760.  
  761.     static List<CodeWordProfile> getCodeWordProfilesFor( int nTotalChars, int iSieveZeroBitCount,
  762.         int iSieveOneBitCount, RevDictionaryDB DDb )
  763.     {
  764.         CodeWordProfileSetIndex CSt = new CodeWordProfileSetIndex( nTotalChars, iSieveZeroBitCount,
  765.             iSieveOneBitCount );
  766.  
  767.         List<CodeWordProfile> CWPs = M_CStsRegistry.get( CSt );
  768.         if( CWPs == null ) {
  769.             CWPs = CodeWordProfileSetIndex.generateAllCodeWordProfiles( nTotalChars, iSieveZeroBitCount,
  770.                 iSieveOneBitCount, DDb );
  771.  
  772.             M_CStsRegistry.put( CSt, CWPs );
  773.         }
  774.         return CWPs;
  775.     }
  776.  
  777.     static final class CodeWordProfileSetIndex {
  778.         final int nTotalChars;
  779.         final int iSieveZeroBitCount;
  780.         final int iSieveOneBitCount;
  781.  
  782.         CodeWordProfileSetIndex( int nTotalChars_, int iSieveZeroBitCount_, int iSieveOneBitCount_ )
  783.         {
  784.             nTotalChars = nTotalChars_;
  785.             iSieveZeroBitCount = iSieveZeroBitCount_;
  786.             iSieveOneBitCount = iSieveOneBitCount_;
  787.         }
  788.  
  789.         public boolean equals( Object o ) {
  790.             if( !(o instanceof CodeWordProfileSetIndex) )
  791.                 return false;
  792.  
  793.             CodeWordProfileSetIndex CSt = (CodeWordProfileSetIndex)o;
  794.             return CSt.nTotalChars == nTotalChars &&
  795.                 CSt.iSieveZeroBitCount == iSieveZeroBitCount &&
  796.                 CSt.iSieveOneBitCount == iSieveOneBitCount;
  797.         }
  798.  
  799.         public int hashCode() {
  800.             return iSieveZeroBitCount + 37*(iSieveOneBitCount + 37*nTotalChars);
  801.         }
  802.  
  803.         public String toString() {
  804.             return "Chars: " + nTotalChars + ", Sieve 0: " + iSieveZeroBitCount + ", Sieve 1: " + iSieveOneBitCount;
  805.         }
  806.  
  807.         static List<CodeWordProfile> generateAllCodeWordProfiles( int nTotalChars_, int iSieveZeroBitCount_,
  808.             int iSieveOneBitCount_, RevDictionaryDB DDb )
  809.         {
  810.             List<CodeWordProfile> CWPs_ = new LinkedList<>();
  811.             int[] iWordLengths = new int[3];
  812.  
  813.             generateCodeWordProfilesImpl( CWPs_, iWordLengths, nTotalChars_ - 2, iSieveZeroBitCount_,
  814.                 iSieveOneBitCount_, DDb.iMaxWordLength, 0, 0 );
  815.  
  816.             return CWPs_;
  817.         }
  818.  
  819.         static void generateCodeWordProfilesImpl( List<CodeWordProfile> CWPs_, int[] iWordLengths, int nTotalChars_,
  820.             int iSieveZeroBitCount_, int iSieveOneBitCount_, int iMaxWordLength, int iReserved,
  821.             int iLevel )
  822.         {
  823.             int iLevelsToGo = iWordLengths.length - 1 - iLevel;
  824.  
  825.             if( iLevelsToGo == 0 ) {
  826.                 iWordLengths[iLevel] = nTotalChars_ - iReserved;
  827.                 if( iWordLengths[iLevel] <= iMaxWordLength &&
  828.                     CodeWordProfile.isSieveCompliant( iWordLengths, iSieveZeroBitCount_, iSieveOneBitCount_ ) )
  829.                 {
  830.                     CWPs_.add( new CodeWordProfile( iWordLengths ) );
  831.                 }
  832.  
  833.                 return;
  834.             }
  835.  
  836.             for( int i = 1; i <= Math.min( iMaxWordLength, nTotalChars_ - iReserved - iLevelsToGo ); i++ ) {
  837.                 iWordLengths[iLevel] = i;
  838.                 generateCodeWordProfilesImpl( CWPs_, iWordLengths, nTotalChars_, iSieveZeroBitCount_,
  839.                     iSieveOneBitCount_, iMaxWordLength, iReserved + i, iLevel + 1 );
  840.             }
  841.         }
  842.     }
  843.  
  844.     static final class CodeWordProfile {
  845.         final int[] iWordLengths;
  846.         final Alignment[] A_WordAlignments;
  847.  
  848.         CodeWordProfile( int[] iWordLengths_ ) {
  849.             iWordLengths = new int[3];
  850.             System.arraycopy( iWordLengths_, 0, iWordLengths, 0, 3 );
  851.  
  852.             A_WordAlignments = new Alignment[2];
  853.             A_WordAlignments[0] = (iWordLengths[0] &1) == 0 ? Alignment.ODD : Alignment.EVEN;
  854.             A_WordAlignments[1] = ((iWordLengths[0] + iWordLengths[1]) &1) == 0 ? Alignment.EVEN : Alignment.ODD;
  855.         }
  856.  
  857.         int wordLength( int iWord ) {
  858.             return iWordLengths[iWord];
  859.         }
  860.  
  861.         Alignment wordAlignment( int iWord ) {
  862.             return iWord == 0 ? Alignment.EVEN : A_WordAlignments[iWord-1];
  863.         }
  864.  
  865.         public String toString() {
  866.             return iWordLengths[0] + " E, " + iWordLengths[1] + ' ' + A_WordAlignments[0].name().charAt( 0 ) + ", " +
  867.                 iWordLengths[2] + ' ' + A_WordAlignments[1].name().charAt( 0 );
  868.         }
  869.  
  870.         static boolean isSieveCompliant( int[] iWordLengths_, int iRefSieveZeroBitCount, int iRefSieveOneBitCount ) {
  871.             int iCombinedLength = iWordLengths_[0] + iWordLengths_[1],
  872.                 iSieveZeroBitCount = ((iWordLengths_[0] &1) == 1 ? 0 : 1) +
  873.                     ((iCombinedLength &1) == 1 ? 1 : 0),
  874.                 iSieveOneBitCount = ((iWordLengths_[0] &2) == 2 ? 0 : 1) +
  875.                     (((iCombinedLength+1) &2) == 2 ? 0 : 1);
  876.  
  877.             return iSieveZeroBitCount == iRefSieveZeroBitCount && iSieveOneBitCount == iRefSieveOneBitCount;
  878.         }
  879.     }
  880. }
  881.  
  882.  
  883. // Word alignment: even or odd.
  884. enum Alignment {
  885.     EVEN,
  886.     ODD;
  887.  
  888.     Alignment onWord( Alignment A ) {
  889.         return this == A ? EVEN : ODD;
  890.     }
  891. }
  892.  
  893.  
  894. // While selecting primary candidates: upper bound matching, or exact matching.
  895. enum SelectType {
  896.     UPPER_BOUND,
  897.     EXACT_MATCH
  898. }
  899.  
  900.  
  901. // A discriminant based on total character count and the count of a particular character.
  902. class TwoPointDiscriminant {
  903.     final int nCharCount;
  904.     final int nCharA;
  905.     final int iCharA;
  906.  
  907.     TwoPointDiscriminant( int nCharCount_, int iCharA_, int nCharA_ ) {
  908.         nCharCount = nCharCount_;
  909.         nCharA = nCharA_;
  910.         iCharA = iCharA_;
  911.     }
  912.  
  913.     public boolean equals( Object o ) {
  914.         if( !(o instanceof TwoPointDiscriminant) )
  915.             return false;
  916.  
  917.         TwoPointDiscriminant TpD = (TwoPointDiscriminant)o;
  918.  
  919.         return TpD.nCharCount == nCharCount && TpD.nCharA == nCharA && TpD.iCharA == iCharA;
  920.     }
  921.  
  922.     public int hashCode() {
  923.         return nCharA + 37*(iCharA + 37*nCharCount);
  924.     }
  925.  
  926.     public String toString() {
  927.         return nCharA + " '" + Revenant.ALPHABET[iCharA] + "' in " + nCharCount;
  928.     }
  929. }
  930.  
  931.  
  932. // A discriminant based on total character count, and odd/even character counts for two particular characters.
  933. class FivePointDiscriminant {
  934.     final int nCharCount;
  935.     final int nEvenCharA;
  936.     final int nOddCharA;
  937.     final int nEvenCharB;
  938.     final int nOddCharB;
  939.     final int iCharA;
  940.     final int iCharB;
  941.  
  942.     FivePointDiscriminant( int nCharCount_, int iCharA_, int nEvenCharA_, int nOddCharA_, int iCharB_,
  943.         int nEvenCharB_, int nOddCharB_ )
  944.     {
  945.         nCharCount = nCharCount_;
  946.         nEvenCharA = nEvenCharA_;
  947.         nEvenCharB = nEvenCharB_;
  948.         nOddCharA = nOddCharA_;
  949.         nOddCharB = nOddCharB_;
  950.         iCharA = iCharA_;
  951.         iCharB = iCharB_;
  952.     }
  953.  
  954.     public boolean equals( Object o ) {
  955.         if( !(o instanceof FivePointDiscriminant) )
  956.             return false;
  957.  
  958.         FivePointDiscriminant FpD = (FivePointDiscriminant)o;
  959.  
  960.         return FpD.nCharCount == nCharCount &&
  961.             FpD.nEvenCharA == nEvenCharA &&
  962.             FpD.nOddCharA == nOddCharA &&
  963.             FpD.nEvenCharB == nEvenCharB &&
  964.             FpD.nOddCharB == nOddCharB &&
  965.             FpD.iCharA == iCharA &&
  966.             FpD.iCharB == iCharB;
  967.     }
  968.  
  969.     public int hashCode() {
  970.         return iCharA + 17*(iCharB + 13*(nEvenCharA + 17*(nOddCharA + 13*(nEvenCharB + 17*(nOddCharB +
  971.             13*nCharCount)))));
  972.     }
  973.  
  974.     public String toString() {
  975.         return nEvenCharA + "/" + nOddCharA + " '" + Revenant.ALPHABET[iCharA] + "', and " +
  976.             nEvenCharB + "/" + nOddCharB + " '" + Revenant.ALPHABET[iCharB] + "' in " + nCharCount;
  977.     }
  978. }
  979.  
  980.  
  981. // A discriminant composited from two five-point discriminants and one two-point discriminant.
  982. class MultipointDiscriminant {
  983.     final int[] iData;
  984.  
  985.     MultipointDiscriminant( FivePointDiscriminant FpD1, FivePointDiscriminant FpD2, TwoPointDiscriminant TpD3,
  986.         SelectType STy )
  987.     {
  988.         iData = new int[] {
  989.                 FpD1.nCharCount, FpD1.nEvenCharA, FpD1.nOddCharA, FpD1.nEvenCharB, FpD1.nOddCharB,
  990.                 FpD2.nEvenCharA, FpD2.nOddCharA, FpD2.nEvenCharB, FpD2.nOddCharB, TpD3.nCharA,
  991.                 STy == SelectType.EXACT_MATCH ? 1 : 0
  992.             };
  993.     }
  994.  
  995.     public boolean equals( Object o ) {
  996.         return o instanceof MultipointDiscriminant && Arrays.equals( iData, ((MultipointDiscriminant)o).iData );
  997.     }
  998.  
  999.     public int hashCode() {
  1000.         return Arrays.hashCode( iData );
  1001.     }
  1002.  
  1003.     public String toString() {
  1004.         return iData[1] + "/" + iData[2] + ", " + iData[3] + "/" + iData[4] + ", " +
  1005.             iData[5] + "/" + iData[6] + ", " + iData[7] + "/" + iData[8] + ", " + iData[9] + " in " + iData[0] + ": " +
  1006.             (iData[10] == 1 ? "Exact Match" : "Upper Bound");
  1007.     }
  1008. }
  1009.  
  1010.  
  1011. // Class encapsulates an outcome by the oracle: number of matches, number of "coincidences" (characters present in
  1012. // both strings but not in matching locations).
  1013. class RevOutcome {
  1014.     final int nMatch;
  1015.     final int nCoincide;
  1016.     final boolean isExactMatch;
  1017.  
  1018.     static final RevOutcome VALID = new RevOutcome();
  1019.  
  1020.     private RevOutcome() {
  1021.         nMatch = -1;
  1022.         nCoincide = -1;
  1023.         isExactMatch = true;
  1024.     }
  1025.  
  1026.     RevOutcome( int nMatch_, int nCoincide_ ) {
  1027.         nMatch = nMatch_;
  1028.         nCoincide = nCoincide_;
  1029.         isExactMatch = false;
  1030.     }
  1031.  
  1032.     public boolean equals( Object o ) {
  1033.         if( !(o instanceof RevOutcome) )
  1034.             return false;
  1035.  
  1036.         RevOutcome Oc = (RevOutcome)o;
  1037.         return Oc.nMatch == nMatch && Oc.nCoincide == nCoincide;
  1038.     }
  1039.  
  1040.     public int hashCode() {
  1041.         return nMatch*37 + nCoincide;
  1042.     }
  1043.  
  1044.     public String toString() {
  1045.         return isExactMatch ? "Exact Match" : (nMatch + " match, " + nCoincide + " coincidence");
  1046.     }
  1047. }
  1048.  
  1049.  
  1050. // Oracle interface. An oracle is the machine that spits out the relevant match data when queried with a specific
  1051. // string.
  1052. interface RevOracle {
  1053.     RevOutcome query( String sCandidate );
  1054. }
  1055.  
  1056.  
  1057. // Class for computing various relevant word metrics.
  1058. class RevDictionaryDB {
  1059.     final Map<String,DBEntry> M_Data;
  1060.     final Map<String,Integer> M_IDsByWord;
  1061.     final String[] sWordsByID;
  1062.     final int nWords;
  1063.     int iMaxWordLength;
  1064.     int iFreeID = 0;
  1065.  
  1066.     RevDictionaryDB( int nWords_ ) {
  1067.         nWords = nWords_;
  1068.         M_Data = new HashMap<>( nWords );
  1069.         M_IDsByWord = new HashMap<>( nWords );
  1070.         sWordsByID = new String[nWords];
  1071.         iMaxWordLength = 0;
  1072.     }
  1073.  
  1074.     void registerWord( String sWord ) {
  1075.         int iLength = sWord.length();
  1076.         iMaxWordLength = Math.max( iMaxWordLength, iLength );
  1077.         sWordsByID[iFreeID] = sWord;
  1078.         M_IDsByWord.put( sWord, iFreeID );
  1079.         iFreeID++;
  1080.  
  1081.         DBEntry DBE = computeDBEntry( sWord );
  1082.         M_Data.put( sWord, DBE );
  1083.     }
  1084.  
  1085.     Map<Integer,Integer> charCountsForWord( String sWord, Alignment A ) {
  1086.         DBEntry DBE = M_Data.get( sWord );
  1087.  
  1088.         return A == null ? DBE.M_CharCounts : (A == Alignment.EVEN ? DBE.M_EvenCharCounts : DBE.M_OddCharCounts);
  1089.     }
  1090.  
  1091.     Long wordTripletToLong( String sWord0, String sWord1, String sWord2 ) {
  1092.         return (long)M_IDsByWord.get( sWord0 ) + ((long)nWords * ((long)M_IDsByWord.get( sWord1 ) + (long)nWords *
  1093.             (long)M_IDsByWord.get( sWord2 )));
  1094.     }
  1095.  
  1096.     String longToWordTriplet( Long L ) {
  1097.         return sWordsByID[(int)(L %nWords)] + ' ' + sWordsByID[(int)((L/nWords) %nWords)] + ' ' +
  1098.             sWordsByID[(int)(L/nWords/nWords)];
  1099.     }
  1100.  
  1101.     static class DBEntry {
  1102.         final Map<Integer,Integer> M_CharCounts;
  1103.         final Map<Integer,Integer> M_EvenCharCounts;
  1104.         final Map<Integer,Integer> M_OddCharCounts;
  1105.  
  1106.         DBEntry( Map<Integer,Integer> M_CharCounts_, Map<Integer,Integer> M_EvenCharCounts_,
  1107.             Map<Integer,Integer> M_OddCharCounts_ )
  1108.         {
  1109.             M_CharCounts = M_CharCounts_;
  1110.             M_EvenCharCounts = M_EvenCharCounts_;
  1111.             M_OddCharCounts = M_OddCharCounts_;
  1112.         }
  1113.     }
  1114.  
  1115.     static DBEntry computeDBEntry( String sWord ) {
  1116.         Map<Integer,Integer> M_Counts = new HashMap<>( sWord.length() ),
  1117.             M_EvenCounts = new HashMap<>( sWord.length()/2 + 1 ),
  1118.             M_OddCounts = new HashMap<>( sWord.length()/2 );
  1119.  
  1120.         int i = 0;
  1121.         for( char ch : sWord.toCharArray() ) {
  1122.             int iCharIndex = Revenant.ALPHABET_STRING.indexOf( ch );
  1123.  
  1124.             M_Counts.put( iCharIndex, M_Counts.getOrDefault( iCharIndex, 0 )+1 );
  1125.             if( (i &1) == 0 )
  1126.                 M_EvenCounts.put( iCharIndex, M_EvenCounts.getOrDefault( iCharIndex, 0 )+1 );
  1127.             else M_OddCounts.put( iCharIndex, M_OddCounts.getOrDefault( iCharIndex, 0 )+1 );
  1128.  
  1129.             i++;
  1130.         }
  1131.         return new DBEntry( M_Counts, M_EvenCounts, M_OddCounts );
  1132.     }
  1133. }
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!