SPOJ "To and Fro"

Question

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)

Answer 1

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

Answer 2

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

Answer 3

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