skip to Main Content

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


  1. 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:

    • even ->
      no user can have more than numberOfEntries / 2
    • odd -> no user can have more than (numberOfEntries – 1) / 2 + 1

    First you have to go against your intuition, you must create a list, putting together the entries of each user, ie:

    {
      firstName: "John",
      lastName: "Doe",
      song: "Rock",
    },
    {
      firstName: "John",
      lastName: "Doe",
      song: "Jazz",
    },
    {
      firstName: "John",
      lastName: "Doe",
      song: "Folk",
    },
    {
      firstName: "Emily",
      lastName: "Jones",
      song: "Rock",
    },
    {
      firstName: "David",
      lastName: "Williams",
      song: "Rock",
    },
    {
      firstName: "David",
      lastName: "Williams",
      song: "Jazz",
    },
    {
      firstName: "Jane",
      lastName: "Smith",
      song: "Jazz",
    },
    

    then you sort them by number of appearances:
    (if no user reaches the maximums set as conditions, this step can be suppressed).

    {
      firstName: "John",
      lastName: "Doe",
      song: "Rock",
    },
    {
      firstName: "John",
      lastName: "Doe",
      song: "Jazz",
    },
    {
      firstName: "John",
      lastName: "Doe",
      song: "Folk",
    },
    {
      firstName: "David",
      lastName: "Williams",
      song: "Rock",
    },
    {
      firstName: "David",
      lastName: "Williams",
      song: "Jazz",
    },
    {
      firstName: "Emily",
      lastName: "Jones",
      song: "Rock",
    },
    {
      firstName: "Jane",
      lastName: "Smith",
      song: "Jazz",
    },
    

    then you only have to enter them in the output matrix, with the following for:

    let old = 0;
    for( let i = 0; i < listNew.length; i += 2 ) {
        listNew [ i ] = listaOld[ old ]; 
        old++;
    }
    for( let i = 1; i < listNew.length; i += 2 ) {
        listNew [ i ] = listaOld[ old ]
        old++;
    }
    
    Login or Signup to reply.
  2. 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.

    function getSortedGroupsWithMinConflicts(inputData) {
      const userGroups = inputData.map(group => new Set(
        group.map(user => `${user.firstName} ${user.lastName}`
      )));
      const groupIndexes = userGroups.map((_, index) => index);
    
      const allowedNeighbors = new Map();
      for (const [i, group1] of userGroups.entries()) {
        const usersGroup = [...group1];
        const allowed = [];
    
        for (const [j, group2] of userGroups.entries()) {
          if (i === j) {
            continue;
          }
          if (usersGroup.every(user => !group2.has(user))) {
            allowed.push(j);
          }
        }
        allowedNeighbors.set(i, new Set(allowed));
      }
    
      function* iterPermutations(result, conflicts = 0) {
        const usedIndexes = new Set(result);
        const availableIndexes = groupIndexes.filter(i => !usedIndexes.has(i));
        if (!availableIndexes.length) {
          yield { result, conflicts };
        }
    
        for (const index of availableIndexes) {
          const isHasConflict = !allowedNeighbors
            .get(index)
            .has(result[result.length - 1]);
          yield * iterPermutations(
            [...result, index],
            conflicts + isHasConflict,
          );
        }
      }
    
      let bestMinConflictValue = Infinity;
      let resultPermutation = null;
    
      for (const rootIndex of groupIndexes) {
        for (const resultObj of iterPermutations([rootIndex])) {
          if (resultObj.conflicts < bestMinConflictValue) {
            bestMinConflictValue = resultObj.conflicts;
            resultPermutation = resultObj.result;
          }
          if (bestMinConflictValue === 0) {
            break;
          }
        }
      }
    
      return resultPermutation.map(rIndex => inputData[rIndex]);
    }
    

    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.

    Login or Signup to reply.
Please signup or login to give your own answer.
Back To Top
Search