6
\$\begingroup\$

I am trying to solve the stable marriage problem in SPOJ in Python 3.

There are given \$n\$ men and \$n\$ women. Each woman ranks all men in order of her preference (her first choice, her second choice, and so on). Similarly, each man sorts all women according to his preference. The goal is to arrange \$n\$ marriages in such a way that if a man \$m\$ prefers some woman \$w\$ more than his wife, then \$w\$ likes her husband more than \$m\$. In this way, no one leaves his partner to marry somebody else. This problem always has a solution and your task is to find one.

Input

The first line contains a positive integer \$t \le 100\$ indicating the number of test cases. Each test case is an instance of the stable marriage problem defined above. The first line of each test case is a positive integer \$n \le 500\$ (the number of marriages to find). The next \$n\$ lines are the woman's preferences: \$i\$th line contains the number \$i\$ (which means that this is the list given by the \$i\$th woman) and the numbers of men (the first choice of \$i\$th woman, the second choice,...). Then, the men's preferences follow in the same format.

Output

For each test case print \$n\$ lines, where each line contains two numbers \$m\$ and \$w\$, which means that the man number \$m\$ and the woman number \$w\$ should get married.

I have tried optimising the code as much as I can (remove slicing, keep it minimal array, remove printing one by one... etc).

But by far the best code I have been able to get runs in 0.13(s?) time and 33M(??) memory. But the best code for the same problem in Python 3 (submitted by @_@) runs in 0.09 time and 13M memory. So I would like suggestions on how to attain the best time and space usage with my code

from sys import stdin, stdout


def findWoman(manArray, womanArray, index, mpref, wpref):
    for woman in mpref[index - 1]:
        if(woman == 0):
            continue
        hub = womanArray[woman - 1]
        if(hub == 0):
            womanArray[woman - 1] = index
            manArray[index - 1] = woman
            return 0
        elif(wpref[woman - 1].index(index) > wpref[woman - 1].index(hub)):
            continue
        else:
            manArray[hub - 1] = 0
            womanArray[woman - 1] = index
            manArray[index - 1] = woman
            return hub


out = ''
t = int(stdin.readline())
while(t > 0):
    t -= 1
    n = int(stdin.readline())
    mpref = []
    wpref = []
    for _ in range(0, n):
        w = list(map(int, stdin.readline().split()))
        w[0] = 0
        wpref.append(w)
    for _ in range(0, n):
        m = list(map(int, stdin.readline().split()))
        m[0] = 0
        mpref.append(m)
    manArray = [0 for _ in range(n)]
    womanArray = [0 for _ in range(n)]
    for k in range(n):
        hub = k + 1
        while(hub != 0):
            hub = findWoman(manArray, womanArray, hub, mpref, wpref)
    for k in range(n):
        out += str(k + 1) + ' ' + str(manArray[k]) + '\n'
stdout.write(out)
\$\endgroup\$
  • \$\begingroup\$ @BillalBEGUERADJ Haha agreed :) \$\endgroup\$ – Nannan AV Jan 28 '18 at 8:37
  • \$\begingroup\$ It looks like you're writing FORTRAN in Python. I'll try to find some time to write a more Pythonic solution. \$\endgroup\$ – Eric Duminil Jan 28 '18 at 12:17
  • \$\begingroup\$ The obvious place where time is lost is in the the calls to the index method in findWoman which take time proportional to the length of the list. These could be sped up by making reverse lookup tables. \$\endgroup\$ – Gareth Rees Jan 28 '18 at 12:20
  • \$\begingroup\$ @GarethRees Ok, let me check what reverse lookup tables are and how to implement them! \$\endgroup\$ – Nannan AV Jan 30 '18 at 18:12
6
\$\begingroup\$

I feel lazy to go through the details of your code, but here are few notes you should think about:

  • Your code, as it is, is not scalable. You should re-design it in terms of functions (I think functions are enough for your case, even in some other situations OOP may be a better choice). Functions allow also your code to be reused.

  • In terms of UX, I think you have some more work to do. For instance, when I run your code, I was waiting for something to happen, until I guessed to type in something, but then I had to check your code to see what it expects me to code. That is bad: imagine every software you use, you have to read its code to guess what you have to write or where to click.

  • You should throw a look to PEP 8 (for example, the naming conventions you use are camelCase, Python developers do not like that and you have to comply to the philosophy of Python)

  • Interesting if you throw a glance to: What does if __name__ == “__main__”: do?

That is the big picture I want to share with you for the moment ... maybe I can come back later to provide more useful help, or maybe other members may dive deeper into your code.

