Предлагаю вашему вниманию перевод статьи 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 — удовлетворяет условию, но занимает бoльшую площадь, чем предыдущий вариант

На основе полученных знаний, распишем наше решение к первому шагу:

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), отобразим нашу первоначальную строку в форме матрицы:

have
anic
eday

Заполнение матрицы происходит достаточно просто:

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 строк. Разве это не прекрасно?

Комментарии (6)


  1. iCubeDm
    24.02.2016 19:49
    -8

    Скажу так. Меня жутко бесит синтаксис Го. Это моё сугубо личное ИМХО, не для холивара.

    Но! Этот код выглядит мило)))


  1. hellman
    24.02.2016 20:14
    -2

    Вы бы ещё helloworld "проанализировали"


    1. Sobit
      24.02.2016 22:01

      hellman, обязательно постараюсь подобрать проблему по-сложнее в следующий раз!


  1. SpyceR
    25.02.2016 00:26
    +1

    В шаге 2 "матрица" не 3х4 и буквы "e" не хватает


    1. Sobit
      25.02.2016 16:20

      SpyceR, большое спасибо за замечание! И как я такое допустил...


  1. mas
    25.02.2016 22:37

    Жалко там J нет. Потому что такое на J писать — самое то.

    NB. Explicit definition. Can be converted by 13 : '...' -- but it will give lots of [:
    e=: 3 : 'FF-.~,|:'' '',~(c,~>.l%c=.>.%:l=.#t)$!.FF t=.'' ''-.~y'
    
    NB. Tacit definition, step by step
    t=: -.&' '          NB. text: without blanks
    c=: >.@%:@#         NB. number of cols
    d=: (>.@(%~#),[)~c  NB. dimension: rows,cols
    m=: (d $!.FF ])@t   NB. matrix of letters
    w=: ,@|:@(' ',~m)   NB. new words with blanks between them
    h=: FF-.~w          NB. hackerrank encryption
    
    NB. or the same in one line ;)
    h=: FF-.~,@|:@(' ',~(((>.@(%~#),[)~>.@%:@#)$!.FF]))@(-.&' ')
    
    echo (e ,: h) 'if man was meant to stay on the ground god would have given us roots'
    NB.            imtgdvs fearwer mayoogo anouuio ntnnlvt wttddes aohghn sseoau
    
    echo (e ,: h) 'hello dear world!'
    NB.            horl edwd leo! lar

    Для "квадратных" текстов двойное шифрование восстанавливает текст:

    echo h h 'now is the time for all good men'
    NB.  -->  nowis theti mefor allgo odmen