Charging Chaos : Google Code Jam [2014]

Question

I am posting this as a solution to the below problem, to share this with others. If there are any better answers than this, then please do post.

Problem Statement

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 ith switch flips the ith 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.

Answer 1

Tricky part in this question is that there can be multiple ways to flip but we need to find the way which involves minimum flips.

Here is my algorithm to solve this:

1. Lets say there are N Devices needing D1...Dn bits to charge itself and power outlets are available with outputs : M1...Mn bits

2. Take a XOR of power needed by device and power available at outlet gives you an idea of number of bits to be flipped to match device with power outlet.

3. So once we have created a XOR map of device and outlets, numbr of 1s in each binary number indicate number of flips needed. All we need to check is if it is possible to map each of the device to an outlet having same binary number in XOR map.

Here is an example:

Number of Devices [N] : 3
Number of bits in Electric charge [L] : 2
Power need by Device 1 [D1] : 01
Power need by Device 2 [D2]:11
Power need by Device 3 [D3]:10

Power available at Outlet 1 [T1] : 11
Power available at Outlet 2 [T2] : 00
Power available at Outlet 3 [T3] : 10

XOR MAP

      Devices  D1  D2  D3
Outlets
T1             10  00  01
T2             01  11  10
T3             11  01  00

Now in above map it can be seen that 01 is only binary number shared by all devices for different outlet. So answer here is 1 flip as 01 as only one 1 [1 indicates number of flips needed]. And if there were multiple binary numbers shared then we will select number with minimum ones.

Following is the java method implementation for this:

private final int totalParams = 2, N = 0, L = 1;

//Params contains value of N[devices] and L[charging bit]
//cn contains power needed by each device
//cs contains power available at outlet
//return value is the number of bits to be flipped. -1 indicates not possible
private int analyseChargeSetUp(int params[], BitSet[] cn, BitSet[] cs) {

        int retVal = -1;

        BitSet ms[] = new BitSet[params[this.N]];

        ArrayList<ArrayList<BitSet>> bxor = new ArrayList<ArrayList<BitSet>>();

        for (int i = 0; i < params[this.N]; i++) {
            BitSet temp = cn[i];

            // System.arraycopy(cs, 0, ms, 0, params[this.N]);

            for (int k = 0; k < params[this.N]; k++)
                ms[k] = (BitSet) cs[k].clone();

            // System.out.println("Size: " + bxor.size());
            bxor.add(i, new ArrayList<BitSet>());

            for (int j = 0; j < params[this.N]; j++) {
                ms[j].xor(temp);
                bxor.get(i).add(j, ms[j]);
            }
        }

        // HashSet<BitSet> evalSet = new HashSet<BitSet>();
        HashMap<BitSet, BitSet> bitMap = new HashMap<BitSet, BitSet>();

        for (ArrayList<BitSet> bl : bxor) {
            for (int j = 0; j < params[this.N]; j++) {
                BitSet temp1 = bl.get(j);
                // if (!evalSet.add(temp1)) {
                if (bitMap.get(temp1) == null) {
                    BitSet temp2 = new BitSet();
                    temp2.set(j);
                    bitMap.put(temp1, temp2);
                } else {
                    bitMap.get(temp1).set(j);
                }
                // }
            }
        }

        BitSet resultGetter = new BitSet(params[this.L]);
        resultGetter.set(0, params[this.L] + 1, true);
        Iterator<BitSet> itr = bitMap.keySet().iterator();
        BitSet temp3 = new BitSet();

        while (itr.hasNext()) {
            temp3 = itr.next();
            if (bitMap.get(temp3).cardinality() == params[this.N]) {
                if (temp3.cardinality() <= resultGetter.cardinality()) {
                    resultGetter = temp3;
                }
            }

        }

        // if (resultGetter.cardinality() == params[this.L])
        // retVal = 0;
        // else if (resultGetter.cardinality() == 0)
        // retVal = -1;
        // else
        if (resultGetter.cardinality() > params[this.L])
            retVal = -1;
        else
            retVal = resultGetter.cardinality();

        return retVal;

    }

Answer 2

nice post and great solution. I did not know about the BitSet class in Java, thanks!
For the implementation storing all the XOR map is not strictly needed. In fact, it is possible to progressively compute the intersection between the columns of the maps in order to find all the possible switch configurations.
Furthermore, considering that the maximum value for l was 40 (and considering that I did not know of BitSets till ten minutes ago :)), it is possible to use longs for storing the outlets' and devices' configurations.
Thus, this is my solution:

String solution(long[] o, long[] d) {

    HashSet<Long> xors = new HashSet<Long>();

    for (int j = 0; j < o.length; j++) {
        xors.add(o[0] ^ d[j]);
    }

    for (int i = 1; i < o.length; i++) {
        HashSet<Long> xors2 = new HashSet<Long>();
        for (int j = 0; j < o.length; j++) { 
            xors2.add(o[i] ^ d[j]);
        }
        for (Iterator<Long> it = xors.iterator(); it.hasNext();) {
            if (!xors2.contains(it.next())) {
                it.remove();
            }
        }
    }

    if (xors.isEmpty()) {
        return "NOT POSSIBLE";
    }

    Integer min = Integer.MAX_VALUE;
    for (long xor : xors) {
        min = Math.min(min, Long.bitCount(xor));
    }

    return min.toString();
}