<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Using Python to solve Regexp CrossWord Puzzles
Have a look at the amazing https
Step1:  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, 
Step2:  Difficult problem of size $(5,5)$ with 20 constraints
Defining the second problem is just a question of more copy-pasting
Step3:  And its alphabet
Step4:  An intermediate problem of size $(3,3)$ with 12 constraints
Defining the third problem is just a question of more copy-pasting
Step5:  And its alphabet
Step6:  A few useful functions
Let's first extract the dimension of a problem
Step7:  Now let's write a representation of a grid, a solution (or partial solution) of a problem
Step8:  As well as a few complete grids which are NOT solutions
Step9:  We also write these short functions to extract the $i$-th line or $j$-th column
Step10:  A partial solution for the intermediate problem
Step11:  And a partial solution for the harder problem
Step12:  Let's extract the dimension of a grid, just to check it
Step13:  Two more checks
We also have to check if a word is in an alphabet
Step14:  And also check that a word matches a regexp
Step15:  As the documentation explains it
Step16:  Now we are ready to write our "smart" match function
Step17:  Let's compare the time of the first match and next ones
Step18:  Well of course it's not different for tiny test like this.
Step19:  That should be enough to start the first "easy" task.
Step20:  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
Step21:  Let's try it!
Step22:  That was long, but it works fine!
Step23:  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.
Step24:  Let's try it!
Step25:  That was long, but it works fine!
Step26:  Second easy task
Step27:  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$.
Step28:  For a complete grid, let's check that our solution is valid
Step29:  And let's also check that the few wrong solutions are indeed not valid
Step30:  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
Step31:  For the hard problem
Well I don't have a solution yet, so I cannot check it!
Third easy task
Step32:  Just a quick check
Step33:  The time and memory complexity of this function should be $\mathcal{O}(|\Sigma|^k)$ for words of size $k\in\mathbb{N}^*$.
Step34:  We can quickly check that even for the larger alphabet of size ~40, it's quite quick for small words of length $\leq 5$
Step35:  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
Step36:  How long does it take and how many grids for the easy problem?
Step37:  That's still pretty small and fast!
How long does it take and how many grids for the hard problem?
Step38:  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!
Step39:  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?
Step40:  This rough estimate gives about $5 * 10^{22}$ seconds, about $10^{15}$ years, so about a million of billion years !
Step41:  First difficult task
Step42:  Let's try it!
Solving the easy problem
Let's check that we can quickly find one solution
Step43:  Then can we find more solutions?
Step44:  No there is indeed a unique solution here for the first "easy" problem!
Solving the intermediate problem
Step45:  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 https
Step46:  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
Step47:  So let's write this algorithm.
I'm using a tqdm.tqdm() wrapper on the foor loops, to keep an eye on the progress.
Step48:  And let's try it
Step49:  So it worked!
🚀 It was also BLAZING fast compared to the naive approach
Step50:  🚀 It was also BLAZING fast compared to the naive approach
<ASSISTANT_TASK:>
Python Code:
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,
}
Explanation: Using Python to solve Regexp CrossWord Puzzles
Have a look at the amazing https://regexcrossword.com/ 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.
Soooooo. I want to use Python3 regular expressions 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.
Author: Lilian Besson (@Naereen) ;
License: MIT License ;
Date: 28-02-2021.
Representation of a problem
Here is a screenshot from the game webpage.
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:
Let's define both, in a small dictionnary containing two to four lists of regexps.
Easy problem of size $(2,2)$ with four constraints
End of explanation
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)}")
Explanation: 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:
End of explanation
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
    ],
}
Explanation: Difficult problem of size $(5,5)$ with 20 constraints
Defining the second problem is just a question of more copy-pasting:
End of explanation
import string
alphabet2 = set(string.digits) \
    | set(string.ascii_uppercase) \
    | { ':', '?', '.', '$', '-' }
