Saturday, March 15, 2014

Practicing for the Google Code Jam - Milkshake

I'm trying to practice for the Google Code Jam. In particular, I want to blog about the Milkshake problem (Round 1A 2008). The problem definition could be read here. My idea is to do a dijkstra graph search algorithm to expand sorted nodes. The node consists of :
  • a state array of the milkshake preparation, * stands for undecided, 0 stands for unmalted, and 1 stands for malted.
  • satisfied customer count
  • satisfied customer boolean array
A customer is said to be satisfied if one of the decided preparation contains one of his/her milkshake flavor preference. The nodes were sorted first by malted flavor count, and then by satisfied customer count. In Dijkstra's terms, we are doing graph traversal on the nodes minimizing cost, whereas the cost is defined as the malted flavor count, and the destination is defined as the condition where all customers are satisfied. The new nodes are defined as a new state where one of the customer's flavors are satisfied. We skip satisfied customers because they have no effect on the world state and objective satisfaction. My first solution failed to solve the small problem set, my basic ideas were not wrong, but inefficient. The source for the first solution is :
package yudhi.pkg;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * User: yudhi
 * Date: 3/15/14
 * Time: 4:00 PM
 * To change this template use File | Settings | File Templates.
 */
public class Milkshake {
    public Milkshake(int flavorCnt, Customer[] customerList) {

        this.flavorCnt = flavorCnt;
        this.customers = customerList;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String testCasesStr= br.readLine();
        int testCases = Integer.parseInt(testCasesStr);
        for (int caseNo=1; caseNo<=testCases; caseNo++)
        {
            String flavorCntStr = br.readLine();
            int flavorCnt = Integer.parseInt(flavorCntStr);
            int custCount = Integer.parseInt(br.readLine());
            Customer[] customerList = new Customer[custCount];
            for (int custIdx=0; custIdx<custCount; custIdx++)
            {
               String custspec = br.readLine();
               String[] words = custspec.split(" ");
               int custFlavorCnt = Integer.parseInt(words[0]);
               int[] likedFlavors = new int[custFlavorCnt];
               boolean[] likeMalted = new boolean[custFlavorCnt];
               for (int i=0; i<custFlavorCnt; i++)
               {
                   likedFlavors[i]= Integer.parseInt(words[i*2+1]);
                   likeMalted[i] = (Integer.parseInt(words[i*2+2]))>0;

               }
               customerList[custIdx] = new Customer(custIdx,custFlavorCnt,likedFlavors,likeMalted);
            }
            Milkshake a = new Milkshake(flavorCnt+1,customerList); // hack because our flavors start from 0
            Node result = a.doDijkstra();
            if (result == null)
            {
                System.out.println("Case #" + caseNo+": IMPOSSIBLE");
            }
            else
            {
                System.out.print("Case #" + caseNo+":");
                for (int j=1; j<= flavorCnt; j++) // start from 1
                {
                    System.out.print(' ');
                    if (result.state[j]=='*') System.out.print('0'); else
                    System.out.print(result.state[j]);
                }
                System.out.println();

            }

        }

    }
    final Customer[] customers;
    final int flavorCnt;
    public Node doDijkstra()
    {
        PriorityQueue<Node> nodesToOpen = new PriorityQueue<Node>();
        nodesToOpen.add(initialNode());
        Node answer = null;
        while (!nodesToOpen.isEmpty())
        {
            Node n = nodesToOpen.poll();
            if (n.satisfiedCnt == customers.length) {
                answer = n;
                break;
            }
            for (int custIdx=0; custIdx< customers.length; custIdx++)
            {
                if (n.satisfiedStates[custIdx]) continue;
                List<Node> newNodes = n.generateNewNodes(customers[custIdx]);
                for (Node newN: newNodes)
                {
                    nodesToOpen.add(newN);
                }
            }
        }
        return answer;
    }
    public static class Customer{
        final   int index;
        final int flavorCnt;
        final int[] likedFlavors;
        final boolean[] likedMalted;

        public Customer(int custIdx, int custFlavorCnt, int[] likedFlavors, boolean[] likeMalted) {

            this.index = custIdx;
            this.flavorCnt= custFlavorCnt;
            this.likedFlavors = likedFlavors;
            this.likedMalted = likeMalted;
        }
    }

