I have been wracking my brain for a week on this problem and would appreciate any help or suggestions. I have a form that collects the users first name, last name and song. It stores those values in an object and all objects with the same song property are stored in an array. Example:
[
[
{
firstName: "John",
lastName: "Doe",
song: "Rock",
},
{
firstName: "Emily",
lastName: "Jones",
song: "Rock",
},
{
firstName: "David",
lastName: "Williams",
song: "Rock",
},
],
[
{
firstName: "Alice",
lastName: "Johnson",
song: "Jazz",
},
{
firstName: "John",
lastName: "Doe",
song: "Jazz",
},
{
firstName: "Jane",
lastName: "Smith",
song: "Jazz",
},
],
[
{
firstName: "Jennifer",
lastName: "Miller",
song: "Pop",
},
],
];
The user is able to add multiple people and associate them with a specific song.(sometimes there will only be one person per song and sometimes there could be 30. So the amount of objects per array will vary). After the form has been submitted, the final result is an array containing multiple nested arrays which each contain several objects.
The final result should be a sorted array containing all of the nested arrays but none of the nested arrays with the same first and last name can be adjacent to each other. In the example above, "John Doe" is in the first array and the second array. I can’t have people with the same name adjacent to each other in the final array.
I have tired creating a compareArrays(array1, array2) function that compares both arrays and if it returns true, push that array to the end of the parent array. That solution didn’t work because then I would just end up with a bunch of entries that got pushed to the end but are still adjacent to the other arrays that got pushed to the end but not compared. Example:
function compareArrays(array1, array2) {
if (!array1 || !array2) {
return false;
}
const length1 = array1.length;
const length2 = array2.length;
//iterate through each element of array1
for (let i = 0; i < length1; i++) {
//compare array[i] with each element of array2
for (let j = 0; j < length2; j++) {
if (
array1[i].firstName === array2[j].firstName &&
array1[i].lastName === array2[j].lastName
) {
console.log("Match found!");
return true; //A match was found
}
}
}
return false; //No match was found in array1
}
Then I used that function inside another function that if compareArrays() returned true, would push that array to the end of the parent array.
function pushMatchingToEnd(parentArray) {
let length = parentArray.length;
let i = 0;
while (i < length) {
const currentArray = parentArray[i];
let j = i + 1;
while (j < length) {
const nextArray = parentArray[j];
// Compare the current array to the next array
if (compareArrays(currentArray, nextArray)) {
// If they match, push nextArray to the end of parentArray
parentArray.push(nextArray);
// Remove nextArray from its current position
parentArray.splice(j, 1);
// Decrement length to account for the added element
length--;
// Decrement j to stay at the same index in the next iteration
j--;
}
j++;
}
// Move to the next array in parentArray
i++;
}
}
pushMatchingToEnd(arrayOfArrays)
Unfortunately, this solution doesn’t work because I just end up with a bunch of arrays that got pushed to the end but never compared. So I usually end up with 5 or so arrays that are adjacent to other arrays with matching names.
2
Answers
I’m not going to provide all the code, because my JavaScript is a bit "asleep" and I don’t want to make mistakes, so I’ll leave you the explanation:
Necessary condition for a solution to exist:
if the number of entries is:
no user can have more than numberOfEntries / 2
First you have to go against your intuition, you must create a list, putting together the entries of each user, ie:
then you sort them by number of appearances:
(if no user reaches the maximums set as conditions, this step can be suppressed).
then you only have to enter them in the output matrix, with the following for:
The idea of my algorithm is to try all possible permutations and choose the one with minimal conflict, or the first one where there is no conflict. I checked on your test case and it returns the expected result. The algorithm can probably still be optimized, but nothing has been stated about the performance requirement.
Please, check if the result is as expected and let me know if something is wrong. If further clarifications are needed, please also let me know and I will complete the answer.