Page 1 of 2 12 Last
1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
13
Rep Power
0

#### Decision (algorithm) problem

Hi everyone!

I've got the following problem: Given a file like:
Lara Monday Tuesday
Lucas Saturday Sunday
Monica Sunday Monday
Carlo Saturday Tuesday
Franco Monday Thursday
Lea Tuesday Wednesday
Chris Friday Saturday

The entries after the name are the days, on which the persons prefer to work.

I should read the file in a dictionary. I did this with the following code:
Code:
```import codecs
from collections import defaultdict

data = defaultdict(list)

print "Enter name of file which you want to read."
filename = raw_input("filename: ")
infile = codecs.open(filename, 'r')
for line in infile:
temp = line.split()
data[temp[0]].append(temp[1])
data[temp[0]].append(temp[2])
print data```

I hope this is ok?
Now, i've a question: How could a possible algorithm look like, which gives every person one of the preferred day s.t. as few persons as possible are unhappy (they don't receive any of the preferred days) and as many persons are happy.
Let's say, we can offer 1 place on Monday, 2 on Tuesday, 4 on Saturday and 2 on Sunday. [only an exemple ]

Thanks for any propositions
2. A quick test of the readFile() function does show that it seems to work:
Code:
`defaultdict(<class 'list'>, {'Carlo': ['Saturday', 'Tuesday'], 'Franco': ['Monday', 'Thursday'], 'Lara': ['Monday', 'Tuesday'], 'Lea': ['Tuesday', 'Wednesday'], 'Monica': ['Sunday', 'Monday'], 'Chris': ['Friday', 'Saturday'], 'Lucas': ['Saturday', 'Sunday']})`
(The order is changed because of how the defaultdict() class hashes the keys.) Your next step presumably is to work out the algorithm for setting the days.
3. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
13
Rep Power
0
Well, in natural language, i'd propose following:
"
1. chek how many preferred mondays, tuesdays etc... there are
2. if there is one day which is preferred more than the offered ones, I would check the other preferred day of the persons which have the same first preferred day. If the second choice is ok (i.e. the second choice is offered sufficiently often), we'll take the second choice. If the second choice of this person isn't offered sufficiently enough, we skip to the other persons and check the same.
3.) If every person has its day or if there are no offered days left, we're finish.
"
This is what I elaborated. Do you think it's ok, logically?
However; I still didn't get the implementation.
Is it possible to help me?
4. I'd assign "satisfaction" weights to each person each day.
0 is best through 6 worst.
Then I'd call on an integer optimization function to find the happiest work force.
Or, you might be able to adapt the genetic algorithm in this recent thread.
Or, if the problem is small enough (I think your sample data set is small enough) you could try every possibility and that way certainly determine the global optimal solution.
5. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
13
Rep Power
0
Your propositions sounds very interesting. How are these satisfaction weights implemented? (or: how would you do that?) And how would you then distribute the days? [a beginning would last...it's just that I see how it should work and how the code should look like]
The thing is: my sample data is really small, so I'm not allowed to use predefined functions or algorithm...
6. I wrote my thoughts apparently while you wrote your natural language description. And the ideas are the same.

Lara prefers Monday, but Tuesday would be okay.
Code:
```#day     staff   weight
#Mon     Lara    0
#Tue     Lara    1
#Wed     Lara    2
#Thu     Lara    2
#...

weights = {(0,'Lucas'):1, # lucas (the name) 2nd preference (the 1) is Sunday (the 0)
#...
}
for name_order in itertools.permutations(names):
score = sum(weights[key] for key in enumerate(name_order))
# do something smart with score and the particular assignments```
7. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
13
Rep Power
0
Thank you very much for your help!
..I've a really stupid question: isn't it possible to assign the weights "automatically"?
Because I read the data from a file and then, I have the data in the following form:
Code:
` defaultdict(<class 'list'>, {'Carlo': ['Saturday', 'Tuesday'], 'Franco': ['Monday', 'Thursday'], 'Lara': ['Monday', 'Tuesday'], 'Lea': ['Tuesday', 'Wednesday'], 'Monica': ['Sunday', 'Monday'], 'Chris': ['Friday', 'Saturday'], 'Lucas': ['Saturday', 'Sunday']})`
8. Sure, your (my) code can figure out that

data['Carlo'][1] stores 'Tuesday' and that 'Tuesday' represents the 2nd day of the week.
9. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
13
Rep Power
0
Is there a way to store the values of all the keys in a dictionary?
I.e. I want to save the values from the first person (without typing 'lucas' or whatever) in the dict; like: days = data.get_values(0)[0] += 1
[this doesn't work - but is there a way without typing the person's name by hand?)
10. Does this help?
Code:
```>>> D=dict(a=1,b=2,c=3)
>>> (names,preferences) = tuple(zip(*D.items()))
>>> names
('a', 'c', 'b')
>>> preferences
(1, 3, 2)
>>>```
11. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
13
Rep Power
0
Honestly, it doesn't help very much...
Maybe I misunderstood something... So I show you what I've got until now.

A defaultdict called data:
data = defaultdict(<class 'list'>, {'Carlo': ['Saturday', 'Tuesday'], 'Franco': ['Monday', 'Thursday'], 'Lara': ['Monday', 'Tuesday'], 'Lea': ['Tuesday', 'Wednesday'], 'Monica': ['Sunday', 'Monday'], 'Chris': ['Friday', 'Saturday'], 'Lucas': ['Saturday', 'Sunday']})

Now, I want to implement the function weights:
Code:
```def weights():
days = {}
#...```
Here, I want to count how many persons wanna work on monday, tuesday, ...
So far so good. But if there are too many preferences for the same day, I have to check if a person's second preference should/can be considered.
And there's the point: I didn't get it yet how to implement this problem, the weights etc...

So, every help is appreciated
Thank you very much.
12. In my algorithm I intended weights as a dictionary. Of course you're supposed to use your algorithm, not mine. None the less, this is how I'd construct it:
Code:
```\$ python
Python 2.7.3 (default, Sep 26 2012, 21:51:14)
[GCC 4.7.2] on linux2
>>> data = {'Carlo': ['Saturday', 'Tuesday'], 'Franco': ['Monday', 'Thursday'], 'Lara': ['Monday', 'Tuesday'], 'Lea': ['Tuesday', 'Wednesday'], 'Monica': ['Sunday', 'Monday'], 'Chris': ['Friday', 'Saturday'], 'Lucas': ['Saturday', 'Sunday']}
>>> days = 'Sunday Monday Tuesday Wednesday Thursday Friday Saturday'.split()
>>> weights = dict()
>>> for (key,value) in data.items():
...     name = key
...     preferences = value
...     for day in days:
...         if day == value[0]:               # best
...             w = 0
...         elif day == value[1]:             # 2nd choice
...             w = 1
...         else:                             # yuck!
...             w = 2
...         weights[(name,day)] = w
...
>>> import pprint
>>> pprint.pprint(weights)
{('Carlo', 'Friday'): 2,
('Carlo', 'Monday'): 2,
('Carlo', 'Saturday'): 0,
('Carlo', 'Sunday'): 2,
('Carlo', 'Thursday'): 2,
('Carlo', 'Tuesday'): 1,
('Carlo', 'Wednesday'): 2,
('Chris', 'Friday'): 0,
('Chris', 'Monday'): 2,
('Chris', 'Saturday'): 1,
('Chris', 'Sunday'): 2,
('Chris', 'Thursday'): 2,
('Chris', 'Tuesday'): 2,
('Chris', 'Wednesday'): 2,
('Franco', 'Friday'): 2,
('Franco', 'Monday'): 0,
('Franco', 'Saturday'): 2,
('Franco', 'Sunday'): 2,
('Franco', 'Thursday'): 1,
('Franco', 'Tuesday'): 2,
('Franco', 'Wednesday'): 2,
('Lara', 'Friday'): 2,
('Lara', 'Monday'): 0,
('Lara', 'Saturday'): 2,
('Lara', 'Sunday'): 2,
('Lara', 'Thursday'): 2,
('Lara', 'Tuesday'): 1,
('Lara', 'Wednesday'): 2,
('Lea', 'Friday'): 2,
('Lea', 'Monday'): 2,
('Lea', 'Saturday'): 2,
('Lea', 'Sunday'): 2,
('Lea', 'Thursday'): 2,
('Lea', 'Tuesday'): 0,
('Lea', 'Wednesday'): 1,
('Lucas', 'Friday'): 2,
('Lucas', 'Monday'): 2,
('Lucas', 'Saturday'): 0,
('Lucas', 'Sunday'): 1,
('Lucas', 'Thursday'): 2,
('Lucas', 'Tuesday'): 2,
('Lucas', 'Wednesday'): 2,
('Monica', 'Friday'): 2,
('Monica', 'Monday'): 1,
('Monica', 'Saturday'): 2,
('Monica', 'Sunday'): 0,
('Monica', 'Thursday'): 2,
('Monica', 'Tuesday'): 2,
('Monica', 'Wednesday'): 2}
>>>```
13. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
13
Rep Power
0
Thank you very much. This really helped developing my code
To finish my whole program: How would you implement the offered days (i.e. Sunday, we need 2 persons, monday 1, tuesday 2 etc), s.t. every person is happy (i.e. as many as possible receive the 1. or the 2.preference)?

• b49P23TIvg disagrees : reread post 6
14. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
13
Rep Power
0
At the moment, I have this:
Code:
```def weight():
choices = 'saturday sunday monday tuesday'.split()
sorts = {}
weights = dict()
for (key, value) in data.items():
name = key
preferences = value
for choice in choices:
if choice == value[0]:
w = 2
elif choice == value[1]:
w = 1
else:
w = 0
weights[(name, choice)] = w
for name, gew in weights.items():
if sorts.has_key(name[1]):
sorts[name[1]] += gew
else:
sorts[name[1]] = gew
print sorts```
Now, I have a dict with the sum of all the preferences.
Let's say I save the offered places also in a dict: offered = {'saturday':1, 'sunday':2, 'monday':1, 'tuesday':2}
How can I finally solve the problem that I can distribute all the "wished" days (s.t. I know who works on which day) and I don't distribute too many places?
15. You've got 7 people and 7 days. These are the possible schedules:
Code:
```>>> import itertools
>>> for schedule in itertools.permutations('Bob Sue Jim Tony Alice Zane Tim'.split()):
...  print(schedule)
...
('Bob', 'Sue', 'Jim', 'Tony', 'Alice', 'Zane', 'Tim')
('Bob', 'Sue', 'Jim', 'Tony', 'Alice', 'Tim', 'Zane')
('Bob', 'Sue', 'Jim', 'Tony', 'Zane', 'Alice', 'Tim')
('Bob', 'Sue', 'Jim', 'Tony', 'Zane', 'Tim', 'Alice')
('Bob', 'Sue', 'Jim', 'Tony', 'Tim', 'Alice', 'Zane')
('Bob', 'Sue', 'Jim', 'Tony', 'Tim', 'Zane', 'Alice')
('Bob', 'Sue', 'Jim', 'Alice', 'Tony', 'Zane', 'Tim')
...etceteras```
The first one means "Bob works on Sunday,...Tim works on Saturday".
If Bob preferred Sunday, Tim's second preference was Saturday, and no one else got their preference, and if we assign 2 to first preference, 1 to 2nd preference, and 0 to dissatisfied, then the first schedule has a score of 3.

Make all the schedules. (You told me that.) Score each schedule. Choose any of the schedules with the highest score. (Maximization.) I called it optimization, which means "find the minimum", but I assigned the weights traditionally. Obviously optimization searches for maximum of a function if you negate the goal function.

And that, dude/dudette is why I told you to review one of my earlier posts.
Page 1 of 2 12 Last