    public Node initialNode()
    {
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<flavorCnt; i++ )
            sb.append('*');
        return new Node(sb.toString().toCharArray());
    }

    static char[] changeState(char[] origState, int flavorNo, boolean likeMalted)
    {
        char[] istate = origState.clone();
        if (likeMalted) {
            istate[flavorNo] = '1';
        }  else istate[flavorNo] = '0';
        return istate;
    }
    public class Node implements Comparable<Node> {
        final char[] state;
        final int satisfiedCnt;
        final int maltCost;
        final boolean[] satisfiedStates;
        List<Node> generateNewNodes(Customer c)
        {
            List<Node> r = new ArrayList<Node>();
            if (satisfiedStates[c.index]) return r;
            for (int flavorIdx=0; flavorIdx<c.flavorCnt; flavorIdx++)
            {
                int flavorNo = c.likedFlavors[flavorIdx];
                boolean likeMalted = c.likedMalted[flavorIdx];
                char currentFlavorState = state[flavorNo];
                if (currentFlavorState == '*')
                {
                   char[] newstate = changeState(this.state,flavorNo,likeMalted);
                   r.add(new Node(newstate));
                }
            }
            return r;
        }

        public Node(char[] nstate)
        {
            state = nstate;
            int cntSatisfied=0;
            int cost =0;
            boolean[] satisfiedStates = new boolean[customers.length];
            for (int j=0; j<flavorCnt; j++)
            {
               if (nstate[j]=='1') cost++;
            }
            maltCost = cost;
            for (Customer c : customers)
            {
               boolean thisSatisfied = false;
               for (int i=0; i<c.flavorCnt; i++)
               {
                   int flavorNo = c.likedFlavors[i];
                   boolean likeMalted = c.likedMalted[i];
                   if (likeMalted)
                   {
                        if (state[flavorNo]== '1') thisSatisfied = true;
                   } else {
                       if (state[flavorNo]== '0') thisSatisfied = true;
                   }
               }
                if (thisSatisfied) {
                    cntSatisfied ++;
                    satisfiedStates[c.index] =true;
                } else satisfiedStates[c.index] = false;
            }
            satisfiedCnt = cntSatisfied;
            this.satisfiedStates =satisfiedStates;
        }

        @Override
        public int compareTo(Node o) {
            if (this.maltCost < o.maltCost)
                return -1;
            if (this.maltCost > o.maltCost)
                return 1;
            if (this.satisfiedCnt > o.satisfiedCnt)
                return -1;
            if (this.satisfiedCnt < o.satisfiedCnt)
                return 1;
            return 0;

        }
    }
}




Because of the failure solving first problem set, I changed the algorithm a bit to the second solution, starting from state '0' instead of '*' and allowing changes on already set states :
 
package yudhi.pkg;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * User: yudhi
 * Date: 3/15/14
 * Time: 4:00 PM
 * To change this template use File | Settings | File Templates.
 */
