Setup
In some fictitious land, there are n
queens and n
kings. These members of royalty are single and looking for a heterosexual relationship.
As the Royal Matchmaker, your job is to pair the nobility with each other. At a ball, each of these individuals have met each other and intermingled. Each queen made a list of their favorite kings, and the kings did the same for their favorite queens.
Write a function that will arrange marriages according to the romantic preference of these queens and kings. You will receive an n * m
matrix of integers queens
, encoding the list of preferences for each queen. A similar matrix kings
with their preferences. An array of n
integer with a stable arrangement of marriages. On the i
-th position of the array should be the number of the king that should marry the i
-th queen.
These marriages must be stable. Infidelity would threaten the well being of the country (and your job). A marriage between two individuals is stable as long as:
- Neither of the two are involved in another marriage.
- There is no other mutually preferred match.
Example
The royalty have made lists that look like this:
Queen 0: [King 1, King 0, King 2]
Queen 1: [King 2, King 1, King 0]
Queen 2: [King 0, King 2, King 1]
King 0: [Queen 1, Queen 0, Queen 2]
King 1: [Queen 2, Queen 1, Queen 0]
King 2: [Queen 0, Queen 2, Queen 1]
These lists would be converted to matrices that look like this:
int[][] queens = { {0,1,2}, {1,2,0}, {2,0,1} }; int[][] kings = { {0,1,2}, {1,2,0}, {2,0,1} }; solution: {0, 1, 2}
Tests
int[][] queens = { {1,0,2}, {2,1,0}, {0,2,1} }; int[][] kings = { {1,0,2}, {2,1,0}, {0,2,1} };
Good luck!
This challenge comes from NotTuringComputableError on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!
Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!
Top comments (2)
JavaScript before trying to refactor:
This will be usefull I guess
Stable Marriage Problem - Numberphile