题目79：通过分析用户的登陆日志，你能否找到用户的数字密码？

欧拉计划

Passcode derivation

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.

题目：

网上银行通用的一种加密方法是向用户询问密码中的三位随机字符。例如，如果密码是 531278，那么银行可以询问第 2,3,5 位字符，预期的回复应该是317。

文本文件 p079_keylog.txt (200 Bytes, 下载次数: 32)

2015-11-5 17:22 上传

点击文件名下载附件
keylog.txt

包含 50 次成功的登录尝试。

已知三位字符总是按顺序询问，分析文件并找出可能的最短的密码（长度未知）。

jerryxjr1220

一种可能的最短密码组合之一：
73162890
满足以上50次成功登录尝试。

jerryxjr1220

穷举，然后排除

import itertools

logins = [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]


for len_code in range(4, 100):

    for code in itertools.permutations(list(range(10)), len_code):
        login_counter = 0
        for login in logins:
            digits = (login // 100, (login % 100) // 10, login % 10)

            if digits[0] not in code:
                break

            pos_0 = code.index(digits[0])
            curr_code = code[pos_0 + 1:]

            if digits[1] not in curr_code:
                break
            pos_1 = curr_code.index(digits[1])
            curr_code = curr_code[pos_1 + 1:]

            if digits[2] not in curr_code:
                break

            login_counter += 1
        # if all logins fit the code, it is a solution
        if login_counter == len(logins):
            print code
            exit()

jerryxjr1220

既然是排列组合和匹配问题，其实可以用itertools和re模块来解决。

logins = [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]
import re
import itertools as it
def findlog(n):
  s = list(str(n))
  return '.*'+'.*?'.join(s)+'.*'
for i in it.permutations(['1','2','3','6','7','8','9','0'],8):
  flag = 1
  for j in logins:
    if not re.match(findlog(j),''.join(i)):
      flag = 0
      break
  if flag:
    print ''.join(i)
    break

秒出答案

najin

用的matlab
结果是
     7     3     1     6     2     8     9     0

     7     3     1     6     2     8     9     0

时间已过 0.004162 秒。
>>