public class MilkshakeB {
    public MilkshakeB(int flavorCnt, Customer[] customerList) {

        this.flavorCnt = flavorCnt;
        this.customers = customerList;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String testCasesStr= br.readLine();
        int testCases = Integer.parseInt(testCasesStr);
        for (int caseNo=1; caseNo<=testCases; caseNo++)
        {
            String flavorCntStr = br.readLine();
            int flavorCnt = Integer.parseInt(flavorCntStr);
            int custCount = Integer.parseInt(br.readLine());
            Customer[] customerList = new Customer[custCount];
            for (int custIdx=0; custIdx<custCount; custIdx++)
            {
                String custspec = br.readLine();
                String[] words = custspec.split(" ");
                int custFlavorCnt = Integer.parseInt(words[0]);
                int[] likedFlavors = new int[custFlavorCnt];
                boolean[] likeMalted = new boolean[custFlavorCnt];
                for (int i=0; i<custFlavorCnt; i++)
                {
                    likedFlavors[i]= Integer.parseInt(words[i*2+1]);
                    likeMalted[i] = (Integer.parseInt(words[i*2+2]))>0;

                }
                customerList[custIdx] = new Customer(custIdx,custFlavorCnt,likedFlavors,likeMalted);
            }
            MilkshakeB a = new MilkshakeB(flavorCnt+1,customerList); // hack because our flavors start from 0
            Node result = a.doDijkstra();
            if (result == null)
            {
                System.out.println("Case #" + caseNo+": IMPOSSIBLE");
            }
            else
            {
                System.out.print("Case #" + caseNo+":");
                for (int j=1; j<= flavorCnt; j++) // start from 1
                {
                    System.out.print(' ');
                    if (result.state[j]=='*') System.out.print('0'); else
                        System.out.print(result.state[j]);
                }
                System.out.println();

            }

        }

    }
    final Customer[] customers;
    final int flavorCnt;
    public Node doDijkstra()
    {
        PriorityQueue<Node> nodesToOpen = new PriorityQueue<Node>();
        HashSet<Node> knownNodes = new HashSet<Node>();
        Node init = initialNode();
        nodesToOpen.add(init);
        knownNodes.add(init);

        Node answer = null;
        while (!nodesToOpen.isEmpty())
        {
            Node n = nodesToOpen.poll();
            if (n.satisfiedCnt == customers.length) {
                answer = n;
                break;
            }
            for (int custIdx=0; custIdx< customers.length; custIdx++)
            {
                if (n.satisfiedStates[custIdx]) continue;
                List<Node> newNodes = n.generateNewNodes(customers[custIdx]);
                for (Node newN: newNodes)
                {
                    if (!knownNodes.contains(newN))
                    {
                        nodesToOpen.add(newN);
                        knownNodes.add(newN);
                    }
                }
            }
        }
        return answer;
    }
    public static class Customer{
        final   int index;
        final int flavorCnt;
        final int[] likedFlavors;
        final boolean[] likedMalted;

        public Customer(int custIdx, int custFlavorCnt, int[] likedFlavors, boolean[] likeMalted) {

            this.index = custIdx;
            this.flavorCnt= custFlavorCnt;
            this.likedFlavors = likedFlavors;
            this.likedMalted = likeMalted;
        }
    }

    public Node initialNode()
    {
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<flavorCnt; i++ )
            sb.append('0');
        return new Node(sb.toString().toCharArray());
    }

    static char[] changeState(char[] origState, int flavorNo, boolean likeMalted)
    {
        char[] istate = origState.clone();
        if (likeMalted) {
            istate[flavorNo] = '1';
        }  else istate[flavorNo] = '0';
        return istate;
    }
    public class Node implements Comparable<Node> {
        final char[] state;
        final int satisfiedCnt;
        final int maltCost;
        final boolean[] satisfiedStates;
        List<Node> generateNewNodes(Customer c)
        {
            List<Node> r = new ArrayList<Node>();
            if (satisfiedStates[c.index]) return r;
            for (int flavorIdx=0; flavorIdx<c.flavorCnt; flavorIdx++)
            {
                int flavorNo = c.likedFlavors[flavorIdx];
                boolean likeMalted = c.likedMalted[flavorIdx];
                char currentFlavorState = state[flavorNo];
                // don't care current state
                char[] newstate = changeState(this.state,flavorNo,likeMalted);
                Node newNode = new Node(newstate);
                r.add(newNode);

            }
            return r;
        }

        public Node(char[] nstate)
        {
            state = nstate;
            int cntSatisfied=0;
            int cost =0;
            boolean[] satisfiedStates = new boolean[customers.length];
            for (int j=0; j<flavorCnt; j++)
            {
                if (nstate[j]=='1') cost++;
            }
            maltCost = cost;
            for (Customer c : customers)
            {
                boolean thisSatisfied = false;
                for (int i=0; i<c.flavorCnt; i++)
                {
                    int flavorNo = c.likedFlavors[i];
                    boolean likeMalted = c.likedMalted[i];
                    if (likeMalted)
                    {
                        if (state[flavorNo]== '1') thisSatisfied = true;
                    } else {
                        if (state[flavorNo]== '0') thisSatisfied = true;
                    }
                }
                if (thisSatisfied) {
                    cntSatisfied ++;
                    satisfiedStates[c.index] =true;
                } else satisfiedStates[c.index] = false;
            }
            satisfiedCnt = cntSatisfied;
            this.satisfiedStates =satisfiedStates;
        }

        @Override
        public int compareTo(Node o) {
            if (this.maltCost < o.maltCost)
                return -1;
            if (this.maltCost > o.maltCost)
                return 1;
            if (this.satisfiedCnt > o.satisfiedCnt)
                return -1;
            if (this.satisfiedCnt < o.satisfiedCnt)
                return 1;
            return 0;

        }
        @Override
        public boolean equals(Object o)
        {
            if (o instanceof Node)
            { Node oth = (Node)o;
               if (Arrays.equals(oth.state,this.state)) return true;
            }
            return false;
        }
        @Override
        public int hashCode()
        {
            return Arrays.hashCode(this.state);
        }


    }
}

