anjshenoy / choices Goto Github PK

####################################################################################################
#  This application was run using:
####################################################################################################
1. ruby 1.9.2
2. Gems used: rspec2. Installing the rspec gem (version 2.6.0) is required if you want to run tests. 
If you have RVM (see https://rvm.beginrescueend.com) and the bundler gem installed, run "bundle install" 
from the command line. Otherwise just run "gem install rspec" from the command line.
3. To run tests simply type "rake" at the command line.
4. To run the app type "ruby jurgensville.rb path/to/data-file item1 item2 (and so on)" at the command 
line.
5. There is also a config file under config using which this app can be run.
Note: I added a .rvmrc file to create a choices gemset against the ruby 1.9.2 version - so it 
doesn't intefere with any existing gemsets. This will also install bundler and use bundler to install
rspec2. If you don't have rvm, it should not intefere with running the app or tests.

####################################################################################################
# Terms used
####################################################################################################
Line Item: a datastructure representing a food item (or items) and its cost. e.g. "fries" -> 2.00 or 
"burger", "fries" -> 5.00. A restaurant's menu comprises one to many line items.
Order: a list of items to order (against the menu).

Note: A distinction is not needed between single items and "value items" (items which are combinations
of single items, who's total cost is less than the total cost of the individual single items). A
single item is a value menu of one.

####################################################################################################
# Approach used:
####################################################################################################
The solution uses the following approach:
1. Load the datafile: load all restaurants and the menu information for each and set up each 
restaurant.
2. Search: Apply the order items from the command line iteratively through each restaurant
3. For each restaurant, first check if all the order items exist as part of the menu. If not, return 
nil.
4. Find all line items that have at least one item in common with the order set. 
5. Iterate through each of these line items and find the lowest price for the rest of the order
i.e. (order - line item) by applying step #4 recursively.
6. Within a recursion, check if the amount of funds available is greater than or equal to the candidate's
cost. If yes, continue otherwise, move on to the next candidate in the list.

Steps 4,5 and 6 are implemented using the "branch and bound" pattern. The "branch" step is steps 
4,5 where we build branches based on the order items matching the line items. The "bound" step is 
step 6 where a price comparison stops us from moving further along a new branch.

####################################################################################################
# Complexity
####################################################################################################
The complexity of this approach worst case is 2 to the power of n i.e. exponential time. On average,
the complexity would be somewhere between polynomial time and exponential time.

####################################################################################################
# Initial approach used:
####################################################################################################
The first approach used was to store all possible combinations of menu items so that when search items
were supplied, the cost of searching would be a simple lookup. The problem with this approach is
that the number of combinations starts to explode by an order of subset combinations or 2 to the 
power of n-1, which will not scale for large sets of line items

####################################################################################################
# Language of choice: ruby. Why?
####################################################################################################
1. Concise: ruby lets me express myself with as little code as possible. As a case in point consider: 
@line_items.keys.flatten.uniq.sort (restaurant#has_items?)
2. IRB - since it's interpreter-based, I can test as much or as little of my code right away.
3. Dynamic class loading - if I want to add a method to a class, I can simply extend it and add the 
method I want.
4. Easy to use testing framework.