Reputation: 1

How to write a bruteforce algorithm for this assignment?

I have to do an assignment for my Computer Science class in High School. I have been trying to write a working algorithm for a couple of weeks already, but I am running out of ideas.

The assignment:

There are n students with n gifts, all of which are numbered. Each student now has to choose what gift he likes best, second best or third best. The gifts are then distributed to the students as well as possible.

A distribution is better than any other distribution, if the number of first wishes fullfilled in the first distribution is higher than the number of first wishes fullfilled in the second distribution. If this number is same for both distributions, the number of second wishes fullfilled decides which distribution is better. And if that number is also equal, the number of third wishes fullfilled decides.

I tried solving this problem using a binary tree and every time there is the same gift in a students wish, the program simulates to situations in which either the first student gets "downranked" or the second student gets "downranked", until you cant either downrank or there is a valuable distribution. After that, all distributions are compared and the best one gets displayed. Also, if a student cant have any of his wishes fullfilled, he gets a gift he didn't want.

But that attempt failed horribly because I had a bad time programming all of this.

So I wanted to know how I would try to solve this using a bruteforce algorithm, since I can't imagine how that would look like.

Here are some example "whishlists" my algorithm hast to solve (each row is a student, and the columns are the first wish, second wish and third wish):

Btw, I would really like to write it in python, and if you guys by any chance have also other ideas on how to solve this, I would be really grateful. I know this is kind of a lot to ask, but I still hope someone here can help me.

Thank you very much!

Upvotes: 0

Answers (2)

tphilipp

Reputation: 466

Here is an incomplete solution based on Answer Set Programming using clingo. Here is a talk from a Torsten Schaub about Answer Set Programming held at the International Conference on Constraint Programming 2013.

The code below has the following limitations

We have three students
We have three gifts
Students can only state which gift they prefer with no precedence, optimization is therefore a bit simpler.

Note that you can easily expand this approach to meet your exact requirements.

% there are three students
student(1..3).
% there are three gifts
gift(1..3).   

% student 1 prefers gift 2
prefer(1, 2).
% student 2 prefers gift 3
prefer(2, 3).
% student 3 prefers gift 1
prefer(3, 1).

% We assign each student a gift.
% Intuitively, the line below means the following:
% For each student S, make exactly one assign(S, G) true
% where G is a gift.
1 { assign(S, G) : gift(G) } 1 :- student(S).

% We have to ensure that a gift can be assigned to a student only once.
:- assign(S1, G), assign(S2, G), S1 != S2.

% Optimize
#maximize { 1, assign(S, G) : assign(S, G), prefer(S, G) }.

% Restrict output to assign
#show assign/2.

If you call clingo, you receive the following output

clingo gifts.pl
clingo version 5.5.0
Reading from gifts.pl
Solving...
Answer: 1
assign(2,1) assign(3,2) assign(1,3)
Optimization: 0
Answer: 2
assign(3,1) assign(2,2) assign(1,3)
Optimization: -1
Answer: 3
assign(3,1) assign(1,2) assign(2,3)
Optimization: -3
OPTIMUM FOUND

Models       : 3
  Optimum    : yes
Optimization : -3
Calls        : 1
Time         : 0.003s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.003s

Upvotes: 2

btilly

Reputation: 46408

I will describe a constraint optimization solution in enough detail to make it doable but without providing code.

First of all an Option specifies a student, a gift and a rank. So each wishlist specifies 3 Options. Also if either the student or gift is None, that specifies a failure to match. It will be helpful to have a __hash__ method on the class implementing it so that it can be used in set objects.

You will need the following global data structures:

student_options: By student, what Options they have.
gift_options: By gift, what Options they have.
assignment: Which students get which gifts.
score: A list of how many got their first, second, third, or no choice. Start with [0, 0, 0, 0]. (You will update, so a list makes sense.)
best_assignment: The best assignment found so far. Start with {}
best_score: The best score found so far. Start with (0, 0, 0, 0). (You only replace, so I prefer a tuple here.)
action_stack: An array that I will explain the purpose of.