\$\endgroup\$
  • 2
    \$\begingroup\$ Well this is a problem on Spoj (I have added the hyperlink in the question now), so typing in comments would give me a wrong answer. I just started coding in Python (originally a JAVA dev) and hence the CamelCases. Will definitely change to Python philosophy when coding in Python though. Do agree with your other points. Thank you :) \$\endgroup\$ – Nannan AV Jan 28 '18 at 9:04
  • \$\begingroup\$ Also it would be great if you could give the source for Point 4 \$\endgroup\$ – Nannan AV Jan 28 '18 at 10:00
  • 2
    \$\begingroup\$ It is okay to do from sys import stdin, stdout, according to PEP8. It is discouraged to do import sys, os, though. \$\endgroup\$ – Graipher Jan 28 '18 at 10:44
  • 1
    \$\begingroup\$ Also, hard-coded input formats like this are usually the only way to beat these competitions. Having a nice argument parser just adds runtime. \$\endgroup\$ – Graipher Jan 28 '18 at 10:46
  • 1
    \$\begingroup\$ thank you very much for the note about the import @Graipher \$\endgroup\$ – Billal Begueradj Jan 28 '18 at 10:47
3
\$\begingroup\$

I have updated the code based on @Billal's suggestions and python code runs faster in a function

time: 0.12

memory: 33M

from sys import stdin, stdout


def find_woman(man_array, woman_array, index, mpref, wpref):
    for woman in mpref[index - 1]:
        if(woman == 0):
            continue
        hub = woman_array[woman - 1]
        if(hub == 0):
            woman_array[woman - 1] = index
            man_array[index - 1] = woman
            return 0
        elif(wpref[woman - 1].index(index) > wpref[woman - 1].index(hub)):
            continue
        else:
            man_array[hub - 1] = 0
            woman_array[woman - 1] = index
            man_array[index - 1] = woman
            return hub


def main():
    out = ''
    t = int(stdin.readline())
    while(t > 0):
        t -= 1
        n = int(stdin.readline())
        mpref = []
        wpref = []
        for _ in range(n):
            w = list(map(int, stdin.readline().split()))
            w[0] = 0
            wpref.append(w)
        for _ in range(n):
            m = list(map(int, stdin.readline().split()))
            m[0] = 0
            mpref.append(m)
        man_array = [0 for _ in range(n)]
        woman_array = [0 for _ in range(n)]
        for k in range(n):
            hub = k + 1
            while(hub != 0):
                hub = find_woman(man_array, woman_array, hub, mpref, wpref)
        for k in range(n):
            out += str(k + 1) + ' ' + str(man_array[k]) + '\n'
    stdout.write(out)


if(__name__ == "__main__"):
    main()
\$\endgroup\$
0
\$\begingroup\$

Your code is too obscure for me, I can't seem to wrap my head around it on a Monday morning. What I do understand is the way you parse the inputs. That way I do this is overwrite te builtin input during testing.

Define the sample data

input_str = '''2
4
1 4 3 1 2
2 2 1 3 4
3 1 3 4 2
4 4 3 1 2
1 3 2 4 1
2 2 3 1 4
3 3 1 2 4
4 3 2 4 1
7
1 3 4 2 1 6 7 5
2 6 4 2 3 5 1 7
3 6 3 5 7 2 4 1
4 1 6 3 2 4 7 5
5 1 6 5 3 4 7 2
6 1 7 3 4 5 6 2
7 5 6 2 4 3 7 1
1 4 5 3 7 2 6 1
2 5 6 4 7 3 2 1
3 1 6 5 4 3 7 2
4 3 5 6 7 2 4 1
5 1 7 6 4 3 5 2
6 6 3 7 5 2 4 1
7 1 7 4 2 6 5 3'''

Define how a line of data is parsed

def parse_people(input, people):
    for _ in range(people):
        person, *prefs = map(int, input().split())
        yield person, prefs

combine it

if(__name__ == "__main__"):
    input = iter(input_str.split('\n')).__next__
    test_cases = int(input())
    for _ in range(test_cases):
        people = int(input())
        women = dict(parse_people(input, people))
        men = dict(parse_people(input, people))
        print(people, men, women)

Then all you need to do when submitting, is removing or commenting the input = iter(input_str.split('\n')).__next__

I've also adopted more descriptive variable names, and instead of

w = list(map(int, stdin.readline().split()))
w[0] = 0
wpref.append(w)