print(f"alphabet2 = \n{sorted(alphabet2)}")
Explanation: And its alphabet:
End of explanation
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
    ],
}
Explanation: An intermediate problem of size $(3,3)$ with 12 constraints
Defining the third problem is just a question of more copy-pasting:
End of explanation
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)}")
Explanation: And its alphabet:
End of explanation
def dimension_problem(problem):
    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)
problem1
dimension_problem(problem1)
Explanation: A few useful functions
Let's first extract the dimension of a problem:
End of explanation
___ = "_"  # represents an empty answer, as _ is not in the alphabet
grid1_partial = [
    [ 'H', ___ ],
    [ ___, 'P' ],
]
grid1_solution = [
    [ 'H', 'E' ],
    [ 'L', 'P' ],
]
Explanation: Now let's write a representation of a grid, a solution (or partial solution) of a problem:
End of explanation
grid1_wrong1 = [
    [ 'H', 'E' ],
    [ 'L', 'F' ],
]
grid1_wrong2 = [
    [ 'H', 'E' ],
    [ 'E', 'P' ],
]
grid1_wrong3 = [
    [ 'H', 'E' ],
    [ 'O', 'F' ],
]
grid1_wrong4 = [
    [ 'O', 'E' ],
    [ 'O', 'F' ],
]
Explanation: As well as a few complete grids which are NOT solutions
End of explanation
def nth_line(grid, line):
    return "".join(grid[line])
def nth_column(grid, column):
    return "".join(grid[line][column] for line in range(len(grid)))
[ nth_line(grid1_solution, line) for line in range(len(grid1_solution)) ]
[ nth_column(grid1_solution, column) for column in range(len(grid1_solution[0])) ]
Explanation: We also write these short functions to extract the $i$-th line or $j$-th column:
End of explanation
___ = "_"  # represents an empty answer, as _ is not in the alphabet
grid3_solution = [
    [ 'N', 'O', 'S' ],
    [ 'F', 'E', 'R' ],
    [ 'A', 'T', 'U' ],
]
Explanation: A partial solution for the intermediate problem:
End of explanation
___ = "_"  # represents an empty answer, as _ is not in the alphabet
grid2_partial = [
    [ 'T', 'R', 'A', 'N', '7' ],
    [ '2', '4', ___, ___, ' ' ],
    [ 'A', ___, ___, ___, ___ ],
    [ '-', ___, ___, ___, ___ ],
    [ 'D', ___, ___, ___, '?' ],
]
Explanation: And a partial solution for the harder problem:
End of explanation
def dimension_grid(grid):
    m = len(grid)
    n = len(grid[0])
    assert all(n == len(grid[i]) for i in range(1, m))
    return (m, n)
print(f"Grid grid1_partial has dimension: {dimension_grid(grid1_partial)}")
print(f"Grid grid1_solution has dimension: {dimension_grid(grid1_solution)}")
print(f"Grid grid2_partial has dimension: {dimension_grid(grid2_partial)}")
def check_dimensions(problem, grid):
    return dimension_problem(problem) == dimension_grid(grid)
assert check_dimensions(problem1, grid1_partial)
assert check_dimensions(problem1, grid1_solution)
assert not check_dimensions(problem2, grid1_partial)
assert check_dimensions(problem2, grid2_partial)
assert not check_dimensions(problem1, grid2_partial)
Explanation: Let's extract the dimension of a grid, just to check it:
End of explanation
def check_alphabet(alphabet, word, debug=True):
    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
assert check_alphabet(alphabet1, 'H' 'E')  # concatenate the strings
assert check_alphabet(alphabet1, 'H' 'E')
assert check_alphabet(alphabet1, 'L' 'P')
assert check_alphabet(alphabet1, 'H' 'L')
assert check_alphabet(alphabet1, 'E' 'P')
assert check_alphabet(alphabet2, "TRAN7")
Explanation: Two more checks
We also have to check if a word is in an alphabet:
End of explanation
import re
Explanation: And also check that a word matches a regexp:
End of explanation
memory_of_compiled_regexps = dict()
Explanation: As the documentation 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!
End of explanation
def match(regexp, word, debug=True):
    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]
    
    result = re.fullmatch(regexp, word)
    result = prog.fullmatch(word)
    entire_match = result is not None
    # entire_match = result.group(0) == word
    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
