This solution is written in Java.
The task:
Three wise men named Caspar, Melchior and Balthazar went to Macy’s Department Store on 34th Street to buy gifts of gold, frankincense, and myrrh. When they took their gifts to the cashier, she multiplied the prices of the items and found a total price of $65.52, but the wise men noticed that she multiplied the numbers and asked her to compute the total price again, but this time using addition instead of multiplication. When she did, the cashier found that the total was exactly the same. What were the individual prices of the three gifts?
Your task is to solve the puzzle and find the three prices.
My solution:
<br /><br />// Author: Will Clausen<br />//<br />// Date: Jan 6, 2013<br />//<br />// This program will solve the Three Wise Men<br />// problem from Programming Praxis<br />// http://programmingpraxis.com/2012/12/28/three-wise-men/<br /><br />import java.util.*; // For lists<br />import java.lang.Math; // For sqrt()<br />import java.text.DecimalFormat; // For converting to dollars at the end.<br /><br />// The solution to this problem will involve factoring multiple times<br />// and determining if the sum of the factors is equal to the cost<br /><br />public class ThreeWiseMenProblem<br />{<br /> public int cost;<br /> public int adjustedCost;<br /> List factors = new ArrayList();<br /><br /> ThreeWiseMenProblem(double price)<br /> {<br /> // The input to the problem will be a double representing the total<br /> // cost. This needs to be adjusted to the number of pennies and then<br /> // again adjusted by a factor of 100 for the purpose of factoring with<br /> // pennies.<br /> adjustedCost = (int) (price*10000);<br /> // The cost in pennies will also be stored.<br /> cost = (int) (price*100);<br /><br /> // This loop produces all of possible combinations of two prices<br /> // (in pennies) that when multiplied produce the total cost. The prices<br /> // (factors of the cost, basically) are stored in a list to be used<br /> // later.<br /> for (int i = 1; i <= (int) Math.sqrt((double) adjustedCost); i ++) {<br /> if (adjustedCost % i == 0) {<br /> Price factor = new Price(i, adjustedCost/i);<br /> factors.add(factor);<br /> }<br /> }<br /> }<br /><br /> // This function generates a solution to the Three Wise Men Problem.<br /> // The helper function factor(Price) does most of the heavy lifting.<br /> public Solution solve()<br /> {<br /> Solution solution = new Solution();<br /><br /> // I need to loop through the list of factors and factor each<br /> // price AGAIN to get three total prices.<br /> // Then, I need to check the sum and If the sum is equal to the<br /> // total cost, then that's the solution!<br /> for (int i = 0; i < factors.size(); i++) {<br /> Price prices = factors.get(i);<br /> solution = factor(prices);<br /><br /> // If a solution is found, then return it and be done.<br /> if ((solution.firstPrice) +<br /> (solution.secPrice) +<br /> (solution.thirdPrice) == ((double) cost)/100) {<br /> return solution;<br /> }<br /> }<br /> // Well, there is no solution if we get here, so just return<br /> // a failed solution.<br /> return solution;<br /> }<br /><br /> // This helper function does the work to generate a solution for the<br /> // Three Wise Men Problem.<br /> public Solution factor(Price prices)<br /> {<br /> // First factor the first price as was done in the constructor for the<br /> // ThreeWiseMenProblem class.<br /> for (int i = 1;<br /> i <= (int) Math.sqrt((double) (prices.first*100));<br /> i++) {<br /> if (prices.first*100 % i == 0) {<br /> // If the three prices add to the total cost, return this<br /> // as the answer!<br /> if (i + (prices.first*100/i) + prices.second == cost) {<br /> Solution solution =<br /> new Solution(i,<br /> (prices.first*100/i),<br /> prices.second);<br /> return solution;<br /> }<br /> }<br /> }<br /><br /> // Now the same thing for the second price.<br /> for (int i = 1; i <= (int) Math.sqrt((double) (prices.second*100)); i++) {<br /> if (prices.second*100 % i == 0) {<br /> // Check the sum as before.<br /> if (i + (prices.second*100/i) + prices.first == cost) {<br /> Solution solution =<br /> new Solution(i,<br /> (prices.second*100/i),<br /> prices.first);<br /> return solution;<br /> }<br /> }<br /> }<br /><br /> // If no solution was found, return a solution that represents that.<br /> Solution failed = new Solution(0, 0, 0);<br /> return failed;<br /> }<br /><br /> // This is merely a wrapper class to allow for keeping prices that are<br /> // factors for the total cost in a list in the three wise men problem.<br /> public class Price<br /> {<br /> public int first;<br /> public int second;<br /><br /> // The only thing needed is a constructor that takes to ints (aka prices).<br /> Price(int one, int two)<br /> {<br /> first = one;<br /> second = two;<br /> }<br /><br /> }<br /><br /> // A wrapper class for taking care of the three solutions<br /> public class Solution<br /> {<br /> public double firstPrice;<br /> public double secPrice;<br /> public double thirdPrice;<br /><br /> // A default constructor is used above and is handy for keeping the code<br /> // a little cleaner.<br /> Solution()<br /> {<br /> firstPrice = 0.00;<br /> secPrice = 0.00;<br /> thirdPrice = 0.00;<br /> }<br /><br /> // A constructor that takes the three prices (in pennies) as arguments.<br /> Solution(int first, int second, int third)<br /> {<br /> // Convert the price in pennies to a price in dollars.<br /> firstPrice = ((double)first)/100.0;<br /> secPrice = ((double)second)/100.0;<br /> thirdPrice = ((double)third)/100.0;<br /> }<br /> }<br />}<br /><br />