$7.11

November 27, 2009

A mathematician purchased four items in a grocery store. He noticed that when he added the prices of the four items, the sum came to $7.11, and when he multiplied the prices of the four items, the product came to $7.11.

Your task is to determine the prices of the four items. When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

19 Responses to “$7.11”

  1. […] 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, […]

  2. Remco Niemeijer said

    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]
    
  3. Jaime said

    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.4396510124
    
  4. Jaime said

    Sorry, 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. ]

  5. PHW said

    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;
    }
    }
    }
    }
    }

  6. Jebb said

    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.

  7. Jaime said

    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 :-(

  8. kbob said

    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.]

  9. kbob said

    Indentation weirded out, sorry. I guess WordPress assumes tab stops every four columns. I assumed eight.

  10. programmingpraxis said

    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.

  11. kernelbob said

    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).

  12. programmingpraxis said

    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.

  13. kernelbob said

    Oh. You dropped the requirement that c <= d. I had missed that.

    Thanks for a fun problem.

  14. PHW said

    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;
    }
    }
    }
    }
    }

  15. Dan Schoch said

    /* 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 ;
    /

  16. Scott Haug said

    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.

  17. […] 2009 de khelben There’s an fun and not very difficult programming exercise, presented on Programming Praxis . The problem is easy to […]

  18. Here’s my solution. My Java code resembles some of the Python code posted by other commentators.

  19. Rohit Phutane said

    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));
    }
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 642 other followers

%d bloggers like this: