Join GitHub today
GitHub is home to over 20 million developers working together to host and review code, manage projects, and build software together.
Latest commit 9bb06e9
Nov 27, 2009
|Failed to load latest commit information.|
Use Permutation http://snippets.dzone.com/posts/show/3332 Required Gems ------------- > gem install permutation active_support hpricot Autotest Guide -------------- Please install ZenTest gem > gem install ZenTest Then run > ./autospec Your goal is to: 1. Use a machine where you have Linux or MacOS X running. You can install Linux easily via http://wubi-installer.org/ 2. Make sure you have installed the Ruby framework (1.8.x) and the gems rspec and hpricot. 3. Write Ruby code to solve the problem below. Use Hpricot (http://wiki.github.com/whymirror/hpricot/an-hpricot-showcase) to parse the html input. 4. We want the code to use efficient algorithms. We don't want O(n^2) when O(n) is possible, for example. 5. We want reasonably clean code. No hacking or lack of product code. We understand you may be first learning ruby and we will be patient from that point of view. 6. Further augment the spec with more test cases. One thing that is important is to see how you broke down the problem into smaller components. You should test components independently (unit tests) in addition to the integration test provided. 7. Write a small document explaining the complexity of your code. 8. If you cannot solve the algorithm completely, then please complete all other parts and spec them out so someone could replace the nonfunctional component in a clean manner. If you are having trouble with the full algorithm, try writing an algorithm that works only when you have an operator between every number, e.g., the second and third examples below. 9. Send us back your code/tests/documentation in a tgz, just as we sent you. Useful commands: to run your program: ruby arith_puzzle.rb to run your test suite: spec arith_puzzle_spec.rb The problem: In an old brainteaser you are given a set of digits and a set of operators and asked to arrange the digits and the operators to form an expression that has a particular value. This problem is a variant of that brainteaser. In this problem you will be presented with a sequence of no more than ten digits (not necessarily unique) with an embedded equal sign, and a collection of at least one but no more than five integer operators (from the set '+', '-', '*', and '/'). Your problem is to insert each of the operators between the correct pair of digits so the equation thus formed is arithmetically correct, assuming all operators have the same precedence, and that each side of the expression is evaluated strictly left to right. At least one digit will appear on each side of the equal sign. If there is not an operator between two digits, then those digits are concatenated. For example, you might be given '957=52' and the operators '+' and '*'. Arranging these in the form '9*5+7=52' makes the equation correct. Or you might be given '123=456' and the operations '+', '+', '-', and '*'. If you arrange these in the form '1*2+3=4-5+6' you'll find each side of the equation has the value 5. As a final example consider '135=642' and the operators '+', '+', '*', and '*'. The arrangement '1+3*5=6+4*2' makes each side of the equation have the value 20 (note the strict left-to-right evaluation order on each side of the equation). The division operator will yield only an integer result, and must obviously never be used with a denominator of zero. No value in an expression will require more than six decimal digits. Each operator must be used exactly once. The order in which the digits appear, and the placement of the equal sign cannot be altered. The input will consist of multiple test cases, each test case being enclosed by a div tag with class "case". Within a case, the div tags of class "equation" and class "operators" contain the respective data. Whitespace is to be ignored. The equation and operators divs may occur in any order. Other irrelevant divs present are to be ignored. You can assume that each case will always have an equation and operators. For each test case your are to display the case id, a colon, and the arithmetically correct expression with the operators shown in the proper positions. If there are multiple correct answers, then any one of them will be acceptable. If there is no solution for a particular case, display "NO SOLUTION" instead of the equation. The cases should be output in lexicographical order. Sample Input: <html> <div class="case" id="abc"> <div class="equation"> 957=52 </div> <div class="operators"> + * </div> </div> <div class="foo"> <div class="case" id="def"> <div class="equation"> 123 = 456 </div> <div class="operators"> + + - * </div> </div> <div class="case" id="ghi"> <div class="equation"> 1 3 5=64 2 </div> </div> <div class="operators"> ++** </div> </div> <div class="case" id="mno"> <div class="operators"> / / + </div> <div class="equation"> 8916 = 95 </div> </div> <div class="case" id="jkl"> <div class="equation"> 12=34 </div> <div class="operators"> +- </div> </div> </html> Expected Output: Case abc: 9*5+7=52 Case def: 1*2+3=4-5+6 Case ghi: NO SOLUTION Case jkl: NO SOLUTION Case mno: 8+9/16=9/5