# Orange lecture #3 - The Boggle Game

### 1, Đề bài
- Một từ hợp lệ:
+ Có 4 kí tự chữ cái
+ Có chính xác 2 nguyên âm (bao gồm y)

- Cho 2 bảng 4x4, tìm danh sách các từ chung của 2 bảng này
+ Một từ trong bảng:
* dãy 4 ô phân biệt, 2 ô liên tiếp kề nhau (có đỉnh/cạnh chung)

#### Input:
- Gồm nhiều dataset, mỗi dataset gồm 1 cặp 2 bảng 4x4, các dataset cách nhau bởi 1 dòng trống
- Dòng cuối chứa '#'

#### Output:
- Với mỗi dataset -> in ra danh sách các từ chung tăng dần hoặc 'There are no common words for this pair of boggle boards.'
- Các dataset cách nhau bởi 1 dòng trống

Sample input

D F F B    W A S U
T U G I    B R E T
O K J M    Y A P Q
K M B E    L O Y R

Z W A V    G S F U
U N C O    A H F T
Y T G I    G N A L
H G P M    B O O B

#

Sample output:

There are no common words for this pair of boggle boards.

ANGO
AOGN
GNAO
GOAN
NAOG
NGOA
OANG
OGNA

### 2, Ý tưởng
- Với mỗi array 4x4 -> backtracking tìm tất cả mọi từ trong bảng
+ Xuất phát tại 1/16 vị trí bất kì -> đi tiếp 3 lần: mỗi lần chỉ đi qua ô kề chưa được đánh dấu
-> Lưu lại mọi từ được đánh dấu của 2 bảng và so sánh rồi in ra

### 3, Implementation

# Import STL
import sys

# List of vowels
vowels = 'AEIOUY'

# Count 2 vowels
def countVowels(word):
  count = 0
  for letter in word:
    if letter in vowels:
      count += 1
  return count == 2

# Find words of length 4 (backtracking)
def findWords(board, cur_row, cur_col, current_word, visited, word_set):
  # Check if the current_word word is a PigEwu word
  if len(current_word) == 4:
    if countVowels(current_word):
      word_set.add(current_word)
    return 
  # If the current_word word is not a PigEwu word yet
  visited[cur_row][cur_col] = True

  for i in range(8):
    new_row = cur_row + dX[i]
    new_col = cur_col + dY[i]
    if new_row >= 0 and new_row < 4 and new_col >= 0 and new_col < 4:
      if not visited[new_row][new_col]:
        new_word = current_word + board[new_row][new_col]
        findWords(board, new_row, new_col, new_word, visited, word_set)

  visited[cur_row][cur_col] = False # backtracking

# Main
if __name__ == '__main__':
  start = True
  iTest = 0
  while True:
    # Read the input
    a = [['A'] * 4 for _ in range(4)] # Board A
    b = [['A'] * 4 for _ in range(4)] # Board B

    for i in range(4):
      S = input().split()
      # Loop condition
      if(len(S) <= 1):
        sys.exit()
      for j in range(4):
        a[i][j] = S[j]
      for j in range(4, 8):
        b[i][j - 4] = S[j]

    dX = [-1,-1,-1,0,0,1,1,1]
    dY = [-1,0,1,-1,1,-1,0,1]

    visited = [[False] * 4 for _ in range(4)]

    # Find all PigEwu words
    setA = set() # all words word_set in set A
    setB = set() # all words word_set in set B
    for row in range(4):
      for col in range(4):

# visited[row][col] = True # find all words starting from (row, col)
        findWords(a, row, col, a[row][col], visited, setA)
        findWords(b, row, col, b[row][col], visited, setB)
        # visited[row][col] = False # backtracking
    
    result = [] # all PigEwu words appearing in both sets
    for word in setB:
      if(word in setA):
        result.append(word)

    # Print the resultult
    iTest += 1
    if(iTest > 1): print()
    
    if(len(result) <= 0):
      print('There are no common words for this pair of boggle boards.')
    else:
      result.sort()
      for word in result:
        print(word)
        
    input()

### 4, Độ phức tạp:
- Với mỗi bảng:
+ Mỗi từ: kí tự thứ nhất có 16 cách chọn, kí tự thứ hai có 7 cách chọn, kí tự thứ ba/bốn có 7 cách chọn
=> Tối đa: 16 * 7^3 từ = W
=> Lưu vào set (hash table)/kiểm tra tồn tại trong set trong O(1) => O(W)

+ Sort lại các từ trong O(WlogW)

=> Toàn bộ: O(T * WlogW)