2
\$\begingroup\$

This is the To and Fro problem at SPOJ:

Mo and Larry have devised a way of encrypting messages. They first decide secretly on the number of columns and write the message (letters only) down the columns, padding with extra random letters so as to make a rectangular array of letters. For example, if the message is “There’s no place like home on a snowy night” and there are five columns, Mo would write down

t o i o y
h p k n n
e l e a i
r a h s g
e c o n h
s e m o t
n l e w x

Mo then sends the message to Larry by writing the letters in each row, alternating left-to-right and right-to-left. So, the above would be encrypted as

toioynnkpheleaigshareconhtomesnlewx

Your job is to recover for Larry the original message (along with any extra padding letters) from the encrypted one.

There will be multiple input sets. Input for each set will consist of two lines. The first line will contain an integer in the range 2...20 indicating the number of columns used. The next line is a string of up to 200 lower case letters. The last input set is followed by a line containing a single 0, indicating end of input.

My code runs fine, but I believe that it is too big. Please help me find a better solution.

import sys
col=int(raw_input())
while(col!=0):
    string=raw_input()
    row=(len(string))/col
    b=""
    for i in range(0,row):
        if i%2==0:
            b+=string[i*5:(i+1)*5]
        else:
            b+=(string[i*5:(i+1)*5])[::-1]
    c=""
    for k in range(0,col):
        for p in range(0,row):
            c+=b[k+p*col]
    print c
    col=int(raw_input())
sys.exit(0)
\$\endgroup\$
  • 5
    \$\begingroup\$ Welcome to Code Review! Since links can rot, Please include a description of the challenge here in your question.. \$\endgroup\$ – 200_success May 15 '15 at 5:52
  • 1
    \$\begingroup\$ What do you mean by "it is too big"? The souce code is too long? The program takes too much time? The program uses too much memory? \$\endgroup\$ – Gareth Rees May 15 '15 at 11:53
  • \$\begingroup\$ @200_success.. I will take care of that from next time.. Thanks. \$\endgroup\$ – Jayant Mundhra JT May 16 '15 at 18:05
  • \$\begingroup\$ @GarethReesI meant that the code is too long I believe. \$\endgroup\$ – Jayant Mundhra JT May 16 '15 at 18:06
