机考A卷100分题 - 猜数字

题目描述

一个人设定一组四码的数字作为谜底，另一方猜。

每猜一个数，出数者就要根据这个数字给出提示，提示以XAYB形式呈现，直到猜中位置。

其中X表示位置正确的数的个数（数字正确且位置正确），而Y表示数字正确而位置不对的数的个数。

例如，当谜底为8123，而猜谜者猜1052时，出题者必须提示0A2B。

例如，当谜底为5637，而猜谜者才4931时，出题者必须提示1A0B。

当前已知N组猜谜者猜的数字与提示，如果答案确定，请输出答案，不确定则输出NA。

输入描述

第一行输入一个正整数，0＜N ＜ 100。

接下来N行，每一行包含一个猜测的数字与提示结果。

输出描述

输出最后的答案，答案不确定则输出NA。

用例

题目解析

我的解题思路是：

暴力枚举所有可能的谜底，即0000~9999，然后用每一个谜底去过输入的猜测。

我们假设某个谜底 和 输入的猜测数字 产生的猜测提示是real_result，而输入中猜测数字对应的猜测提示是expect_result，如果real_result == expect_result，那么说明说明当前谜底符合当前猜测数字的要求。

如果某个谜底，可以符合所有猜测数字的要求，那么该谜底就是一个可用谜底。

如果，暴力枚举出来的所有谜底中，只有一个可用谜底，那么该谜底就是题解。否则本题无解，返回NA。

当前上面算法非常容易超时，原因就是我们需要验证0000~9999这一万个可能的谜底，而每个可能的谜底有需要验证最多100个输入的猜测数字。

因此，我们需要做一些剪枝优化，比如题目用例输入中有一行：

4901 0A0B

这行的含义其实是：真正的谜底的四个数字不能取4，9，0，1这些。

再比如：

5716 0A1B
7842 0A1B
4901 0A0B

上面三行中，都是0A，即每一位上的数字都不是真正谜底的该位置的数字。

比如：5716 0A1B

即：真正的谜底，第一位不可能是5，第二位不可能是7，第三位不可能是1，第四位不可能是6

那么真正的谜底，第一位只能从非5数种选，第二位只能从非7数中选.......

这样的话，就做到了剪枝优化，即四码谜底的每一位数不需要从0~9中选，而是可以从更小的范围内选。

目前，我这边制作了0A，以及0A0B的剪枝处理，其他情况比如：

0A0B  0A1B  0A2B  0A3B  0A4B
1A0B  1A1B  1A2B  1A3B
2A0B  2A1B  2A2B
3A0B  3A1B
4A0B

可以视实际机试时间限制要求选做。

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
let n;
let infos;
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length == 1) {
    n = lines[0] - 0;
  }

  if (n && lines.length == n + 1) {
    lines.shift();
    infos = lines.map((line) => line.split(" "));
    console.log(getResult());
    lines.length == 0;
  }
});

function getResult() {
  const num = getCombine();
  const cache = [];

  for (let c1 of num[0]) {
    for (let c2 of num[1]) {
      for (let c3 of num[2]) {
        for (let c4 of num[3]) {
          const answer = `${c1}${c2}${c3}${c4}`;
          if (isValid(answer)) cache.push(answer);
        }
      }
    }
  }

  // 答案不确定则输出NA
  if (cache.length != 1) return "NA";
  else return cache[0];
}

// 剪枝逻辑，本题的后期优化主要在这个方法内进行
// 返回的是一个集合，集合有四个元素，分别对应四码的谜底数字的每一位，而每个集合元素又是一个Set，里面存放谜底数字对应的位上可能是哪些数字
function getCombine() {
  // 初始时，四码谜底的每一位都有十种可能，即每一位都能取值0~9
  const num = new Array(4)
    .fill(0)
    .map(() => new Set(new Array(10).fill(0).map((_, i) => i + "")));

  // 遍历猜谜者猜的数字guess_num与提示guess_result
  for (let info of infos) {
    const [guess_num, guess_result] = info;

    // 数字正确且位置正确的个数
    let countA = guess_result[0] - 0;
    // 数字正确而位置不对的数的个数
    let countB = guess_result[2] - 0;

    // 如果countA == 0,则说明当前guess_num的每一位上的数字的位置都不正确，即对应位上不应该出现对应数字
    if (countA == 0) {
      for (let i = 0; i < 4; i++) {
        const c = guess_num[i];
        // 如果countB == 0，则说明当前guess_num上所有位上的数字都不正确，即任意位上都不应该出现该数字
        if (countB == 0) {
          num[0].delete(c);
          num[1].delete(c);
          num[2].delete(c);
          num[3].delete(c);
        } else {
          num[i].delete(c);
        }
      }
    }
  }

  return num;
}

