[Tutor] problem solving with lists: preliminary solution
marcus.luetolf at bluewin.ch
marcus.luetolf at bluewin.ch
Wed May 25 13:19:07 EDT 2022
....sorry, forgott correct e_mail address.....
Hello Experts, hello dn,
In resuming my task to write code for a special constellation of the
"SocialGolferProblem" (SGP) :
number_of_days (number_of_weeks) = 5
number_of_flights (number_of_groupings) = 4
seize of flight (players_per_grouping) = 4
and given the solution below (draws for week 1 through 5) I've come up with
a code of which I only post part of it (for it gets to big):
for day 1( hardcoded) and for day 2 (as a function to be used through day
5).
The crucial part of my functions for day 2 to 5 are the conditional
statements. These conditional statements do not follow a consistent pattern.
This inconsistency casts some doubt on the effectiveness of my code below
and I'd appreciate critical comments.
My code so far:
def startlist():
all_players = list('abcdefghijklmnop')
n = 4 # n = seize of flight
a_flight_day_1 = []
b_flight_day_1 = []
c_flight_day_1 = []
d_flight_day_1 = []
a_flight_day_2 = []
b_flight_day_2 = []
c_flight_day_2 = []
d_flight_day_2 = []
a_flight_day_3 = []
b_flight_day_3 = []
c_flight_day_3 = []
d_flight_day_3 = []
a_flight_day_4 = []
b_flight_day_4 = []
c_flight_day_4 = []
d_flight_day_4 = []
a_flight_day_5 = []
b_flight_day_5 = []
c_flight_day_5 = []
d_flight_day_5 = []
history = {'a':[],
'b':[],'c':[],'d':[],'e':[],'f':[],'g':[],'h':[],'i':[],'j':[],'k':[],'l':[],'m':[],'n':[],'o':[],'p':[]}
[a_flight_day_1.append(player)for player in all_players[0:n]]
print('a_flight_day_1: ', a_flight_day_1)
del all_players[0:n]
[b_flight_day_1.append(player)for player in all_players[0:n]]
print('b_flight_day_1: ', b_flight_day_1)
del all_players[0:n]
[c_flight_day_1.append(player)for player in all_players[0:n]]
print('c_flight_day_1: ', c_flight_day_1)
del all_players[0:n]
[d_flight_day_1.append(player)for player in all_players[0:n]]
print('d_flight_day_1: ', d_flight_day_1)
history['a'].extend(a_flight_day_1)
history['b'].extend(a_flight_day_1)
history['c'].extend(a_flight_day_1)
history['d'].extend(a_flight_day_1)
history['e'].extend(b_flight_day_1)
history['f'].extend(b_flight_day_1)
history['g'].extend(b_flight_day_1)
history['h'].extend(b_flight_day_1)
history['i'].extend(c_flight_day_1)
history['j'].extend(c_flight_day_1)
history['k'].extend(c_flight_day_1)
history['l'].extend(c_flight_day_1)
history['m'].extend(d_flight_day_1)
history['n'].extend(d_flight_day_1)
history['o'].extend(d_flight_day_1)
history['p'].extend(d_flight_day_1)
def day_2_flights():
lead_player = 'a'
temp = history[lead_player][:]
for i in range(n-1):
for player in all_players:
if player not in temp:
a_flight_day_2.extend(player)
temp.extend(history[player])
break
history[lead_player].append(player)
history[lead_player] = list(set(history[lead_player]))
#eliminate duplicates
a_flight_day_2.extend(lead_player)
a_flight_day_2.sort()
print('a_flight_day_2: ', a_flight_day_2)
[history[pl].extend(a_flight_day_2) for pl in a_flight_day_2[1:]]
lead_player = 'b'
temp = history['a'][:]
for i in range(n-1):
for player in all_players:
if player not in temp:
b_flight_day_2.extend(player)
temp.extend(history[player])
break
history[lead_player].append(player)
history[lead_player] = list(set(history[lead_player]))
#eliminate duplicates
b_flight_day_2.extend(lead_player)
b_flight_day_2.sort()
print('b_flight_day_2: ', b_flight_day_2)
[history[pl].extend(b_flight_day_2) for pl in b_flight_day_2[1:]]
lead_player = 'c'
temp = history['a'][:]
for i in range(n-1):
for player in all_players:
if player not in temp and player not in history['b']:
c_flight_day_2.extend(player)
temp.extend(history[player])
break
history[lead_player].append(player)
history[lead_player] = list(set(history[lead_player]))
#eliminate duplicates
c_flight_day_2.extend(lead_player)
c_flight_day_2.sort()
print('c_flight_day_2: ', c_flight_day_2)
[history[pl].extend(c_flight_day_2) for pl in c_flight_day_2[1:]]
lead_player = 'd'
temp = history['a'][:]
for i in range(n-1):
for player in all_players:
if player not in temp and player not in history['b'] and
player not in history['c']:
d_flight_day_2.extend(player)
temp.extend(history[player])
break
history[lead_player].append(player)
history[lead_player] = list(set(history[lead_player]))
#eliminate duplicates
d_flight_day_2.extend(lead_player)
d_flight_day_2.sort()
print('d_flight_day_2: ', d_flight_day_2)
[history[pl].extend(d_flight_day_2) for pl in d_flight_day_2[1:]]
all_players = list('abcdefghijklmnop')
n = 4 #n = seize of flight
day_2_flights()
startlist()
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 06:35
An: tutor at python.org
Betreff: Re: [Tutor] problem solving with lists
Have I managed to understand the problem, this time?
On 21/03/2022 05.05, Dennis Lee Bieber wrote:
> On Sun, 20 Mar 2022 15:55:27 +0100, <marcus.luetolf at bluewin.ch>
> declaimed the following:
>
>>> all_letters = ‘abcdefghijklmnop’
>>> number_of_lists = 5
>>> number_of_sublists per list = 4
>>> number_per_sublist = 4
>> to
>>> all_letters = ‘abcdefghi’
>>> number_of_lists = 4
>>> number_of_sublists per list = 3
>>> number_per_sublist = 3
>> to
>>> all_letters = 'abcdef'.
> The discussion would be much easier if you gave real names to all
> those... (since you later confirm this is the SGP)
>
> number of weeks
> number of groupings
> players per grouping
>
> This avoids all confusion over lists, sublists, etc... "week 1",
> "group 3", "player 2".
How about these as 'meaningful names':
players = "abcdefghijklmnop"
number_of_weeks = 5
number_of_groupings = 4
players_per_grouping = 4
>> seems rather straightforward. But for now I cannot see yet how to use it
>> to remove all non-uniques sublists/teams.
> You don't "remove" them! "Remove" implies you already placed a
> grouping into the solution and now are checking for if they meet the
> constraints.
> Instead you check the constraints for a candidate grouping BEFORE
ADDING it
> to the solution.
Yes, the more 'constructivist' approach is probably easier - it is easier to
'see' as things are added to the solution, than it is to keep track of what
was there 'before' when subtracting/pruning. YMMV!
This solution keeps track of each player's history, ie if player-a is
grouped with players 'b', 'c', and 'd' in the first game, then:
player_history['a'] == {'b','c','d'}
and in the second game (s)he is grouped with players 'e', 'i', 'm'; then it
becomes:
player_history['a'] == {'b','c','d', 'e', 'i', 'm'}
and so-on (see output-report, below)
The player's history is used whenever (s)he is 'selected' to ensure that
there is no repetition of anyone who has participated in that player's
previous groupings.
>> SPG exactly describes my goal.
>
> The SGP is not a week-end programming exercise. It is the subject of
> multiple university research papers in developing/optimizing
> constraint-based solver algorithms.
>
> A one-time pass over the output of .combinations() will not be
> sufficient (especially as the criteria per week that no player appears
> more than once means going from "abcd" [the first foursome
> .combinations() spits out] has to skip all other groups that begin
> with "a", "b", "c" or "d" -- and you can't get them back later. At a
> minimum you need to restart the
> .combinations() on each week. You'll really need to implement some way
> of backtracking ("we ran out of groupings without being able to place
> one ink 'this' position, back up and change the previously placed
> grouping and start over on this position") -- it is possible you might
> have to back all the way up to the first grouping and try a different
> value for it.
Which all serves to make me think that I have yet to grasp the full-measure
of the problem!
Herewith the output-report.
The "draw" for each week (who is playing whom during that week) appears as
four Python-lists under the week's sub-title. (the 'real' output)
Inspecting the "draw", one can visually-check that each player only plays
against everyone else, once - and only once - and exactly once (per @Dennis'
comment about byes - no, none of them necessary with this combination of
definitions)!
The 16-player listing (debug-print) underneath each week's draw, shows how
the program[me] keeps a record of which players each player has played
to-date - thus after each week's game it extends by another three players'
names/letters.
Finally, by the end of the league/tournament (whatever you want to call the
five-weeks of play, per definitions), every player is shown to have played
against every other player:-
/usr/bin/python3 /home/dn/Projects/Experiments/marcus.py
Draw for 5 week league
Draw for week 1
['a', 'b', 'c', 'd']
['e', 'f', 'g', 'h']
['i', 'j', 'k', 'l']
['m', 'n', 'o', 'p']
a ['a', 'b', 'c', 'd']
b ['a', 'b', 'c', 'd']
c ['a', 'b', 'c', 'd']
d ['a', 'b', 'c', 'd']
e ['e', 'f', 'g', 'h']
f ['e', 'f', 'g', 'h']
g ['e', 'f', 'g', 'h']
h ['e', 'f', 'g', 'h']
i ['i', 'j', 'k', 'l']
j ['i', 'j', 'k', 'l']
k ['i', 'j', 'k', 'l']
l ['i', 'j', 'k', 'l']
m ['m', 'n', 'o', 'p']
n ['m', 'n', 'o', 'p']
o ['m', 'n', 'o', 'p']
p ['m', 'n', 'o', 'p']
Draw for week 2
['a', 'e', 'i', 'm']
['b', 'f', 'j', 'n']
['c', 'g', 'k', 'o']
['d', 'h', 'l', 'p']
a ['a', 'b', 'c', 'd', 'e', 'i', 'm']
b ['a', 'b', 'c', 'd', 'f', 'j', 'n']
c ['a', 'b', 'c', 'd', 'g', 'k', 'o']
d ['a', 'b', 'c', 'd', 'h', 'l', 'p']
e ['a', 'e', 'f', 'g', 'h', 'i', 'm']
f ['b', 'e', 'f', 'g', 'h', 'j', 'n']
g ['c', 'e', 'f', 'g', 'h', 'k', 'o']
h ['d', 'e', 'f', 'g', 'h', 'l', 'p']
i ['a', 'e', 'i', 'j', 'k', 'l', 'm']
j ['b', 'f', 'i', 'j', 'k', 'l', 'n']
k ['c', 'g', 'i', 'j', 'k', 'l', 'o']
l ['d', 'h', 'i', 'j', 'k', 'l', 'p']
m ['a', 'e', 'i', 'm', 'n', 'o', 'p']
n ['b', 'f', 'j', 'm', 'n', 'o', 'p']
o ['c', 'g', 'k', 'm', 'n', 'o', 'p']
p ['d', 'h', 'l', 'm', 'n', 'o', 'p']
Draw for week 3
['a', 'f', 'k', 'p']
['b', 'e', 'l', 'o']
['c', 'h', 'i', 'n']
['d', 'g', 'j', 'm']
a ['a', 'b', 'c', 'd', 'e', 'f', 'i', 'k', 'm', 'p'] b ['a', 'b', 'c', 'd',
'e', 'f', 'j', 'l', 'n', 'o'] c ['a', 'b', 'c', 'd', 'g', 'h', 'i', 'k',
'n', 'o'] d ['a', 'b', 'c', 'd', 'g', 'h', 'j', 'l', 'm', 'p'] e ['a', 'b',
'e', 'f', 'g', 'h', 'i', 'l', 'm', 'o'] f ['a', 'b', 'e', 'f', 'g', 'h',
'j', 'k', 'n', 'p'] g ['c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'm', 'o'] h
['c', 'd', 'e', 'f', 'g', 'h', 'i', 'l', 'n', 'p'] i ['a', 'c', 'e', 'h',
'i', 'j', 'k', 'l', 'm', 'n'] j ['b', 'd', 'f', 'g', 'i', 'j', 'k', 'l',
'm', 'n'] k ['a', 'c', 'f', 'g', 'i', 'j', 'k', 'l', 'o', 'p'] l ['b', 'd',
'e', 'h', 'i', 'j', 'k', 'l', 'o', 'p'] m ['a', 'd', 'e', 'g', 'i', 'j',
'm', 'n', 'o', 'p'] n ['b', 'c', 'f', 'h', 'i', 'j', 'm', 'n', 'o', 'p'] o
['b', 'c', 'e', 'g', 'k', 'l', 'm', 'n', 'o', 'p'] p ['a', 'd', 'f', 'h',
'k', 'l', 'm', 'n', 'o', 'p']
Draw for week 4
['a', 'g', 'l', 'n']
['b', 'h', 'k', 'm']
['c', 'e', 'j', 'p']
['d', 'f', 'i', 'o']
a ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'i', 'k', 'l', 'm', 'n', 'p'] b ['a',
'b', 'c', 'd', 'e', 'f', 'h', 'j', 'k', 'l', 'm', 'n', 'o'] c ['a', 'b',
'c', 'd', 'e', 'g', 'h', 'i', 'j', 'k', 'n', 'o', 'p'] d ['a', 'b', 'c',
'd', 'f', 'g', 'h', 'i', 'j', 'l', 'm', 'o', 'p'] e ['a', 'b', 'c', 'e',
'f', 'g', 'h', 'i', 'j', 'l', 'm', 'o', 'p'] f ['a', 'b', 'd', 'e', 'f',
'g', 'h', 'i', 'j', 'k', 'n', 'o', 'p'] g ['a', 'c', 'd', 'e', 'f', 'g',
'h', 'j', 'k', 'l', 'm', 'n', 'o'] h ['b', 'c', 'd', 'e', 'f', 'g', 'h',
'i', 'k', 'l', 'm', 'n', 'p'] i ['a', 'c', 'd', 'e', 'f', 'h', 'i', 'j',
'k', 'l', 'm', 'n', 'o'] j ['b', 'c', 'd', 'e', 'f', 'g', 'i', 'j', 'k',
'l', 'm', 'n', 'p'] k ['a', 'b', 'c', 'f', 'g', 'h', 'i', 'j', 'k', 'l',
'm', 'o', 'p'] l ['a', 'b', 'd', 'e', 'g', 'h', 'i', 'j', 'k', 'l', 'n',
'o', 'p'] m ['a', 'b', 'd', 'e', 'g', 'h', 'i', 'j', 'k', 'm', 'n', 'o',
'p'] n ['a', 'b', 'c', 'f', 'g', 'h', 'i', 'j', 'l', 'm', 'n', 'o', 'p'] o
['b', 'c', 'd', 'e', 'f', 'g', 'i', 'k', 'l', 'm', 'n', 'o', 'p'] p ['a',
'c', 'd', 'e', 'f', 'h', 'j', 'k', 'l', 'm', 'n', 'o', 'p']
Draw for week 5
['a', 'h', 'j', 'o']
['b', 'g', 'i', 'p']
['c', 'f', 'l', 'm']
['d', 'e', 'k', 'n']
a ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p'] b ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l',
'm', 'n', 'o', 'p'] c ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
'k', 'l', 'm', 'n', 'o', 'p'] d ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h',
'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p'] e ['a', 'b', 'c', 'd', 'e', 'f',
'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p'] f ['a', 'b', 'c', 'd',
'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p'] g ['a', 'b',
'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p'] h
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o',
'p'] i ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
'n', 'o', 'p'] j ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k',
'l', 'm', 'n', 'o', 'p'] k ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i',
'j', 'k', 'l', 'm', 'n', 'o', 'p'] l ['a', 'b', 'c', 'd', 'e', 'f', 'g',
'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p'] m ['a', 'b', 'c', 'd', 'e',
'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p'] n ['a', 'b', 'c',
'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p'] o ['a',
'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p'] p
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o',
'p']
Process finished with exit code 0
Is this what we're trying to achieve?
--
Regards,
=dn
_______________________________________________
Tutor maillist - Tutor at python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
More information about the Tutor
mailing list