当前位置:首页 » Project Euler » 详细页

Passcode derivation 题号:79 难度: 5 中英对照

A common security method used for online banking is to ask the user for three random characters from a passcode. For example, if the passcode was 531278, they may ask for the 2nd, 3rd, and 5th characters; the expected reply would be: 317.

The text file, keylog.txt, contains fifty successful login attempts.

Given that the three characters are always asked for in order, analyse the file so as to determine the shortest possible secret passcode of unknown length.

Solution

本题较简单,直接遍历求解,结合代码分析: 1. 将keylog 文件中所有密钥保存在数组(SUBSEQS)中; 2. 预处理,将密钥数字全部存储在字符串数组packedSubseqs 中; 3. 从3位~50位数字$(10^3 \sim 10 ^{50})$ 序列升序遍历所有数字,找到满足条件的数字序列即可; 4. 使用toChars 方法将要遍历数字 转化为指定位数的字符数组,不足位数补 '0'; 5. 对遍历数字进行判断,判断密钥文件每个字符串,即数组packedSubseqs 中每个字符是否是该数字序列的子序列,若是返回结果,反之继续增序遍历知道找到该序列。

Code

public class p79 {
    public static void main(String[] args) {
        long start = System.nanoTime();
        long end = System.nanoTime();
        System.out.println(run());
        System.out.println((end - start) / 1000000 + "ms");

    }

    // keylog 文件中所有密钥保存在数组中
    private static String[] SUBSEQS = {"319", "680", "180", "690", "129", "620", "762", "689", "762", "318", "368", "710", "720", "710", "629", "168", "160", "689", "716", "731", "736", "729", "316", "729", "729", "710", "769", "290", "719", "680", "318", "389", "162", "289", "162", "718", "729", "319", "790", "680", "890", "362", "319", "760", "316", "729", "380", "319", "728", "716"};

    private static char[] packedSubseqs;


    public static String run() {
        // 预处理,将密钥数字全部存储在 packedSubseqs 字符数组中
        packedSubseqs = new char[SUBSEQS.length * 3];
        for (int i = 0; i < packedSubseqs.length; i++)
            packedSubseqs[i] = SUBSEQS[i / 3].charAt(i % 3);

        //  从 10^3 ~ 10^50(这里50 换成packedSubseqs.length 更严谨)升序遍历所有数,找到满足条件的数字序列
        for (int len = 3; len <= 50; len++) {
            int end = power(10, len);
            for (int guess = 0; guess < end; guess++) {
                // 将 guess 字符化为len 位字符,不足位数补'0'
                char[] guessChars = toChars(guess, len);
                // 判断该guessChars 字符是否包含密钥数组中的所有序列,若包含就返回结果
                if (isConsistent(guessChars))
                    return new String(guessChars);
            }
        }
        throw new RuntimeException("Not found"); //未找到
    }


    private  static boolean isConsistent(char[] guess) {
        // For each string 's' in SUBSEQS, test if 's' is a subsequence of 'guess'
        for (int i = 0; i < packedSubseqs.length; i += 3) {
            int j = 0;  // Index in 's'
            for (int k = 0; k < guess.length && j < 3; k++) {  // Index in 'guess'
                if (guess[k] == packedSubseqs[i + j])
                    j++;
            }
            if (j < 3)  // Not all characters consumed, fail
                return false;
        }
        return true;
    }


    // Converts integer to string with zero padding, in little endian.
    // Since we're trying all combinations, the order doesn't matter.
    private static char[] toChars(int n, int len) {
        char[] result = new char[len];
        int i = 0;
        for (; i < result.length; i++, n /= 10)
            result[i] = (char)('0' + (n % 10));
        if (n != 0)
            throw new IllegalArgumentException();
        for (; i < result.length; i++)
            result[i] = '0';
        return result;
    }

    // 求指数x^n
    private static int power(int x,int n){
        int prod = 1;
        for(int i = 0;i<n;i++){
            prod *= x;
        }
        return  prod;
    }

}
73162890
1ms