Now the small problem set is solved, but run out of memory for the large problem set. The third solution changes the dijkstra algorithm again, I even renamed it because I weren't sure it is still dijkstra. Essentially it mixes customer iteration sorted by possibilites (the lesser possibilities iterated first) with dijkstra-style node opening. And only one customer is chosen to be opened in each iteration. The benefits are zero possibility cases are identified as dead ends and not opened further. Here are the sources, these code solved the large problem set :
package yudhi.pkg;

/**
 * Created with IntelliJ IDEA.
 * User: yudhi
 * Date: 3/15/14
 * Time: 5:59 PM
 * To change this template use File | Settings | File Templates.
 */


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * User: yudhi
 * Date: 3/15/14
 * Time: 4:00 PM
 * To change this template use File | Settings | File Templates.
 */
public class MilkshakeC {
    public MilkshakeC(int flavorCnt, Customer[] customerList) {

        this.flavorCnt = flavorCnt;
        this.customers = customerList;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String testCasesStr= br.readLine();
        int testCases = Integer.parseInt(testCasesStr);
        for (int caseNo=1; caseNo<=testCases; caseNo++)
        {
            String flavorCntStr = br.readLine();
            int flavorCnt = Integer.parseInt(flavorCntStr);
            int custCount = Integer.parseInt(br.readLine());
            Customer[] customerList = new Customer[custCount];
            for (int custIdx=0; custIdx<custCount; custIdx++)
            {
                String custspec = br.readLine();
                String[] words = custspec.split(" ");
                int custFlavorCnt = Integer.parseInt(words[0]);
                int[] likedFlavors = new int[custFlavorCnt];
                boolean[] likeMalted = new boolean[custFlavorCnt];
                for (int i=0; i<custFlavorCnt; i++)
                {
                    likedFlavors[i]= Integer.parseInt(words[i*2+1]);
                    likeMalted[i] = (Integer.parseInt(words[i*2+2]))>0;

                }
                customerList[custIdx] = new Customer(custIdx,custFlavorCnt,likedFlavors,likeMalted);
            }
            MilkshakeC a = new MilkshakeC(flavorCnt+1,customerList); // hack because our flavors start from 0
            Node result = a.doSomething();
            if (result == null)
            {
                System.out.println("Case #" + caseNo+": IMPOSSIBLE");
            }
            else
            {
                System.out.print("Case #" + caseNo+":");
                for (int j=1; j<= flavorCnt; j++) // start from 1
                {
                    System.out.print(' ');
                    if (result.state[j]=='*') System.out.print('0'); else
                        System.out.print(result.state[j]);
                }
                System.out.println();

            }

        }

    }
    final Customer[] customers;
    final int flavorCnt;
    public Node doSomething()
    {
        PriorityQueue<Node> nodesToOpen = new PriorityQueue<Node>();
        HashSet<Node> knownNodes = new HashSet<Node>();
        final Node init = initialNode();
        nodesToOpen.add(init);
        knownNodes.add(init);
        Node answer = null;
        while (!nodesToOpen.isEmpty())
        {
            final Node n = nodesToOpen.poll();
            if (n.satisfiedCnt == customers.length) {
                answer = n;
                break;
            }
            ArrayList<Customer> customersList = new ArrayList<Customer>();
            customersList.addAll(Arrays.asList(this.customers));
            Collections.sort(customersList, new Comparator<Customer>() {
                @Override
                public int compare(Customer o1, Customer o2) {
                    return o1.possibilities(n) - o2.possibilities(n);  //To change body of implemented methods use File | Settings | File Templates.
                }
            });
            Customer chosenCustomer = null;
            for (Customer currentCustomer : customersList )
            {
                int custIdx = currentCustomer.index;
                if (n.satisfiedStates[custIdx]) continue;
                if (currentCustomer.possibilities(n)==0) {
                    break;
                }
                chosenCustomer = currentCustomer; break;
            }
            if (chosenCustomer != null)
            {
                List<Node> newNodes = n.generateNewNodes(chosenCustomer);
                for (Node newN: newNodes)
                {
                    if (!knownNodes.contains(newN))
                    {
                        nodesToOpen.add(newN);
                        knownNodes.add(newN);
                    }
                }
            }
        }
        return answer;
    }
    public static class Customer{
        final   int index;
        final int flavorCnt;
        final int[] likedFlavors;
        final boolean[] likedMalted;
        public int possibilities(Node n)
        {
            int cnt = 0;      // 0 means impossible
            for (int i=0; i<flavorCnt;i++)
            {
                int flavorNo = likedFlavors[i];
                if (n.state[flavorNo] == '*') cnt++;
                if ((n.state[flavorNo] == '1') && likedMalted[i]) return 1; // already satisfied
                if ((n.state[flavorNo] == '0') && (!likedMalted[i])) return 1; // already satisfied

            }
            return cnt;
        }
        public Customer(int custIdx, int custFlavorCnt, int[] likedFlavors, boolean[] likeMalted) {

            this.index = custIdx;
            this.flavorCnt= custFlavorCnt;
            this.likedFlavors = likedFlavors;
            this.likedMalted = likeMalted;
        }
    }

