Matchmaking

This challenge is extremely interesting because it can be applied to many fields in game development and, a bit modified of course, also to a diversity of other problem that rely on grouping users together. The idea is to use the concept of coloring graphs to find groupings for multiplayer games. So to fully understand this, you should probably be familiar with bipartite graph coloring. If you need to freshen up on this topic i recommend you the following resource which explains it quite clearly:

Ok! Now that we are ready, let’s dive right into the challenge. The problem description is as follows:

You are developing a matchmaking system for your online game and you prioritize that strangers play against each other. This means that if two players a and b are not friends, then they should be in opposite teams. Since you want some diversity you’ll allow that friends are grouped in different teams (So two strangers are always in different teams while two friends might be). Develop an algorithm that determines wheter such a grouping is possible given the needed friendship informations.

  • Input:
    • The first line contains three integers k,l,m, denoting the number of people attending in the game, the total number of “not friends” relations and a player ID.
    • The next l lines each contain two integers a,b, indicating that the player a is not friends with person b. (You can assume that friendships are symmetric, so if a is not friends with b then b is also not friends with a)
  • Output:
    • Output a list of player ID’s that are in the opposite team of m ordered increasingly, or “false” if a matchmaking with the given properties is not possible
  • Constraints:
    • Your algorithm should have a time complexity of O(k + l)

Now that we have a task let’s start working on a solution. As i’ve already hinted such a problem can be solved using bipartite graph coloring. Let us first define how we model a graph from the given data:

Let G=(V,E) be an undirected and unweighted graph as follows:

  • Every player of our game is represented by a distinct node in G. So we have

        \begin{align*}|V| = k\end{align*}

  • Two nodes x,y \in V are connected with an edge, exactly if the player represented by x is not friends with the player represented by y. So we have

        \begin{align*}\forall x,y \in V(e=(x,y) \in E \Leftrightarrow x \text{   is not friends with   } y)\end{align*}


    and

        \begin{align*}|E| = l\end{align*}

The trick is now that a biparite partition of G corresponds exactly to a grouping that we want. And here’s why:

By the definition of a bipartite partition V = A \uplus B, we have

    \begin{align*}\forall x,y \in A \nexists e=(x,y) \in E \;\;\; \text{and}  \;\;\;  \forall x,y \in B \nexists e=(x,y) \in E   \end{align*}


so grouping the players into the two groups A and B assures us that no two players who are not friends are in the same group (otherwise there would be an edge between them and thus A \uplus B wouldn’t be a bipartition).

Perfect! Everything that’s left is an implementation. As always i’ll solve this problem in java. The same concepts will of course work just as well with other languages. First of all we need to implement a function that partitions a given graph into a bipartition. We can use a modified Breadth-First-Search to do this. Basically we start at some node and give it a color. All it’s neighbours will be colored differently and so on. This way we color the graph layer by layer and we can even check if a bipartition is possible (as soon as we can not color a node differently from its neighbours we can simply return false).

/**
   * Performs a bipartit partitioning on a given graph
   * @param source start node of bfs
   * @param adjList the graph as an adjacency list
   * @param coloring partition array
   * @return true if partition was possible, false if not. Partition itself is stored in coloring array
   */
  static boolean partitioningBfs(int source, LinkedList<Integer>[] adjList, int[] coloring) {
    LinkedList<Integer> queue = new LinkedList<Integer>(); //Used for bfs traversal
    
    //Start bfs from node 0
    queue.add(source);
    coloring[source] = 1;
    
    //Perform bfs from 0
    while(queue.size() > 0) {
      int s = queue.removeFirst();
      for(int neighbour: adjList[s]) {
        if(coloring[neighbour] == 0) {
          if(coloring[s] == 1) {coloring[neighbour] = 2;}
          else {coloring[neighbour] = 1;}
          queue.add(neighbour);
        }
        //If neighbour must have the same color as source then not bipartit
        else if(coloring[neighbour] == coloring[s]) {
          return false;
        }
        
        
      }
    }
    
    //Repeat for potentially remaining other connected components
    for(int i = 0; i < coloring.length; i++) {
      if(coloring[i] == 0) {return partitioningBfs(i, adjList, coloring);}
    }
    
    //At this point we have partitioned the graph sucessfully, so return true
    return true;
    
  }

Next we need a function that builds a list of players according to the output specification. As we’ve seen an opponent of a player is in the opposite partition, so we can traverse the coloring array and add all players colored differently than our given player to a list, sort said list and return it. Should a bipartition not be possible, we simply return null.

 /**
   * Check if it is possible to group all non-friends in opposite teams.
   * @param adjList A graph that represents non-friendship between the players
   * @param opp the player whose opponents should be in the list
   * @return a list of players that are not in the same team as the given player, 
   * empty list if matchmaking is not possible
   */
  static LinkedList<Integer> getOpponents(LinkedList<Integer>[] adjList, int opp) {
    int[] coloring = new int[adjList.length]; //Stores the partition of a node [0 is unpartitioned]
    
    if(partitioningBfs(0,adjList,coloring)) {
      
      //Partitioning successful, build list
      LinkedList<Integer> out = new LinkedList<Integer>();
      int playPart = coloring[opp];
      for(int i = 0; i<coloring.length; i++) {
        if(coloring[i] != playPart) {
          out.add(i);
        }
      }
      
      //Sort list in ascending order
      Collections.sort(out);
      
      //Return list
      return out;
      
    } else { return new LinkedList<Integer>(); }
  }

Finally all that’s left is handling I/O by building a graph from the input and outputting either the list elements or “false

private static int m;
private static LinkedLIst<Integer>[] adjList;

public static void testCase() {
    getAndStoreUserInput();
    LinkedList<Integer> opponents = getOpponents(adjList, m);
    printAnswer(opponents);
}

private static void getAndStoreUserInput() {
    Scanner scanner = new Scanner(System.in);

    int k = scanner.nextInt();
    int l = scanner.nextInt();
    m = scanner.nextInt(); 
    
    adjList = new LinkedList[k];     
    for(int i = 0; i<k; i++) {
      adjList[i] = new LinkedList<Integer>();
    }
        
    for(int i = 0; i<l; i++) {
      int a = scanner.nextInt();
      int b = scanner.nextInt();
          
      adjList[a].add(b);
      adjList[b].add(a);
    }

    scanner.close();
}

private static void printAnswer(LinkedList<Integer> opponents) {
    StringBuilder str = new StringBuilder();
    for(int opponendID: opponents) {
        str.append(opponendID + " ");
    }
    String builtString = str.toString();
    String out = builtString.equals("") ? "false": builtString;
    System.out.println(out);
}

Runtime analysis:
Building the graph from input takes O(k + l) (since we have two loops with constant body, one takes k and one l iterations). Building the output takes O(k) since there can not be more opponents than players. Building the opponent list takes O(k) since we have to iterate once through the colorings array which has as many items as G has nodes. Last but not least we perform our modified bfs exactly once on the graph. Our modifications did not change the runtime of bfs and bfs is known to run in O(k + l). So our total runtime is:

    \begin{align*}O(k+l) + O(k) + O(k) + O(k+l) = O(4k + 2l) = O(k + l)\end{align*}


Which means that we have met the runtime requirements