#!/usr/bin/env python # coding: utf-8 # # Using Python to solve Regexp CrossWord Puzzles # # Have a look at the amazing website. # # I played during about two hours, and could manually solve almost all problems, quite easily for most of them. # But then I got stucked on [this one](https://regexcrossword.com/challenges/volapuk/puzzles/5). # # Soooooo. I want to use [Python3](https://docs.python.org/3/) [regular expressions](https://docs.python.org/3/library/re.html) and try to solve any such cross-word puzzles. # # **Warning:** This notebook will *not* explain the concept and syntax of regular expressions, go read on about it on Wikipedia or in a good book. The Python documentation gives a nice introduction [here](https://docs.python.org/3/howto/regex.html#regex-howto). # # - Author: [Lilian Besson](https://besson.link) ([@Naereen](https://GitHub.com/Naereen)) ; # - License: [MIT License](https://lbesson.mit-license.org/) ; # - Date: 28-02-2021. # ## Representation of a problem # # Here is a screenshot from the game webpage. # # ![](Using_Python_to_solve_Regexp_CrossWord_Puzzles_1.png) # # As you can see, an instance of this game is determined by its rectangular size, let's denote it $(m, n)$, so here there are $m=5$ lines and $n=5$ columns. # # I'll also use this [easy problem](https://regexcrossword.com/challenges/beginner/puzzles/1): # # ![](Using_Python_to_solve_Regexp_CrossWord_Puzzles_2.png) # # Let's define both, in a small dictionnary containing two to four lists of regexps. # ### Easy problem of size $(2,2)$ with four constraints # In[1]: problem1 = { "left_lines": [ r"HE|LL|O+", # HE|LL|O+ line 1 r"[PLEASE]+", # [PLEASE]+ line 2 ], "right_lines": None, "top_columns": [ r"[^SPEAK]+", # [^SPEAK]+ column 1 r"EP|IP|EF", # EP|IP|EF column 2 ], "bottom_columns": None, } # The keys `"right_lines"` and `"bottom_columns"` can be empty, as for easier problems there are no constraints on the right and bottom. # Each line and column (but not each square) contains a regular expression, on a common alphabet of letters and symbols. # Let's write $\Sigma$ this alphabet, which in the most general case is $\Sigma=\{$ `A`, `B`, ..., `Z`, `0`, ..., `9`, `:`, `?`, `.`, `$`, `-`$\}$. # For the first beginner problem, the alphabet can be shorten: # In[2]: alphabet1 = { 'H', 'E', 'L', 'O', 'P', 'L', 'E', 'A', 'S', 'E', 'S', 'P', 'E', 'A', 'K', 'E', 'P', 'I', 'P', 'I', 'F', } print(f"alphabet1 = \n{sorted(alphabet1)}") # ### Difficult problem of size $(5,5)$ with 20 constraints # Defining the [second problem](https://regexcrossword.com/challenges/volapuk/puzzles/5) is just a question of more copy-pasting: # In[3]: problem2 = { "left_lines": [ r"(N3|TRA|N7)+", # left line 1 r"[1LOVE2?4]+.", # left line 2 r"(A|D)M[5-8$L]+", # left line 3 r"[^\s0ILAD]+", # left line 4 r"[B-E]+(.)\1.", # left line 5 ], "right_lines": [ r"[^OLD\s]+", # right line 1 r"(\d+)[LA\s$?]+", # right line 2 r"(\-P|5\$|AM|Z|L)+", # right line 3 r"(\-D|\-WE)+[^L4-9N$?]+", # right line 4 r"[FED$?]+", # right line 5 ], "top_columns": [ r"[2TAIL\-D]+", # top column 1 r"(WE|R4|RY|M)+", # top column 2 r"[FEAL3-5S]+", # top column 3 r"[^FA\sT1-2]+F", # top column 4 r"[LO\s\?5-8]+", # top column 5 ], "bottom_columns": [ r"[^ILYO]+", # top column 1 r".+[MURDEW]+", # top column 2 r"[1ALF5$E\s]+", # top column 3 r"[\dFAN$?]+", # top column 4 r".+\s.+\?", # top column 5 ], } # And its alphabet: # In[4]: import string # In[5]: alphabet2 = set(string.digits) | set(string.ascii_uppercase) | { ':', '?', '.', '$', '-', ' ' } print(f"alphabet2 = \n{sorted(alphabet2)}") # ### An intermediate problem of size $(3,3)$ with 12 constraints # Defining the [third problem](https://regexcrossword.com/challenges/doublecross/puzzles/3) is just a question of more copy-pasting: # In[6]: problem3 = { "left_lines": [ r"[ONE]*[SKA]", # left line 1 r".*(RE|ER)", # left line 2 r"A+[TUB]*", # left line 3 ], "right_lines": [ r".*(O|S)*", # right line 1 r"[^GOA]*", # right line 2 r"[STUPA]+", # right line 3 ], "top_columns": [ r".*[GAF]*", # top column 1 r"(P|ET|O|TEA)*", # top column 2 r"[RUSH]+", # top column 3 ], "bottom_columns": [ r"(NF|FA|A|FN)+", # top column 1 r".*(A|E|I).*", # top column 2 r"[SUPER]*", # top column 3 ], } # And its alphabet: # In[7]: alphabet3 = { 'O', 'N', 'E', 'S', 'K', 'A', 'R', 'E', 'E', 'R', 'A', 'T', 'U', 'B', 'O', 'S', 'G', 'O', 'A', 'S', 'T', 'U', 'P', 'A', 'G', 'A', 'F', 'P', 'E', 'T', 'O', 'T', 'E', 'A', 'R', 'U', 'S', 'H', 'N', 'F', 'F', 'A', 'A', 'F', 'N', 'A', 'E', 'I', 'S', 'U', 'P', 'E', 'R', } print(f"alphabet3 = \n{sorted(alphabet3)}") # ### A few useful functions # # Let's first extract the dimension of a problem: # In[8]: from typing import Tuple, Dict, List, Set, Any, Union def dimension_problem(problem: dict) -> Tuple[int, int]: m = len(problem['left_lines']) if problem['right_lines'] is not None: assert m == len(problem['right_lines']) n = len(problem['top_columns']) if problem['bottom_columns'] is not None: assert n == len(problem['bottom_columns']) return (m, n) # In[9]: problem1 # In[10]: dimension_problem(problem1) # Now let's write a representation of a grid, a solution (or partial solution) of a problem: # In[11]: ___ = "_" # represents an empty answer, as _ is not in the alphabet grid1_partial = [ [ 'H', ___ ], [ ___, 'P' ], ] # In[12]: grid1_solution = [ [ 'H', 'E' ], [ 'L', 'P' ], ] # As well as a few complete grids which are NOT solutions # In[13]: grid1_wrong1 = [ [ 'H', 'E' ], [ 'L', 'F' ], ] # In[14]: grid1_wrong2 = [ [ 'H', 'E' ], [ 'E', 'P' ], ] # In[15]: grid1_wrong3 = [ [ 'H', 'E' ], [ 'O', 'F' ], ] # In[16]: grid1_wrong4 = [ [ 'O', 'E' ], [ 'O', 'F' ], ] # We also write these short functions to extract the $i$-th line or $j$-th column: # In[17]: def nth_line(grid: List[List[str]], line: int) -> str: return "".join(grid[line]) def nth_column(grid: List[List[str]], column: int) -> str: return "".join(grid[line][column] for line in range(len(grid))) # In[18]: [ nth_line(grid1_solution, line) for line in range(len(grid1_solution)) ] # In[19]: [ nth_column(grid1_solution, column) for column in range(len(grid1_solution[0])) ] # A partial solution for the intermediate problem: # In[20]: ___ = "_" # represents an empty answer, as _ is not in the alphabet grid3_solution = [ [ 'N', 'O', 'S' ], [ 'F', 'E', 'R' ], [ 'A', 'T', 'U' ], ] # And a partial solution for the harder problem: # In[21]: ___ = "_" # represents an empty answer, as _ is not in the alphabet grid2_partial = [ [ 'T', 'R', 'A', 'N', '7' ], [ '2', '4', ___, ___, ' ' ], [ 'A', ___, ___, ___, ___ ], [ '-', ___, ___, ___, ___ ], [ 'D', ___, ___, ___, '?' ], ] # Let's extract the dimension of a grid, just to check it: # In[22]: def dimension_grid(grid: List[List[str]]) -> Tuple[int, int]: m = len(grid) n = len(grid[0]) assert all(n == len(grid[i]) for i in range(1, m)) return (m, n) # In[23]: print(f"Grid grid1_partial has dimension: {dimension_grid(grid1_partial)}") print(f"Grid grid1_solution has dimension: {dimension_grid(grid1_solution)}") # In[24]: print(f"Grid grid2_partial has dimension: {dimension_grid(grid2_partial)}") # In[25]: def check_dimensions(problem: dict, grid: List[List[int]]) -> bool: return dimension_problem(problem) == dimension_grid(grid) # In[26]: assert check_dimensions(problem1, grid1_partial) assert check_dimensions(problem1, grid1_solution) # In[27]: assert not check_dimensions(problem2, grid1_partial) # In[28]: assert check_dimensions(problem2, grid2_partial) # In[29]: assert not check_dimensions(problem1, grid2_partial) # ### Two more checks # # We also have to check if a word is in an alphabet: # In[30]: def check_alphabet(alphabet: Set[str], word: str, debug: bool=True) -> bool: result = True for i, letter in enumerate(word): new_result = letter in alphabet if debug and result and not new_result: print(f"The word {repr(word)} is not in alphabet {repr(alphabet)}, as its #{i}th letter {letter} is not present.") result = result and new_result return result # In[31]: assert check_alphabet(alphabet1, 'H' 'E') # concatenate the strings # In[32]: assert check_alphabet(alphabet1, 'H' 'E') assert check_alphabet(alphabet1, 'L' 'P') assert check_alphabet(alphabet1, 'H' 'L') assert check_alphabet(alphabet1, 'E' 'P') # In[33]: assert check_alphabet(alphabet2, "TRAN7") # And also check that a word matches a regexp: # In[34]: import re # As the [documentation](https://docs.python.org/3/library/re.html#re.compile) explains it: # # > but using `prog = re.compile(regepx)` and saving the resulting regular expression object `prog` for reuse is more efficient when the expression will be used several times in a single program. # # I don't want to have to think about compiling a regexp before using it, so... I'm gonna memoize them! # In[42]: memory_of_compiled_regexps = dict() # Now we are ready to write our "smart" match function: # In[43]: def match(regexp: str, word: str, debug: bool=True) -> bool: global memory_of_compiled_regexps if regexp not in memory_of_compiled_regexps: prog = re.compile(regexp) memory_of_compiled_regexps[regexp] = prog print(f"For the first time seeing this regexp {repr(regexp)}, compiling it and storing in memory_of_compiled_regexps, now of size {len(memory_of_compiled_regexps)}.") else: prog = memory_of_compiled_regexps[regexp] # XXX This is slow! # result = re.fullmatch(regexp, word) # DONE This is faster! result = prog.fullmatch(word) entire_match = result is not None if debug: if entire_match: print(f"The word {repr(word)} is matched by {repr(regexp)}") else: print(f"The word {repr(word)} is NOT matched by {repr(regexp)}") return entire_match # Let's compare the time of the first match and next ones: # In[44]: match(r"(N3|TRA|N7)+", "TRAN7") # In[45]: match(r"(N3|TRA|N7)+", "TRAN8") # Well of course it's not different for tiny test like this. # In[ ]: match(r"(N3|TRA|N7)+", "") # In[ ]: match(r"(N3|TRA|N7)+", "TRA") # That should be enough to start the first "easy" task. # In[47]: match(r"(N3|TRA|N7)+", "TRA", debug=False) re.fullmatch(r"(N3|TRA|N7)+", "TRA") # We can see that our "memoization trick" indeed helped to speed-up the time required to check a regexp, by about a factor 2, even for very small tests like this. # ## First easy task: check that a line/column word validate its contraints # # Given a problem $P$ of dimension $(m, n)$, its alphabet $\Sigma$, a position $i \in [| 0, m-1 |]$ of a line or $j \times [|0, n-1 |]$ of a column, and a word $w \in \Sigma^k$ (with $k=m$ for line or $k=n$ for column), I want to write a function that checks the validity of each (left/right) line, or (top/bottom) constraints. # # To ease debugging, and in the goal of using this Python program to improve my skills in solving such puzzles, I don't want this function to just reply `True` or `False`, but to also print for each constraints if it is satisfied or not. # # **Bonus:** for each regexp contraint, highlight the parts which corresponded to each letter of the word? # ### For lines # We are ready to check the one or two constraints of a line. # The same function will be written for columns, just below. # In[48]: def check_line(problem: dict, alphabet: Set[str], word: str, position: int, debug: bool=True, early: bool=False) -> bool: if not check_alphabet(alphabet, word, debug=debug): return False m, n = dimension_problem(problem) if len(word) != n: if debug: print(f"Word {repr(word)} does not have correct size n = {n} for lines") return False assert 0 <= position < m constraints = [] if "left_lines" in problem and problem["left_lines"] is not None: constraints += [ problem["left_lines"][position] ] if "right_lines" in problem and problem["right_lines"] is not None: constraints += [ problem["right_lines"][position] ] # okay we have one or two constraint for this line, assert len(constraints) in {1, 2} # let's check them! result = True for cnb, constraint in enumerate(constraints): if debug: print(f"For line constraint #{cnb} {repr(constraint)}:") new_result = match(constraint, word, debug=debug) if early and not new_result: return False result = result and new_result return result # Let's try it! # In[49]: print(problem1, alphabet1, grid1_solution) # In[50]: n, m = dimension_problem(problem1) for line in range(n): word = nth_line(grid1_solution, line) print(f"- For line number {line}, checking word {repr(word)}:") result = check_line(problem1, alphabet1, word, line) # In[51]: n, m = dimension_problem(problem1) fake_words = ["OK", "HEY", "NOT", "HELL", "N", "", "HU", "OO", "EA"] for word in fake_words: print(f"# For word {repr(word)}:") for line in range(n): result = check_line(problem1, alphabet1, word, line) print(f" => {result}") # That was long, but it works fine! # In[52]: n, m = dimension_problem(problem2) for line in [0]: word = nth_line(grid2_partial, line) print(f"- For line number {line}, checking word {repr(word)}:") result = check_line(problem2, alphabet2, word, line) print(f" => {result}") # In[53]: n, m = dimension_problem(problem2) fake_words = [ "TRAN8", "N2TRA", # violate first constraint "N3N3N7", "N3N3", "TRA9", # smaller or bigger dimension "O L D", "TRA ", # violate second contraint ] for word in fake_words: for line in [0]: print(f"- For line number {line}, checking word {repr(word)}:") result = check_line(problem2, alphabet2, word, line) print(f" => {result}") # ### For columns # We are ready to check the one or two constraints of a line. # The same function will be written for columns, just below. # In[54]: def check_column(problem: dict, alphabet: Set[str], word: str, position: int, debug: bool=True, early: bool=False) -> bool: if not check_alphabet(alphabet, word, debug=debug): return False m, n = dimension_problem(problem) if len(word) != m: if debug: print(f"Word {repr(word)} does not have correct size n = {n} for columns") return False assert 0 <= position < n constraints = [] if "top_columns" in problem and problem["top_columns"] is not None: constraints += [ problem["top_columns"][position] ] if "bottom_columns" in problem and problem["bottom_columns"] is not None: constraints += [ problem["bottom_columns"][position] ] # okay we have one or two constraint for this column, assert len(constraints) in {1, 2} # let's check them! result = True for cnb, constraint in enumerate(constraints): if debug: print(f"For column constraint #{cnb} {repr(constraint)}:") new_result = match(constraint, word, debug=debug) if early and not new_result: return False result = result and new_result return result # Let's try it! # In[55]: print(problem1, alphabet1, grid1_solution) # In[56]: n, m = dimension_problem(problem1) for column in range(m): word = nth_column(grid1_solution, column) print(f"- For column number {column}, checking word {repr(word)}:") result = check_column(problem1, alphabet1, word, column) print(result) # In[57]: n, m = dimension_problem(problem1) fake_words = ["OK", "HEY", "NOT", "HELL", "N", "", "HU", "OO", "EA"] for word in fake_words: print(f"# For word {repr(word)}:") for column in range(m): result = check_column(problem1, alphabet1, word, column) print(f" => {result}") # That was long, but it works fine! # In[58]: n, m = dimension_problem(problem2) for column in [0]: word = nth_column(grid2_partial, column) print(f"- For column number {column}, checking word {repr(word)}:") result = check_column(problem2, alphabet2, word, column) print(f" => {result}") # In[59]: n, m = dimension_problem(problem2) fake_words = [ "TRAN8", "N2TRA", # violate first constraint "N3N3N7", "N3N3", "TRA9", # smaller or bigger dimension "O L D", "TRA ", # violate second contraint ] for word in fake_words: for line in [0]: print(f"- For line number {line}, checking word {repr(word)}:") result = check_column(problem2, alphabet2, word, line) print(f" => {result}") # ## Second easy task: check that a proposed grid is a valid solution # # I think it's easy, as we just have to use $m$ times the `check_line` and $n$ times the `check_column` functions. # In[60]: def check_grid(problem: dict, alphabet: Set[str], grid: List[List[str]], debug: bool=True, early: bool=False) -> bool: m, n = dimension_problem(problem) ok_lines = [False] * m for line in range(m): word = nth_line(grid, line) ok_lines[line] = check_line(problem, alphabet, word, line, debug=debug, early=early) ok_columns = [False] * n for column in range(n): word = nth_column(grid, column) ok_columns[column] = check_column(problem, alphabet, word, column, debug=debug, early=early) # TODO: of course we could be more efficient than computing all the bool and taking all(...), by doing early stopping # Worst case stays O(n + m) so I don't care return all(ok_lines) and all(ok_columns) # Let's try it! # ### For the easy problem # For a partial grid, of course it's going to be invalid just because `'_'` is *not* in the alphabet $\Sigma$. # In[61]: check_grid(problem1, alphabet1, grid1_partial) # For a complete grid, let's check that our solution is valid: # In[62]: check_grid(problem1, alphabet1, grid1_solution) # And let's also check that the few wrong solutions are indeed not valid: # In[63]: check_grid(problem1, alphabet1, grid1_wrong1) # In[64]: check_grid(problem1, alphabet1, grid1_wrong2) # In[65]: check_grid(problem1, alphabet1, grid1_wrong3) # In[66]: check_grid(problem1, alphabet1, grid1_wrong4) # We can see that for each wrong grid, at least one of the contraint is violated! # # That's pretty good! # ### For the intermediate problem # # My solution for the intermediate problem `problem3` is indeed valid: # # ![](Using_Python_to_solve_Regexp_CrossWord_Puzzles_3.png) # In[67]: check_grid(problem3, alphabet3, grid3_solution) # ### For the hard problem # # Well I don't have a solution yet, so I cannot check it! # ## Third easy task: generate all words of a given size in the alphabet # # Using [`itertools.product`](https://docs.python.org/3/library/itertools.html#itertools.product) and the alphabet defined above, it's going to be easy. # # Note that I'll first try with a smaller alphabet, to check the result (for problem 1). # In[68]: import itertools # In[69]: from typing import Generator def all_words_of_alphabet(alphabet: Union[List[str], Set[str]], size: int) -> Generator: yield from itertools.product(alphabet, repeat=size) # Just a quick check: # In[70]: list(all_words_of_alphabet(['0', '1'], 3)) # The time and memory complexity of this function should be $\mathcal{O}(|\Sigma|^k)$ for words of size $k\in\mathbb{N}^*$. # In[71]: alphabet0 = ['0', '1'] len_alphabet = len(alphabet0) for k in [2, 3, 4, 5]: print(f"Generating {len_alphabet**k} words of size = {k} takes about") list(all_words_of_alphabet(alphabet0, k)) # In[72]: list(all_words_of_alphabet(['0', '1', '2', '3'], 10)) # We can quickly check that even for the larger alphabet of size ~40, it's quite quick for small words of length $\leq 5$: # In[73]: len_alphabet = len(alphabet1) for k in [2, 3, 4, 5]: print(f"Generating {len_alphabet**k} words of size = {k} takes about") list(all_words_of_alphabet(alphabet1, k)) # In[74]: # len_alphabet = len(alphabet2) # for k in [2, 3, 4, 5]: # print(f"Generating {len_alphabet**k} words of size = {k} takes about") # list(all_words_of_alphabet(alphabet2, k)) # Who, it takes 12 seconds to just *generate* all the possible words for the largest problem (which is just of size $(5,5)$)... # # I'm afraid that my naive approach to solve the puzzle will be VERY slow... # ## Fourth easy task: generate all grids of a given size # In[75]: def all_grids_of_alphabet(alphabet: Union[List[str], Set[str]], lines: int, columns: int) -> Generator: all_words = list(itertools.product(alphabet, repeat=columns)) all_words = [ "".join(words) for words in all_words ] all_grids = itertools.product(all_words, repeat=lines) for pre_tr_grid in all_grids: tr_grid = [ [ pre_tr_grid[line][column] for line in range(lines) ] for column in range(columns) ] yield tr_grid # In[76]: for alphabet in ( ['0', '1'], ['T', 'A', 'C', 'G'] ): for (n, m) in [ (1, 1), (2, 2), (1, 2), (2, 1), (3, 3), (3, 2), (2, 3) ]: assert len(list(all_grids_of_alphabet(alphabet, n, m))) == len(alphabet)**(n*m) print(list(all_grids_of_alphabet(alphabet0, n, m))[0]) print(list(all_grids_of_alphabet(alphabet0, n, m))[-1]) # In[77]: print(f"For the alphabet {alphabet0} of size = {len(alphabet0)} :") for (n, m) in [ (1, 1), (2, 1), (1, 2), (2, 2) ]: all_these_grids = list(all_grids_of_alphabet(alphabet0, n, m)) print(f"For (n, m) = {(n, m)} the number of grids is {len(all_these_grids)}") # ### How long does it take and how many grids for the easy problem? # In[78]: print(f"For the alphabet {alphabet1} of size = {len(alphabet1)} :") for (n, m) in [ (1, 1), (2, 1), (1, 2), (2, 2) ]: all_these_grids = list(all_grids_of_alphabet(alphabet1, n, m)) print(f"For (n, m) = {(n, m)} the number of grids is {len(all_these_grids)}") # That's still pretty small and fast! # ### How long does it take and how many grids for the hard problem? # In[79]: print(f"For the alphabet {alphabet2} of size = {len(alphabet2)} :") for (n, m) in [ (1, 1), (2, 1), (1, 2), (2, 2) ]: all_these_grids = list(all_grids_of_alphabet(alphabet2, n, m)) print(f"For (n, m) = {(n, m)} the number of grids is {len(all_these_grids)}") # In[80]: 41**(2*3) # Just for $(n, m) = (2, 2)$ it takes about 7 seconds... # So to scale for $(n, m) = (5, 5)$ would just take... WAY TOO MUCH TIME! # In[81]: n, m = 5, 5 41**(5*5) # In[82]: import math # In[83]: math.log10(41**(5*5)) # For a grid of size $(5,5)$, the number of different possible grids is about $10^{40}$, that is CRAZY large, we have no hope of solving this problem with a brute force approach. # # How much time would that require, just to generate the grids? # In[84]: s = 7 estimate_of_running_time = 7*s * len(alphabet1)**(5*5) / len(alphabet1)**(2*2) estimate_of_running_time # in seconds # This rough estimate gives about $5 * 10^{22}$ seconds, about $10^{15}$ years, so about a million of billion years ! # In[85]: math.log10( estimate_of_running_time / (60*60*24*365) ) # ## First difficult task: for each possible grid, check if its valid # In[91]: def naive_solve(problem: dict, alphabet: Union[List[str], Set[str]], debug: bool=False, early: bool=True) -> List[List[List[str]]]: n, m = dimension_problem(problem) good_grids = [] for possible_grid in all_grids_of_alphabet(alphabet, n, m): is_good_grid = check_grid(problem, alphabet, possible_grid, debug=debug, early=early) if is_good_grid: if early: return [ possible_grid ] good_grids.append(possible_grid) return good_grids # Let's try it! # ### Solving the easy problem # Let's check that we can quickly find *one* solution: # In[92]: good_grids1 = naive_solve(problem1, alphabet1, debug=False, early=True) print(f"For problem 1\\n{problem1}\\nOn alphabet\{alphabet1}\\n==> We found one solution:\\n{good_grids1}") # Then can we find more solutions? # In[93]: good_grids1 = naive_solve(problem1, alphabet1, debug=False, early=False) print(f"For problem 1\\n{problem1}\\nOn alphabet\{alphabet1}\\n==> We found these solutions:\\n{good_grids1}") # No there is indeed a unique solution here for the first "easy" problem! # ### Solving the intermediate problem # In[261]: # good_grids3 = naive_solve(problem3, alphabet3, debug=False, early=True) # print(f"For problem 3\\n{problem3}\\nOn alphabet\{alphabet3}\\n==> We found one solution:\\n{good_grids3}") # That was so long... # # I could try to use Pypy3 IPython kernel, to speed things up? # # > Yes it's possible to use a Pypy kernel from your regular Python notebook! # > See # ### Solving the hard problem # # Most probably, it will run forever if I use the naive approach of: # # - generate all grids of $m$ words of size $n$ in given alphabet $\Sigma$ ; # - for all grid: # + test it using naive algorithm # + if it's valid: adds it to the list of good grids # # There are $|\Sigma|^{n \times m}$ possible grids, so this approach is doubly exponential in $n$ for square grids. # # I must think of a better approach... # Being just exponential in $\max(m, n)$ would imply that it's practical for the harder problem of size $(5,5)$. # In[192]: # good_grids2 = naive_solve(problem2, alphabet2, debug=False, early=True) # print(f"For problem 2\\n{problem2}\\nOn alphabet\{alphabet2}\\n==> We found one solution:\\n{good_grids2}") # My first idea was to try to tackle each constraint independently, and generate the set of words that satisfy this contraint. (by naively checking `check(constraint, word)` for each word in $\Sigma^n$ or $\Sigma^m$). # # - if there are two line constraints (left/right), get the intersection of the two sets of words; # - then, *for each* line we have a set of possible words: # + we can build each column, and then check that the top/bottom constraint is valid or not # + if valid, continue to next column until the last # + if all columns are valid, then these lines/columns form a possible grid! # + (if we want only one solution, stop now, otherwise continue) # ## Second difficult task: a more efficient approach to solve any problem # In[94]: n, m = dimension_problem(problem1) # In[95]: problem1 # In[96]: alphabet1 # In[97]: len(list(all_words_of_alphabet(alphabet1, n))) # In[98]: ["".join(word) for word in list(all_words_of_alphabet(alphabet1, n))][:10] # In[99]: [ [ "".join(word) for word in all_words_of_alphabet(alphabet1, n) if check_line(problem1, alphabet1, "".join(word), line, debug=False, early=True) ] for line in range(m) ] # In[100]: [ [ "".join(word) for word in all_words_of_alphabet(alphabet1, m) if check_column(problem1, alphabet1, "".join(word), column, debug=False, early=True) ] for column in range(n) ] # So let's write this algorithm. # # I'm using a [`tqdm.tqdm()`](https://tqdm.github.io/docs/notebook/) wrapper on the foor loops, to keep an eye on the progress. # In[101]: # from tqdm.notebook import trange, tqdm from tqdm import trange, tqdm # In[102]: def smart_solve(problem: dict, alphabet: Union[List[str], Set[str]], debug: bool=True, early: bool=True) -> List[List[List[str]]]: n, m = dimension_problem(problem) good_grids = [] possible_words_for_lines = [ [ "".join(word) for word in all_words_of_alphabet(alphabet, n) if check_line(problem, alphabet, "".join(word), line, debug=False, early=True) # TODO don't compute this "".join(word) twice? ] for line in range(m) ] number_of_combinations = 1 for line in range(m): number_of_combinations *= len(possible_words_for_lines[line]) print(f"- There are {len(possible_words_for_lines[line])} different words for line #{line}") print(f"=> There are {number_of_combinations} combinations of words for lines #{0}..#{m-1}\n\n") nb_combination = 0 for possible_words in itertools.product(*possible_words_for_lines): nb_combination += 1 percentage = 100 * nb_combination / float(number_of_combinations) if debug: print(f"{percentage:.3g}% Trying possible_words #{nb_combination}/{number_of_combinations}, from line constraints = {possible_words}") column = 0 no_wrong_column = True while no_wrong_column and column < n: word_column = "".join(possible_words[line][column] for line in range(m)) if debug: print(f" For column #{column}, word = {word_column}, checking constraint...") if not check_column(problem, alphabet, word_column, column, debug=False, early=True): # this word is NOT valid for this column, so let's go to the next word if debug: print(f" This word {word_column} is NOT valid for this column {column}, so let's go to the next word") no_wrong_column = False # break: this was failing... broke the outer for-loop and not the inner one column += 1 if no_wrong_column: print(f" These words seemed to satisfy the column constraints!\n{possible_words}") # so all columns are valid! this choice of words is good! possible_grid = [ list(word) for word in possible_words ] print(f"Giving this grid:\n{possible_grid}") # let's check it, just in case (this takes a short time, compared to the rest) is_good_grid = check_grid(problem, alphabet, possible_grid, debug=debug, early=early) if is_good_grid: if early: return [ possible_grid ] good_grids.append(possible_grid) # after the outer for loop on possible_words return good_grids # And let's try it: # ### For the easy problem # In[103]: print(grid1_solution) # In[104]: good_grids1 = smart_solve(problem1, alphabet1) print("Solution good_grids1 =", good_grids1) # So it worked! # # ๐Ÿš€ It was also *BLAZING* fast compared to the naive approach: 160ms against about 900ยตs, almost a 160x speed-up factor! # # ๐Ÿค” *I don't understand why it's so slow now* I did get a time of 900 ยตs at first try, now it's about 90 ms... just a 2x spee-up factor. # # Let's try for the harder problem! # ### For the intermediate problem # In[106]: import time before = time.time() print(f"\n\n\n\nFiding solution for problem3 = {problem3} on alphabet = {alphabet3}...") good_grids3 = smart_solve(problem3, alphabet3) print(f"Solution good_grids3 = {good_grids3}") after = time.time() delta_time = after - before print(f"Found this solution for problem3 in about {delta_time} seconds.") # ๐Ÿš€ It was also *BLAZING* fast compared to the naive approach: 90ms, when the naive approach was just too long that I killed it... # ### For the harder problem # In[ ]: before = time.time() print(f"\n\n\n\nFiding solution for problem2 = {problem2} on alphabet = {alphabet2}...") good_grids2 = smart_solve(problem2, alphabet2) print(f"Solution good_grids2 = {good_grids2}") after = time.time() delta_time = after - before print(f"Found this solution for problem2 in about {delta_time} seconds.") # It made my kernel restart... # ## Improve the solution - TODO # # > If you're extra curious about this puzzle problem, and my experiments, you can continue from here and finish these ideas: # # - It could be great if it were be possible to give a partially filled grid, and start from there. # # - It could also be great to just be able to fill *one* cell in the grid, in case you're blocked and want some hint. # ## My feeling about these problems and my solutions # # I could have tried to be more efficient, but I didn't have much time to spend on this. # ## Conclusion # # That was nice! Writing this notebook took about 4.5 hours entirely, from first idea to final edit, on Sunday 28th of February, 2021. (note that I was also cooking my [pancakes](https://perso.crans.org/besson/cuisine/pancakes.html) during the first half, so I wasn't intensely coding) # # Have a look at [my other notebooks](https://GitHub.com/Naereen/notebooks/).