    public Node initialNode()
    {
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<flavorCnt; i++ )
            sb.append('*');
        return new Node(sb.toString().toCharArray());
    }

    static char[] changeState(char[] origState, int flavorNo, boolean likeMalted)
    {
        char[] istate = origState.clone();
        if (likeMalted) {
            istate[flavorNo] = '1';
        }  else istate[flavorNo] = '0';
        return istate;
    }
    public class Node implements Comparable<Node> {
        final char[] state;
        final int satisfiedCnt;
        final int maltCost;
        final boolean[] satisfiedStates;
        List<Node> generateNewNodes(Customer c)
        {
            List<Node> r = new ArrayList<Node>();
            if (satisfiedStates[c.index]) return r;
            for (int flavorIdx=0; flavorIdx<c.flavorCnt; flavorIdx++)
            {
                int flavorNo = c.likedFlavors[flavorIdx];
                boolean likeMalted = c.likedMalted[flavorIdx];
                char currentFlavorState = state[flavorNo];
                // don't care current state
                char[] newstate = changeState(this.state,flavorNo,likeMalted);
                Node newNode = new Node(newstate);
                r.add(newNode);

            }
            return r;
        }

        public Node(char[] nstate)
        {
            state = nstate;
            int cntSatisfied=0;
            int cost =0;
            boolean[] satisfiedStates = new boolean[customers.length];
            for (int j=0; j<flavorCnt; j++)
            {
                if (nstate[j]=='1') cost++;
            }
            maltCost = cost;
            for (Customer c : customers)
            {
                boolean thisSatisfied = false;
                for (int i=0; i<c.flavorCnt; i++)
                {
                    int flavorNo = c.likedFlavors[i];
                    boolean likeMalted = c.likedMalted[i];
                    if (likeMalted)
                    {
                        if (state[flavorNo]== '1') thisSatisfied = true;
                    } else {
                        if (state[flavorNo]== '0') thisSatisfied = true;
                    }
                }
                if (thisSatisfied) {
                    cntSatisfied ++;
                    satisfiedStates[c.index] =true;
                } else satisfiedStates[c.index] = false;
            }
            satisfiedCnt = cntSatisfied;
            this.satisfiedStates =satisfiedStates;
        }

        @Override
        public int compareTo(Node o) {
            if (this.maltCost < o.maltCost)
                return -1;
            if (this.maltCost > o.maltCost)
                return 1;
            if (this.satisfiedCnt > o.satisfiedCnt)
                return -1;
            if (this.satisfiedCnt < o.satisfiedCnt)
                return 1;
            return 0;

        }
        @Override
        public boolean equals(Object o)
        {
            if (o instanceof Node)
            { Node oth = (Node)o;
                if (Arrays.equals(oth.state, this.state)) return true;
            }
            return false;
        }
        @Override
        public int hashCode()
        {
            return Arrays.hashCode(this.state);
        }


    }
}

No comments: