《程序员》2007第十期算法擂台之JAVA解法

题目：

引用

人和计算机做猜数游戏.人默想一个四位数,由计算机来猜.计算机将所猜的数据显示到屏幕上,并问两个问题:一,有几个数字猜对了;二,猜对的数字中有几个位置也对了.人通过键盘来回答这两个问题。计算机一次又一次地猜,直到猜对位置。
         为了简化输入输出,计算机每次输出一个四位数,然后人输入两个用空格分开的数，分别表示有几个数字猜对，有几个数字位置也对。下面有某次猜数过程:人默认的数是3422，奇数行是计算机猜的数，偶数行是人输入的信息。在这个例子中，计算机第五次猜中了数，在人输入4 4后程序结束退出.
         请你写一个这样的猜数游戏，看看你所想的数能在几次后被程序猜中。如果在猜数过程中，计算机发现人故意欺骗，输入了不正确的信息,那么程序将输出0然后直接退出.

例子:
6897
0 0
5555
0 0
4444
1 1
4333
2 0
3422
4 4

算法描叙：
每次从剩下的可能值中选择能使下一次筛选后可能值最少（平均意义下）的数去猜。

算法效果：
不甚理想，平均需要5.8步才能猜对。下面是统计数据：
Step[k]  n  x 表示使用k步猜对的数字有n个,x表示在总游戏数中占得比例:
   Step[ 1]       1    0.0001
   Step[ 2]      13    0.0013
   Step[ 3]     110    0.0110
   Step[ 4]     713    0.0713
   Step[ 5]    2792    0.2792
   Step[ 6]    4440    0.4440
   Step[ 7]    1553    0.1553
   Step[ 8]     277    0.0277
   Step[ 9]      82    0.0082
   Step[10]      19    0.0019
   Total:     57824 steps      10000 games
   Use time:  420266 ms

代码：

import java.util.*;

/**
　 猜数字游戏
   @author Eastsun
   @version 2.0 2007/10/15
*/
public class NumberGuess{
    public static void main(String[] args){
        Scanner s =new Scanner(System.in);
        AI solver =new AI();
        try{
            System.out.println(solver.firstGuess());
            int b =s.nextInt();
            int a =s.nextInt();
            while(!(a==Item.SIZE&&b==Item.SIZE)){
                System.out.println(solver.nextGuess(a,b));
                b =s.nextInt();
                a =s.nextInt();
            }
        }catch(IllegalArgumentException ex){
            System.out.println("0");
        }
    }
}

class AI{
    private static final Item[] ITEMS_BUFFER ={
        new Item(56),
        new Item(156),
        new Item(256),
        new Item(145),
        new Item(135),
        new Item(235),
        new Item(123),
        new Item(1322),
        new Item(1124),
        new Item(234),
        new Item(2341),
        new Item(1342),
        new Item(1243),
        null,
        new Item(1234)
    };
    //可能的答案
    private List＜Item＞ candidates;
    
    //最近一次的猜测
    private Item lastGuess;
    
    //已经猜过的次数
    private int step;
    
    /**
       第一次猜测
    */
    public Item firstGuess(){
        step =1;
        //初始化candidates为所有可能的答案
        candidates =new LinkedList＜Item＞(Item.ALL_POSSIBLE_ITEMS);
        //选择"1234"作为第一次的猜测.事实上任意一个四个数字各不相同的都可以,在统计意义下效果一样
        lastGuess = new Item(1234); //
        return lastGuess;
    }
    
    /**
       根据上次的猜测结果得到下一次猜测
    */
    public Item nextGuess(int a,int b){
        step ++;
        //根据上次结果对候选集进行过滤
        filter(candidates,lastGuess,a,b);
        //如果候选集为空,说明输入的数据有误
        if(candidates.isEmpty()) throw new IllegalArgumentException();
        
        if(step ==2){
            lastGuess = ITEMS_BUFFER[b*(b+1)/2+a];
            return lastGuess;
        }
        //从剩下的候选集中取出权重最小那个作为下一次的猜测
        int min =Integer.MAX_VALUE;
        for(Item guess : candidates){
            int weight =weight(candidates, guess);
            if(weight ＜min){
                min =weight;
                lastGuess =guess;
            }
        }
        return lastGuess;
    }

