[Tutor] Filling an array - with a twist

[dn]

On 12/11/2020 09:08, Mats Wichmann wrote:
> 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:

Apologies, whilst the original use of the "pool" idea went this way, I 
didn't/wouldn't.

Accordingly, (and in my mind, but not in the response!) I would stick 
with using random() multiplied-up to cover the integral range 0~6 and 
using the pools only to ensure the rules/spec is fulfilled.

Maybe I'm channelling my inner-Monty Hall (or maybe it's the quantity of 
pollen and/or smelly dog expanding my sinuses) but I immediately started 
to worry about the stochastic nature of a reducing-population (before 
quickly giving-up - thinking about anything). Feel free to set me 
straight...


* not mine, a colleague brought along with him - others have brought 
kid(s), some a preferred food. Me? All I need is my security-blanket 
(https://peanuts.fandom.com/wiki/Linus%27_security_blanket)


>  >>> 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

Well done!
PS "pop" is "population" not collection.pop()

I didn't offer code, because I'm not sure if that would be doing the 
OP's homework for him. Also, didn't worry about this (need for "locking 
a transaction") because (a) it 'spoils' the smooth description of the 
algorithm, and (b) leaving some process-of-discovery for the coder.
(hey, it's a good line, and I'm going to stick with it!)


Certainly, this is the issue with all multi-criteria "subtractive" 
solutions.

Is it made more (or less) complex by using the pools as part of the 
random() selection step?


The "in" check is an elegant solution, but by the time we add that 
check, have we saved anything over the additive approach?
(performance-wise, even code-complexity-wise)


> 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.

Are you sure? (forgive my sinuses-where-brain-used-to-be) The 
population-range (=14) is so much larger than the sample(s) (=8).
-- 
Regards =dn