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 satisfie...