Now if you use recursion, you have to constantly copy these data structures to make changes. This is slow and wasteful. So I'll describe an explicit stack based approach instead.

The idea is to have an action_stack. Each action will have a do and an option. Where do is a function. Then the body of our program looks like:

while 0 < len(action_stack):
    action = action_stack.pop()
    action.do(action.payload)

And Action itself is pretty trivial.

class Action:
    def __init__(self, do, option):
        self.do = do
        self.option = option

Why do we do this? It is because we can do stuff now by calling a function, or we can choose to do it later by appending to action_stack. So we can edit the data structure, and stack an action to undo our edit.

Here are the actions that you will need in alphabetical order.

add_option: Adds the option to student_options and gift_options. Creating a key/value pair if necessary. Skip None values.
assign: Assigns that gift to that student and adjusts the score appropriately.
analyze: This is the heart of "figure out what conclusions to make/discover". Will describe more.
choose: For the distinct options sharing a student/gift with the option (including itself), appends add_option to action_stack, actually removes the option, then appends analyze and assign to the action_stack to make sure that we assign and then analyze.
remove_option: Removes the option from student_options and gift_options. Deleting the key/value pair if necessary.
unassign: Undoes the assignment, and adjusts the score appropriately.

Here is an implementation of choose to show the style.

def choose(option):
    global action_stack
    found = set()
    for options in (student_options.get(option.student, []), gift_options(option.gift, [])):
        for o in options:
            found.add(o)
    for o in found:
        remove_option(o)
        action_stack.append(Action(add_option, o))
    action_stack.append(Action(analyze, None))
    action_stack.append(Action(assign_option, option))

In other words we actually clear out all of the options relevant to the choice that we made, make sure that we will replace them, make sure that we will analyze and make sure that we will assign.

Which means that next we assign. And then analyze with a bunch of options gone. Then when we backtrack down the stack, we'll undo what we did.

OK, that leaves us with the giant black box of analyze. How can it work? The idea is that we look for forced conclusions, and if we find them we conclude and try again. Failing that we look for the smallest number of choices we can make and recursively search. Failing that we are at a solution, see if it is best.

The forced conclusions we focus on is that if a gift is someone's most wanted, that gift will never go to someone who wants it less. (It might go to someone else, but never to someone who wants it less.)

In pseudo-code it works like this.

remove_options = []
for each student:
    for their most desired option:
        all lower ranked options on its gift to into remove_options

if 0 < len(remove_options):
    # Note, sets are useful for calculating distinct.
    for distinct option in removed_options:
        remove_option(option)
        action_stack.append(Action(add_option(option))
    action_stack.append(Action(analyze, None))
else:
    find smallest non-empty option group from students, gifts
    if group found:
        for option in group:
            action_stack.append(Action(choose, option))
    elif best_score < tuple(score):
        best_score = tuple(score)
        best_assignment = assignment.copy()

OK, so we are nearly done. With all of that machinery, how does the code work? The idea is like this.

action_stack = [Action(analyze, None)]
for wishlist_item in wishlists:
    action_stack.append(Action(add_option(option from wishlist_item)))
for student in students:
    # This assumes ranks go from 0..2 for wanted gifts so 3 is for unwanted
    action_stack.append(Action(add_option(student, None, 3)))
for gift in gifts:
    # This assumes ranks go from 0..2 for wanted gifts so 3 is for unwanted
    action_stack.append(Action(add_option(None, gift, 3)))

while 0 < len(action_stack):
    action = action_stack.pop()
    action.do(action.option)

Fix up assignment to assign unwanted presents to those who don't have presents.
show assignment

Good luck!

Upvotes: 0

How to write a bruteforce algorithm for this assignment?

Answers (2)

Related Questions