3
\$\begingroup\$
  1. There's no need to call sys.exit. When Python reaches the end of a program it exits automatically.

  2. string is a very vague variable name. Something like ciphertext would be more meaningful.

  3. In string[i*5:(i+1)*5] and similar expressions, the number 5 should be col.

  4. The code employs a two-stage decryption process. First, it undoes the reversal of every other row, and then it selects every col-th letter in the result.

    But it is possible to do the decryption in just one stage, by considering carefully where each letter in the ciphertext goes in the plaintext. For consider a ciphertext like this, where the number of columns is \$n=5\$:

    toioynnkpheleaigshareconhtomesnlewx
    

    To read down column \$ i = 0 \$ of the rectangular array, we need to pick the following letters:

    toioynnkpheleaigshareconhtomesnlewx
    ↥        ↑↥        ↑↥        ↑↥
    

    That is, letters 0, 10, 20, ... (indicated with ↥) interleaved with letters 9, 19, 29, ... (indicated with ↑). Expressed in terms of \$n\$ and \$i\$, that's letters $$ i, 2n - i - 1, 2n + i, 4n - i - 1, 4n + i, \dotsc $$

    This leads to the following simple implementation, using itertools.product:

    from itertools import product
    
    def decipher(ciphertext, cols):
        rows = len(ciphertext) // cols
        return ''.join(ciphertext[j * cols + (cols - i - 1 if j % 2 else i)]
                       for i, j in product(range(cols), range(rows)):
    
\$\endgroup\$
  • \$\begingroup\$ Thanks for describing the use of product from itertools. I'm new to python and I got to learn a new concept due to that. Also, I did find the mistake that "col<->5" and I had corrected that and my code got accepted. \$\endgroup\$ – Jayant Mundhra JT May 16 '15 at 18:15
2
\$\begingroup\$
  • In python 2.7, the range method actually creates a list so it will be better to use xrange which creates a generator

  • Try to build your output into a string using join and finally output the entire string as output. This is to reduce amount of time spent on IO as IO is slow

With that said, this is how I will rewrite your code:

from sys import stdin

read_message = lambda: (int(stdin.readline().strip()), stdin.readline().strip())

def solve():
    col, string = read_message()
    if col == 0: return
    row = len(string)//col

    b = "".join([string[i*5:(i+1)*5] if i % 2 == 0 else string[i*5:(i+1)*5][::-1] for i in xrange(row)])

    c = "".join([b[k+p*col] for k in xrange(col) for p in xrange(row)])
    yield c

if __name__ == '__main__':
    print "\n".join(solve())

One more thing, don't be afraid of spaces :)

\$\endgroup\$
  • \$\begingroup\$ thanks for help. Can you tell me when to use raw_input() and stdin.readline() ? And which one is more preferable for competitive coding like on spoj.com or codechef? \$\endgroup\$ – Jayant Mundhra JT May 16 '15 at 18:26
  • \$\begingroup\$ I used stdin.readline because it doesn't throw an exception if stdin has reached EOF, otherwise, raw_input () is recommended \$\endgroup\$ – smac89 May 16 '15 at 18:42
1
\$\begingroup\$

You are following the big ball of mud anti-pattern: you wrote a single monolithic and impossible to reuse piece of code. I think you should strive to write functions that are as small as possible and as reusable as possible, (automatic testing is also a nice habit to get used to). Writing a modular program with tests takes more time and space (about 15-20 min for this trivial problem and 63 lines) but the result is more readable, that is what you want, since you asked here at Codereview.

import doctest

def thunks(lst, n):
    """
    Divides the list in `n` equally sized pieces.

    >>> thunks([1,2,3,4,5,6], 2)
    [[1, 2, 3], [4, 5, 6]]
    >>> thunks('hello now', 3)
    ['hel', 'lo ', 'now']
    """
    thunk_size = len(lst) // n
    return [lst[i:i+thunk_size] for i in range(0,len(lst),thunk_size)]

def flatten1(lst):
    """
    Flattens one level (shallow).

    >>> flatten1([[4,5],[1]])
    [4, 5, 1]
    """
    return [i for sublst in lst for i in sublst]

def invert_odd_indexed(lst_of_lsts):
    """
    Reverses the elements of the odd-indexed lists.

    >>> invert_odd_indexed([ [1,2], [3,4], [5,6] ])
    [[1, 2], [4, 3], [5, 6]]
    """
    return [list(reversed(lst)) if index % 2 == 1 else lst
               for index, lst in enumerate(lst_of_lsts)]


def decode_text(text, key):
    """
    Mo and Larry have devised a way of encrypting messages.
    They first decide secretly on the number of columns and write the message (letters only) down the columns,7
    padding with extra random letters so as to make a rectangular array of letters.
    For example, if the message is “There’s no place like home on a snowy night” and there are five columns, Mo would write down

    t o i o y
    h p k n n
    e l e a i
    r a h s g
    e c o n h
    s e m o t
    n l e w x

    Mo then sends the message to Larry by writing the letters in each row,
    alternating left-to-right and right-to-left. So, the above would be encrypted as:

    toioynnkpheleaigshareconhtomesnlewx

    >>> decode_text('toioynnkpheleaigshareconhtomesnlewx', 5)
    'theresnoplacelikehomeonasnowynightx'
    >>> decode_text('ttyohhieneesiaabss', 3)
    'thisistheeasyoneab'
    """
    rows = thunks(text, len(text)//key)
    return ''.join(flatten1(zip(*invert_odd_indexed(rows))))

if __name__ == "__main__":
    doctest.testmod()
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.