Вирішуємо завдання Hackerrank — «Encryption» (використовуючи Go)

Пропоную вашій увазі переклад статті Cracking Hackerrank Encryption з сайту sobit.me.

Як любить говорити мій друг: "Кращий спосіб вивчити мову програмування — почати писати на ньому алгоритми". Звичайно, це не зробить нікого експертом мови, але є велика ймовірність зустріти більшість структур даних і відчути міць унікальних конструкцій мови.

Є багато хороших ресурсів для починання, але я віддаю перевагу проводити вільний час на Hackerrank. Він безкоштовний, має приємний інтерфейс і солідний набір алгоритмічних проблем, зручно розбиті на категорії та рівні складності.

Після вирішення кожної проблеми, найчастіше частина з аналізом рішення йде в відро. І це навело мене на думку записувати хід думок у формі статей в блозі. Завжди корисно подивитися в минуле і оцінити, наскільки хороший ти був. Поїхали!

Наше сьогоднішнє завдання — "Стандарт" (посилання).

Крок 1. Визначаємо розмір матриці
Завдання визначає кілька критеріїв для визначення розміру матриці:

  • floor(sqrt(L)) <= рядка <= стовпці <= ceil(sqrt(L))
  • рядка * стовпці >= L
Якщо кілька матриць, що відповідають цим умовам, ми виберемо ту, що має мінімальну площу, тобто
кількість рядків * кількість стовпців
.

Скористаємося зразком даних на вході і виході, наданими командою Hackerrank, для докладного розбору прийнятих нами рішень. Більш конкретно, рядок
haveaniceday
має вивести
hae and via ecy
.

Для того, щоб отримати якусь основу для ручних обчислень, почнемо з вирішення перелічених умов:

  • L = len("haveaniceday") = 12
  • sqrt(L) = sqrt(12) = 3.46
  • floor(sqrt(L)) = floor(3.46) = 3
  • ceil(sqrt(L)) = ceil(3.46) = 4
Підставляючи ці значення в перше умова,

3 <= кількість рядків <= кількість стовпців <= 4

отримуємо доступні нам розміри матриці. Проаналізуємо кожен з них в порядку зростання:

  • 3 * 3 = 9
    — не задовольняє умові
    кількість рядків * кількість стовпців >= L
  • 3 * 4 = 12
    — задовольняє умові
  • 4 * 4 = 16
    — задовольняє умові, але займає більшу площу, ніж попередній варіант
На основі отриманих знань, розпишемо наше рішення до першого кроку:

1. кількість рядків = кількість стовпців = floor(sqrt(L))
2. якщо кількість рядків * кількість стовпців < L тоді кількість стовпців = ceil(sqrt(L))
3. якщо кількість рядків * кількість стовпців < L тоді кількість рядків = ceil(sqrt(L))

І сам код, написаний на 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
}

Крок 2. Заповнюємо матрицю
Використовуючи отримані значення (
кількість рядків = 3
and
кількість стовпців = 4
), відобразимо нашу первісну рядок у формі матриці:

hav
ani
ced
ay

Заповнення матриці відбувається досить просто:

1. итерируем i з 0 до кількості рядків
2. итерируем j з 0 до кількості стовпців
3. якщо i*N+j менше, ніж довжина рядка, то присвоїти S[i*N+j] значення G[i][j]

І код на Go:

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

Крок 3. Виводимо стовпці матриці
Частина завдання — виведення на екран результат отриманої матриці. Будуємо слово з першого стовпця, далі пробіл, далі слово з другого стовпця, і так далі:

1. итерируем j з 0 до кількості стовпців
2. итерируем i з 0 до кількості рядків
3. якщо значення G[i][j] встановлено, то виводимо G[i][j]
4. виводимо " "

Код:

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

Збираємо всі разом
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, string s) {
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(" ")
}
}

Що далі?
Отримане нами рішення вже проходить всі контрольні приклади, підготовлені командою Hackerrank. Але чи можемо ми поліпшити його?

Легко помітити, наскільки неефективними останні два кроки, де кожен з них проходиться по всіх елементів в матриці. Чи потрібно нам робити це двічі? Чи нам потрібно заповнювати нашу матрицю? Чи потрібна нам взагалі матриця?

Якщо ви відповіли "Ні" на всі питання — відмінно! А тепер подивимося, як виглядає оптимізоване рішення:

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, int n, string s) {
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(" ")
}
}

І отримуємо рішення, майже вдвічі швидше, при цьому "легше" на 16 рядків. Хіба це не чудово?

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.