GuessNumber

GuessNumber.java

package oyyq.algo;

import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class GuessNumber {

    private static char[]    elements = new char[] {'1', '2', '3', '4', '5', '6', '7', '8', '9',
            '0'                       };
    private static boolean[] used     = new boolean[elements.length];
    private static char[]    result   = null;
    private static Scanner   sc       = new Scanner(System.in);

    private static void perm(int i, int r, Collection<char[]> dest) {
        for (int j = 0; j < elements.length; j++) {
            if (!used[j]) {
                used[j] = true;
                result[i] = elements[j];
                if (i == r - 1) {
                    dest.add(result.clone());
                } else {
                    perm(i + 1, r, dest);
                }
                used[j] = false;
            }
        }
    }

    private static void perm(int r, Collection<char[]> dest) {
        result = new char[r];
        Arrays.fill(used, false);
        perm(0, r, dest);
    }

    private static void solve(int n) {
        List<char[]> perms = new LinkedList<char[]>();
        perm(n, perms);

        while (perms.size() > 1) {
            char[] answer = perms.get(0);
            System.out.println("I guess it's ");
            for (char c : answer) {
                System.out.print(c + " ");
            }
            System.out.println(", how about it? (I think there are " + perms.size()
                    + " possibilities!)");
            int a, b;
            a = sc.nextInt();
            b = sc.nextInt();
            filterAnswers(answer, perms, a, b);
        }
        if (perms.size() == 0) {
            System.out.println("No answer!");
        } else {
            char[] answer = perms.get(0);
            System.out.println("Yes I got it, it's ");
            for (char c : answer) {
                System.out.print(c + " ");
            }
            System.out.println();
        }
    }

    private static void filterAnswers(char[] answer, Collection<char[]> perms, int a, int b) {
        Iterator<char[]> it = perms.iterator();
        while (it.hasNext()) {
            int na = 0, nb = 0;
            char[] candidate = it.next();
            for (int j = 0; j < answer.length; j++) {
                if (candidate[j] == answer[j]) {
                    na++;
                }
                for (int k = 0; k < answer.length; k++) {
                    if (j == k) {
                        continue;
                    }
                    if (candidate[j] == answer[k]) {
                        nb++;
                    }
                }
            }
            if (na != a || nb != b) {
                it.remove();
                continue;
            }
        }
    }

    public static void main(String[] args) {
        do {
            System.out.println("So, tell me how many digits are there?");
            int n = sc.nextInt();
            if (n <= 0) {
                System.out.println("Seems you don't want to play anymore..So bye!");
                break;
            }
            solve(n);
            System.out.println("\n\nOh, Its a new game now?");
        } while (true);
        sc.close();
    }
}