Daily Coding Problem #292

Enemies.java

/* 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