Break in list comprehension in Python

user_10726996 0
Viewed 133

I am solving a sudoku and I have a list of constraints for that. They look like this:

(1,2,[1,2,3])

Each tuple contains the row number, column number and the possible values for that position. Now I have the following code to make this constraints:

[(row, column, notIn(matrix[row - 1], getColumn(matrix, column),
           getSubgrid(matrix, row, column)))
           for row in range(1, len(matrix) + 1)
           for column in range(1, len(matrix) + 1)
           if matrix[row - 1][column - 1] == 0]

I am trying to make my code more efficient and my program now makes all the constraints all the time, but I would like it to stop when it finds a constraint with only one possible value, like this:

(3,4,[2])

I want to break the list comprehension when it finds a element like this, but the element has to be included in the list. Otherwise I would like to return the constraint when I find one. It is possible that there aren't constraints with only one possible value, in that case I still need all the constraints.

How can I do this?

python
3 Answers

Start by writing a generator expression (not a list comprehension) that generates all the constraints.

from itertools import product


constraints = ((r, c, notIn(matrix[r-1],
                            getColumn(matrix, c),
                            getSubgrid(matrix, r, c))) 
               for r, c in product(range(1, len(matrix) + 1), repeat=2)
               if matrix[r-1][c-1] == 0)

Next, filter that by the condition the candidate list should have only one element.

ready_to_fill = filter(lambda c: len(c[2]) == 1, constraints)

Now you can iterate over ready_to_fill in its entirety

for row, column, [value] in ready_to_fill:
    matrix[row-1][column-1] = value

Or just get the first one (keeping in mind that you may not have found a square that's ready to fill yet):

try:
    next_to_fill = next(ready_to_fill)
except StopIteration:
    ...

In Python 3.8, you can use an assignment expression to both check that there is such a constraint and get a reference to it with any:

# No need for filter in this case
# If any returns True, next_to_fill will be the first constraint
# with a singleton list.
if any(len((next_to_fill := c)[2]) == 1 for c in constraints):
    ...

Update: to get everything up to and including the singleton-list constraint, a generator expression is less convenient. You can use a generator function, though.

def get_constraints():
    for r, c in product(range(1, len(matrix) + 1), repeat=2):
        if matrix[r-1][c-1]:
            continue
        v = notIn(matrix[r-1],
                  getColumn(matrix, c),
                  getSubgrid(matrix, r, c))
        yield (r, c, v)
        if len(v) == 1:
            return

 for row, column, [value] in get_constraints():
     ...
user_11268410

Just please do a normal loop.I use list comprehension to quickly populate a list in a clear and concise manner. This is the opposite of that, I don't even want to understand it.

And this will make things harder to debug. This seems to be the opposite of what a convenience function should be.

user_70608290

Lets say you have a function which just returns the list comprehension:

def getConstraints(matrix): 
    return [(row, column, notIn(matrix[row - 1], getColumn(matrix, column),
               getSubgrid(matrix, row, column)))
               for row in range(1, len(matrix) + 1)
               for column in range(1, len(matrix) + 1)
               if matrix[row - 1][column - 1] == 0]

We can rewrite this pretty easily into a generator that does yield without breaking the way we were originally using it:

def getConstraints(matrix):
    # probably can just use generator directly in most of your cases...
    # but might as well keep this around for max compatibility.
    return list(getConstraintsGENERATOR(matrix))

def getConstraintsGENERATOR(matrix):
    for row in range(1, len(matrix) + 1):
        for column in range(1, len(matrix) + 1):
            if matrix[row - 1][column - 1] == 0:
                x = notIn(matrix[row - 1],
                          getColumn(matrix, column),
                          getSubgrid(matrix, row, column)
                        )
                yield (row, column, x)

Now because we have a function that is yielding values it becomes trivial to add a case to return early, in your case I think it would be if len(x) == 1: return, and since you want to include that element you would do that after the yield.

user_58272150
Related