6
\$\begingroup\$

Given a two-dimensional list, say some_list = ["ABCD", "EFGH", "IJ"], I am supposed to encrypt it by reading each column top to bottom, thus:

A B C D

E F G H

I J

Would become:

AEI BFJ CG DH

My initial try had “index out of range” problem so I did this:

def encrypt_list(some_list):
    encrpted_list = []
    for i in range(c):
        string = ""
        for j in range(f):
            string += my_list[j][i:i + 1]
        encrpted_list.append(string)
    return encrpted_list

Which looks like a hack. Is there a more Pythonic way?

(This is essentially the Encryption problem from HackerRank.)

Complete working code:

import math

s = "feedthedog"
length_s = len(s)

f = math.floor(math.sqrt(length_s))
c = math.ceil(math.sqrt(length_s))

if c * f < length_s:
    f = c


def chunks(string, split_point):
    for start in range(0, len(string), split_point):
        yield s[start:start + split_point]


split_list = [chunk for chunk in chunks(s, c)]


def encrypt_list(my_list):
    encrpted_list = []
    for i in range(c):
        string = ""
        for j in range(f):
            string += my_list[j][i:i + 1]
        encrpted_list.append(string)
    return encrpted_list


solution_list = encrypt_list(split_list)


for item in solution_list:
    print(item, end=" ")
\$\endgroup\$

3 Answers 3

5
\$\begingroup\$

There's an app for that

The nice thing about the python standard library, especially itertools is that there's always a function for what you want to do. In this case, you want to take chunks like:

['ABCD', 'EFGH', 'IJ']

and turn them into chunks like:

['AEI', 'BFJ', 'CG', 'DH']

That is, we're round robining through each row. There's a recipe for that:

def roundrobin(*iterables):
    "roundrobin('ABC', 'D', 'EF') --> A D E B F C"
    # Recipe credited to George Sakkis
    pending = len(iterables)
    nexts = cycle(iter(it).__next__ for it in iterables)
    while pending:
        try:
            for next in nexts:
                yield next()
        except StopIteration:
            pending -= 1
            nexts = cycle(islice(nexts, pending))

So ultimately, we have just a couple steps:

  1. Get our chunks.
  2. Round robin through them.
  3. Join the result

    def chunks(l, n):
        """Yield successive n-sized chunks from l."""
        for i in range(0, len(l), n):
            yield l[i:i+n]
    
    def encrypt(s):
        n = int(math.sqrt(len(s))
        chunked = chunks(s, n)
        return ''.join(roundrobin(*chunked))
    

Prefer to join

In your solution, you have:

string = ""
for j in range(f):
    string += my_list[j][i:i + 1]
encrpted_list.append(string)

This is inefficient though. When we're building up strings, it's much better to join them:

encrpted_list.append(''.join(my_list[j][i:i+1] for j in range(f)))

Evaluate lazily

This is inefficient:

split_list = [chunk for chunk in chunks(s, c)]

You likely only evaluated out chunks due to the way you wrote your encrypter, but you want to keep things as generators for as long as possible. It's more efficient to pass in chunks(s,c) into the zip_longest() than it would be to fully evaluate it. Though if you do, it's shorter to just write:

split_list = list(chunks(s,c))

Minor points

  1. Excessive amounts of vertical spacing here.
  2. encrpted_list is misspelled: should be encrypted_list.
  3. Why do you have encrypt_list that takes a list and returns a list? You should have encrypt that takes a string and returns a string.
  4. You don't need f,c... you can use int to get the floor, and add 1 if necessary. And avoid single-letter names.
\$\endgroup\$
1
  • \$\begingroup\$ Minor point (1): I think your solution have it all as one string; it has to be separated by a single space. Minor point (2): I think your code assumes the new matrix as complete. \$\endgroup\$
    – blackened
    Commented Dec 1, 2015 at 23:41
3
\$\begingroup\$

I agree with Barry that itertools is your friend here. However, I would note that transposing matrices is often done using some kind of zip() function. Here, I would use itertools.zip_longest(), since it's not a complete rectangle.

[''.join(filter(None, col)) for col in itertools.zip_longest(*some_list)]
# ^^^^^^^^^^^^^^^^^^^^^^^^^            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
# Convert tuples to strings            Transpose matrix
\$\endgroup\$
2
  • \$\begingroup\$ Yeah that's what I started with, but then I thought we needed to join everything back together at the end too so I went with roundrobin. Also, you can pass in a fillvalue for zip_longest to avoid the filter. \$\endgroup\$
    – Barry
    Commented Dec 2, 2015 at 14:53
  • \$\begingroup\$ You could also just use an outer " ".join if you need to return a string rather than a list \$\endgroup\$
    – Felipe
    Commented Dec 4, 2015 at 23:42
3
\$\begingroup\$

Another approach you could take is to pad the string with empty characters. These characters have no effect on the result. But they help you avoid "index out of range" problem and no need to use if-else for the boundary checks.

Moreover, we do not need to split the string into chunks. Instead, we could pick out values from the padded string using strides with step = n_cols.

Here's the full implementation:

def encrypt(s):
    L = len(s)
    n_cols = int(ceil(sqrt(L)))
    n_rows = (L + n_cols - 1) // n_cols
    s_padded = list(s) + [''] * (n_rows * n_cols - L)
    out = []

    for c in range(n_cols):
        out += s_padded[c::n_cols]
        out.append(' ')
    return ''.join(out[:-1])
\$\endgroup\$

Your Answer

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

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