anjshenoy / choices Goto Github PK
View Code? Open in Web Editor NEWchoices
choices
#################################################################################################### # 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.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.