// 判断谜底answer是否正确，即是否符合所有猜测提示
function isValid(answer) {
  for (let info of infos) {
    const [guess, expect_result] = info;
    const real_result = getGuessResult(guess, answer);
    if (real_result != expect_result) return false;
  }
  return true;
}

// 获取猜的数字guess在指定谜底answer下的猜测提示
function getGuessResult(guess, answer) {
  let countA = 0;
  let countB = 0;

  const answer_arr = new Array(10).fill(0);
  const guess_arr = new Array(10).fill(0);

  for (let i = 0; i < guess.length; i++) {
    const c1 = guess[i] - 0;
    const c2 = answer[i] - 0;

    if (c1 == c2) countA++;
    else {
      guess_arr[c1]++;
      answer_arr[c2]++;
    }
  }

  for (let i = 0; i < 10; i++) {
    countB += Math.min(answer_arr[i], guess_arr[i]);
  }

  return `${countA}A${countB}B`;
}

Java算法源码

import java.util.*;

public class Main {
  static String[][] infos;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();

    infos = new String[n][2];
    for (int i = 0; i < n; i++) {
      infos[i][0] = sc.next();
      infos[i][1] = sc.next();
    }

    System.out.println(getResult());
  }

  public static String getResult() {
    ArrayList<HashSet<Character>> num = getCombine();
    ArrayList<String> cache = new ArrayList<>();

    for (Character c1 : num.get(0)) {
      for (Character c2 : num.get(1)) {
        for (Character c3 : num.get(2)) {
          for (Character c4 : num.get(3)) {
            String answer = new String(new char[] {c1, c2, c3, c4});
            if (isValid(answer)) {
              cache.add(answer);
            }
          }
        }
      }
    }

    // 答案不确定则输出NA
    if (cache.size() != 1) return "NA";
    else return cache.get(0);
  }

  // 剪枝逻辑，本题的后期优化主要在这个方法内进行
  // 返回的是一个集合，集合有四个元素，分别对应四码的谜底数字的每一位，而每个集合元素又是一个Set，里面存放谜底数字对应的位上可能是哪些数字
  public static ArrayList<HashSet<Character>> getCombine() {
    List<Character> tmp = Arrays.asList('0', '1', '2', '3', '4', '5', '6', '7', '8', '9');
    ArrayList<HashSet<Character>> num = new ArrayList<>();
    // 初始时，四码谜底的每一位都有十种可能，即每一位都能取值0~9
    for (int i = 0; i < 4; i++) num.add(new HashSet<>(tmp));

    // 将infos按照猜测提示进行字典序升序，即0A0B排在最前面，4A0B排在最后面，这样排序的用意是0A0B可以不依赖其他条件完成数字过滤
    //    Arrays.sort(infos, (a, b) -> a[1].compareTo(b[1]));

    // 遍历猜谜者猜的数字guess_num与提示guess_result
    for (String[] info : infos) {
      String guess_num = info[0];
      String guess_result = info[1];

      // 数字正确且位置正确的个数
      int countA = guess_result.charAt(0) - '0';
      // 数字正确而位置不对的数的个数
      int countB = guess_result.charAt(2) - '0';

      // 如果countA == 0,则说明当前guess_num的每一位上的数字的位置都不正确，即对应位上不应该出现对应数字
      if (countA == 0) {
        for (int i = 0; i < 4; i++) {
          Character c = guess_num.charAt(i);
          if (countB == 0) {
            // 如果countB == 0，则说明当前guess_num上所有位上的数字都不正确，即任意位上都不应该出现该数字
            num.get(0).remove(c);
            num.get(1).remove(c);
            num.get(2).remove(c);
            num.get(3).remove(c);
          } else {
            num.get(i).remove(c);
          }
        }
      }
    }

    return num;
  }

  // 判断谜底answer是否正确，即是否符合所有猜测提示
  public static boolean isValid(String answer) {
    for (String[] info : infos) {
      String guess = info[0];
      String expect_result = info[1];
      String real_result = getGuessResult(guess, answer);
      if (!expect_result.equals(real_result)) return false;
    }
    return true;
  }

  // 获取猜的数字guess在指定谜底answer下的猜测提示
  public static String getGuessResult(String guess, String answer) {
    int countA = 0;
    int countB = 0;

    int[] answer_arr = new int[10];
    int[] guess_arr = new int[10];

    for (int i = 0; i < guess.length(); i++) {
      char c1 = guess.charAt(i);
      char c2 = answer.charAt(i);

      if (c1 == c2) countA++;
      else {
        answer_arr[c2 - '0']++;
        guess_arr[c1 - '0']++;
      }
    }

    for (int i = 0; i < 10; i++) {
      countB += Math.min(answer_arr[i], guess_arr[i]);
    }

    return new StringBuilder().append(countA).append("A").append(countB).append("B").toString();
  }
}

