Improvement On Python Algorithm For Hackerrank Encryption Challenge

This article is based on the solution to the hackerrank encryption programming challenge. I would like to document the process it took for me to get an efficient algorithm and explain my reasoning, realization and re-learning process. With hopes that, it might help another developer studying to move from average to 10X. To improve ones algorithms with respect to programming, the developer must change the way programming problems are evaluated mentally, as well as, how solutions to the problems are created. One must first understand the default way one thinks to arrive at the solution and then, improve it by including the optimization into the default process not as an after-thought but rather, integrating it as one of the crucial initial guiding factors.

Lately, I have been really focused on algorithms as I realized that the beginning of the journey to becoming a 10X programmer commences with the efficiency of one’s algorithms. Imagine a programming world where every single line of code is written efficiently the very first time with respect to time and space, this would automatically eliminate the need for code optimization saving coders a lot of time and corporations a lot of money. Of course, this idea only exists in a perfect world. However, it’s my earnest belief that in the programming sphere the very first level, is learning programming syntax, semantics and being able to write logical solutions to problems by working with the programming language of choice. This is ground zero for all coders, the mere requirement to usher a beginner into the world of endless possibilities as a programmer, once this has been achieved it is imperative that the coder proceed to the next level which is efficiency of algorithms. I am almost certain that this level should precede the mighty Design Patterns.

Problem

An English text needs to be encrypted using the following encryption scheme.
First, the spaces are removed from the text. Let L be the length of this text.
Then, characters are written into a grid, whose rows and columns have the following constraints:

For example, the sentence s = if man was meant to stay on the ground god would have given us roots, after removing spaces is 54 characters long. √54 is between 7 and 8, so it is written in the form of a grid with 7 rows and 8 columns

The rest of the question can be seen and attempted here: Hackerrank Encryption Challenge

Here is my approach and thought process

After reading through the problem, I decided to follow each thought process of the given problem and efficiently implement the steps suggested to solve the challenge exactly as they are stated in the problem formulation by writing a code translation for each line:

1. Get the row and column of the array by finding the floor and ceiling of the root of the length of the space-less string and verifying the constraint is preserved
2. Creating an array and inserting the individual character values inside the array in the described order
3. Looping through the array and printing the results column by column

Looks easy enough right? Yea Sure, this was what I came up with:

First Algorithm

from sys import stdin, stdout
import math
import time

#Get the input 
x = stdin.readline()
z = len(x)
w = math.sqrt(z)
u = list(x)

#Get the rows and columns of the array
if w%1 == 0:
    r = int(w)
    c = int(w)
else:
    r = int(w)
    c = int(w)+1

while(r * c) < z:
    r = r + 1
    if(r * c) < z:
        c = c + 1

#Create the array
a = [[0 for y in range (c)] for x in range (r)]

#Insert values inside the array
i = 0
j = 0
k = 0

while (i <= (r-1)) and (k <= (z-1)):
    if j <= (c-1):
        a[i][j] = u[k]
        j += 1
        k += 1
    else:
        j = 0
        i += 1

#Create the result & return the value
result = ""
for p in range(c):
    for q in range(r):
        if (a[q][p] != 0):
            result = result + a[q][p]
    result = result + " "
stdout.write(result)

Would you like to guess what the time complexity of this solution is? My first thought process was just solving the problem, I did exactly everything stated in the problem statement without thinking of alternative/better ways to arrive at the solution.

Time Complexity: O(2√n + n-1 + n)

Sure there may or may not have been other routes to take but without pausing to consider and analyze, the first idea is all one has to go by. I had accepted without question the default idea I had and quickly began coding to get a solution as early as possible.

With this approach, you will get alot of surprises along the way, which will lead to the inclusion of many avoidable conditional statements, all in a bid to hold the code together and come-out at the other end with a solution. The initial time gained by running with the very first idea will be lost at the time of debugging. Whereas, if you had taken the time to think thoroughly, when you eventually start coding the process would move along alot faster, with fewer hiccups.

Yes, its a solution, no doubt about it but its a very bad one and so I took a look at some of the other approaches taken by other programmers who have solved the problem in the discussion section and tasked myself to think of a better way to solve the problem and improve the efficiency of my code

Now that was my new objective, no-longer simply to have an algorithm that solves the problem but rather one with lesser and optimized code. Specifically, reducing the loops i.e “while”, “for loops” and eliminating as much lines of code as possible:

Second Algorithm

import math
#Get the input from the user
s = stdin.readline()

#Get the rows and columns
rl = math.floor(math.sqrt(len(s)))
cl = math.ceil(math.sqrt(len(s)))
j = 0
k = 1
r = 1

#Generate the result and return the output
result = ""
for i in range(len(s) + rl):
    if (r <= rl) and i < len(s):
        if (k <= cl):
            j += r
            k += 1
        else:
            j = r
            k = 2
            r += 1
        result = result[:j] + s[i] + result[j:]
    else:
        j = r
        r += rl
        result = result[:j] + " " + result[j:]
        r += 1

stdout.write(result)

