[Tutor] Filling an array - with a twist

[Mats Wichmann]

On 11/11/20 12:06 PM, dn via Tutor wrote:

> Thus:
> - generate a "pool" for every row and every column in the 8x8 'result'
> - generate a new random() value
> - remove it* from the applicable row and column pools
> - add the value to the 8x8
> * if either remove() fails (exception = ValueError), two examples of 
> that number already exist in the applicable row/column
> ...
> 
> 
> This is a "subtractive" approach to checking. Whereas previously we took 
> an "additive" approach to deciding if the repetition rule(s) are about 
> to be broken.

This is nice idea that I was also going to pursue, but a complication 
emerged that I didn't want to deal with.

You can generate a population pool quite simply, even if inelegantly:

 >>> p = list(range(7)) * 2
 >>> print(p)
[0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6]

Now we want to pick a number from that population, which could be easy:

 >>> print(random.choice(p))
3

The complication is we actually want to pick a number that appears in 
two populations simultaneously - again, this would be trivial if we 
could use sets, where we could perform the choice on the intersection of 
the two, but the lack of uniqueness means other approaches are needed.

After thinking again, you should be able to do that with a simple-ish 
function that's passed the two relevant populations.  I'm not as fond of 
doing the removes as the check, because you have to fixitup - if it 
removed cleanly from row-population, and takes an exception from 
column-population, then you have to put it back into row-population and 
start the picking process again... I'd rather pick from one and check if 
the other population disqualifies that choice, something like this:


def select(row_pop, column_pop):
     """choose a value in both populations and remove it from both"""
     while True:
         x = random.choice(row_pop)
         if x not in column_pop:
             continue
         row_pop.remove(x)
         column_pop.remove(x)
         return x


Note that for some instances of this problem, you can run into deadlocks 
where there is no value that satisfies both row and column constraints, 
and you would have to backtrack to fix the whole thing up (perhaps throw 
away and start again).  I believe, without stopping to think deeply that 
the stated problem space does not fall into that.