Cracking Hackerrank - Encryption
As a friend of mine loves to say, “The best way to learn a programming language is to start writing algorithms in it”. While that most probably won’t make you the language expert, there’s a high chance that you will face most of the data structures it provides as well as feel the power of it’s unique language constructs.
There’re lots of good resources to help you get started, but I prefer to spend my spare time on Hackerrank. It’s free, has pleasant user interface and a solid selection of algorithmic problems conveniently broken down into categories and difficulty levels.
After solving each problem, the whole analyzing part is usually getting thrown out. And that pointed me to the idea of writing the way of thinking into blog posts. Always good to look back and see how good you were and how bad was your English. So let’s get it started!
Our today’s problem - “Encryption” (link to the challenge).
Step 1. Detect the grid size
The problem defines a handful of conditions to detect the grid size:
floor(sqrt(L)) <= rows <= columns <= ceil(sqrt(L))
rows * columns >= L
If multiple grids satisfy the above conditions, we will choose the one with the minimum area, i.e.
rows * columns.
Let’s use the sample input and output provided by Hackerrank for the sake of clarity in the decision we will make. More
concrete, the string
haveaniceday should produce
hae and via ecy.
To have some base for the manual calculations, we are going to start by resolving the conditions:
L = len("haveaniceday") = 12
sqrt(L) = sqrt(12) = 3.46
floor(sqrt(L)) = floor(3.46) = 3
ceil(sqrt(L)) = ceil(3.46) = 4
By placing these values into the first condition,
we get the idea of the grid sizes available to us. Let’s analyze each of them in the ascending order:
3 * 3 = 9- the condition
rows * columns >= Lis not satisfied
3 * 4 = 12- the condition is satisfied
4 * 4 = 16- the condition is satisfied, but the area is larger than the one of the previous grid
Based on the knowledge we’ve got, let’s write our solution to the first step:
And the actual code in Go:
Step 2. Populate the grid
Using the values we calculated (
rows = 3 and
columns = 4), let’s represent our initial string in the form of a grid:
Populating the grid is fairly simple:
And the code in Go:
Step 3. Print the grid columns
The remaining piece of the problem is to display the resulted grid. The first column constructs the first word, followed by a space, followed by the word constructed from the second column, and so on:
The code implementation:
Getting everything together
The solution we have already passes all the test cases prepared by the Hackerrank team. But can we do even better?
It’s easy to spot how inefficient last two steps are, as both of them are iterating through all the elements inside our grid. Do we really need to do it twice? Do we need to have the grid populated? Do we need to initialize the grid at all?
If you answered “No” to all of the questions - fantastic! And let’s see what our optimized solution looks like:
And now it is almost twice as fast with 16 lines of code saved. Isn’t that great?