«Поиск сетки» на HackerRank с языком R

Question

Я работаю над файлом pretty simple problem на HackerRank в течение нескольких дней, но я застрял в проблемах с тайм-аутом, и я не могу больше оптимизировать свой код.

Проблема заключается в следующем: Учитывая двумерный массив цифр (размеры R * C), попробуйте найти возникновение данного двумерного шаблона цифр (размеры r * c).

Здесь вы воспроизводимый пример переменных:

pattern <- c("11111", "11111", "11110") 
text <- c("111111111111111", 
"111111111111111", 
"111111011111111", 
"111111111111111", 
"111111111111111") 
R <- 5 
C <- 15 
r <- 3 
c <- 5 

Это своего рода регулярного выражения проблемы, но в 2D, и это то, что я не мог найти где-нибудь в качестве функции готовых к употреблению в R. Есть несколько угловых случаев, с которыми мне удалось справиться, пытаясь избежать опции грубой силы (вышеприведенная версия является одним из тех случаев, когда обычное «регулярное выражение» с трудом удается найти шаблон) ,

Ниже приведен мой код: он отлично подходит для 13 из 15 случаев, но он не работает по причине таймаута, когда он идет против некоторых тестов с (например, R * C = 500 * 500 и r * c = 236 * 208.

RW <- c() 
    pattern2 <- paste0(pattern, collapse = "") 
    RW <- c(rep(NA,(C-c+1)*(R-r+1))) 
    for (v in 1:(C-c+1)) 
    { 
     for (y in 1:(R-r+1)) 
     { 
     RW[(C-c+1)*(y-1)+v] <- paste0(substr(text[y:(y+r-1)],v,c+v-1),collapse="") 
     } 
    } 
    per <- ifelse(pattern %in% RW, result <- "YES",result <- "NO") 
    cat(result, "\n") 

Пожалуйста, обратите внимание, что есть до 5 случаев для каждого теста, и это является причиной, почему мой код не: в то время как она могла бы работать ломать тест на 5 частей, он проходит порог времени, когда случаи вместе с большими R C и r c размеры.

Есть ли у кого-нибудь идеи о том, как улучшить производительность кода?

Answer 1

Если вы хотите сохранить свой подход, моим первым предложением было бы преобразовать строки в числовые матрицы, потому что substr, вероятно, не очень быстро.

Вы также можете использовать более сложные алгоритмы согласования, которые сдвигают положение более чем на одно место, например, Knuth-Morris-Pratt Algorithm.

Однако петли for всегда будут довольно медленными в R, поэтому я считаю, что лучший подход в этой ситуации действительно будет регулярным выражением. Если вы объединяете строки большой сетки в одну длинную строку, число символов между строками шаблона фиксировано. Это означает, что вы можете сделать что-то вроде этого (который, я считаю, решающий тест, вы дали):

grepl(
    paste0(pattern[1], ".{", C - c, ",}", 
      pattern[2], ".{", C - c, "}", 
      pattern[3]), 
    paste0(text, collapse = "") 
    ) 

https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm