Daily Challenge #155 - Royal Arranged Marriages

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!