0

recently I was trying out some past year AIO questions, and I couldn't solve this one.

The problem is as follows:

Safe Cracking Input File: safein.txt Output File: safeout.txt Time Limit: 1 second Over the centuries many wars have been won, not through a battle of strength but a battle of wits. Your sources have recently informed you that your mother has purchased a pre-release copy of the latest computer game, WheeZork, and is hiding it in the safe at home. To open the safe, one must enter a long sequence of numbers by rotating the circular dial to each number in the correct order.

If the correct sequence of numbers is entered into the safe, the safe opens and you can sneak your Christmas present out early. If you get the sequence wrong the alarm system is activated and you will be grounded for life! Luckily, you know that your mother has written the code down on a sheet of paper in her bedside drawer, which she likes to call the "code sheet".

She often boasts about how clever she is and explains to you that the numbers on the sheet are indeed the code to the safe, however each number in the sequence has been increased by a constant non-negative integer, k, which only she knows. Without this value the sheet is useless, and thus only she can open the safe ... or so she thinks!

In order to determine the correct code, you have spied on your mother when she unlocks the safe and you have managed to remember part of the code that she entered. You are not sure which part of the code this corresponds to, but it is definitely a consecutive sequence of numbers in the code. Armed with this knowledge, you set out to determine the full code to the safe.

Your task is, given the full list of numbers your mother has written down on her code sheet, and the shorter sequence that you know appears in the actual code, determine the entire sequence to unlock the safe.

For example, if the code to the safe was 7, 9, 4, 6, 8, 12, and your mother had incremented all numbers by 4, her code sheet would read 11, 13, 8, 10, 12, 16. This is because 7 + 4 = 11, giving the first number 11. The second number is obtained by adding 9 + 4 = 13. The third number is obtained by adding 4 + 4 = 8, and so forth. You may have caught a glimpse of her entering the numbers 4, 6, 8, in order. With this knowledge, you can determine the entire code.

Input The first line of the input file will contain two integers, a b, separated by a space. The integer a is the length of the sequence written on your mother's code sheet ( 2 <= a <= 100000). The integer b is the length of the sequence that you know is contained within the code to the safe ( 2 <= b <= 30).

Following this will be a lines, each containing a single integer between 1 and 1000000. These lines are the sequence written on your mother's code sheet, in the order they are entered into the safe.

Following this will be b lines, each containing a single integer, also between 1 and 1000000. These lines describe the glimpse of the actual code to the safe.

You are guaranteed that there will only be one possible solution for any given input scenario.

Output Your output file should consist of a lines. Each of these lines should contain a single integer, representing the full sequence of numbers required to open the safe.

My code (that passes most test cases) is as follows:

'''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")

As this code passes most test cases, with the exception of some cases that give an error (I do not know what error it is), I was wondering if anyone could suggest some corner cases that would lead to this algorithm creating an error. So far all the cases that I have thought of have passed.

EDIT: as niemmi has pointed out below, there are some side cases which my above algorithm cannot handle. As such, I have rewritten another algorithm to solve it. This algorithm passes most test cases, and there are no errors, except that the execution takes longer than 1s. Could anyone help reduce the time complexity of this solution?

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

EDIT: Thanks to niemmi, who provided a solution below that I edited slightly to pass a test case returning an error. 

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))

Thanks!

Improve this question
1
  • Maybe your code fails because it takes too long for the input considered. Commented Aug 25, 2017 at 13:24

1 Answer 1

Reset to default
2

The above implementation calculates repeatedly the differences of consecutive elements on following lines:

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

When run against the example input after first round temp_sub is [2, 2] and after second and final round it is [0]. Then the implementation proceeds to do the same kind of reduction for temp_lst that contains the incremented code which results to [-7, 7, 0, 2].

Then index is used to find the index with 0 value from temp_lst which is then used to deduce k. This approach obviously won't work if there's another 0 value on temp_lst before the index you're trying to find. We can easily craft an input where this might be the case, for example adding 11 twice at the beginning of the code sheet so the full sheet would be [11, 11, 11, 13, 8, 10, 12, 16].

EDIT Why not just use the initial approach of differences of subsequent numbers to find k? Code below loops over code sheet and for each position checks if plain sequence can start from there i.e. if the number is equal or greater than first number in plain sequence since k was defined to be non-negative integer. Then it loops over next b - 1 numbers both on code sheet and plain sequence to see if differences match or not.

Worst case time complexity is O(ab), if that's not good enough you could utilize KMP for faster matching.

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))
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

hmm i did consider that, however the problem seems to be that an error is generated, rather than the answer being wrong. However I'll go and make the necessary edits and tell you if it worked. Thanks!
upvote because your answer offers a test case for which the code fails, which is what was requested.
@RussellNg Added example solution
@niemmi hi, thanks for the example solution. However it still returns incorrect answers in 3 test cases (I believe this is because the answer outputs numbers that are greater than 1000000 or less than 0; is there any way to ensure that the numbers outputted are between 1 to 1000000?) Also I edited your solution slightly to pass a test case that returned an error. Thanks!
@RussellNg There was indeed a bug in the code that you discovered and another one, the lack of checking if k is negative which is not possible according to problem statement. I fixed both issues and tested against AIO site where it seems to work.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.