Grid Search (HackerRank) - Python

Question

Я разработчик несколько лет, но я практикую свои навыки работы с алгоритмами.

Я столкнулся с "The Grid Search" в HackerRank, и хотя я мог бы его решить, я хочу знать, подходит ли это для этого.

PS: Я пытаюсь сделать большую часть этого с помощью простых инструкций, разработав целую логику вместо использования предварительно построенных функций. Моя цель - улучшить мою логическую мысль, а не мои знания магических методов языка.

#!/bin/python3 

import sys 


t = int(input().strip()) 
for a0 in range(t): 
    R,C = input().strip().split(' ') 
    R,C = [int(R),int(C)] 
    G = [] 
    G_i = 0 
    for G_i in range(R): 
     G_t = list(input().strip()) 
     G.append(G_t) 
    r,c = input().strip().split(' ') 
    r,c = [int(r),int(c)] 
    P = [] 
    P_i = 0 
    for P_i in range(r): 
     P_t = list(input().strip()) 
     P.append(P_t) 

    mIsEqual = False 

    #For each line of the matrix 
    for a1 in range(0,len(G) - (len(P)-1)): 
     #For each column of the given line 
     for a2 in range(0,len(G[a1]) - (len(P[0])-1)): 
      #If the top left value of the pattern matches the current value of the matrix, try to match it 
      if(P[0][0] == G[a1][a2]): 
       #If the pattern 'fits' horizontally in the matrix, try to match it 
       if(len(P[0]) <= (len(G[a1]) - a2)): 
        #If the pattern 'fits' vertically in the matrix, try to match it 
        if(len(P) <= (len(G) - a1)): 
         #Match every single field of the pattern to the given area of the matrix. 
         for a3 in range(0,len(P)): 
          for a4 in range(0,len(P[0])): 
           #If the fields are equal mIsEqual is true 
           if(P[a3][a4] == G[a3+a1][a4+a2]): 
            mIsEqual = True 
           else: 
           #If the fields are not equal stop matching this area of the matrix. 
            mIsEqual = False 
            break 
          #If one field in a line was not equal, stop matching this area of the matrix. 
          if(mIsEqual == False): 
           break 
        #If, after matching the whole area with the pattern mIsEqual is still true, the pattern is there. 
        if(mIsEqual): 
         break 
     #If the pattern was found in the previous line, no need to keep this going. 
     if(mIsEqual): 
      break 

    if(mIsEqual == True): 
     print("YES") 
    else: 
     print("NO") 

Я ищу какие-либо предложения, чтобы улучшить этот сценарий или, если вы думаете, что это совершенно неправильно, причина, почему это не очень хороший способ сделать это.

Спасибо!

Answer 1

Это лучше на сайте обзора кода.

Ваш алгоритм, как описано, выглядит примерно правильно. Однако было бы легче следовать, если бы вы мысленно поместили вещи в функции. Это также устранит некоторый дублированный код, а также уменьшит, сколько вам нужно написать то же самое как в коде, так и в похвалах.

Сравните то, что вы написали, со следующим непроверенным кодом. Который, по сути, что вы написали только с функциями вспыхнувших и только один комментарий на функцию:

#!/bin/python3 
import sys 


# Read the dimensions then a matrix from stdin 
def read_matrix(): 
    R,C = input().strip().split(' ') 
    R,C = [int(R),int(C)] 
    M = [] 
    M_i = 0 
    for M_i in range(R): 
     M_t = list(input().strip()) 
     M.append(M_t) 
    return M 


# See if P can be found anywhere in G. 
def found_match_in(G, P): 
    for a1 in range(0,len(G) - (len(P)-1)): 
     for a2 in range(0,len(G[a1]) - (len(P[0])-1)): 
      if found_match_at(G, P, a1, a2): 
       return True 
    return False 


# See if P can be found in G at location (a1, a2). 
def found_match_at(G, P, a1, a2): 
    for a3 in range(0,len(P)): 
     for a4 in range(0,len(P[0])): 
      if G[a1+a3][a2+a4] != P[a3][a4]: 
       return False 
    return True 


t = int(input().strip()) 
for a0 in range(t): 
    G = read_matrix() 
    P = read_matrix() 
    if found_match_in(G, P): 
     print "YES" 
    else: 
     print "NO"