## DEV Community is a community of 891,295 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

dev.to staff

Posted on

# 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!

## Discussion (2)

Brett Martin

JavaScript before trying to refactor:

``````const marry = (queens, kings) => {
const engagements = new Array(queens.length).fill({engaged: false, fiance: -1, preference: Infinity});
const kingsEngaged = new Array(kings.length).fill(false);

let i = 0;
while(true) {
if (kingsEngaged[i]) continue;
for (let j = 0; j < queens.length; j++) {
let currentStatus = engagements[j];
let preference = queens[j].findIndex(id => id === i);

if (currentStatus.fiance === -1) {
kingsEngaged[i] = true;
engagements[j] = {engaged: true, fiance: i, preference };
break;
} else {
if (preference < currentStatus.preference) {
kingsEngaged[currentStatus.fiance] = false;
kingsEngaged[i] = true;
engagements[j] = {engaged: true, fiance: i, preference };
break;
}
}
}

if (kingsEngaged.every(k => k)) break;
i = (i + 1) % kings.length;
}

return engagements.map(status => status.fiance);
};
``````