Charging Chaos Solution – Google CodeJam

First problem in Google CodeJam 2014, Round 1A

Its about getting the minimum number of switch you need to do to get the desired electric flow.

Problem

Shota the farmer has a problem. He has just moved into his newly built farmhouse, but it turns out that the outlets haven’t been configured correctly for all of his devices. Being a modern farmer, Shota owns a large number of smartphones and laptops, and even owns a tablet for his favorite cow Wagyu to use. In total, he owns N different devices.

As these devices have different specifications and are made by a variety of companies, they each require a different electric flow to charge. Similarly, each outlet in the house outputs a specific electric flow. An electric flow can be represented by a string of 0s and 1s of length L.

Shota would like to be able to charge all N of his devices at the same time. Coincidentally, there are exactly N outlets in his new house. In order to configure the electric flow from the outlets, there is a master control panel with L switches. The i^thswitch flips the i^th bit of the electric flow from each outlet in the house. For example, if the electric flow from the outlets is:

Outlet 0: 10
Outlet 1: 01
Outlet 2: 11

Then flipping the second switch will reconfigure the electric flow to:

Outlet 0: 11
Outlet 1: 00
Outlet 2: 10

If Shota has a smartphone that needs flow “11” to charge, a tablet that needs flow “10” to charge, and a laptop that needs flow “00” to charge, then flipping the second switch will make him very happy!

Misaki has been hired by Shota to help him solve this problem. She has measured the electric flows from the outlets in the house, and noticed that they are all different. Decide if it is possible for Shota to charge all of his devices at the same time, and if it is possible, figure out the minimum number of switches that needs to be flipped, because the switches are big and heavy and Misaki doesn’t want to flip more than what she needs to.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of three lines. The first line contains two space-separated integers N and L. The second line contains N space-separated strings of length L, representing the initial electric flow from the outlets. The third line also contains N space-separated strings of length L, representing the electric flow required by Shota’s devices.

Output

For each test case, output one line containing “Case #x: y“, where x is the case number (starting from 1) and y is the minimum number of switches to be flipped in order for Shota to charge all his devices. If it is impossible, y should be the string “NOT POSSIBLE” (without the quotes). Please note that our judge is not case-sensitive, but it is strict in other ways: so although “not  possible” will be judged correct, any misspelling will be judged wrong. We suggest copying/pasting the string NOT POSSIBLE into your code.

Limits

1 ≤ T ≤ 100.
No two outlets will be producing the same electric flow, initially.
No two devices will require the same electric flow.

Small dataset

1 ≤ N ≤ 10.
2 ≤ L ≤ 10.

Large dataset

1 ≤ N ≤ 150.
10 ≤ L ≤ 40.

Sample

3
3 2
01 11 10
11 00 10
2 3
101 111
010 001
2 2
01 10
10 01

Case #1: 1
Case #2: NOT POSSIBLE
Case #3: 0

Explanation

In the first example case, Misaki can flip the second switch once. The electric flow from the outlets becomes:

Outlet 0: 00
Outlet 1: 10
Outlet 2: 11

Then Shota can use the outlet 0 to charge device 1, the outlet 1 to charge device 2, outlet 2 to charge device 0. This is also a solution that requires the minimum amount number of switches to be flipped.

Solution

We have N electric flow outlets
and N devices require some flow to charge

Let define Switch pattern here, a switch pattern has 0’s and 1’s. ex. 101, denotes we need to switch first and third outlet and keep second outlet as it is.

Now, We first calculate, For each device the switch pattens required from each outlet such that the device can be charged. We will get N such different switch patterns(as each outlet as different flow initially), we store this in a map, map of switch pattern required to the outlet number, done in getSwitchPatternMap.
We do this for all the devices, and put these maps in a list, called mapList in the code.

Now, we need to select the switch pattern which is capable of turning all the devices on. In order to do that we just take the intersection of all the switch patterns in N lists. we do it via getInterSectionOfSwitchPatterns method.

But, For any switch pattern in the intersection, we also need to ensure that they should be operated on different outlets, so we must validate this condition and remove remaining switch patterns from the intersection set. we validate this via isValidSwitchPattern method.

This picture will help you understand the solution to second input

charging chaos solution – google code jam 2014 round 1A

Now we have the set of valid patterns, if its size is zero, then it means it is not possible to charge all devices simultaneously. if there are more than one, simply return the pattern where minimum number of switches are required.

Here is the java code for Charging Chaos problem in Google Code Jam 2014, Round 1A

