可能導致錯誤的角落案例

Question

最近我嘗試了一些過去一年的AIO問題，而且我無法解決這個問題。

的問題如下：

安全開裂 輸入文件：safein.txt 輸出文件：safeout.txt 時間限制：1秒 千百年來的戰爭已經贏了，不通過戰鬥力量，但鬥智鬥勇。您的消息來源最近通知您，您的母親已經購買了最新電腦遊戲WheeZork的預發佈副本，並將其隱藏在家中的保險箱中。要打開保險櫃，必須按正確的順序將圓形轉盤旋轉到每個數字，然後輸入一長串數字。

如果號碼的正確順序進入安全的，安全的打開，您可以潛入你的聖誕禮物早早出局。如果序列錯誤，報警系統將被激活，您將終身接地！幸運的是，您知道您的母親已將代碼寫在她牀頭抽屜裏的一張紙上，她喜歡稱之爲「代碼表」。

她經常吹噓自己是多麼聰明，並向您解釋說明表中的數字確實是安全的代碼，但序列中的每個數字已增加了一個常數非負整數k，只有她知道。如果沒有這個價值，這張紙是沒用的，因此只有她才能打開保險櫃......或者她認爲！

爲了確定正確的代碼，你有你的母親窺探時，她解鎖安全，你得記住，她輸入的代碼的一部分。您不確定這段代碼的哪一部分對應，但它絕對是代碼中連續的數字序列。掌握了這些知識後，您開始着手確定保險箱的完整代碼。

你的任務是，給你的母親已經寫在她的代碼表編號的完整列表，並且您知道出現在實際的代碼的短序列，確定整個序列保險箱的鎖打開。

例如，如果保險箱的代碼是7,9,4,6,8,12，而您的母親已將所有數字遞增4，她的代碼表將會讀取11,13,8,10,12 ，這是因爲7 + 4 = 11，給出第一個數字11.第二個數字是通過加上9 + 4 = 13得到的。第三個數字是通過加上4 + 4 = 8等等獲得的。你可能已經看到了她爲了輸入數字4,6,8。有了這些知識，你可以確定整個代碼。

輸入 輸入文件的第一行包含兩個整數，A B，由空格分開。整數a是寫在母親代碼表上的序列的長度（2 < = a < = 100000）。整數b是您知道包含在安全代碼中的序列長度（2 < = b < = 30）。

在此之後將是一個線條，每片含1到1000000之間的一個整數。這些線是寫在你母親的碼片序列，在它們的順序依次進入安全。

在此之後會是B行，每行包含一個整數，也1和1000000，這些線之間的描述實際的代碼到安全的一瞥。

我們保證只有一種可能的解決方案適用於任何給定的輸入場景。

輸出 輸出文件應該由一行代碼組成。這些行中的每一行都應該包含一個整數，表示打開保險箱所需的全部數字序列。

我的代碼（即通過大多數測試用例）如下：

'''program implements a function diff which is returns a list that is the difference of the current elements in the list 
to solve the problem, the subset list is reduced until it consists of a single integer 
the index of this integer in the original list is then found, before determining the non-negative integer 
which was used to encode the numbers''' 
def diff(lst): 
    lst2=[] 
    for i in range(len(lst)-1): 
     lst2.append(lst[i+1]-lst[i]) 
    return lst2 
infile = open("safein.txt", "r") 
outfile = open("safeout.txt", "w") 
a, b = map(int, infile.readline().split()) 
lst, sub = [], [] 
for i in range(a): 
    lst.append(int(infile.readline())) 
for j in range(b): 
    sub.append(int(infile.readline())) 
temp_sub=sub 
temp_lst=lst 
k = 0 
while len(temp_sub) != 1: 
    temp_sub=diff(temp_sub) 
    k+=1 
for x in range(k): 
    temp_lst=diff(temp_lst) 
n = temp_lst.index(temp_sub[0]) 
m = lst[n]-sub[0] 
lst=[x-m for x in lst] 
for i in lst: 
    outfile.write(str(i) + "\n") 

由於此代碼將最測試用例，某些情況下，讓一個錯誤的例外（我不知道是什麼錯誤時是），我想知道是否有人可以建議一些會導致此算法創建錯誤的角落案例。到目前爲止，我所想到的所有情況都已經過去了。

