TakeAppleGame

gistfile1.txt

package interview;

import org.apache.commons.lang3.RandomUtils;

import java.util.ArrayList;
import java.util.List;

import static java.util.stream.Collectors.toList;

/**
 * 面试题；
 * A、B两个人轮流拿苹果 每次只能拿 1 / 2 / 3个 谁拿了最后一个获胜 问该怎么拿？
 * Created by zhuguowei on 5/18/17.
 */
public class TakeApple {
    private final int total = 25;

    List<String> takeList = new ArrayList();
    List<String> firstWinList ;
    List<String> secondWinList ;

    public List<String> getFirstWinList(){
        if(firstWinList == null){
            firstWinList = takeList.stream().parallel().filter(s -> s.split(" ").length % 2 == 1).collect(toList());
        }
        return firstWinList;
    }
    public List<String> getSecondWinList(){
        if(secondWinList == null){
            secondWinList = takeList.stream().parallel().filter(s -> s.split(" ").length % 2 == 0).collect(toList());
        }
        return secondWinList;
    }

    public void take(String prefix, int count){
        if(count > total){
            return;
        }
        if(count == total ){
            if(prefix.endsWith("1")) { // 有人拿了最后一个
                takeList.add(prefix.trim());
            }
            return;
        }
        // take one apple
        StringBuilder sb  = new StringBuilder();
        sb.append(prefix).append(" ").append("1");
        take(sb.toString(),count+1);

        // take two apple
        sb.setLength(0);
        sb.append(prefix).append(" ").append("2");
        take(sb.toString(),count+2);

        // take three apple
        sb.setLength(0);
        sb.append(prefix).append(" ").append("3");
        take(sb.toString(),count+3);
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        TakeApple app = new TakeApple();
        app.take("",0);
        long end = System.currentTimeMillis();
        System.out.println(app.takeList.size());
        System.out.printf("took time: %d%n",(end-start));

        // A 1 2 3 里面随机选 B 该怎么选 能保证取胜
        StringBuilder sb = new StringBuilder();
        for (int count = 0; count < 25; ) {
            // A 选
            int countA = RandomUtils.nextInt(1, 4);
            sb.append(countA).append(" ");
            // B 选 通过模式匹配 得到B的选择
            String matched = app.getSecondWinList().parallelStream().filter(s -> s.startsWith(sb.toString())).findFirst().orElse(null);
            System.out.println("pattern: "+sb.toString());
            System.out.println("matched: "+matched);
            System.out.println();
            if(matched == null){
                // B 赢不了
                // TODO: 回退回去 重新选择 但是得要保证A的选择不变
                System.out.println("B lost because cannot find match this pattern: "+sb.toString());
                break;
            }
            String countBStr = matched.substring(sb.toString().length(), sb.toString().length() + 1);
            int countB = Integer.parseInt(countBStr);
            sb.append(countB).append(" ");

            count += (countA + countB);
        }
        if(sb.toString().trim().split(" ").length % 2 == 0){
            System.out.println("B Win and the final result: "+sb.toString().trim());
        }

    }
}