We solve the problem Hackerrank - "Encryption" (using Go)

I bring to your attention a translation of the Cracking Hackerrank - Encryption article from sobit.me .

As my friend likes to say: "The best way to learn a programming language is to start writing algorithms on it." Of course, this will not make anyone an expert of the language, but there is a high probability of meeting most of the data structures and feeling the power of unique language constructs.

There are many good resources to get started , but I prefer to spend my free time on Hackerrank . It is free, has a nice interface and a solid set of algorithmic problems, conveniently divided into categories and levels of complexity.
')
After solving each problem, often the part with the analysis of the solution goes into the bucket. And that gave me the idea to write down the train of thought in the form of blog articles. It is always useful to look into the past and evaluate how good you were. Go!

Our current task is "Encryption" ( link ).

Step 1. Determine the size of the matrix.

The task defines several conditions for determining the size of the matrix:

• floor(sqrt(L)) <= <= <= ceil(sqrt(L))
• * >= L

If several matrices meet these conditions, we will choose the one that has the minimum area, i.e. * .

We use the sample data in the input and output, provided by the Hackerrank team, for a detailed analysis of the decisions we make. More specifically, the haveaniceday line should output hae and via ecy .

In order to get some kind of basis for manual calculations, let's start with solving the listed 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

Substituting these values ​​into the first condition,

 3 <=   <=   <= 4 

we get the size of the matrix available to us. Let's analyze each of them in ascending order:

• 3 * 3 = 9 - does not satisfy the condition * >= L
• 3 * 4 = 12 - satisfies the condition
• 4 * 4 = 16 - satisfies the condition, but occupies a larger area than the previous version

Based on the knowledge gained, we will write down our solution to the first step:

 1.   =   = floor(sqrt(L)) 2.    *   < L    = ceil(sqrt(L)) 3.    *   < L    = ceil(sqrt(L)) 

And the code itself, written in Go :

 func detectGridSize(l int) (int, int) { s := math.Sqrt(float64(l)) f := int(math.Floor(s)) if f * f >= l { return f, f } c := int(math.Ceil(s)) if f * c >= l { return f, c } return c, c } 

Step 2. Fill in the matrix

Using the values ​​obtained ( = 3 and = 4 ), we display our original row in the form of a matrix:

 have anic eday 

Filling the matrix is ​​quite simple:

 1.  i  0    2.  j  0    3.  i*N+j ,   ,   S[i*N+j]  G[i][j] 

And the code on Go:

 func populateGrid(g [][]byte, s string) { for i := range g { for j := range g[i] { if k := i * len(g[i]) + j; k < len(s) { g[i][j] = s[k] } } } } 

Step 3. Display the columns of the matrix

The rest of the task is the output to the screen the result of the resulting matrix. We build a word from the first column, then a space, then a word from the second column, and so on:

 1.  j  0    2.  i  0    3.   G[i][j] ,   G[i][j] 4.  " " 

Code:

 func printGridColumns(g [][]byte) { for j := range g[0] { for i := range g { if (g[i][j] != 0) { fmt.Print(string(g[i][j])) } } fmt.Print(" ") } } 

Putting it all together

 package main import ( "fmt" "math" ) func main() { var s string fmt.Scanln(&s) m, n := detectGridSize(len(s)) g := make([][]byte, m) for i := range g { g[i] = make([]byte, n) } populateGrid(g, s) printGridColumns(g) } func detectGridSize(l int) (int, int) { s := math.Sqrt(float64(l)) f := int(math.Floor(s)) if f * f >= l { return f, f } c := int(math.Ceil(s)) if f * c >= l { return f, c } return c, c } func populateGrid(g [][]byte, s string) { for i := range g { for j := range g[i] { if k := i * len(g[i]) + j; k < len(s) { g[i][j] = s[k] } } } } func printGridColumns(g [][]byte) { for j := range g[0] { for i := range g { if (g[i][j] != 0) { fmt.Print(string(g[i][j])) } } fmt.Print(" ") } } 

What's next?

The solution we received is already passing all test cases prepared by the Hackerrank team. But can we improve it?

It is easy to see how inefficient the last two steps are, where each of them goes through all the elements in the matrix. Do we need to do this twice? Do we need to fill out our matrix? Do we need a matrix at all?

If you answered "No" to all questions - great! And now let's see what an optimized solution looks like:

 package main import ( "fmt" "math" ) func main() { var s string fmt.Scanln(&s) m, n := detectGridSize(len(s)) encodeString(m, n, s) } func detectGridSize(l int) (int, int) { s := math.Sqrt(float64(l)) f := int(math.Floor(s)) if f * f >= l { return f, f } c := int(math.Ceil(s)) if f * c >= l { return f, c } return c, c } func encodeString(m, n int, s string) { for j := 0; j < n; j++ { for i := 0; i < m; i++ { if k := i * n + j; k < len(s) { fmt.Print(string(s[k])) } } fmt.Print(" ") } } 

And we get a solution, almost twice as fast, while “easier” by 16 lines. Isn't that great?