Python算法源码

# 输入获取
n = int(input())
infos = [input().split() for _ in range(n)]


# 获取猜的数字guess在指定谜底answer下的猜测提示
def getGuessResult(guess, answer):
    countA = 0
    countB = 0

    answer_arr = [0] * 10
    guess_arr = [0] * 10

    for i in range(len(guess)):
        c1 = int(guess[i])
        c2 = int(answer[i])

        if c1 == c2:
            countA += 1
        else:
            guess_arr[c1] += 1
            answer_arr[c2] += 1

    for i in range(10):
        countB += min(answer_arr[i], guess_arr[i])

    return f"{countA}A{countB}B"


# 判断谜底answer是否正确，即是否符合所有猜测提示
def isValid(answer):
    for info in infos:
        guess, expect_result = info
        real_result = getGuessResult(guess, answer)
        if expect_result != real_result:
            return False
    return True


# 剪枝逻辑，本题的后期优化主要在这个方法内进行
# 返回的是一个列表，列表有四个元素，分别对应四码的谜底数字的每一位，而每个列表元素又是一个列表，里面存放谜底数字对应的位上可能是哪些数字
def getCombine():
    # 初始时，四码谜底的每一位都有十种可能，即每一位都能取值0~9
    num = [set([i for i in range(10)]) for _ in range(4)]

    # 遍历猜谜者猜的数字guess_num与提示guess_result
    for info in infos:
        guess_num, guess_result = info

        # 数字正确且位置正确的个数
        countA = int(guess_result[0])
        # 数字正确而位置不对的数的个数
        countB = int(guess_result[2])

        # 如果countA == 0,则说明当前guess_num的每一位上的数字的位置都不正确，即对应位上不应该出现对应数字
        if countA == 0:
            for i in range(4):
                c = int(guess_num[i])
                if countB == 0:
                    # 如果countB == 0，则说明当前guess_num上所有位上的数字都不正确，即任意位上都不应该出现该数字
                    num[0].discard(c)
                    num[1].discard(c)
                    num[2].discard(c)
                    num[3].discard(c)
                else:
                    num[i].discard(c)

    return num


# 算法入口
def getResult():
    num = getCombine()
    cache = []

    for c1 in num[0]:
        for c2 in num[1]:
            for c3 in num[2]:
                for c4 in num[3]:
                    answer = f"{c1}{c2}{c3}{c4}"
                    if isValid(answer):
                        cache.append(answer)

    # 答案不确定则输出NA
    if len(cache) != 1:
        return "NA"
    else:
        return cache[0]


# 算法调用
print(getResult())