$7.11
November 27, 2009
We’ll work in pennies, because it’s easier than working in dollars and cents; thus, our sum is 711 and our product is 711000000 = 7.11 × 1004. We could form the cross-product of all prices from 1 to 711 and check the sum and product of each one, but there are 7114 = 255551481441 (over a quarter of a trillion) combinations, so that would take a while (it took about twenty minutes on my recent-vintage home computer). Instead, we note that the prices of the four items must come from the list of divisors of 711:
(define div711
(let loop ((d 711) (ds '()))
(cond ((zero? d) ds)
((zero? (modulo 711000000 d))
(loop (- d 1) (cons d ds)))
(else (loop (- d 1) ds)))))
That list has only 62 items and 624 = 14776336 combinations. so it will be much simpler to check. We form the cross-products, order them to eliminate duplicate lists, and check each for the appropriate sum and product:
> (list-of (list a b c d)
(a in div711)
(b in div711) (<= a b)
(c in div711) (<= b c)
(d in div711) (<= c d)
(= (+ a b c d) 711)
(= (* a b c d) 711000000))
((120 125 150 316))
That takes about a sixth of a second to compute the answer. The prices of the four items are $1.20, $1.25, $1.50 and $3.16. We used the list-of macro from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/fqz7hDas. Zbigniew Michalewicz and David B. Fogel give an analytical solution in their book How to Solve It: Modern Heuristics; they factor 711 as 3² · 79 and consider all the possibilities at each multiple of 79.
Programming Praxis 
[…] Praxis – $7.11 By Remco Niemeijer Today’s Programming Praxis problem is an easy one. We’re supposed to give the prices of four items, […]
My Haskell solution (see http://bonsaicode.wordpress.com/2009/11/27/programming-praxis-7-11/ for a version with comments):
divs :: [Int] divs = [x | x <- [1..711], mod (711 * 10^6) x == 0] main :: IO () main = print [(a,b,c,d) | a <- divs, b <- divs, b <= a, c <- divs, c <= b, d <- divs, d <= c, a + b + c + d == 711, a * b * c * d == 711 * 10^6]I’ve made it on Python, but it’s much slower than the proposed solution, about 90 seconds. I’ve tried finding 9.00 with three items (0.5,4.5 and 4.0) and it takes about 5 seconds.
from decimal import Decimal, getcontext from itertools import combinations, product, ifilter import time import operator def solve(dec_number, step, number_of_numbers): integer_range = int(dec_number * 100) all_numbers = [ Decimal(i) * step for i in range(1, integer_range) ] multiples = 1 / reduce(operator.mul, [step] * (number_of_numbers)) correct_numbers = [ i for i in all_numbers if (dec_number * multiples % i) == 0 ] def check(numbers): """Check the numbers added and multiplied are the same""" return sum(numbers) == dec_number == reduce(operator.mul, numbers) #it's naive to get only the combinations, but it's faster posibilities = combinations(correct_numbers, number_of_numbers) filter_mul = ifilter(check, posibilities) return list(filter_mul) if __name__ == '__main__': #Measuring time t1 = time.time() print solve(Decimal('9.00'), Decimal('0.01'), 3) t2 = time.time() print "time 9.00: ", ((t2 - t1)) t1 = time.time() print solve(dec_number=Decimal('7.11'), step=Decimal('0.01'), number_of_numbers=4) t2 = time.time() print "time 7.11: ", ((t2 - t1))The running console (time in seconds)
$python 711.py [(Decimal('0.50'), Decimal('4.00'), Decimal('4.50'))] time 9.00: 4.24505376816 [(Decimal('1.20'), Decimal('1.25'), Decimal('1.50'), Decimal('3.16'))] time 7.11: 97.4396510124Sorry, I don’t know how to highlight the syntaxis…
[ Edit from programmingpraxis: Read the topic “HOWTO: Posting Source Code” on the “Contents” page. I fixed it for you, but in the future you can do it yourself. ]
A triple loop, brute force version in perl. It runs in roughly 5 seconds on my Mac, finding the solution in around 1 second but keeping checking for other solutions.
The lower boundaries on the loops are set so that a solution is found where the 4th item in the most expensive, the 3rd the next most expensive, the 2nd cheaper still and the first the cheapest (allowing for equal priced items).
The upper boundaries on the loops are set remembering that the each item must cost at least 1 and that the total can’t be greater than 711.
The price of the 4th item is set to make the total 711.
#!/usr/bin/perl
use strict;
for (my $a=708; $a>=1 ; $a-= 1) {
for (my $b=(709-$a); $b >=$a ; $b-=1) {
for(my $c=(710-$a-$b); $c>=$b; $c-=1) {
my $d = 711 – $a – $b – $c;
if ($d>$c) {
my $prd = $a*$b*$c*$d;
if ($prd==711000000) {
printf “%3.2f %3.2f %3.2f %3.2f\n”,$a/100,$b/100,$c/100,$d/100;
}
}
}
}
}
A solution in plain old C, using the same trick as PHW’s perl solution:
#include <stdio.h> int main() { int i, j, k, l; for (i = 1; i < 711; i++) for (j = i; j < 711; j++) for (k = j; k < 711; k++) { l = 711 - i - j - k; if (l < 0) break; if (((i*j*k*l) == 711000000)){ printf("%d %d %d %d\n", i,j,k,l); return 0; } } return -1; }This one runs in about 50ms. Without testing for (l<0), it's 180ms. And the stupid version looping all 4 variables takes about 17 seconds.
I wan’t very satisfied with the previous version, so I’ve make a “sigthly less brute” approach, in C to not having to wait forever:
#include <stdio.h> int main() { int w =0, x=0, y=0, z=0; for(w=1;w<711;w++) { for(x=1;x<(711-w);x++) { for(y=1;y<(711-w-x);y++) { z = 711-x-y-w; if((w*x*y*z==711000000)) { printf("w: %d x: %d y: %d z: %d\n", w,x,y,z); } } } } return 0; }I’ve just narrow the fors limits, as you know the final variable can’t be negative. It reduces the time about 4 times for a similar loop than the one from Jebb. As you can see, I’m not limiting just the first solution, but all (which in fact, are the same numbers in different order).
PD: Thank for including the sourcecode tag! I’ve been looking how to change it afterwards, but you can’t change a post :-(
I think calling the simple version “brute force” is misleading. In its fastest form (Jebb’s version), it uses 2,506,497 iterations. The author’s divisor method uses 677,240 iterations, if I understand the list-of macro, plus 711 iterations to initialize the div711 list. The divisor method uses fewer iterations, but not drastically fewer.
But you can combine both methods. Just search the divisors, and bound the search carefully.
In C, for concreteness:
#include <stdio.h> int main() { int a, b, c, d, i, j, k, nd; int divisors[711]; /* generous upper bound */ nd = 0; for (i = 1; i <= 711; i++) if (711000000 % i == 0) divisors[nd++] = i; for (i = 0; i < nd; i++) { a = divisors[i]; for (j = i; j < nd; j++) { b = divisors[j]; for (k = j; k < nd; k++) { c = divisors[k]; d = 711 - a - b - c; if (d < c) break; if (a * b * c * d == 711000000LL) printf("%d %d %d %d\n", a, b, c, d); } } } return 0; }That requires 710 iterations for the first loop and 18,827 for
the second.
But this problem smells as if it has a dynamic programming solution.
[PS: Thanks for the source code formatting tip. I’ll use it in my own ‘blog now.]
Indentation weirded out, sorry. I guess WordPress assumes tab stops every four columns. I assumed eight.
I get 677,040, which is close to your calculation. See http://programmingpraxis.codepad.org/tvysKxmF.
Since the prime factors of 711 are 3, 3, and 79, you could do even better by having d iterate through 1×79, 2×79, … 9×79. See http://programmingpraxis.codepad.org/B0W4qEU0. That reduces the size of the cross-product to 374,976.
677040, correct. I transcribed the number wrong.
It’s not clear to me that d has to be a multiple of 79. Can you explain your reasoning? It seems to me that it could be any of the 62 factors, though it’s at least the fourth root of 711000000 (i.e., greater than 163).
The product 7.11 × 108 factors as 26 × 32 × 56 × 79. The 79 factor has to be there someplace, and d is as good a place as any. And by the way, the multiplier can’t be 7, because there is no 7 in the factorization, can’t be 9, because 9 × 79 = 711 leaving no room for the other factors, and you’ve already demonstrated that it can’t be 1 or 2.
Oh. You dropped the requirement that c <= d. I had missed that.
Thanks for a fun problem.
Rejigged my earlier solution to take advantage of the idea that all 4 costs must be a factor of the overall product. Also (hopefully) I pretty-printed the code this time. The code now completes in less than a second.
#!/usr/bin/perl
use strict;
my $PRODUCT = 711000000;
for (my $a=708; $a>=1 ; $a-= 1) {
if ( ($PRODUCT % $a) !=0 ) {next;}
for (my $b=(709-$a); $b >=$a ; $b-=1) {
if ( ($PRODUCT % $b) !=0 ) {next;}
for (my $c=(710-$a-$b); $c>=$b; $c-=1) {
if ( ($PRODUCT % $c) !=0 ) {next;}
my $d = 711 – $a – $b – $c;
if ($d>$c) {
my $prd = $a*$b*$c*$d;
if ($prd==$PRODUCT) {
printf "%3.2f %3.2f %3.2f %3.2f\n",$a/100,$b/100,$c/100,$d/100;
}
}
}
}
}
/* FWIW — Here’s my Oracle PL/SQL solution */
declare
done boolean := false ;
item4 pls_integer ;
begin
for item1 in 1..711
loop
for item2 in item1..(711-item1)
loop
for item3 in item2..(711-item1-item2)
loop
item4 := 711-(item1+item2+item3) ;
if item1*item2*item3*item4 = 711000000 then
dbms_output.put_line(‘Item 1 = $’||to_char(item1/100,’fm999.00’)) ;
dbms_output.put_line(‘Item 2 = $’||to_char(item2/100,’fm999.00’)) ;
dbms_output.put_line(‘Item 3 = $’||to_char(item3/100,’fm999.00’)) ;
dbms_output.put_line(‘Item 4 = $’||to_char(item4/100,’fm999.00’)) ;
done := true ;
end if ;
exit when done ;
end loop ;
exit when done ;
end loop ;
exit when done ;
end loop ;
end ;
/
Late to the game on this one, but I’m using this site to get some practice writing clojure. Here’s my submission:
(use '[clojure.contrib.combinatorics :only (combinations)]) (filter #(and (= (apply + %) 711) (= (apply * %) 711000000)) (combinations (filter #(zero? (mod 711000000 (int %))) (range 1 712)) 4))Not the fastest by any means, but it gets the job done in about 1.4 secs on my laptop.
[…] 2009 de khelben There’s an fun and not very difficult programming exercise, presented on Programming Praxis . The problem is easy to […]
Here’s my solution. My Java code resembles some of the Python code posted by other commentators.
package com.rohit.classes;
import java.text.DecimalFormat;
public class Seven11Puzzle {
/**
* RohitPhutane…:)
* @param args
*/
public static void main(String[] args) {
for (double four = 1.00; four < 7.12; four += 0.01) {
four = roundTwoDecimals(four);
for (double three = 1.00; three < 7.12; three += 0.01) {
three = roundTwoDecimals(three);
for (double two = 1.00; two < 7.12; two += 0.01) {
two = roundTwoDecimals(two);
for (double one = 0.00; one 7.00
&& roundTwoDecimals(one + two + three + four) ” + one + ” : ” + two
+ ” : ” + three + ” : ” + four);
if (roundTwoDecimals(one + two + three + four) == 7.11
&& roundTwoDecimals(one * two * three
* four) == 7.11) {
System.out.println(one + ” : ” + two + ” : ”
+ three + ” : ” + four);
System.exit(0);
}
}
}
}
}
}
}
private static double roundTwoDecimals(double d) {
DecimalFormat twoDForm = new DecimalFormat(“#.##”);
return Double.valueOf(twoDForm.format(d));
}
}