跳水名将问题

　　　　　　　　　比赛的实际名次．

基本数据类型：

package com.plunge.data;public class Statement {public String person;public int rank;public String source;public boolean isTruth = false;public Statement(String source){this.source = source;person = source.split(" ")[0];rank = Integer.parseInt(source.split(" ")[1]);}public String toString() {return source;}
}

package com.plunge.data;public class PlayerStatement {public String player;public Statement[] statements = new Statement[]{null, null};public int checkStatus = -1;public String[] rawData = new String[] {"",""};public SelectActions actions;public PlayerStatement(String playerName, String statementA, String statementB) {player = playerName;statements[0] = new Statement(statementA);statements[1] = new Statement(statementB);rawData[0] = statementA;rawData[1] = statementB;}public Statement getTruth() {if (checkStatus < 0) {System.out.println("checkStatus uninitialized!");return null;}if (checkStatus < 2) {return statements[checkStatus];}return null;}public Statement getUntruth() {if (checkStatus == 1) {return statements[0];} else if (checkStatus == 0) {return statements[1];}return null;}public String toString() {return player + " said: " + rawData[0] + "," + rawData[1];}public String getTruthString() {if (checkStatus >= 0 && checkStatus < 2) {return player + " told truth: " + rawData[checkStatus];} else {return player + " told no truth";}}}

