[Из песочницы] Решаем задачу Hackerrank — «Encryption» (используя Go)25.02.2016 12:33

Предлагаю вашему вниманию перевод статьи Cracking Hackerrank Encryption с сайта sobit.me.

Как любит говорить мой друг: «Лучший способ изучить язык программирования — начать писать на нем алгоритмы». Конечно, это не сделает никого экспертом языка, но есть большая вероятность встретить большинство структур данных и почувствовать мощь уникальных конструкций языка.

Есть много хороших ресурсов для начинания, но я предпочитаю проводить свободное время на Hackerrank. Он бесплатный, имеет приятный интерфейс и солидный набор алгоритмических проблем, удобно разбитых на категории и уровни сложности.

После решения каждой проблемы, зачастую часть с анализом решения уходит в ведро. И это навело меня на мысль записывать ход мыслей в форме статей в блоге. Всегда полезно посмотреть в прошлое и оценить, насколько хорош ты был. Поехали!

Наша сегодняшняя задача — «Encryption» (ссылка).

Шаг 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, 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]
            }
        }
    }
}

Шаг 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, 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(" ")
    }
}

Что дальше?

Полученное нами решение уже проходит все контрольные примеры, подготовленные командой 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, 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(" ")
    }
}

И получаем решение, почти вдвое быстрее, при этом «легче» на 16 строк. Разве это не прекрасно?