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 [e-mail] with your suggestions!

Comments

[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);
};

[Daniel Barwikowski]

This will be usefull I guess
Stable Marriage Problem - Numberphile