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
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);
}
}
}
Comments