Source Code Listing 4

• By Vince Huston
• February 24, 2001

import java.io.*;
import java.util.Vector;

public class MastermindSolve {
   public static void main( String[] args ) throws IOException {
      BufferedReader rdr = new BufferedReader( new InputStreamReader( System.in ));
      String str = null;
      System.out.print( "Enter puzzle: " );
      str = rdr.readLine();
      Board  b = new Board( str.toCharArray() );
      Solver s = new Solver( b );
      s.solve();
}  }

class Board {
   public static final int NUM_CHOICES = 6;
   public static final int NUM_SLOTS   = 4;

   private char[] answerAttr      = new char[NUM_SLOTS];
   private int[]  answerCharsAttr = new int[NUM_CHOICES];
   private int[]  inputChars      = new int[NUM_CHOICES];

   public Board() {
      for (int i=0; i < num_slots;="" i++)="" answerattr[i]="(char)" ('a'="" +="" (int)="" (math.random()*1000)="" %="" num_choices);="" for="" (int="" i="0;" i="">< num_slots;="" i++)="" answercharsattr[="" answerattr[i]="" -="" 'a'="" ]++;="" }="" public="" board(="" char[]="" puzzle="" )="" {="" answerattr="puzzle;" for="" (int="" i="0;" i="">< num_slots;="" i++)="" answercharsattr[="" answerattr[i]="" -="" 'a'="" ]++;="" }="" public="" void="" evaluate(="" char[]="" guess,="" int[]="" response="" )="" {="" evaluate(="" answerattr,="" answercharsattr,="" guess,="" response="" );="" }="" public="" void="" evaluate(="" char[]="" answer,="" int[]="" answerchars,="" char[]="" guess,="" int[]="" response="" )="" {="" for="" (int="" i="0;" i="">< num_choices;="" i++)="" inputchars[i]="0;" response[0]="response[1]" =="" 0;="" for="" (int="" i="0;" i="">< num_slots;="" i++)="" inputchars[="" guess[i]="" -="" 'a'="" ]++;="" for="" (int="" i="0;" i="">< num_slots;="" i++)="" if="" (guess[i]="=" answer[i])="" response[0]++;="" for="" (int="" i="0;" i="">< num_choices;="" i++)="" response[1]="" +="(inputChars[i]">< answerchars[i]="" inputchars[i]="" :="" answerchars[i]);="" response[1]="response[1]" -="" response[0];="" }="" }="" class="" outparameterstruct="" {="" char="" next;="" boolean="" carry;="" }="" class="" slot="" {="" private="" stringbuffer="" choices="new" stringbuffer();="" private="" int="" next;="" public="" slot()="" {="" for="" (int="" i="0;" i="">< board.num_choices;="" i++)="" choices.append(="" (char)('a'+i)="" );="" }="" public="" char="" reset()="" {="" next="0;" return="" choices.charat(="" next="" );="" }="" public="" void="" getnext(="" outparameterstruct="" s="" )="" {="" s.carry="false;" if="" (++next="=" choices.length())="" {="" next="0;" s.carry="true;" }="" s.next="choices.charAt(next);" }="" public="" void="" remove(="" char="" ch="" )="" {="" int="" i;="" for="" (i="0;" i="">< choices.length();="" i++)="" if="" (choices.charat(i)="=" ch)="" break;="" if="" (i="">< choices.length())="" choices.deletecharat(="" i="" );="" }="" public="" void="" report()="" {="" for="" (int="" i="0;" i="">< choices.length();="" i++)="" system.out.print(="" choices.charat(i)="" );="" system.out.print(="" "="" "="" );="" }="" public="" char="" get()="" {="" return="" choices.charat(next);="" }="" }="" class="" turnstruct="" {="" public="" char[]="" guess;="" public="" int="" black,="" white;="" public="" turnstruct(="" char[]="" g,="" int[]="" ans="" )="" {="" guess="new" char[board.num_slots];="" for="" (int="" i="0;" i="">< board.num_slots;="" i++)="" guess[i]="g[i];" black="ans[0];" white="ans[1];" }="" }="" class="" solver="" {="" private="" board="" b;="" private="" slot[]="" slots="new" slot[board.num_slots];="" private="" vector="" history="new" vector();="" private="" state="" current;="" private="" int[]="" answerchars="new" int[board.num_choices];="" private="" int[]="" response="new" int[2];="" private="" char[]="" next="new" char[board.num_slots];="" private="" outparameterstruct="" s="new" outparameterstruct();="" private="" int="" notconsistent="0;" public="" solver(="" board="" bored="" )="" {="" b="bored;" for="" (int="" i="0;" i="">< board.num_slots;="" i++)="" slots[i]="new" slot();="" current="GuessOne.inst();" }="" public="" void="" setcurrent(="" state="" s="" )="" {="" current="s;" }="" public="" void="" solve()="" {="" while="" (="" !="" current.solve(="" this="" ));="" }="" public="" boolean="" evaluate(="" char[]="" guess,="" int[]="" response="" )="" {="" b.evaluate(="" guess,="" response="" );="" for="" (int="" i="0;" i="">< guess.length;="" i++)="" system.out.print(="" guess[i]="" );="" system.out.println(="" "="" "="" +="" response[0]="" +="" "="" "="" +="" response[1]="" );="" history.add(="" new="" turnstruct(="" guess,="" response="" )="" );="" return="" response[0]="=" board.num_slots;="" }="" public="" void="" eliminate(="" char="" gone="" )="" {="" system.out.println(="" "="" eliminating="" "="" +="" gone="" );="" for="" (int="" j="0;" j="">< board.num_slots;="" j++)="" slots[j].remove(="" gone="" );="" }="" public="" boolean="" applyrules(="" char[]="" guess,="" int[]="" response="" )="" {="" if="" (="" !="" ruleone(="" guess,="" response="" ))="" ruletwo(="" guess,="" response="" );="" return="" rulethree(="" guess,="" response="" );="" }="" public="" boolean="" ruleone(="" char[]="" guess,="" int[]="" response="" )="" {="" if="" (response[0]="" +="" response[1]="=" 0)="" {="" for="" (int="" i="0;" i="">< guess.length;="" i++)="" eliminate(="" guess[i]="" );="" return="" true;="" }="" else="" return="" false;="" }="" public="" boolean="" ruletwo(="" char[]="" guess,="" int[]="" response="" )="" {="" if="" (response[0]="=" 0)="" {="" for="" (int="" i="0;" i="">< guess.length;="" i++)="" {="" system.out.println(="" "="" removing="" "="" +="" guess[i]="" +="" "="" from="" position="" "="" +="" (i+1)="" );="" slots[i].remove(="" guess[i]="" );="" }="" return="" true;="" }="" else="" return="" false;="" }="" public="" boolean="" rulethree(="" char[]="" guess,="" int[]="" response="" )="" {="" if="" (response[0]="" +="" response[1]="=" board.num_slots)="" {="" guesspermute.inst().setstate(="" guess="" );="" current="GuessPermute.inst();" return="" true;="" }="" else="" return="" false;="" }="" public="" boolean="" isconsistent(="" char[]="" a="" )="" {="" for="" (int="" j="0;" j="">< board.num_choices;="" j++)="" answerchars[j]="0;" for="" (int="" j="0;" j="">< board.num_slots;="" j++)="" answerchars[="" a[j]="" -="" 'a'="" ]++;="" for="" (int="" i="0;" i="">< history.size();="" i++)="" {="" turnstruct="" t="(TurnStruct)" history.elementat(i);="" b.evaluate(="" a,="" answerchars,="" t.guess,="" response="" );="" if="" (response[0]="" !="t.black" ||="" response[1]="" !="t.white)" {="" notconsistent++;="" return="" false;="" }="" }="" return="" true;="" }="" public="" void="" reportnotconsistent()="" {="" system.out.println(="" "="" possible="" guesses="" eliminated="" were="" "="" +="" notconsistent="" );="" notconsistent="0;" }="" public="" void="" reportslots()="" {="" system.out.print(="" "reportslots="" -="" "="" );="" for="" (int="" i="0;" i="">< board.num_slots;="" i++)="" system.out.print(slots[i].get());="" system.out.println();="" }="" public="" char[]="" first_count_string()="" {="" for="" (int="" i="0;" i="">< board.num_slots;="" i++)="" next[i]="slots[i].reset();" return="" next;="" }="" public="" char[]="" next_count_string()="" {="" int="" x="0;" slots[x].getnext(="" s="" );="" next[x]="s.next;" while="" (s.carry)="" {="" slots[++x].getnext(="" s="" );="" next[x]="s.next;" if="" (x="=" board.num_slots-1="" &&="" s.carry)="" return="" null;="" }="" return="" next;="" }="" }="" interface="" state="" {="" boolean="" solve(="" solver="" wrapper="" );="" }="" class="" guessone="" implements="" state="" {="" private="" static="" guessone="" me="new" guessone();="" public="" static="" guessone="" inst()="" {="" return="" me;="" }="" public="" boolean="" solve(="" solver="" wrapper="" )="" {="" char="" first="(char)('a'" +="" ((int)(math.random()="" *="" 29))="" %="" board.num_choices);="" char="" first='b' ;="" char="" second="(char)('a'" +="" (first+1-'a')="" %="" board.num_choices);="" char[]="" guess="new" char[board.num_slots];="" int="" i;="" for="" (i="0;" i="">< board.num_slots="" 2;="" i++)="" guess[i]="first;" for="" (="" ;="" i="">< board.num_slots;="" i++)="" guess[i]="second;" int[]="" answer="new" int[2];="" if="" (wrapper.evaluate(="" guess,="" answer="" ))="" return="" true;="" if="" rule="" 3="" sets="" the="" current="" state="" to="" guesspermute,="" then="" don't="" set="" the="" current="" state="" to="" guesstwo,="" but="" do="" return="" false="" to="" indicate="" that="" the="" puzzle="" has="" not="" yet="" been="" solved="" if="" (wrapper.applyrules(="" guess,="" answer="" ))="" return="" false;="" pass="" on="" to="" the="" next="" state:="" the="" next="" random="" letter,="" and="" the="" total="" of="" black="" plus="" white="" guesstwo.inst().setstate(="" (char)('a'="" +="" (second+1-'a')="" %="" board.num_choices),="" answer[0]="" +="" answer[1]="" );="" wrapper.setcurrent(="" guesstwo.inst()="" );="" return="" false;="" }="" }="" class="" guesstwo="" implements="" state="" {="" private="" char="" first;="" private="" int="" firsttotal;="" private="" static="" guesstwo="" me="new" guesstwo();="" public="" static="" guesstwo="" inst()="" {="" return="" me;="" }="" public="" void="" setstate(="" char="" n,="" int="" total="" )="" {="" first="n;" firsttotal="total;" }="" public="" boolean="" solve(="" solver="" wrapper="" )="" {="" char="" second="(char)('a'" +="" (first+1-'a')="" %="" board.num_choices);="" char[]="" guess="new" char[board.num_slots];="" int="" i;="" for="" (i="0;" i="">< board.num_slots="" 2;="" i++)="" guess[i]="first;" for="" (="" ;="" i="">< board.num_slots;="" i++)="" guess[i]="second;" int[]="" answer="new" int[2];="" if="" (wrapper.evaluate(="" guess,="" answer="" ))="" return="" true;="" if="" (wrapper.applyrules(="" guess,="" answer="" ))="" return="" false;="" if="" (firsttotal="" +="" answer[0]="" +="" answer[1]="=" board.num_slots)="" {="" for="" (int="" j="0;" j="">< board.num_choices="" -="" 4;="" j++)="" wrapper.eliminate(="" (char)('a'="" +="" (second+1+j-'a')="" %="" board.num_choices)="" );="" }="" wrapper.setcurrent(="" guesscompute.inst()="" );="" return="" false;="" }="" }="" class="" guesscompute="" implements="" state="" {="" private="" static="" guesscompute="" me="new" guesscompute();="" public="" static="" guesscompute="" inst()="" {="" return="" me;="" }="" public="" boolean="" solve(="" solver="" wrapper="" )="" {="" char[]="" a;="" int[]="" answer="new" int[2];="" a="wrapper.first_count_string();" while="" (true)="" {="" if="" (a="=" null)="" return="" true;="" if="" (wrapper.isconsistent(="" a="" ))="" {="" wrapper.reportnotconsistent();="" if="" (wrapper.evaluate(="" a,="" answer="" ))="" return="" true;="" if="" (wrapper.ruleone(="" a,="" answer="" )="" ||="" wrapper.ruletwo(="" a,="" answer="" ))="" {="" a="wrapper.first_count_string();" continue;="" }="" if="" (wrapper.rulethree(="" a,="" answer="" ))="" return="" false;="" }="" a="wrapper.next_count_string();" }="" }="" }="" class="" guesspermute="" implements="" state="" {="" private="" int[]="" answer="new" int[2];="" private="" char[]="" a;="" private="" static="" guesspermute="" me="new" guesspermute();="" public="" static="" guesspermute="" inst()="" {="" return="" me;="" }="" public="" void="" setstate(="" char[]="" ans="" )="" {="" a="ans;" }="" public="" boolean="" solve(="" solver="" wrapper="" )="" {="" sort();="" while="" (true)="" {="" if="" (wrapper.isconsistent(="" a="" ))="" {="" wrapper.reportnotconsistent();="" if="" (wrapper.evaluate(="" a,="" answer="" ))="" return="" true;="" }="" next_permutation_string();="" }="" }="" private="" boolean="" next_permutation_string()="" {="" char="" t;="" if="" (a.length="">< 2)="" return="" false;="" for="" (int="" i="a.length-1," ii,="" j;="" ;="" )="" {="" ii="i--;" if="" (a[i]="">< a[ii])="" {="" j="a.length;" while="" (="" !="" (a[i]="">< a[--j]))="" {="" }="" t="a[i];" a[i]="a[j];" a[j]="t;" reverse(="" ii,="" a.length-1="" );="" return="" true;="" }="" if="" (i="=" 0)="" {="" reverse(="" 0,="" a.length-1="" );="" return="" false;="" }="" }="" }="" private="" void="" sort()="" {="" shell="" sort="" int="" n="a.length;" char="" t;="" for="" (int="" g="n/2;" g=""> 0; g /= 2)
         for (int i = g; i < n;="" i++)="" for="" (int="" j="i-g;" j="">= 0; j -= g)
               if (a[j] > a[j+g]) {
                  t = a[j];  a[j] = a[j+g];  a[j+g] = t; }
   }
   private void reverse( int b, int e ) {
      int m = (b + e + 1) / 2;
      char t;
      for (int i=b, j=e; i < m;="" i++,="" j--)="" {="" t="a[i];" a[i]="a[j];" a[j]="t;" }="" }="" }="">