package com.plunge;import java.util.ArrayList;
import java.util.Date;
import java.util.HashMap;import com.plunge.creator.Method1;
import com.plunge.creator.Method2;
import com.plunge.creator.MethodAcurate;
import com.plunge.creator.MethodSimple;
import com.plunge.data.PlayerStatement;//Ａ选手说：Ｂ第二，我第三；
//Ｂ选手说：我第二，Ｅ第四；
//Ｃ选手说：我第一，Ｄ第二；
//Ｄ选手说：Ｃ最后，我第三；
//Ｅ选手说：我第四，Ａ第一．
//
//决赛成绩公布之后，每位选手的预测都只说对了一半，即一对一错．请编程解出
//比赛的实际名次．
public class Main {
//	statementLst.add(new PlayerStatement("A", "B 2", "A 3"));
//	statementLst.add(new PlayerStatement("B", "B 2", "E 4"));
//	statementLst.add(new PlayerStatement("C", "C 1", "D 2"));
//	statementLst.add(new PlayerStatement("D", "C 5", "D 3"));
//	statementLst.add(new PlayerStatement("E", "E 4", "A 1"));//	statementLst.add(new PlayerStatement("A", "B 3", "A 4"));
//	statementLst.add(new PlayerStatement("B", "D 1", "C 4"));
//	statementLst.add(new PlayerStatement("C", "D 3", "C 4"));
//	statementLst.add(new PlayerStatement("D", "A 2", "D 3"));//	statementLst.add(new PlayerStatement("A", "D 2", "B 4"));
//	statementLst.add(new PlayerStatement("B", "D 2", "A 1"));
//	statementLst.add(new PlayerStatement("C", "D 1", "C 3"));
//	statementLst.add(new PlayerStatement("D", "C 2", "D 4"));public static void main(String[] args) {//"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L"//"A", "B", "C", "D", "E"
//		String[] playerArr = new String[] {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L"};
//		ArrayList ret = DivingIssueCreator.create(playerArr);
//		for (int i = 0; i < ret.size(); i++) {
//			PlayerStatement item = ret.get(i);
//			System.out.println(item.toString());
//		}PlungeRank plunge = new PlungeRank();
//		ArrayList statementLst = new ArrayList();
//		statementLst.add(new PlayerStatement("A", "D 3", "A 2"));
//		statementLst.add(new PlayerStatement("B", "B 4", "B 2"));
//		statementLst.add(new PlayerStatement("C", "A 1", "B 4"));
//		statementLst.add(new PlayerStatement("D", "C 4", "C 3"));
//		statementLst.add(new PlayerStatement("E", "A 4", "D 5"));
//		plunge.process(statementLst);Method1 oneWay = new Method1();Method2 twoWay = new Method2();MethodSimple simpleWay = new MethodSimple();MethodAcurate acurateWay = new MethodAcurate();ArrayList correctIssues = new ArrayList();for (int i = 0; i < 10; i++) {String[] playerArr = new String[] {"A", "B", "C", "D", "E"};ArrayList ret = acurateWay.create(playerArr);System.out.println("==========issue " + i + "=======================");for (int j = 0; j < ret.size(); j++) {System.out.println(ret.get(j).toString());}if (plunge.process(ret)) {correctIssues.add(i);}}System.out.println(correctIssues.toString() + ", " + correctIssues.size() + " issues generate success!");}}

PlungeRank.java

核心代码,  采用DFS 搜索答案

package com.plunge;import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;import com.plunge.data.PlayerStatement;
import com.plunge.data.SelectActions;
import com.plunge.data.Statement;public class PlungeRank {private ArrayList statementLst = new ArrayList();private ArrayList allPlayers = new ArrayList();private ArrayList allRanks = new ArrayList();private HashMap checkFlags = new HashMap();private HashMap personMap = new HashMap(); private HashMap rankMap = new HashMap();private HashMap> personMapFallacy = new HashMap>();private HashMap> rankMapFallacy = new HashMap>();private static final int STATUS_UNCHECKED = 0; private static final int STATUS_TRUE = 1;private static final int STATUS_FALSE = 2;public PlungeRank(){}public boolean process(ArrayList lst) {ArrayList> answerLst = new ArrayList>();statementLst = lst;initData();int index = 0;PlayerStatement first = statementLst.get(0);while(true) {
//			System.out.println(index);PlayerStatement playerWords = statementLst.get(index);if(selectStatement(playerWords)) {index++;if (index < statementLst.size()) {PlayerStatement nextWords = statementLst.get(index);nextWords.checkStatus = -1;}} else {index--;if (index >= 0) {playerWords = statementLst.get(index);unSelectStatement(playerWords);}}if (index == statementLst.size()) {System.out.println("==========answer=======================");ArrayList answer = retrieveAnswer();answerLst.add(answer);printAnswer(answer);index--;PlayerStatement lastOne = statementLst.get(index);unSelectStatement(lastOne);}if (first.checkStatus > 1) {//backtracking endedbreak;}}if (answerLst.size() < 1) {System.out.println("failed to find answer!");}if (answerLst.size() == 1) {return true;}return false;}private ArrayList retrieveAnswer() {ArrayList ret = new ArrayList();for (int i = 0; i < statementLst.size(); i++) {PlayerStatement item = statementLst.get(i);ret.add(item.checkStatus);}return ret;}private void printAnswer(ArrayList answer) {String[] allPlayerArr = new String[allPlayers.size()];allPlayers.toArray(allPlayerArr);ArrayList playerLst = new ArrayList(Arrays.asList(allPlayerArr));ArrayList deduceLst = new ArrayList();for (int i = 0; i < statementLst.size(); i++) {PlayerStatement item = statementLst.get(i);item.checkStatus = answer.get(i);System.out.println(item.getTruthString());playerLst.remove(item.getTruth().person);}HashMap> deducedPersonFallacy = deducePersonFallacy();for (int i = 0; i < playerLst.size(); i++) {ArrayList rankLst = deducedPersonFallacy.get(playerLst.get(i));if (rankLst.size() == 1) {deduceLst.add(playerLst.get(i) + " " + rankLst.get(0));}}System.out.println("==========deduce=======================");System.out.println(deduceLst.toString());}private HashMap> deducePersonFallacy() {HashMap> copy = new HashMap>();Iterator>> iter = personMapFallacy.entrySet().iterator();while (iter.hasNext()) {Map.Entry> entry = (Map.Entry>) iter.next(); String keyPerson = entry.getKey();ArrayList rankLst = entry.getValue();Integer[] rankArr = new Integer[rankLst.size()];rankLst.toArray(rankArr);ArrayList copiedRankLst =  new ArrayList(Arrays.asList(rankArr));copy.put(keyPerson, copiedRankLst);}
//		System.out.println("deducePersonFallacy");int oldSingleNum = -1;while(true) {ArrayList singleRanks = new ArrayList();Iterator>> iterCopy = copy.entrySet().iterator();while (iterCopy.hasNext()) {Map.Entry> entry = (Map.Entry>) iterCopy.next(); ArrayList rankLst = entry.getValue();if (rankLst.size() == 1) {singleRanks.add(rankLst.get(0));}}if (oldSingleNum < 0) {oldSingleNum = singleRanks.size();} else if (oldSingleNum == singleRanks.size()){break;}if (!changeMap(copy, singleRanks)) {break;}}return copy;}private boolean changeMap(HashMap> map, ArrayList deduced) {Iterator>> iter = map.entrySet().iterator();boolean changed = false;while (iter.hasNext()) {Map.Entry> entry = (Map.Entry>) iter.next(); ArrayList rankLst = entry.getValue();if (rankLst.size() > 1) {for (int i = 0; i < deduced.size(); i++) {int value = deduced.get(i);int index = rankLst.indexOf(value);if (index >= 0) {rankLst.remove(index);changed = true;}}}}return changed;}private void initData() {allPlayers.clear();allRanks.clear();checkFlags = new HashMap();personMap = new HashMap();rankMap = new HashMap();personMapFallacy = new HashMap>();rankMapFallacy = new HashMap>();for (int i = 0; i < statementLst.size(); i++) {int rank = i + 1;String playerString = statementLst.get(i).player;allRanks.add(rank);allPlayers.add(playerString);}for (int i = 0; i < statementLst.size(); i++) {PlayerStatement player = statementLst.get(i);Statement words1 = player.statements[0];Statement words2 = player.statements[1];checkFlags.put(words1.source, STATUS_UNCHECKED);checkFlags.put(words2.source, STATUS_UNCHECKED);personMap.put(player.player, -1);int rank = i + 1;rankMap.put(rank, "");Integer[] allRankArr = new Integer[allRanks.size()];allRanks.toArray(allRankArr);personMapFallacy.put(player.player, new ArrayList(Arrays.asList(allRankArr)));String[] allPlayerArr = new String[allPlayers.size()];allPlayers.toArray(allPlayerArr);rankMapFallacy.put(rank, new ArrayList(Arrays.asList(allPlayerArr)));}}private boolean selectStatement(PlayerStatement statement) {statement.checkStatus++;if (statement.checkStatus > 1) {return false;}
//		System.out.println(statement.getTruthString());
//		if (statement.player.equals("C")) {
//			System.out.println("ssaa");
//		}Statement truth = statement.getTruth();SelectActions actions = getSelectActions(statement);
//		boolean permission1 = canAddStatementToMap(truth, true);
//		boolean permission2 = canAddStatementToMap(fallacy, false);if (actions != null) {//modify 5 maps and record changes for backtrackingfor (int i = 0; i < actions.checkFlagChanges.size(); i++) {String checkMapKey = actions.checkFlagChanges.get(i);if (truth.source.equals(checkMapKey)) {checkFlags.put(checkMapKey, STATUS_TRUE);} else {checkFlags.put(checkMapKey, STATUS_FALSE);}}int rankMapKey = actions.rankMapChange;if (rankMapKey > 0) {rankMap.put(rankMapKey, truth.person);}String personMapKey = actions.personMapChange;if (personMapKey.length() > 0) {personMap.put(personMapKey, truth.rank);}Iterator>> iter = actions.rankFallacyChanges.entrySet().iterator();while (iter.hasNext()) {Map.Entry> entry = (Map.Entry>) iter.next();int keyRank = entry.getKey();ArrayList deleted = entry.getValue();ArrayList oldLst = rankMapFallacy.get(keyRank);for (int i=0; i>> iterPerson = actions.personFallacyChanges.entrySet().iterator();while (iterPerson.hasNext()) {Map.Entry> entry = (Map.Entry>) iterPerson.next(); String keyPerson = entry.getKey();ArrayList deleted = entry.getValue();ArrayList oldLst = personMapFallacy.get(keyPerson);for (int i=0; i 0) {rankMap.put(rankMapKey, "");}String personMapKey = actions.personMapChange;if (personMapKey.length() > 0) {personMap.put(personMapKey, -1);}Iterator>> iter = actions.rankFallacyChanges.entrySet().iterator();while (iter.hasNext()) {Map.Entry> entry = (Map.Entry>) iter.next();int keyRank = entry.getKey();ArrayList deleted = entry.getValue();ArrayList oldLst = rankMapFallacy.get(keyRank);for (int i=0; i>> iterPerson = actions.personFallacyChanges.entrySet().iterator();while (iterPerson.hasNext()) {Map.Entry> entry = (Map.Entry>) iterPerson.next(); String keyPerson = entry.getKey();ArrayList deleted = entry.getValue();ArrayList oldLst = personMapFallacy.get(keyPerson);for (int i=0; i>> iter = personMapFallacy.entrySet().iterator();while (iter.hasNext()) {Map.Entry> entry = (Map.Entry>) iter.next(); String keyPerson = entry.getKey();if (!keyPerson.equals(truth.person)) {ArrayList ranks = entry.getValue();int removeIndex = ranks.indexOf(truth.rank);if (removeIndex >= 0) {
//						int removed = ranks.remove(removeIndex);ArrayList lst = actions.personFallacyChanges.get(keyPerson);lst.add(truth.rank);}}}} else if (personMap.get(truth.person) != truth.rank) {return null;}if (rankMap.get(truth.rank) == "") {
//			rankMap.put(truth.rank, truth.person);actions.rankMapChange = truth.rank;Iterator>> iter = rankMapFallacy.entrySet().iterator();while (iter.hasNext()) {Map.Entry> entry = (Map.Entry>) iter.next();int keyRank = entry.getKey();if (keyRank != truth.rank) {ArrayList persons = entry.getValue();int removeIndex = persons.indexOf(truth.person);if (removeIndex >= 0) {
//						String removed = persons.remove(removeIndex);ArrayList lst = actions.rankFallacyChanges.get(keyRank);lst.add(truth.person);}}}} else if (!rankMap.get(truth.rank).equals(truth.person)) {return null;}ArrayList rankLst = personMapFallacy.get(fallacy.person);int index = rankLst.indexOf(fallacy.rank);if (index >= 0) {
//			rankLst.remove(index);ArrayList lst = actions.personFallacyChanges.get(fallacy.person);if (lst.indexOf(fallacy.rank) < 0) {lst.add(fallacy.rank);}}ArrayList personLst = rankMapFallacy.get(fallacy.rank);index = personLst.indexOf(fallacy.person);if (index >= 0) {
//			personLst.remove(index);ArrayList lst = actions.rankFallacyChanges.get(fallacy.rank);if (lst.indexOf(fallacy.person) < 0) {lst.add(fallacy.person);}}Iterator>> iter = actions.personFallacyChanges.entrySet().iterator();while (iter.hasNext()) {Map.Entry> entry = (Map.Entry>) iter.next(); String keyPerson = entry.getKey();ArrayList ranks = entry.getValue();ArrayList currentRankLst = personMapFallacy.get(keyPerson);if (ranks.size() == currentRankLst.size()) {return null;}}Iterator>> iterChanges = actions.rankFallacyChanges.entrySet().iterator();while (iterChanges.hasNext()) {Entry> entry = (Map.Entry>) iterChanges.next(); Integer keyRank = entry.getKey();ArrayList persons = entry.getValue();ArrayList currentPersonLst = rankMapFallacy.get(keyRank);if (persons.size() == currentPersonLst.size()) {return null;}}return actions;}}

package com.plunge.data;import java.util.ArrayList;
import java.util.HashMap;public class SelectActions {public SelectActions(ArrayList allPlayers) {//init rankFallacyChanges and personFallacyChangesfor (int i = 0; i < allPlayers.size(); i++) {String player = allPlayers.get(i);personFallacyChanges.put(player, new ArrayList());Integer rank = i+1;rankFallacyChanges.put(rank, new ArrayList());}}public ArrayList checkFlagChanges = new ArrayList();public int rankMapChange = -1;public String personMapChange = "";public HashMap> rankFallacyChanges = new HashMap>();public HashMap> personFallacyChanges = new HashMap>();
}

package com.plunge.Interface;import java.util.ArrayList;import com.plunge.data.PlayerStatement;public interface ICreator {public ArrayList create(String[] players);
}

package com.plunge.creator;import java.util.ArrayList;import com.plunge.Interface.ICreator;
import com.plunge.data.PlayerStatement;
import com.plunge.util.Tool;public class Method1 implements ICreator{@Overridepublic ArrayList create(String[] players) {int size = players.length;ArrayList allCombinations = getAll2Combs(players);ArrayList personLst = new ArrayList();ArrayList rankLst = new ArrayList();for (int i = 1; i <= size; i++) {rankLst.add(i);personLst.add(i-1);}personLst = Tool.shuffle(personLst);rankLst = Tool.shuffle(rankLst);ArrayList statements = new ArrayList();for (int i=0; i < size; i++) {ArrayList randomSet = new ArrayList();String combo = getRandomCombination(allCombinations);String person1 = combo.split(" ")[0];String person2 = combo.split(" ")[1];get2RandomItems(rankLst, randomSet);int rank1 = randomSet.get(0);int rank2 = randomSet.get(1);String statementA = person1 + " " + rank1;String statementB = person2 + " " + rank2;PlayerStatement playerWords = new PlayerStatement(players[i], statementA, statementB);statements.add(playerWords);}return statements;}private void get2RandomItems(ArrayList list, ArrayList ret) {int first = (int) (list.size() * Math.random());int second = (int) (list.size() * Math.random());while (first == second) {second = (int) (list.size() * Math.random());}ret.clear();ret.add(list.get(first));ret.add(list.get(second));}private ArrayList getAll2Combs(String[] players) {ArrayList ret = new ArrayList();for (int i = 0; i < players.length; i++) {for (int j = i+1; j < players.length; j++) {String item = players[i] + " " + players[j];ret.add(item);}}return ret;}private String getRandomCombination(ArrayList combos) {int index = (int) (Math.random() * combos.size());String item = combos.get(index);combos.remove(index);return item;}}

当选手很多时， MethodAcurate类， 生成问题的成功率很高，Method1类成功率很低，
比如:
当有12个选手："A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", Method1的成功率不到 1%， 而MethodAcurate的成功率大于 80%, 
当有5个选手: "A", "B", "C", "D", "E"，Method1的成功率 大于20 %， MethodAcurate的成功率大于 50%
Method1可能生成需要推理才能得到最终结果的问题， MethodAcurate目前生成的都是不需要推理，就能得到结果的问题

package com.plunge.creator;import java.util.ArrayList;import com.plunge.Interface.ICreator;
import com.plunge.data.PlayerStatement;
import com.plunge.data.Statement;
import com.plunge.util.Tool;public class MethodAcurate implements ICreator {private String[] playerArr;ArrayList personLst = new ArrayList();ArrayList rankLst = new ArrayList();public ArrayList create(String[] players) {personLst.clear();rankLst.clear();playerArr = players;int size = players.length;for (int i = 1; i <= size; i++) {rankLst.add(i);personLst.add(i-1);}personLst = Tool.shuffle(personLst);rankLst = Tool.shuffle(rankLst);ArrayList answer = new ArrayList();for (int i = 0; i < size; i++) {answer.add(new Statement(players[personLst.get(i)] + " " + rankLst.get(i)));}System.out.println("================generator======================");
//		System.out.println("personLst: " + personLst.toString());
//		System.out.println("rankLst: " + rankLst.toString());System.out.println("supposed: " + answer.toString());ArrayList statements = new ArrayList();for (int i = 0; i < size; i++) {Statement fallacy = getFalseStatement(answer, i);Statement truth = answer.get(i);String sen1 = truth.source;String sen2 = fallacy.source;PlayerStatement words;if ( (int) (Math.random() * 2) == 1) {words = new PlayerStatement(playerArr[i], sen1, sen2);} else {words = new PlayerStatement(playerArr[i], sen2, sen1);}statements.add(words);}return statements;}private Statement getFalseStatement(ArrayList answer, int index) {Statement item = answer.get(index);int personInt = getRandomItem(personLst);String person = playerArr[personInt];while (person.equals(item.person)) {personInt = getRandomItem(personLst);person = playerArr[personInt];}int rightRank = getRankByPerson(answer, person);int rank = getRandomItem(rankLst);
//		System.out.println("getFalseStatement, rank:"+rank+", mentioned:"+item.rank+","+rightRank);while (rank == item.rank || rank == rightRank) {rank = getRandomItem(rankLst);
//			System.out.println("getFalseStatement, rank:"+rank);}return new Statement(person + " " + rank);}private int getRandomItem(ArrayList lst) {int index = (int) (lst.size() * Math.random());return lst.get(index);}private int getRankByPerson(ArrayList answer, String person) {for (int i = 0; i < answer.size(); i++) {if (answer.get(i).person.equals(person)) {return answer.get(i).rank;}}return 1;}}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！