"The Grid Search" auf HackerRank mit R Sprache

Question

Ich habe ein paar Tage auf einem pretty simple problem auf HackerRank gearbeitet, aber ich bin mit Timeout-Problemen stecken und ich kann meinen Code nicht weiter optimieren.

Das Problem ist das: Gegeben ein 2D-Array von Ziffern (Dimensionen R * C), versuchen Sie das Auftreten eines gegebenen 2D-Muster von Ziffern (Dimensionen r * c) zu finden.

Hier sind Sie ein reproduzierbares Beispiel von Variablen:

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

Es ist irgendwie ein Regex Problem, aber in 2D, und das ist etwas, das ich nicht überall als ready-to-use-Funktion finden konnte, in R. Es gibt ein paar Eckfälle, mit denen ich umgehen konnte, die Brute-Force-Option zu vermeiden (die obige Version ist einer jener Fälle, in denen die übliche 'regexp' kläglich das Muster nicht findet) .

Darunter ist mein Code: es funktioniert perfekt in 13 von 15 Fällen, aber es scheitert aus Timeout, wenn es gegen einige Tests mit (zB) R * C = 500 * 500 und r * c = 236 geht * 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") 

Bitte beachten Sie, dass für jeden Test bis zu 5 Fällen sind, und dies ist der Grund, warum mein Code nicht: während sie den Test in 5 Teilen zu brechen arbeiten können, übergibt er die Zeitschwelle, wenn die Fälle sind kombiniert mit großen R C und r c Dimensionen.

Hat jemand eine Idee, wie man die Code-Leistung verbessern kann?

Answer 1

Wenn Sie Ihren Ansatz beibehalten möchten, wäre mein erster Vorschlag, die Zeichenfolgen in numerische Matrizen zu konvertieren, weil substr wahrscheinlich nicht sehr schnell ist.

Sie können weiter ausgefeiltere Matching-Algorithmen verwenden, die die Position für mehr als einen Ort wie die Knuth-Morris-Pratt Algorithm verschieben.

Allerdings sind for Loops in R immer sehr langsam, so dass ich denke, dass der beste Ansatz in dieser Situation tatsächlich ein regulärer Ausdruck wäre. Wenn Sie die Zeilen des großen Rasters zu einer langen Zeichenfolge verketten, ist die Anzahl der Zeichen zwischen den Zeilen des Musters festgelegt. Dies bedeutet, dass Sie etwas tun kann (was, glaube ich, den Testfall löst Sie gab):

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