codekata/mastermind – 论坛（BBS）

Context Navigation

7.5,7.12,7.19,7.26 代码道场主题MasterMind记实

代码道场的参与者:秦鸿源，陈阳，王安宁，丁健勇，邝巨恒，李炳岳,黄志强,李剑文，张艺辉, 李峰

地点：4G会议室

题目介绍：

MasterMind中文名为珠玑妙算,是一个智力小游戏。出谜语的人，给出4位数字，让猜谜的人猜，如果猜中一个数字，得到一个B，如果数字的位置也对的话，得到一个A，如：谜底是2386，则2135，得到的结果是1A1B,所以，当得到4A0B时，即中结果，胜利出局。

要求用程序，以尽量少的次数，猜出结果

由于，这次题目，较前几期活动难度更大，活动参与人数也较大，众口难调，为了统一思想，让大家都充分理解解题思路，

花费了较多的时间，在编码过程中却又难以形成思路的统一，再加上成员技术水平有限，这几次代码道场活动，最终没有完成.

这是一次失败的教训

失败原因归结为以下几点:

1,题目难度较大,大家花了较多精力专注于如何解决问题，怱视了测试驱动开发.

2,大家在讨论如何解决问题时，不是从易到难，循序渐进，个个击破，而是一开始就期望找到最优的解题方法。后面两次活动，才纠正这个问题

3,活动一开始时，大家没有形成统一思想，就开始各顾各的编码，后继同事，难于续接。

大家最终讨论的方案实现代码如下

猜测结果类 Result.java

/**
 * 猜测结果类，若结果是4A0B，则猜中
 * @author chenyang
 * @version 7.0
 * date : 2013-7-29
 * 
 */
public class Result {
	
	private int numA;
	
	private int numB;

	public int getNumA() {
		return numA;
	}

	public void setNumA(int numA) {
		this.numA = numA;
	}

	public int getNumB() {
		return numB;
	}

	public void setNumB(int numB) {
		this.numB = numB;
	}
	
	public Result() {
		
	}

	public Result(int numA, int numB) {
		super();
		this.numA = numA;
		this.numB = numB;
	}

	public int sum(){
		return numA + numB;
	}
	
	/**
	 * 是否猜中所有数字
	 * @return
	 */
	public boolean isRight(){
		return this.numA == 4;
	}

	@Override
	public String toString() {
		return numA+"A"+numB+"B"; 
	}
	
}

猜测结果测试类 ResultTest?.java

import static org.junit.Assert.*;

import org.junit.Test;

/**
 * @author chenyang
 * @version 7.0
 * 
 */
public class ResultTest {
	@Test
	public void isRight() throws Exception {
		Result r = new Result(1,1);
		assertFalse(r.isRight());
		
		r = new Result(4,0);
		assertTrue(r.isRight());
	}
}

谜底类 Puzzle.java

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Random;

/**
 * @author chenyang
 * @version 7.0
 * date : 2013-7-29
 * 
 */
public class Puzzle {
	
	//谜底
	private int[] numbers;

	public int[] getNumbers() {
		return numbers;
	}

	public void setNumbers(int[] numbers) {
		this.numbers = numbers;
	}
	
	public Puzzle(){
		this.numbers = new int[4];
		LinkedList<String> list = new LinkedList<String>();
		for(int i=0; i<10; i++){
			list.add(String.valueOf(i));
		}
		Random random = new Random();
		//随机产生谜底
		for(int i=0; i<4; i++){
			int posi = random.nextInt(list.size());	
			String value = list.remove(posi);
			this.numbers[i] = Integer.valueOf(value);
		}
	}
	
	/**
	 * 用指定数组猜结果
	 * @param guess
	 * @return 猜测结果
	 */
	public Result match(int[] guess) {
        int a=0;
        int b=0;
        for(int i =0; i<guess.length;i++){
	        for(int j =0;j<numbers.length;j++){
	            if(guess[i] == numbers[j] && i == j){
	                a++;
	            } else if(guess[i] == numbers[j]){
	                b++;
	            }
	        }
        }
        return new Result(a,b); 
	        
	}

	@Override
	public String toString() {
		return "Puzzle [numbers=" + Arrays.toString(numbers) + "]";
	}
	
	
	
}

谜底测试类 PuzzleTest?.java

import static org.junit.Assert.*;

import org.junit.Test;

/**
 * @author chenyang
 * @version 7.0
 * 
 */
public class PuzzleTest {
	@Test
	public void testPuzzle() throws Exception {
		Puzzle puzzle = new Puzzle();
		int[] numbers = puzzle.getNumbers();
		assertNotNull(numbers);
		
		for(int i=0; i<numbers.length; i++){
			assertTrue(numbers[i] >=0 && numbers[i] < 10);
		}
		
	}
	
	@Test
	public void match() throws Exception {
		Puzzle puzzle = new Puzzle();
		puzzle.setNumbers(new int[]{1,8,2,6});
		
		Result result = puzzle.match(new int[]{2,0,3,5});
		assertTrue(result.getNumA() == 0);
		assertTrue(result.getNumB() == 1);
		
		result = puzzle.match(new int[]{1,0,2,5});
		assertTrue(result.getNumA() == 2);
		assertTrue(result.getNumB() == 0);
		
		result = puzzle.match(new int[]{1,8,2,6});
		assertTrue(result.getNumA() == 4);
		assertTrue(result.getNumB() == 0);
	}
}