Explanation: Now we are ready to write our "smart" match function:
End of explanation
%%time
match(r"(N3|TRA|N7)+", "TRAN7")
%%time
match(r"(N3|TRA|N7)+", "TRAN8")
Explanation: Let's compare the time of the first match and next ones:
End of explanation
match(r"(N3|TRA|N7)+", "")
match(r"(N3|TRA|N7)+", "TRA")
Explanation: Well of course it's not different for tiny test like this.
End of explanation
%timeit match(r"(N3|TRA|N7)+", "TRA", debug=False)
%timeit re.fullmatch(r"(N3|TRA|N7)+", "TRA")
Explanation: That should be enough to start the first "easy" task.
End of explanation
def check_line(problem, alphabet, word, position, debug=True, early=False):
    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
Explanation: 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.
End of explanation
problem1, alphabet1, grid1_solution
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)
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}")
Explanation: Let's try it!
End of explanation
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}")
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}")
Explanation: That was long, but it works fine!
End of explanation
def check_column(problem, alphabet, word, position, debug=True, early=False):
    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
Explanation: 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.
End of explanation
problem1, alphabet1, grid1_solution
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)
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}")
Explanation: Let's try it!
End of explanation
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}")
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}")
Explanation: That was long, but it works fine!
End of explanation
def check_grid(problem, alphabet, grid, debug=True, early=False):
    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)
    
    return all(ok_lines) and all(ok_columns)
Explanation: 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.
End of explanation
check_grid(problem1, alphabet1, grid1_partial)
Explanation: 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$.
End of explanation
check_grid(problem1, alphabet1, grid1_solution)
Explanation: For a complete grid, let's check that our solution is valid:
End of explanation
check_grid(problem1, alphabet1, grid1_wrong1)
check_grid(problem1, alphabet1, grid1_wrong2)
check_grid(problem1, alphabet1, grid1_wrong3)
check_grid(problem1, alphabet1, grid1_wrong4)
Explanation: And let's also check that the few wrong solutions are indeed not valid:
End of explanation
check_grid(problem3, alphabet3, grid3_solution)
Explanation: 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:
End of explanation
import itertools
def all_words_of_alphabet(alphabet, size):
    yield from itertools.product(alphabet, repeat=size)
Explanation: 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 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).
End of explanation
list(all_words_of_alphabet(['0', '1'], 3))
Explanation: Just a quick check:
End of explanation
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")
    %timeit list(all_words_of_alphabet(alphabet0, k))
%timeit list(all_words_of_alphabet(['0', '1', '2', '3'], 10))
Explanation: The time and memory complexity of this function should be $\mathcal{O}(|\Sigma|^k)$ for words of size $k\in\mathbb{N}^*$.
End of explanation
len_alphabet = len(alphabet1)
for k in [2, 3, 4, 5]:
    print(f"Generating {len_alphabet**k} words of size = {k} takes about")
    %timeit list(all_words_of_alphabet(alphabet1, k))
len_alphabet = len(alphabet2)
for k in [2, 3, 4, 5]:
    print(f"Generating {len_alphabet**k} words of size = {k} takes about")
    %timeit list(all_words_of_alphabet(alphabet2, k))
Explanation: We can quickly check that even for the larger alphabet of size ~40, it's quite quick for small words of length $\leq 5$:
End of explanation
def all_grids_of_alphabet(alphabet, lines, columns):
    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
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])
print(f"For the alphabet {alphabet0} of size = {len(alphabet0)} :")
for (n, m) in [ (1, 1), (2, 1), (1, 2), (2, 2) ]:
    %time 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)}")
