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!