The second approach was much better than the first, from the discussion I realized that there was a given python library I could use to get the row and column. This solves that section of the problem with a single line which negates the necessity for reinventing the wheel. Using this, solved the problem of getting the rows and columns in two line, what previously took 12 lines in the first approach

Time Complexity: O(n + √n)

Next I wanted to improve the code as mentioned earlier and after a considerable amount of time thinking, I began to question if I could actually solve the problem without creating an array, so by using a single loop I could go through the given string and using the row and column relationship, sort out the characters and still within this same loop generate the result and print it. My reasoning was that, there are two ways to achieve this:

1. Using the size i.e rows and columns of the array create a nested loop and generate the solution within the same loop.
2. Using a single loop through the string + a loop of the size of the rows to add the desired space between the final output.

The important thing to me was adjusting my mental approach to solving problems, the logical steps I took to get the solution. I really wanted to understand what the other developers who used a different approach were thinking and why they solved the problems that way. So I took some time to think on this and eventually I realized that their thoughts were on the best way to solve the problem while still obeying all the constraints.

Seems easy enough right? Sure, let me go into details. This means after seeing the problem, you should:

1. Take out a pen and paper to mentally think about the most efficient way to solve the problem on paper. Not thinking about code now but just the most efficient solution. My initial mental approach was using a limited understanding of the language and fitting the solution to that, rather than thinking about the best possible solution first and then going about implementing it. Try not to limit your approach to your understanding of the language but rather, get the best solution by thinking about the problem critically, which then guides the next phase.
2. Next write the code to implement the best possible solution you have thought of. This way you avoid just jumping into the code getting stuck and cheating by adding as many “try catches” and “if else” statements required to come-out at the other end
3. Thirdly, after writing the code and running it to ensure it passes the sample cases. Quickly go through it again to see if any part of it can be optimized before the final submission.

After writing the second code I compared the time and space complexity of the second code with some solutions to the same problem I found online and was quite impressed with myself, till I found a much better one and realized there was still alot more improvements that could have been done. From that I learnt that, to get the best, one must pass through good and better. What I mean is, if you think up only one approach to solving a challenge, then you have only one choice and no options, however, if you think of many smart ways to solve it and then compare them for the best one, you stand a much better chance of getting the best solution.

Third Algorithm

import math
#Get the input from the user
s = stdin.readline()

#Get the rows and columns
rl = math.floor(math.sqrt(len(s)))
cl = math.ceil(math.sqrt(len(s)))

#Generate the result and return the output
result = ""
for i in range(cl):

    currentIndex = i
    for t in range(rl):
        if (currentIndex <= len(s) - 1):
            result = result + s[currentIndex]
            currentIndex += cl
    if (i + 1 != cl): result = result + " "


stdout.write(result)

The main difference between the code snippet above and the previous one is that this one takes the number one pattern of approach where the array size is used as the determining factor to loop over the string and generate the result.

I had actually thought about this but didn’t implement it because I felt there were situations where the array would be bigger than the number of strings and so a loop that goes through the entire string once is preferred to one with the size of the array which could be larger than the string size in some cases.

Time Complexity: O(n)

However if you look at the loop (range(len(s) + rl)), you would notice that the loop of the second algorithm does not just run over the size of the given string but also adds the size of the rows in order to add the final space between the output and at this very point the time complexity of the third approach beats the second.

“What I learnt from this was that thinking ideas through is also very important”.

I had discarded the idea of the third algorithm because of a notion I had which could have actually been correct but I should have gone further to create examples to test out and compare both approaches before finally choosing one. Doing this would have allowed me realize which was better.

Final Algorithm

import math

#Get the input
s=input()
sm=s.replace(" ","")

#Get the rows and Columns
r=math.floor(math.sqrt(len(sm)))
c=math.ceil(math.sqrt(len(sm)))

#Loop through the string and print the result
for i in range(c):
    print(sm[i::c],end=" ")

With the third algorithm I was completely confident that there could be no further optimization but little did I know. A few more searches and I found this. A solution that further reduced the space and time complexity.

Time Complexity: O(√n)

This code was written by Samar Yadav. The explanation can be found here

I invite you to read through his explanation. His approach utilized the slicing of list and array function in python. This enabled the use of a single loop based on the column size to go through the string and print the results with as few lines as possible. Very impressive stuff. The time complexity of his algorithm is much more efficient than the previously written codes and utilizes the very best of python, by reading through his code and the explanation it further dawned on me that in addition to an optimized logical steps, a great grasp of the precise programming language is also very important in this process. As this enables the use of functions that optimize one’s algorithm and also reduces the code required to solve the problems.

This part can be gained by extensive reading of programming books in general, yes but specifically it’s better to focus on the precise programming language of choice and once in a while comparing its approach to dealing with certain tasks with the approach taken by other languages to attend to the same task. Also a lot of practice is required. As in anything in life the more one practices, they better one becomes.

“Perhaps the most important principle for the good algorithm designer is to refuse to be content.”

― Alfred V. Aho

Thanks for taking the time to read this and good luck as your continue your journey to attain the 10X programmer status.