[Tutor] problem solving with lists

[marcus.luetolf at bluewin.ch]

If  I may make a comment:
Starting off with the real task to provide a startlist for next week:  16
players, teams of 4 players, 5 days to play, 4 teams a day ,
each player playes once with each other, I reckoned  I could find a solution
with these particular "parameters" using python instead
of trial and error on an Excel sheet (and never accomplish the task).
I then found that I could define other particular parameters: 

n = number of players
r =  numbert of players in a team 
if  (n-1)%(r-1) == 0  
then (n-1)/(r-1) =  p = numbers of days played.

A couple of years ago I tried to find a generalized solution for variable
parameters and posted my attempts on tutor. 
At that time I was refered to a mathematics forum for it was felt  to be a
mathematical problem of very high order.

Regards, Marcus.

-----Ursprüngliche Nachricht-----
Von: Tutor <tutor-bounces+marcus.luetolf=bluewin.ch at python.org> Im Auftrag
von dn
Gesendet: Montag, 21. März 2022 22:54
An: tutor at python.org
Betreff: Re: [Tutor] problem solving with lists

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
_______________________________________________
Tutor maillist  -  Tutor at python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor