Cerinta completa

Jack and Daniel are friends. They want to encrypt their conversations so that they can save themselves from interception by a detective agency so they invent a new cipher.

Every message is encoded to its binary representation. Then it is written down times, shifted by bits. Each of the columns is XORed together to get the final encoded string.

If and it looks like so: 

1001011     shift 0 
01001011    shift 1
001001011   shift 2
0001001011  shift 3
----------
1110101001  <- XORed/encoded string s

Now we have to decode the message. We know that . The first digit in so our output string is going to start with . The next two digits are also , so they must have been XORed with . We know the first digit of our shifted string is a as well. Since the digit of is , we XOR that with our and now know there is a in the position of the original string. Continue with that logic until the end.

Then the encoded message and the key are sent to Daniel.

Jack is using this encoding algorithm and asks Daniel to implement a decoding algorithm.
Can you help Daniel implement this?

Function Description

Complete the cipher function in the editor below. It should return the decoded string.

cipher has the following parameter(s):

  • k: an integer that represents the number of times the string is shifted
  • s: an encoded string of binary digits

Input Format

The first line contains two integers and , the length of the original decoded string and the number of shifts.
The second line contains the encoded string consisting of ones and zeros.

Constraints




It is guaranteed that is valid.

Output Format

Return the decoded message of length , consisting of ones and zeros.

Sample Input 0

7 4
1110100110

Sample Output 0

1001010

Explanation 0

1001010
 1001010
  1001010
   1001010
----------
1110100110

Sample Input 1

6 2
1110001

Sample Output 1

101111

Explanation 1

101111
 101111
-------
1110001

Sample Input 2

10 3
1110011011

Sample Output 2

10000101

Explanation 2

10000101
010000101

0010000101

1110011011

Limbajul de programare folosit: python3

Cod:

#!/bin/python3

import sys

def cipher(k, s):
    s_len = len(s)
    out_len = s_len - k + 1
    result = [0] * out_len
    
    result[-1] = int(s[-1])
    keep_prev = result[-1]
    for it_ind in range(1, out_len):
        # keep the result string only
        to_update = out_len - 1 - it_ind
        result[to_update] = int(s[-(it_ind+1)])
        #print(result)
        #print("it_ind = {} < {} = k".format(it_ind, k))
        #if it_ind < k:
        #    keep_prev = 0
        #    for k_ind in range(1, k):
        #        from_update = to_update + k_ind
        #        if from_update == out_len:
        #            #print('breaking')
        #            break
        #        #print("to_update = [{}] <-- [{}] outlen = {}".format(to_update, from_update, out_len))
        #        #result[to_update] ^= result[from_update]
        #        #print("POPULATE KEEP to_update = [{}] <-- [{}] outlen = {}".format(to_update, from_update, out_len))
        #        keep_prev ^= result[from_update]
        #else:
        #    #print("UPDATE KEEP to_update + k = [{} + {}]".format(to_update, k))
        #    keep_prev ^= result[to_update + k]
        if it_ind >= k:
            keep_prev ^= result[to_update + k]
            
        result[to_update] ^= keep_prev
        keep_prev ^= result[to_update]
                

    return "".join(map(str, result))
        
if __name__ == "__main__":
    n, k = input().strip().split(' ')
    n, k = [int(n), int(k)]
    s = input().strip()
    result = cipher(k, s)
    print(result)

Scor obtinut: 1.0

Submission ID: 464605160

Link challenge: https://www.hackerrank.com/challenges/cipher/problem

Cipher