編輯： 正如niemmi指出的那樣，我的上述算法無法處理一些副案例。因此，我重寫了另一個算法來解決它。該算法通過大多數測試用例，並且沒有錯誤，除了執行時間超過1s。任何人都可以幫助減少此解決方案的時間複雜性？

def subset(lst1, lst2): 
    if lst2[0] in lst1: 
     idx = lst1.index(lst2[0]) 
     for i in range(len(lst2)): 
      if lst2[i]==lst1[idx+i]: 
       continue 
      else: 
       return False 
    else: 
     return False 
    return True 

infile = open("safein.txt", "r") 
outfile = open("safeout.txt", "w") 

a, b = map(int, infile.readline().split()) 
lst, sub = [], [] 
for x in range(a): 
    lst.append(int(infile.readline())) 
for y in range(b): 
    sub.append(int(infile.readline())) 

if subset(lst, sub): 
    for i in range(a): 
     outfile.write(str(int(lst[i])) + "\n") 
    infile.close() 
    outfile.close() 
    exit() 

i=1 
while True: 
    temp_sub = [x+i for x in sub] 
    if subset(lst, temp_sub): 
     lst = [x-i for x in lst] 
     for j in range(a): 
      outfile.write(str(int(lst[j])) + "\n") 
     infile.close() 
     outfile.close() 
     exit() 
    i+=1 

編輯： 由於niemmi，誰提供低於予略微編輯通過測試情況下返回一個錯誤的溶液。

def diff(seq): 
    return (seq[i - 1] - seq[i] for i in range(1, len(seq))) 


with open('safein.txt') as in_file: 
    a, b = (int(x) for x in in_file.readline().split()) 
    code = [int(in_file.readline()) for _ in range(a)] 
    plain = [int(in_file.readline()) for _ in range(b)] 

code_diff = tuple(diff(code)) 
plain_diff = tuple(diff(plain)) 

k = 0 
def index(plain_diff, code_diff, plain, code, a, b, k): 
    for i in range(k, a - b): 
     for j, x in enumerate(plain_diff, i): 
      if code_diff[j] != x: 
       break 
     else: 
      k = code[i] - plain[0] 
      break # found match, break outer loop 
    return k 

k = index(plain_diff, code_diff, plain, code, a, b, k) 

with open('safeout.txt', 'w') as out_file: 
    out_file.write('\n'.join(str(x - k) for x in code)) 

謝謝！

Answer 1

上述實施重複計算上下面的行的連續元素的差異：

while len(temp_sub) != 1: 
    temp_sub=diff(temp_sub) 
    k+=1 

當抵靠例如輸入第一輪temp_sub後運行是[2, 2]和後第二和最後一輪它是[0]。然後執行繼續執行temp_lst的相同類型的縮減，其中包含遞增的代碼，結果爲[-7, 7, 0, 2]。

然後index用於查找與來自temp_lst0值，然後將其用於推導k中的索引。如果在您嘗試查找的索引之前temp_lst上存在另一個0值，則此方法顯然不起作用。在這種情況下，我們可以很容易地創建一個輸入，例如在代碼表的開頭添加11兩次，這樣整個表就是[11, 11, 11, 13, 8, 10, 12, 16]。

編輯爲什麼不直接使用後續數字差異的初始方法來找到k？下面的代碼在代碼表上循環，並且對於每個位置檢查平原序列是否可以從那裏開始，即，如果該數字等於或大於以普通序列的第一數字，因爲k被定義爲非負整數。然後循環遍歷編碼表和普通序列上的下一個b - 1數字，以查看差異是否匹配。

最壞情況的時間複雜度是O（ab），如果這還不夠好，你可以利用KMP來加快匹配。

with open('safein.txt') as in_file: 
    a, b = (int(x) for x in in_file.readline().split()) 
    code = [int(in_file.readline()) for _ in range(a)] 
    plain = [int(in_file.readline()) for _ in range(b)] 

for i in range(a): 
    k = code[i] - plain[0] 
    if k < 0: 
     continue 

    for j in range(1, b): 
     if code[i] - code[i + j] != plain[0] - plain[j]: 
      break 
    else: 
     break # found match, break outer loop 

with open('safeout.txt', 'w') as out_file: 
    out_file.write('\n'.join(str(x - k) for x in code))