猜测过程实现类 GuessHandler?.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author chenyang
 * @version 7.0
 * date : 2013-7-29
 * 
 */
public class GuessHandler {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method st
		
		Puzzle puzzle = new Puzzle();
		System.out.println(puzzle);
		guessNumbers(puzzle, null);

	}
	
	/**
	 * 猜谜
	 * @param puzzle 谜语
	 * @param guess 试猜的谜语
	 * @return 谜底
	 */
	public static int[] guessNumbers(Puzzle puzzle, int[] guess){
		
		if(guess == null){
			//默认给一个答案
			guess = new int[]{1,2,3,4};
		}
		System.out.println(Arrays.toString(guess));
		Result r = puzzle.match(guess);
		
		//运气好，一次就猜中
		if(r.isRight()){
			return guess;
		}
		
		int[] result = new int[4];
		
		LinkedList<String> list = new LinkedList<String>();
		for(int i=0; i<10; i++){
			list.add(String.valueOf(i));
		}
		for(int i=0; i<guess.length; i++){
			int index = list.indexOf(String.valueOf(guess[i]));
			list.remove(index);
		}
		
		//答案以外其它数字
		int[] remain = new int[list.size()];
		for(int i=0; i<list.size(); i++){
			int num = Integer.valueOf(list.get(i));
			remain[i] = num;
		}
		
		//当前答案数字匹配个数
		int sum = r.sum();
		
		//用答案以外的每一个数字去替换答案中的每一个数,如果匹配的个数增加，说明，替换的数是匹配数字
		out : for(int i=0; i<remain.length; i++){
			int temp = remain[i];
			for(int j=0; j<guess.length; j++){
				int init = guess[j]; //保留初始状态
				guess[j] = temp;
				System.out.println(Arrays.toString(guess));
				r = puzzle.match(guess);
				//猜中结果
				if(r.isRight()){
					return guess;
				}
				if(r.sum() > sum){
					//替换的数字是匹配数
					result = guess;
					sum = r.sum();
					continue out;
				}else{
					//替换的数字不匹配，恢复到初始状态
					guess[j] = init;
				}
				
				if(sum == 4){
					//数字全部匹配
					break out;
				}
			}
		}
		
		//将匹配的数字全排列
		List<int[]> items = pl(result);
		for(int i=0; i<items.size(); i++){
			int[] curr = items.get(i);
			System.out.println(Arrays.toString(curr));
			//每种组合都猜下
			r = puzzle.match(curr);
			
			if(r.isRight()){
				//数字，位置都正确
				return curr;
			}
		}
		return result;
	}
	

	/**
	 *  全排列
	 * @param data
	 * @return
	 */
	public static List<int[]> pl(int[] data){
		List<int[]> list = new ArrayList<int[]>();
		if(data.length == 1){
			list.add(data);
			return list;
		}
		for(int i=0; i<data.length; i++){
			int c = data[i];
			int[] subdata = new int[data.length-1];
			if(i == 0){
				System.arraycopy(data, 1, subdata, 0, data.length-1);
			}else if(i == data.length - 1){
				System.arraycopy(data, 0, subdata, 0, data.length-1);
			}else{
				System.arraycopy(data, 0, subdata, 0, i);
				System.arraycopy(data, i+1, subdata, i, data.length-(i+1));
			}
			List<int[]> sublist = pl(subdata);
			for(int j=0; j<sublist.size(); j++){
				int[] subarr = sublist.get(j);
				int[] item = new int[subarr.length + 1];
				item[0] = c;
				System.arraycopy(subarr, 0, item, 1, subarr.length);
				list.add(item);
			}
			
		}
		return list;
	}
}

猜测过程实现类测试 GuessHandlerTest?.java

import java.util.Arrays;
import java.util.List;
import static org.junit.Assert.*;

import org.junit.Test;

/**
 * @author chenyang
 * @version 7.0
 * 
 */
public class GuessHandlerTest {
	@Test
	public void pl() throws Exception {
		List<int[]> list = GuessHandler.pl(new int[]{1,2,3});
		assertTrue(list.size() == 6);
		for(int i=0; i<list.size(); i++){
			int[] item = list.get(i);
			if(i == 0) assertEquals("[1, 2, 3]",Arrays.toString(item));
			if(i == 1) assertEquals("[1, 3, 2]",Arrays.toString(item));
			if(i == 2) assertEquals("[2, 1, 3]",Arrays.toString(item));
			if(i == 3) assertEquals("[2, 3, 1]",Arrays.toString(item));
			if(i == 4) assertEquals("[3, 1, 2]",Arrays.toString(item));
			if(i == 5) assertEquals("[3, 2, 1]",Arrays.toString(item));
		}
	}
	
	@Test
	public void guessNumbers() throws Exception {
		
		Puzzle puzzle = new Puzzle();
		
		int[] result = GuessHandler.guessNumbers(puzzle, null);
		for(int i=0; i<4; i++){
			assertEquals(puzzle.getNumbers()[i],result[i]);	
		}
		
	}
}

Download in other formats:

Plain Text