Daily Coding Problem #292: Teams without Enemies

A teacher must divide a class of students into two teams to play dodgeball. Unfortunately, not all the kids get along, and several refuse to be put on the same team as that of their enemies.

Given an adjacency list of students and their enemies, write an algorithm that finds a satisfactory pair of teams, or returns False if none exists.

  For example, given the following enemy graph you should return the teams {0, 1, 4, 5} and {2, 3}.

  students = {
    0: [3],
    1: [2],
    2: [1, 4],
    3: [0, 4, 5],
    4: [2, 3],
    5: [3]
  }
  
  On the other hand, given the input below, you should return False.

  students = {
    0: [3],
    1: [2],
    2: [1, 3, 4],
    3: [0, 2, 4, 5],
    4: [2, 3],
    5: [3]
  }
      

Solution

The Solution is straight forward. We maintain Two Lists representing two teams. At the same time we also maintain Two Sets representing the enemies of the teams.

We iterate through all the members one by one. We insert the member into eligible list and update the enemies set as well. If we can successfully insert all the members, then we have our solution. If we are unbale to insert all memebers, then the two teams cannot be formed.

WARNING!!

The solution is not as straight forward as it sounds.

It may be possible that the team member inserted previously into any of the list might cause conflict and hence result might not be possible.

  For following example, if we iterate in the order 0, 1, 2, 3, 4, 5 we will enounter 4 is enemies in both the team.

  students = {
    0: [3],
    1: [5],
    2: [4],
    3: [0, 4, 5],
    4: [2, 3],
    5: [3]
  }

  But it has valid team division and that is: {0, 4, 5} and {1, 2, 3}.
      

So for some of the inputs, we might need to iterate in different permutation. For this reason, we need Back Tracking

Implementation

Following is implementation with back tracking.

	/* File: Enemies.java
	* Created: 7/24/2019
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2019 Hogwart Inc.
	*/
	import java.util.*;
	//=======================================================================================
	/**
	* @author Sabbir Manandhar
	* @version 1.0
	*/
	public class Enemies {
	/**
	* Driver method
	*/
	public static void main(String[] args) {
	Map<Integer, int[]> enemyMap = new HashMap<>();
	enemyMap.put(0, new int[]{3});
	enemyMap.put(1, new int[]{2});
	enemyMap.put(2, new int[]{1, 4});
	enemyMap.put(3, new int[]{0, 4, 5});
	enemyMap.put(4, new int[]{2, 3});
	enemyMap.put(5, new int[]{3});
	System.out.println(divide(enemyMap));
	enemyMap = new HashMap<>();
	enemyMap.put(0, new int[]{3});
	enemyMap.put(1, new int[]{2});
	enemyMap.put(2, new int[]{1, 3, 4});
	enemyMap.put(3, new int[]{0, 2, 4, 5});
	enemyMap.put(4, new int[]{2, 3});
	enemyMap.put(5, new int[]{3});
	System.out.println(divide(enemyMap));
	enemyMap = new HashMap<>();
	enemyMap.put(0, new int[]{3});
	enemyMap.put(1, new int[]{5});
	enemyMap.put(2, new int[]{4});
	enemyMap.put(3, new int[]{0, 4, 5});
	enemyMap.put(4, new int[]{2, 3});
	enemyMap.put(5, new int[]{3});
	System.out.println(divide(enemyMap));
	} // main
	//-----------------------------------------------------------------------------------------------
	/**
	* Divide the team into two
	* @param enemyMap
	* @return
	*/
	private static String divide(Map<Integer, int[]> enemyMap) {
	List<Integer> first = new ArrayList<>(), second = new ArrayList<>();
	Set<Integer> firstEnemies = new HashSet<>(), secondEnemies = new HashSet<>();
	return helper(enemyMap, new ArrayList<>(enemyMap.keySet()), 0, first, second, firstEnemies, secondEnemies);
	} // divide
	//-------------------------------------------------------------------------------------
	/**
	* Helper method to divide the team using Back Tracking
	* @param enemyMap
	* @param members
	* @param cursor
	* @param first
	* @param second
	* @param firstEnemies
	* @param secondEnemies
	* @return
	*/
	private static String helper(Map<Integer, int[]> enemyMap, List<Integer> members, int cursor, List<Integer> first, List<Integer> second, Set<Integer> firstEnemies, Set<Integer> secondEnemies) {
	if (cursor == members.size()) {
	return "(" + first.toString() + ", " + second.toString() + ")";
	}
	int member = members.get(cursor);
	if (first.isEmpty() || !firstEnemies.contains(member)) {
	List<Integer> cFirst = new ArrayList<>(first);
	List<Integer> cSecond = new ArrayList<>(second);
	Set<Integer> cFirstEnemies = new HashSet<>(firstEnemies);
	Set<Integer> cSecondEnemies = new HashSet<>(secondEnemies);
	addMember(cFirst, cFirstEnemies, member, enemyMap.get(member));
	String result = helper(enemyMap, members, cursor + 1, cFirst, cSecond, cFirstEnemies, cSecondEnemies);
	if (result != null) return result;
	}
	if (second.isEmpty() || !secondEnemies.contains(member)) {
	List<Integer> cFirst = new ArrayList<>(first);
	List<Integer> cSecond = new ArrayList<>(second);
	Set<Integer> cFirstEnemies = new HashSet<>(firstEnemies);
	Set<Integer> cSecondEnemies = new HashSet<>(secondEnemies);
	addMember(cSecond, cSecondEnemies, member, enemyMap.get(member));
	String result = helper(enemyMap, members, cursor + 1, cFirst, cSecond, cFirstEnemies, cSecondEnemies);
	if (result != null) return result;
	}
	if (!first.isEmpty() && firstEnemies.contains(member) && !second.isEmpty() && secondEnemies.contains(member)) {
	return null;
	}
	return null;
	} // helper
	//-------------------------------------------------------------------------------------
	private static void addMember(List<Integer> team, Set<Integer> teamEnemies, int member, int[] enemies) {
	team.add(member);
	for (Integer enemy : enemies ) {
	teamEnemies.add(enemy);
	}
	} // addMember
	} // Enemies

view raw Enemies.java hosted with ❤ by GitHub

---

---

---