package codejam2014;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.Reader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class ChargingChaos {
	
	public String getMinimumNumberOfSwitches(int[][] availableFlow, int [][] requiredFlow){
		ArrayList<Map<String, Integer>> mapList = new ArrayList<Map<String,Integer>>();
		for(int i =0; i < requiredFlow.length; i++){
			mapList.add(getSwitchPatternMap(requiredFlow[i], availableFlow));
		}
		Set<String> intersectionSwitchPatterns = getInterSectionOfSwitchPatterns(mapList);
		Set<String> validSwitchPatterns = new HashSet<String>();
		for(String pattern: intersectionSwitchPatterns){
			if(isValidSwitchPattern(mapList, pattern)){
				validSwitchPatterns.add(pattern);
			}
		}
		if(validSwitchPatterns.size() == 0)
		{
			return  "NOT POSSIBLE";
		}
		
		return ""+getMinimunLengthPattern(validSwitchPatterns);
	}
	
	 // Returns the Itersection of patterns in mapList
	private Set<String> getInterSectionOfSwitchPatterns(ArrayList<Map<String, Integer>> mapList){
		Set<String> outSet = mapList.get(0).keySet();
		for(int i = 1; i < mapList.size(); i++){
			Set<String> newCommonSet = new HashSet<String>();
			Set<String> nextSet = mapList.get(i).keySet();
			for(String pattern: nextSet){
				if(outSet.contains(pattern)){
					newCommonSet.add(pattern);
				}
			}
			outSet = newCommonSet;
		}
		
		return outSet;
	}
	
	 // Returns the map of switches required from availableFlows to requiredFlow
	 // key is switchpattern required and value is the index of electric flow outlet

	private Map<String, Integer> getSwitchPatternMap(int[] requiredFlow, int[][] availableFlows){
		Map<String, Integer> requiredSwitches = new HashMap<String, Integer>();
		for(int i=0; i < availableFlows.length; i++){
			requiredSwitches.put(getSwitchPattern(requiredFlow, availableFlows[i]), i);
		}
		return requiredSwitches;
	}
	
	//Simply returns the switches required to change the available electric flow to requiredflow
	private String getSwitchPattern(int[] requiredFlow, int[] availableFlow){
		String out = "";
		for(int i=0; i < availableFlow.length; i++){
			out += availableFlow[i]^requiredFlow[i];
		}
		return out;
	}
	
	//It checks if all the devices can be charged for a switch pattern
	private boolean isValidSwitchPattern(ArrayList<Map<String, Integer>> mapList, String pattern){
		//Contains the index of devices which can be charged for the pattern
		Set<Integer> availableFlowPosSet = new HashSet<Integer>();
		
		for(Map<String, Integer> map: mapList){
			if(availableFlowPosSet.contains(map.get(pattern))){
				return false;
			}
			availableFlowPosSet.add(map.get(pattern));
		}
		return true;
	}
	
	/*
	 * Returns the number od 1's in input String
	 */
	private int getNumberOfOnes(String s){
		int count =0;
		for(Character c: s.toCharArray()){
			if(c.equals('1')){
				count++;
			}
		}
		return count;
	}
	
	private int getMinimunLengthPattern(Set<String> patterns){
		int minimumLength = Integer.MAX_VALUE;
		for(String pattern: patterns){
			int numberOfSwitchesRequired = getNumberOfOnes(pattern);
			if(numberOfSwitchesRequired < minimumLength){
				minimumLength = numberOfSwitchesRequired;
			}
		}
		return minimumLength;
	}
	

	public static void main(String[] argv) {
		try {
			long startTime = System.currentTimeMillis();
			Reader reader = new FileReader("small.in");
			BufferedReader bufReader = new BufferedReader(reader);
			String x = bufReader.readLine();
			int numOfTestCases = Integer.parseInt(x);
			int count = 0;
	
			File file = new File("small.out");
			FileWriter writer = new FileWriter(file);
			for(count =1; count<= numOfTestCases; count++) {
				bufReader.readLine();//ignoring N and L line
				int[][] availableFlows = getIntArray(bufReader.readLine());
				int[][] requiredFlows = getIntArray(bufReader.readLine());
				
				String out = new ChargingChaos().getMinimumNumberOfSwitches(availableFlows, requiredFlows);
				writer.write("Case #" + count + ": "+out+"\n");
				System.out.println("Case #" + count + ":"+out);
			}
			writer.close();
			System.out.println("Total time = " + (System.currentTimeMillis() - startTime));
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	private static int[][] getIntArray(String s){
		String[] strArr = s.split(" ");
		int[][] mat = new int[strArr.length][];
		int i=0;
		for(String str: strArr){
			int[] arr = new int[str.length()];
			int j = 0;
			for(Character c: str.toCharArray()){
				arr[j++] = Integer.parseInt(""+c);
			}
			mat[i++] = arr;
		}
		return mat;
	}
}