I work with a generator and a dict. The result of my parsin is:

 women
{1: [3, 4, 2, 1, 6, 7, 5],
 2: [6, 4, 2, 3, 5, 1, 7],
 3: [6, 3, 5, 7, 2, 4, 1],
 4: [1, 6, 3, 2, 4, 7, 5],
 5: [1, 6, 5, 3, 4, 7, 2],
 6: [1, 7, 3, 4, 5, 6, 2],
 7: [5, 6, 2, 4, 3, 7, 1]}

That way you don't have to do the if(woman == 0):, and a lot of the indexing becomes easier. 0 or 1- indexing, or even names for input will not make a difference like this.

indexing

Following Gareth Rees' comment, instead of returning lists, you could let parse_people yield a lookup table, changing the call to .index to a dict lookup

def parse_people(input, people):
    for _ in range(people):
        person, *prefs = map(int, input().split())
        yield person, {k: i for i, k in enumerate(prefs)}
women
{1: {1: 3, 2: 2, 3: 0, 4: 1, 5: 6, 6: 4, 7: 5},
 2: {1: 5, 2: 2, 3: 3, 4: 1, 5: 4, 6: 0, 7: 6},
 3: {1: 6, 2: 4, 3: 1, 4: 5, 5: 2, 6: 0, 7: 3},
 4: {1: 0, 2: 3, 3: 2, 4: 4, 5: 6, 6: 1, 7: 5},
 5: {1: 0, 2: 6, 3: 3, 4: 4, 5: 2, 6: 1, 7: 5},
 6: {1: 0, 2: 6, 3: 2, 4: 3, 5: 4, 6: 5, 7: 1},
 7: {1: 6, 2: 2, 3: 4, 4: 3, 5: 0, 6: 1, 7: 5}}

Actual algorithm

After some thinking, I've taken a stab at your algorithm, converting the list-based approach to a dict-based one

parsing people

changed the input to a lookup table:

def parse_people(input, people):
    for _ in range(people):
        person, *prefs = map(int, input().split())
        yield person, {k: i for i, k in enumerate(prefs)}

Find the partners

the part in your main routine, the main difference is that I work with an OrderedDict as lookup table, instead of a list, and I use None as sentinel value instead of 0

def find_partners(people, prefs_women, prefs_men):
    from collections import OrderedDict
    choices_women = OrderedDict(((key, None ) for key in prefs_women))
    choices_men = OrderedDict(((key, None) for key in prefs_men))

    for k in choices_men:
        hub = k
        while(hub is not None):
            hub = find_woman(choices_women, choices_men, hub, prefs_women, prefs_men)
#             print(hub, choices_women)
    return choices_women, choices_men

finding the woman

Here I just tried to convert your code to the different indexing and lookup. By changing the comparison, you can omit the continue statement

def find_woman(choices_women, choices_men, index_man, prefs_women, prefs_men):
    for woman in prefs_men[index_man]:
        hub = choices_women[woman]
        if hub is None:
            choices_women[woman] = index_man
            choices_men[index_man] = woman
            return None
        elif prefs_women[woman][index_man] <= prefs_women[woman][hub]:
            choices_men[hub] = None
            choices_women[woman] = index_man
            choices_men[index_man] = woman
            return hub

combining it

if(__name__ == "__main__"):
    input = iter(input_str.split('\n')).__next__
    from collections import OrderedDict
    test_cases = int(input())
    for _ in range(test_cases):
        people = int(input())
        women = OrderedDict(parse_people(input, people, 'woman', 'man'))
        men = OrderedDict(parse_people(input, people, 'man', 'woman'))
#         print('-----preferences: ', women, men)
        choices_women, choices_men = find_partners(people, women, men)

        for man, woman in choices_men.items():
            print(man, ' ', woman)

I adapted my earlier version slightly

1   3
2   2
3   1
4   4
1   4
2   5
3   1
4   3
5   7
6   6
7   2

NB: for Python 3.6, you can use dict instead of OrderedDict, but that is an implementation detail

bughunting

Since the names of the men and women are the same, to hunt for a bug I changed the parse_people temporary to this:

def parse_people(input, people, sex1='man', sex2 = 'woman'):
    for _ in range(people):
        # person, *prefs = map(int, input().split())
        person, *prefs = input().split()
        # yield person, {k: i for i, k in enumerate(prefs)}
        yield sex1 + '_' + person, {sex2 + '_' + k: i for i, k in enumerate(prefs)}

for a more verbose output. This way I found out I had changed the order of women and men somewhere

\$\endgroup\$
  • \$\begingroup\$ Since I''m relatively new to Python, theres a lot of new stuff in your answer for me. I will go through them slowly and give my update. Thank u :) \$\endgroup\$ – Nannan AV Jan 30 '18 at 7:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.