[Tutor] problem solving with lists

[dn]

On 22/03/2022 08.14, Dennis Lee Bieber wrote:
> On Mon, 21 Mar 2022 18:34:40 +1300, dn <PythonList at DancesWithMice.info>
> declaimed the following:
> 
>> Which all serves to make me think that I have yet to grasp the
>> full-measure of the problem!
>>
> 
> 	Is your solution generalized enough to handle the classic SGP test?
> 
> 		8 groups of		4 players over		10 weeks

Sadly, no!

NB the number of players in the tournament/available to draw, is an
important component!

My 'solution' is relatively brute-force, in that it lacks any
tactical-component to the selection process - in fact it is close to
alphabetical if it can be described as having any intent.

Thus the above configuration fails after week 5/the fifth iteration. By
this stage, player-a has played everyone from 'b' to 'p'. Thus, the next
logical 'pairing' would be to group 'a' with 'q'. However, in the
mean-time 'q' has played everyone from 'r' to 'F'. So, 'stalemate'!


> According to the research, there IS a solution to this.
> 
> 	I've spent the afternoon hacking my previous code to work in loops of
> 		weeks
> 			groups in week
> using set intersection as the filter (within week, intersection between
> groups must return empty sets -- no duplicate players) and then against
> prior weeks (intersection must not be greater than 1; 2+ indicates a
> repeated pair of players). The 4 4 6 case is an expected result.

Generalising the problem, takes it way-beyond the level of an
intermediate~advanced (Python) programming course (IMHO). It requires
some higher-order math, rather than 'just Python'! If you told me this
was a post-grad level assignment in a math stream, I'd believe you!
Certainly it's beyond (my impression of) the OP's level (and interest).

As mentioned, my 'solution' (to @marcus) was simplistic and basic. It
doesn't even consider back-tracking and is limited to one 'strategy' (ie
selection based upon not much more than blind-luck).


Beyond the four definitions:

globals(): player_history is a dict (key is player-name) of sets
(previous team-mates?opponents)
* yes, I know about the perils of globals! Referring to discussion of
OO, perhaps making the league/tournament an object which contains all
the specifications would have the advantage of avoiding globals...

arrange_draws_for_league() could assemble a list of weekly draws/groups,
but as the spec seemed to only require a print-out, I refactored it 'out'.

arrange_this_weeks_groups() has two constructs:
- this_weeks_draw which  a list to be filled with the groups of (4)
players (itself a list, returned from the inner function...)
- players_already_drawn is the set of players already placed in
this_weeks_draw

Hence the (inner) function find_undrawn_player() which serially-searches
the list of players (string of letters) to find a player with which to
'seed' the next player-group. [here is where the simplicity of rote (as
a tactic) reduces generalisation!]
I guess these two constructs might be combined, but I wasn't sure if the
order of players in the draw might have some significance; whereas
processing is faster and (the thinking) easier using sets (where 'order'
has no meaning).
NB both start the 'week' empty, which is why player-a will always be the
first player, in the first group, every week - again a gross
simplification and referring to previous criticism, may not be 'fair' if
the order of the players within a group (or of the groups within a draw)
has particular significance!

arrange_group_to_play() is the 'inner loop'/inner layer of the 'onion'
- grouping is the set of players who will play together 'this time' and
seeded by the player selected above
- players_played starts life as a copy* of the seed-player's
player_history, and is extended by the history of each player as (s)he
is added to the group. Thus, it informs the mechanism ensuring that no
player repeats a meeting with any other player in the competition.
* Yes, whilst grouping is a set, to ease the load on my eyes, I always
sort before printing. What a cheat!

So, whilst the solution keeps 'player history', it makes no record of
attempts to solve, and thus there's no opportunity to back-track.
Perhaps instead of the first combination being 'a' and 'b' (simplistic
approach), if 'a' and 'p' (say) were tried first, might that lead to an
actual solution that was not otherwise possible?

At which point I say: "stop the world - I want to get off"!

If you'd like a copy of this code-solution* (off-list), then will be
happy to send - but I think you're an order of magnitude beyond my
achievement to-date (and my interest for the future)!

* 69 LoC, nicely commented, written for 'intermediate level' coders,
blah-blah, puff-puff, including debug-prints for the player histories.


> C:\Users\Wulfraed\Documents\_Hg-Repositories\Python Progs\SGP>main.py
> 
> ***     Usage: SGP.py number_of_groups group_size number_of_weeks

Another point-of-difference is that I perhaps (mis-)understood that the
specs included a requirement that every player play every other player,
at some stage during the league/tournament.

In reality the number_of_weeks specification is the code's control.

Many of these (snipped) combinations of league-definitions you've
attempted don't meet that spec - hence I've not tried. Apologies...
(see comment elsewhere about the elegance and careful selection of
definitions in the 'assignment')


> 	I have no back-tracking in place, beyond the restart of the generator
> on each week. I suspect the next attempt -- should I get ambitious -- is to
> put a generator on each group in each week (and save them as some
> structure), to allow for back-tracking.

"You're a braver man than I [am], Gunga Din"!
-- 
Regards,
=dn