Today I was looking into the following problem for word counter in python from Hack Bulgaria:

*You are given a rectangular table filled with characters and a word. Your task is to count the occurrences of the word in the table. The word can be found horizontally, vertically and across both left to right and right to left.*

As you see in the picture, you have to look for the word in 8 directions – two diagonals, once per line and once per row, left to right and right to left. Which is pretty much coding, if you start doing it like this. So, I was thinking what a good programmer should do. Then I have decided that a good programmer would outsource it, so I have started to think what a mediocre programmer would do. Thus, I have decided that I actually need not more than 4 operations – I do not need to look for left to right and right to left separately, but I can reverse the word and look the reversed word as well.

After understanding this, I have tought of reversing the matrix in a way that the rows become columns and columns become rows. Thus, I can do two types of search with one function. With the diagonals, I have used something similar – mirroring the matrix and repeating the search in the mirrored matrix. Thus, with 2 procedures I have managed to do the 8 searches in a good way! 🙂

So far so good, here comes the code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
def calculate_in_matrix(columns, lines, word, word_reversed, list_matrix): current_result = 0 difference_in_lines = columns - len(word) + 1 if difference_in_lines: for i in range (0, lines): for k in range (0, difference_in_lines): test_result = list_matrix[i] test_result = "".join(test_result[k:k+len(word_as_list)]) if test_result == word or test_result == word_reversed: current_result += 1 return current_result def mirror_matrix(list_matrix): reversed_matrix = [] for line in list_matrix: reversed_matrix.append(line[::-1]) return reversed_matrix def calculate_in_diagonals(columns, lines, word, word_reversed, list_matrix): current_result = 0 difference_in_lines = lines - word_size + 1 difference_in_columns = columns - word_size + 1 for p in range(0, difference_in_columns): matrix = [row[p:] for row in list_matrix] for i in range(0, difference_in_lines): diagonal_word = "" for m in range(0+i, word_size+i): for k in range(0,word_size): if m-i == k: diagonal_word += matrix[m][k] if diagonal_word == word or diagonal_word == word_reversed: current_result += 1 return current_result word = input() word_size = len(word) word_reversed = word[::-1] word_as_list = list(word) size_matrix = list(map(int, input().split())) lines = size_matrix[0] columns = size_matrix[1] list_matrix = [] for i in range(0, lines): list_matrix.append(list(input().split())) result = 0 #check horizontal lines >>>> result += calculate_in_matrix(columns,lines, word, word_reversed, list_matrix) #reversing matrix list_matrix_reversed = [[list_matrix[j][i] for j in range(len(list_matrix))] for i in range(len(list_matrix[0]))] #check vertical lines vvvv result += calculate_in_matrix(lines, columns, word, word_reversed, list_matrix_reversed) result += calculate_in_diagonals(columns, lines, word, word_reversed, list_matrix) list_matrix = mirror_matrix(list_matrix) result += calculate_in_diagonals(columns, lines, word, word_reversed, list_matrix) print(result) |

Enjoy it!