Explanation: 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
End of explanation
print(f"For the alphabet {alphabet1} of size = {len(alphabet1)} :")
for (n, m) in [ (1, 1), (2, 1), (1, 2), (2, 2) ]:
    %time 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)}")
Explanation: How long does it take and how many grids for the easy problem?
End of explanation
print(f"For the alphabet {alphabet2} of size = {len(alphabet2)} :")
for (n, m) in [ (1, 1), (2, 1), (1, 2), (2, 2) ]:
    %time 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)}")
41**(2*3)
Explanation: That's still pretty small and fast!
How long does it take and how many grids for the hard problem?
End of explanation
n, m = 5, 5
41**(5*5)
import math
math.log10(41**(5*5))
Explanation: 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!
End of explanation
s = 7
estimate_of_running_time = 7*s * len(alphabet1)**(5*5) / len(alphabet1)**(2*2)
estimate_of_running_time  # in seconds
Explanation: 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?
End of explanation
math.log10( estimate_of_running_time / (60*60*24*365) )
Explanation: This rough estimate gives about $5 * 10^{22}$ seconds, about $10^{15}$ years, so about a million of billion years !
End of explanation
def naive_solve(problem, alphabet, debug=False, early=True):
    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
Explanation: First difficult task: for each possible grid, check if its valid
End of explanation
%%time
good_grids1 = naive_solve(problem1, alphabet1, debug=False, early=True)
print(f"For problem 1\n{problem1}\nOn alphabet\n{alphabet1}\n==> We found one solution:\n{good_grids1}")
Explanation: Let's try it!
Solving the easy problem
Let's check that we can quickly find one solution:
End of explanation
%%time
good_grids1 = naive_solve(problem1, alphabet1, debug=False, early=False)
print(f"For problem 1\n{problem1}\nOn alphabet\n{alphabet1}\n==> We found these solutions:\n{good_grids1}")
Explanation: Then can we find more solutions?
End of explanation
%%time
good_grids3 = naive_solve(problem3, alphabet3, debug=False, early=True)
print(f"For problem 3\n{problem3}\nOn alphabet\n{alphabet3}\n==> We found one solution:\n{good_grids3}")
Explanation: No there is indeed a unique solution here for the first "easy" problem!
Solving the intermediate problem
End of explanation
%%time
good_grids2 = naive_solve(problem2, alphabet2, debug=False, early=True)
print(f"For problem 2\n{problem2}\nOn alphabet\n{alphabet2}\n==> We found one solution:\n{good_grids2}")
Explanation: 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 https://stackoverflow.com/questions/33850577/is-it-possible-to-run-a-pypy-kernel-in-the-jupyter-notebook
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)$.
End of explanation
n, m = dimension_problem(problem1)
problem1
alphabet1
len(list(all_words_of_alphabet(alphabet1, n)))
["".join(word) for word in list(all_words_of_alphabet(alphabet1, n))][:10]
[
    [ "".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)
]
[
    [ "".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)
]
Explanation: 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
End of explanation
from tqdm.notebook import trange, tqdm
def smart_solve(problem, alphabet, debug=False, early=True):
    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}")
    for possible_words in tqdm(
        list(itertools.product(*possible_words_for_lines)),
        desc="lines"
    ):
        if debug: print(f"    Trying possible_words 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
Explanation: So let's write this algorithm.
I'm using a tqdm.tqdm() wrapper on the foor loops, to keep an eye on the progress.
End of explanation
grid1_solution
%%time
good_grids1 = smart_solve(problem1, alphabet1)
good_grids1
Explanation: And let's try it:
For the easy problem
End of explanation
%%time
#assert False  # uncomment when ready
good_grids3 = smart_solve(problem3, alphabet3)
good_grids3
Explanation: 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
End of explanation
%%time
#assert False  # uncomment when ready
good_grids2 = smart_solve(problem2, alphabet2)
good_grids2
Explanation: 🚀 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
End of explanation
<END_TASK>