New Topic/Question
Reply
Spoiler
This is a Combinatorics problem. We know that there are 103 possible choices. If the digits are distinct, there are 3! permutations. If there are only two distinct digits, say a 3 and two 4's as an example, there are 3!/2! permutations. Given that we only know there are two distinct digits, there are 3!/2! * 2 permutations. The 3!/2! case handles a 3 and two 4's, and then we multiply by 2 to account for two 3's and a 4.
We know that permutations grow at a rate of O(n!), so knocking out numbers is a good thing. My solution determined which digits we needed, so it knocked it down to at most 3 digits. I did this by aiming to ignore Picos, as they ate up more guesses.
Thus for three distinct digits, we have 3! permutations, so at most 16 guesses.
For two distinct digits, we have 2 * 3!/2! permutations, so also at most 16 guesses.
For one distinct digit, at most 10 guesses.
This is a Combinatorics problem. We know that there are 103 possible choices. If the digits are distinct, there are 3! permutations. If there are only two distinct digits, say a 3 and two 4's as an example, there are 3!/2! permutations. Given that we only know there are two distinct digits, there are 3!/2! * 2 permutations. The 3!/2! case handles a 3 and two 4's, and then we multiply by 2 to account for two 3's and a 4.
We know that permutations grow at a rate of O(n!), so knocking out numbers is a good thing. My solution determined which digits we needed, so it knocked it down to at most 3 digits. I did this by aiming to ignore Picos, as they ate up more guesses.
Thus for three distinct digits, we have 3! permutations, so at most 16 guesses.
For two distinct digits, we have 2 * 3!/2! permutations, so also at most 16 guesses.
For one distinct digit, at most 10 guesses.
package test;
import java.util.Scanner;
import java.util.*;
class BagelChallenge{
private String bagelNumber;
public BagelChallenge(){
Random rand = new Random();
bagelNumber = rand.nextInt(1000) + "";
if(bagelNumber.length() < 3){
int difference = 3 - bagelNumber.length();
for(int i = 0; i < difference; i++){
bagelNumber = bagelNumber + "0";
}
}
System.out.println(bagelNumber);
}
public State getState(String guess){
if(guess.length() != 3){
throw new IllegalArgumentException("Guess length must equal 3. Guess length: " + guess.length());
}
if(guess.equals(bagelNumber)){
return State.BAGEL;
}
for(int i = 0; i < guess.length(); i++){
if(guess.charAt(i) == bagelNumber.charAt(i)){
return State.FERMI;
}
}
State temp = State.LOSS;
for(int i = 0; i < guess.length(); i++){
for(int j = 0; j < bagelNumber.length(); j++){
if(guess.charAt(i) == bagelNumber.charAt(j)){
temp = State.PICO;
}
}
}
return temp;
}
}
enum State {
LOSS, PICO, FERMI, BAGEL
}
class BagelAI{
private BagelChallenge challenge;
private ArrayList<Character> acceptableDigits;
public BagelAI(){
challenge = new BagelChallenge();
acceptableDigits = new ArrayList<Character>();
}
public String solve(){
for(char i = '0'; i <= '9' && acceptableDigits.size() < 3; i++ ){
String s = i + "" + i + "" + i;
State state = challenge.getState(s);
if(state == State.BAGEL){
return s;
}
else if(state == State.FERMI){
acceptableDigits.add(i);
}
}
System.out.println("Acceptable digits: " + acceptableDigits);
if(acceptableDigits.size() == 2){
acceptableDigits.add(acceptableDigits.get(1));
String attempt = getListString();
if(challenge.getState(attempt) == State.BAGEL){
return attempt;
}
for(int i = 0; i < 2; i++){
Collections.swap(acceptableDigits, i, i+1);
attempt = getListString();
if(challenge.getState(attempt) == State.BAGEL){
return attempt;
}
}
acceptableDigits.remove(0);
acceptableDigits.add(acceptableDigits.get(1));
attempt = getListString();
if(challenge.getState(attempt) == State.BAGEL){
return attempt;
}
for(int i = 0; i < 2; i++){
Collections.swap(acceptableDigits, i, i+1);
attempt = getListString();
if(challenge.getState(attempt) == State.BAGEL){
return attempt;
}
}
}
else{
return permuteList(0, 3);
}
return null;
}
private String permuteList(int start, int end){
if(start + 1 == end){
String attempt = getListString();
System.out.println("If statement attempt " + attempt);
if(challenge.getState(attempt) == State.BAGEL){
return attempt;
}
}
int range = end - start;
for(int i = 0; i < range; i++){
Collections.swap(acceptableDigits, start, start+i);
String attempt = permuteList(start+1, end);
if(attempt != null){
return attempt;
}
Collections.swap(acceptableDigits, start, start+i);
}
return null;
}
private String getListString(){
String s = "";
for(Character c: acceptableDigits){
s += c;
}
return s;
}
}
class Main{
public static void main(String[] args){
BagelAI ai = new BagelAI();
System.out.println(ai.solve());
}
}
MultiQuote
/> 
| 