@maxi(paths generator) clear solution for Graphical Key by Phil15 - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
@maxi(paths generator) solution in Clear category for Graphical Key by Phil15
from itertools import product
MOVES = {(i,j) for i,j in product((-1,0,1), repeat=2) if i or j} # all 8 moves

maxi = lambda f: lambda *args: max(f(*args), default=0)

@maxi
def g_key(array, length, path = [(0,0)]):
    """Generate values of path from upper-left corner to lower-right corner,
    no longer than given length."""
    nb_rows, nb_cols = len(array), len(array[0])
    if length >= nb_rows * nb_cols: # here because if not... complexity blow me!
        yield sum(sum(row) for row in array)
    else:
        neighbors = lambda i,j: ((i+I,j+J) for I, J in MOVES
                                           if (0<=i+I
                        Sept. 25, 2018

                        
                            Comments:
                            
                                
                                    BrianMcleod
 on Sept. 26, 2018, 10:39 a.m.

                                    <p>I like the use of product to generate MOVES!!</p>

                                
                            
                                
                                    Phil15
 on Sept. 26, 2018, 3:27 p.m.

                                    <p>Imagine you do a mistake writing allowed moves (with 8 it's possible), and imagine debug your program to finally see a mistake in moves... Never happen to me hopefully and it won't.</p>

<p><em>You don't like this generator decorated by maxi?</em></p>

                                
                            
                                
                                    BrianMcleod
 on Sept. 26, 2018, 4:39 p.m.

                                    <p>ahhh, I don't understand how it works.  I understand the decorator, but not the generator workings. Can you give me an outline of how it works?</p>

                                
                            
                                
                                    Phil15
 on Sept. 26, 2018, 5:18 p.m.

                                    <p>First a "yield" is like return an element and keep searching for another element to return. So a yield doesn't end the function. It gives elements of a list one by one. <em>Maybe you already know that but it's said.</em></p>

<p>So for the else...</p>

<p>neighbors generate neighbors (not previously visited)</p>

<p>If the last element in path is the end, then we yield the sum of values on the path.</p>

<p>If len(path) &lt; length, then we have the right to add an element to the path. It's necessarily a neighbor of path[-1], then we yield all possibilities. It's recursive: one call of the function add only one element on the path...</p>

<p>It's bruteforce search with generator (hopefully) and maxi decorator.</p>

                                
                            
                                
                                    BrianMcleod
 on Sept. 26, 2018, 7:26 p.m.

                                    <p>Thanks, it is clearer now.  One more question:
So, when checkio calls your function, it gets wrapped by the decorator, then acts like an iterator?  Where in your code indicates the last yield-how does it end?  Is the max calling the iterator/generator and calculating the largest one?</p>

<p>OK, that's really three questions.</p>

                                
                            
                                
                                    Phil15
 on Sept. 26, 2018, 8:17 p.m.

                                    <p>Important to know how it ends. Each call of g<em>key add a thing on path. Then one day, there is length things in path and then "len(path) &lt; length" bool is false so no more call of g</em>key. That's why it ends. And if it yield nothing (this happen when len(path)==length and path[-1]!=end), max has default value = 0 (this is why I write it).</p>

<p>For each call of g<em>key, there is no more than 8 things it yields: maybe the sum yielded and one yield per neighbor considered (no more than 7, because at least one is already visited). So for each call of g</em>key, it's like I do a list (but I generate) of at most 8 elements and put max on it, but without the management of a list neither his memory.</p>

<p>I think I answered the three, right?</p>

<p><em>I really like generators (and here it's a "bit" necessary for bruteforce).</em> And decorator change the generator into the function we need.</p>

                                
                            
                                
                                    BrianMcleod
 on Sept. 26, 2018, 8:27 p.m.

                                    <p>Thanks!!  It makes sense now.  So, you used the generator pattern to manage memory bloat for the large number of calls caused by brute force.  Is that right?</p>

                                
                            
                                
                                    Phil15
 on Sept. 26, 2018, 8:34 p.m.

                                    <p>Totally, <em>generators are made for that</em>. I didn't measure the difference but it must make a huge difference.</p>

                                
                            
                                
                                    BrianMcleod
 on Sept. 26, 2018, 9:11 p.m.

                                    <p>I've got a feeling that I will have a chance to practice on the next ESCHER mission.  I'll try it out.</p>

                                
                            
                                
                                    Phil15
 on Sept. 26, 2018, 9:21 p.m.

                                    <p>I use generators every time I can. Every time you read only one time in order an iterable (especially lists), you can use a generator instead. Like change [list comprehension] into (generator comprehension).</p>

<p>Every time you write any/all/sum/join/...(comprehension thing) without [] around comprehension thing, it's generator. Efficiency and less characters.</p>

<p>So yeah, many missions can have a little generator somewhere.</p>

<p>My neighbors function here return a generator for example.</p>

                                
                            
                                
                                    BrianMcleod
 on Nov. 29, 2018, 1:57 p.m.

                                    <p>So, I wrote my first true generator function.  Check it out in "Painting Wall" on the Mine Island.  I think I understand how it works now.</p>

                                
                            
                                
                                    Phil15
 on Nov. 29, 2018, 2 p.m.

                                    <p>Thanks for feedback but I didn't solve this mission yet. I'm on my (at least) third attempt on "Family Gifts" on Shelter Island, it's an evil task.</p>
Escher
0 %
You ClassRoom Demo is Ready With the new tool CheckiO ClassRoom, you will be able to analyze your students' progress, have your own leaderboard, change missions order on the map, and so on.