fork(1) download
copy 
  1. board3 = [["d","c","e","b","d","e","d","a"],
  2.           ["c","a","e","a","d","d","e","e"],
  3.           ["a","c","r","d","b","i","c","b"],
  4.           ["c","b","a","n","a","r","i","e"],
  5.           ["a","e","d","e","r","i","d","e"],
  6.           ["a","a","a","m","i","a","d","e"],
  7.           ["b","d","n","b","b","b","k","o"],
  8.           ["d","a","e","e","b","e","o","o"],
  9.           ["b","b","c","a","b","b","p","a"],
  10.           ["a","c","b","a","c","a","d","d"]]
  11.  
  12.  
  13. class MatrixPookHrook:
  14.     def __init__(self, mtx):
  15.         self.mtx = self.prepare_matrix(mtx)
  16.  
  17.     def prepare_matrix(self, mtx):
  18.         out, idx = {}, 0
  19.         for _l, lst in enumerate(mtx):
  20.             for _w, ltr in enumerate(lst):
  21.                 out[idx], out[idx]['letter'] = {}, ltr
  22.                 out[idx]['left'] = (lst[_w-1], idx-1) if _w else None
  23.                 out[idx]['right'] = (lst[_w+1], idx+1) if _w != len(lst)-1 else None
  24.                 out[idx]['up'] = (mtx[_l-1][_w], len(mtx[_l-1])*(_l-1)+_w) if _l else None
  25.                 if _l != len(mtx)-1 and len(mtx[_l+1]) > _w:
  26.                     out[idx]['down'] = (mtx[_l+1][_w], len(mtx[_l])*(_l+1)+_w)
  27.                 else:
  28.                     out[idx]['down'] = None
  29.                 idx += 1
  30.         return out
  31.  
  32.     def find_one_word(self, word, out=None):
  33.         # возвращает индексы матрицы, так если бы матрица была плоским списком
  34.         def rectal_search(word, ltr_idx, mtx_idx, res=[], fork=[]):
  35.             _tmp = self.mtx[mtx_idx]
  36.             if ltr_idx or _tmp['letter'] == word[ltr_idx]:
  37.                 res.append(mtx_idx)
  38.                 ltr_idx += 1
  39.                 if ltr_idx == len(word):
  40.                     return res
  41.                 for r in ('left', 'right', 'up', 'down'):
  42.                     if _tmp[r] and _tmp[r][0] == word[ltr_idx] and _tmp[r][1] not in res:
  43.                         fork.append((ltr_idx, _tmp[r][1]))
  44.                 if fork:
  45.                     ltr_idx, mtx_idx = fork.pop()
  46.                     res = res[:ltr_idx]
  47.                     return rectal_search(word, ltr_idx, mtx_idx, res, fork)
  48.  
  49.         for idx in self.mtx:
  50.             out = rectal_search(word, 0, idx)
  51.             if out:
  52.                 return out
  53.         return None
  54.  
  55.     def find_words(self, word_lst):
  56.         out = []
  57.         for w in words3:
  58.             if self.find_one_word(w):
  59.                 out.append(w)
  60.         return out
  61.  
  62. words3 = ["ab","nariman", "poook", "ededa","d"]
  63.  
  64. mtx = MatrixPookHrook(board3)
  65. #print(mtx.find_one_word("nariman"))
  66. print(mtx.find_words(["ab","nariman", "poook", "ededa","d"]))
Success #stdin #stdout 0.04s 9596KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
['ab', 'nariman', 'poook', 'ededa', 'd']
https://ideone.com/tx38pn
language:
Python 3 (python  3.12)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!