    /**
       将list中所有用guess猜答案不是(b,a)的过滤掉
    */
    public static void filter(List＜Item＞ list,Item guess,int a,int b){
        for(Iterator＜Item＞ itr =list.iterator();itr.hasNext();){
            if(!Item.isMatch(itr.next(),guess,a,b)) itr.remove();
        }
    }
    
    
    /**
       用guess去猜结果集list时的权重,这个值越小越好
    */
    public static int weight(List＜Item＞ list,Item guess){
        int[] count =new int[(Item.SIZE+1)*(Item.SIZE+2)/2];
        for(Item word :list){
            int a =Item.getA(word,guess);
            int b =Item.getB(word,guess);
            int index =(b+1)*b/2 +a;  //hash for (b,a)
            count[index] ++;
        }
        int value =0;
        for(int c : count)
            value += c*c;
        return value;
    }
}

class Item {
    /**
       数字位数
    */
    public static final int SIZE =4;
    
    //一个包含了所有可能解的不可修改的list
    public static final List＜Item＞ ALL_POSSIBLE_ITEMS;
    static{
        List＜Item＞ list =new ArrayList＜Item＞(10000);
        for(int num =0;num ＜10000;num ++)     //magic number: 10000 is result of 10^Item.SIZE
            list.add(new Item(num));
        ALL_POSSIBLE_ITEMS =Collections.unmodifiableList(list);
    }
    //数字的各位,从高位到低位排列
    int[] bits;
    public Item(int num){
        bits =new int[SIZE];
        for(int index=SIZE-1;num＞0;num/=10)
            bits[index--] = num%10;
    }
    
    @Override
    public String toString(){
        StringBuilder sb =new StringBuilder(SIZE);
        for(int index =0;index＜ SIZE;index ++)
            sb.append(bits[index]);
        return sb.toString();
    }
    
    /**
       用guess去猜word,结果是否返回(b,a)
    */
    public static boolean isMatch(Item word,Item guess,int a,int b){
        return (getA(word,guess)==a&&getB(word,guess)==b);
    }
    /**
       word 为谜底,guess去猜.
       @return guess与word中位置相同数字也相同的个数
    */
    public static int getA(Item word,Item guess){
        int count =0;
        for(int index =0;index＜SIZE; index++)
            if(word.bits[index]==guess.bits[index]) count ++;
        return count;
    }
    
    /**
       word 为谜底,guess去猜.
       @return 猜对的数字个数
    */
    public static int getB(Item word,Item guess){
        int count =0;
        boolean[] flags =new boolean[SIZE];
        for(int i =0;i ＜SIZE;i ++)
            for(int j =0;j ＜SIZE;j ++)
                if((!flags[j])&&word.bits[i]==guess.bits[j]){
                    count ++;
                    flags[j] =true;
                    break;
                }
        return count;
    }
}

评论

3 楼 Eastsun 2007-10-25  

<程序员>的参考代码出来了:
http://blog.csdn.net/programmer_editor/archive/2007/10/25/1843300.aspx
和我的算法是一样的.
比较郁闷的是参考代码里面考虑的"四位数"是从1000~9999,而我的代码考虑了0000~9999

2 楼 Eastsun 2007-10-16  

jasongreen 写道

这我以前做过，一般是6步，没做过统计。
对下次筛选可能性最小没有做判断，仅仅是任意挑选一个可能的排列。

这个题标准点，是不可以有重复数字的

这个是允许重复数字的."任意挑选一个"我也试过,平均是6.3步左右.

好像通常的猜数字游戏是不允许重复数字的,在那种情况下我的算法可以做到平均5.16步猜出来(最坏情况需要9步).

1 楼 jasongreen 2007-10-16  

这我以前做过，一般是6步，没做过统计。
对下次筛选可能性最小没有做判断，仅仅是任意挑选一个可能的排列。

这个题标准点，是不可以有重复数字的