Solve a permutation of the stable matching problem for Homebuyers and Neighborhoods.
This was developed on macOS 13.6 using the system Python: v3.8.2. It makes use of the following modules:
- abc
- argparse
- functools
- logging
- operator
- sys
- typing
- unittest
all of which should be part of the core Python library.
No claims are made about backwards/forwards compatibility.
I've made no effort to profile the code in terms of memory or CPU requirements. The matching algorithm was based on Gale-Shapley, which is itself O(n2), and it would be reasonable to expect similar if slightly worse performance here.
# get some helpful instructions:
python3 match.py -h
# read parameters from test_input.txt and execute a match,
# writing results to test_output.txt
python3 match.py test_input.txt --output=test_output.txt
# Run the unit tests:
python3 test.pyI made a few assumptions in writing this code
- it would be fine to borrow code for the matching algorithm; if everyone had to write everything from scratch nothing would ever get done
- No homeowner will leave any neighborhood unranked in their preferences
- We're only concerned with "fit" values as integers (we could be more fine-grained using floats)
- We're always going to get valid data (this is, in practice, a hugely optimistic assumption)
- No homeowner will specify a neighborhood that doesn't exist