Project Euler 93: Using four distinct digits and the rules of arithmetic, find the longest sequence of target numbers.

Project Euler 93: Using four distinct digits and the rules of arithmetic, find the longest sequence of target numbers.

Written by on 21 April 2012

Topics: Project Euler

I really start feeling that the problems become more and more difficult. Problem 93 of Project Euler was not trivial at all. And as we shall see the only solution I found was a brute force solution.  The problem reads

By using each of the digits from the set, {1, 2, 3, 4}, exactly once, and making use of the four arithmetic operations (+, −, *, /) and brackets/parentheses, it is possible to form different positive integer targets.

For example,

8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) – 1
36 = 3 * 4 * (2 + 1)

Note that concatenations of the digits, like 12 + 34, are not allowed.

Using the set, {1, 2, 3, 4}, it is possible to obtain thirty-one different target numbers of which 36 is the maximum, and each of the numbers 1 to 28 can be obtained before encountering the first non-expressible number.

Find the set of four distinct digits, a < b < c < d, for which the longest set of consecutive positive integers, 1 to n, can be obtained, giving your answer as a string: abcd.

As I mentioned in the beginning, I have only been able to solve this using brute force. That being said there are several interesting aspects on how to cover the whole search space for the best solution.

First of all we need to pick 4 digits. This can be done by combinatorics as we covered did in Problem 90. However here we have 0 digits (0-9) so that means we have the “10 choose 4″=210 different combinations we can make. Once again, I would like to mention Donald Knuth’s The Art of Computer Programming Vol 4A which is an amazing source of this kind of algorithms.

Second thing, is that once we have picked four digits we need to check all permutations of it. This we developed an algorithm for in Problem 24. There are 4!=24 permutations. For each permutation we need to test all combinations of the operators. There are 4 operators which can be arbitrarily picked for any of the 3 placements, meaning that we need to search  43 = 64 times the number of solutions. Last but not least we need to check every combination of parenthesis. There are a total of 5 parenthesis combinations valid which are

a+b+c+d

a+(b+c)+d

a+b+(c+d)

a+(b+c+d)

(a+b)+(c+d)

This gives us a total of 210*24*64*5=1612800 possibilities to check. Of course we will end up getting some things we are just the same, since addition is commutative and so on. But I haven’t found a way to eliminate these cases.

The whole thing can be written as this not very beautiful code

int[] best = null;
int bestcount = 0;

int[] comb = {0,1,2,3};
while (comb != null) {
    bool[] results = new bool[9 * 8 * 7 * 6];
    int[] perm = (int[]) comb.Clone();

    while(perm != null){
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                for (int k = 0; k < 4; k++) {

                    double? number = ope(ope(ope(perm[0], perm[1], i), perm[2], j), perm[3], k);
                    if(number != null && number == (int) number && number < results.Length && number > 0)
                        results[(int)number] = true;

                    number = ope(ope(perm[0], ope(perm[1], perm[2], j), i), perm[3], k);
                    if (number != null && number == (int)number && number < results.Length && number > 0)
                        results[(int)number] = true;

                    number = ope(perm[0], ope(ope(perm[1], perm[2], j), perm[3], k), i);
                    if (number != null && number == (int)number && number < results.Length && number > 0)
                        results[(int)number] = true;

                    number = ope(perm[0], ope(perm[1],ope(perm[2], perm[3], k),j),i);
                    if (number != null && number == (int)number && number < results.Length && number > 0)
                        results[(int)number] = true;

                    number = ope(ope(perm[0], perm[1], i), ope(perm[2], perm[3], k), j);
                    if (number != null && number == (int)number && number < results.Length && number > 0)
                        results[(int)number] = true;
                }
            }
        }

        int l = 1;
        while (results[l]) l++;

        if (l > bestcount) {
            best = (int[])comb.Clone();
            bestcount = l;
        }

        perm = getNextPerm(perm);
    }
    comb = getNextCombination(4, 10, comb);
}

where the operator function looks like

private double? ope(double? a, double? b, int op){
    if (a == null || b == null) return null;
    switch (op){
        case 0:
            return a+b;
        case 1:
            return a-b;
        case 2:
            return a*b;
        case 3:
            if (b == 0) return null;
            return a*1.0/b;
    }
    return 0;
}

in order to handle the changing operators. I have chosen to allow null in to represent the case of division by zero.

This (in my opinion) not very beautiful code gives the the following result

The best solution is 1258
Which creates 52 solutions
Solution took 435,2276 ms

So the execution time is also on the very slow side. But to be honest I can’t figure out other ways to solve this problem.

Wrapping up

We have solved the problem using different combinatorics and permutation algorithms in order to search through all possible combinations for the problem. This allowed us to find the best solution.

You can find the full source code for the problem right here in order to see the other algorithms. Did you approach the problem differently, and did you find a better solution than this?

30 Comments For This Post I'd Love to Hear Yours!

  1. Rob Tsai says:

    Thanks for another great article Kristian. I couldn’t do these harder problems without your blog!

    I used most of your blueprint to generate all the brute force combinations to test.

    Rather then writing code for the mathematical operators +,-,*,/ and figuring out how to write the priority of mathematical operators (i.e. scan from left to right, do operators within parentheses first, and do *,/ before doing +,-), I ended up mostly doing string operations and then sending the resulting string directly to the Python operator using the eval() function.

  2. Kristian says:

    Thanks. Yes in languages where that is a possibility I would have done the same thing, as that at least to me seems like an easier option. It might not be as fast, but it should be easier to read the code.

  3. Robert Watkins says:

    Try using RPN/postfix instead of parentheses. That way, you only have to worry about the pattern AB(op)C(op)D(op).

  4. Kristian says:

    Not that I have had time to try it out, but the approach is brilliant. It basically saves us a factor 5 in complexity and might as well be easier to implement.

  5. Kal says:

    Are you sure that the pattern AB(op)C(op)D(op) covers all possibilities? I don’t see why this is so.

  6. Kristian says:

    If you use reverse polish notation then yes I think it covers all possibilities.

  7. Kal says:

    Well, I tested it and, as far as I could tell, that implementation did not work. For {1,2,5,8} it was unable to form 36, for example. This could be an error in my implementation, but I am unsure.

  8. Kristian says:

    I see what you are saying.

    I get the solution from my code saying that this is possible as

    (1+5) * (8-2)

    Using this site’s converter gives me

    1 5 + 8 2 – *

    which is indeed not the pattern given above

  9. Kal says:

    Using RPN is still a good improvement, as you can fix the problem by including operations of the form (A B op) (C D op) op. I’m pretty unfamiliar with RPN, and rather lazy, so I didn’t bother converting this to standard RPN notation, but this is still 2.5 times faster than evaluating all five groupings of parentheses.

  10. Khaur says:

    Hi there!

    I also used only 2 groupings, although I didn’t use RPN.

    My code was a pain to debug, but surprisingly it runs in about 10ms. I have no idea why it’s so much faster, as I’m still trying out pretty much every combination.
    The code is at http://pastebin.com/jKBvadiP (beware, it’s ugly (~150 lines) — although I’ve seen worse).

    The verbose output doesn’t respect regular priority rules, but leftmost priority (unless you have parentheses of course), I use the absolute value for difference and the backslash operator is just division with the operands switched.

    The result at the end is always off by one (just like yours by the way, there is no way to make 52 with 1,2,5 and 8), but it doesn’t really matter since we aren’t interested in the actual value.

    I had trouble at some point because I was only considering divisions that didn’t generate non-integers (even though one of the examples did) and therefore I couldn’t generate 44 (and maybe also some others).

    If later readers want something to help them debug their code, I recommend using http://www.dcode.fr/compte-est-bon . If you can’t read French, just use the 1st button of the 3rd calculator for a single target number or the 3rd button of the 4th calculator for all possible numbers. The show it’s based on also has an English version (Countdown), so there should be calculators in English as well.

  11. Benjamin Button says:

    Can you please tell which part of your code checks the priority of the operators? I mean where does it see that *,/ have to be done before +,-

    Thanks

  12. Kristian says:

    The programming language has the normal precedence of operators. However, in this solution I don’t assume anything, and therefore use parenthesis to control the evaluation of the result. This is what happens on line 14, 19, 22, 26 and 30.

  13. Dav2.71828 says:

    I happened to get the right answer using groupings: (((a.b).c).d) and (a.b).(c.d)
    (Using only the first grouping gave me {1256} with n=43)

    Could you please go into more detail on how you chose the 5 parenthetical groupings you used. Somebody in the Euler comment section mentioned it “corresponds to the number of possible 3-node trees”

  14. Kristian says:

    Not really. To be honest I am not sure that I fully understand why that works.

    I am aware that going through all the combinations will give you a lot of duplicates, especially since some of the paranthesis will just enfore the same rule as it would have done otherwise.

  15. Dav2.71828 says:

    First off, thanks for helping increase the world’s understanding of math. In an attempt to do the same I’ll try to explain my reasoning for the groupings I used:

    Operations act on two inputs. So with ‘n’ numbers all the combinations that need to be tried are all the ways you can make a unique binary tree with n leafs and the requirement that each parent node has two children.
    With ‘.’ being an operation, for n=4 this leads to: ((a.b).c).d and (a.b).(c.d)
    For n=5: (((a.b).c).d).e; ((a.b).(c.d)).e; ((a.b).c).(d.e)
    For n=6 ((((a.b).c).d).e).f; (((a.b).(c.d)).e).f; (((a.b).c).(d.e)).f; (((a.b).c).d).(e.f); (((a.b).(c.d)).(e.f); ((a.b).c).((d.e).f)

    Only using these groupings should lead to a significant speed up as n gets larger. How many groups would your method generate if n=6?

  16. Tom Leslie says:

    Don’t want to throw an unnecessary spanner in the works, but I get 297 consecutive integers using the starting set {5, 6, 8, 9}.

    Basically I’m using the rpn approach, and (by inspection), with four possible numerical arguments, there are four syntactically correct rpn sequences.

    The four syntactically correct sequences each use exactly three operators (out of the possible four). So each sequence has 4*4*4 operator combinations. With four such sequences, this gives a total of 4*4*4*4=256 possible equations (with quite a lot of duplicates – in fact basic duplicate removal takes it down to 138).

    With a further 126 combinations of four distinct digits (I’m only using 1->9, although interestingly using 0->9 doesn’t change the answer) this gives a total of 138*126=17388 possible answers. Obviously, a lot of these won’t be integers, and quite a few give negative answers.

    However I reckon the set {5, 6, 8 9} gives rise to 483 distinct positive integers and 1->297 inclusive are part of this set.

    One of us is getting this one badly wrong, and past performance suggests that it is probably me, but are you sure that 52 consecutive digits is the best you can do!?

  17. Kristian says:

    I just checked the combination 5,6,8,9 using my approach and it tells me I am missing 15. So if you have a way of creating that specific number I might be wrong otherwise I guess you have a bug somewhere.

  18. Tom Leslie says:

    Please accept grovelling apologies, I had an incorrect reset between testing different digit combinations.

    I now agree that the set 1258 produces the longest sequence, although I get 51 (ie 1, 2, 3,…., 51). I can only get to 52 for this set if I allow 0 as an answer, in which case I can get 0, 1, 2,….,51. However this violates the problem statement, which asks for

    “longest set of consecutive positive integers, 1 to n, can be obtained”

    can you verify that your sequence length of 52 is 1, 2 ,3, .., 52 or 0, 1, 2, .. 51? If it is the former, I still have a problem somewhere

  19. Kristian says:

    No worries. I know exactly how much you can stare blindly at a piece of code and convince yourself that it is correct.

    The second part you have right. I had added one for some reason which is wrong. So the longest sequence is 1,2,3,…,51.

  20. centrefold says:

    I think there are more possible paranthesis combinations:

    for example : (4 * (1 + 3)) / 2 ( which is written in the problem definition )

    I also solved the problem in a similar manner with your solution, but with one added observation : I did not consider 0 will be part of the 4 digit solution. Because with 0, sums(+,-) of 4 will be sums of 3, most products will be 0, some divisions by 0 will not be good… so not a lot of numbers will be generated with a 0 in the sequence.

  21. Kristian says:

    That specific one you mention here does not differ from 4*(1+3)/2 which is covered. I think you will see that any other combination is covered as well.

    Regarding you mention of 0, that is indeed a very good conclusion which is most certainly right.

  22. Khaur says:

    I disagree regarding the 0 on a principle basis, although it turns out it doesn’t influence the solution to this specific problem.

    Adding 0 is convenient in that it lets you ignore the last digit (multiplying by 1 also lets you do that, but you might have used it already).
    I’m not sure you can make every combination of 3 digits with 4 digits if you exclude the 0. Unfortunately I can’t find an example out of thin air (and I’m feeling to lazy to get one out of my code). Even if it is possible, it’s not obvious (at least to me) and needs to be demonstrated.

  23. LouWeed says:

    I didn’t like this problem, though my solution runs pretty quick (any time I manage to get a Euler solution on my aging 2005 desktop pc with TCL code to run under a second is a victory).

    I have a procedure called combine: Combine 2 numbers (a+b, a-b, b-a, a*b, a/b, b/a) and return a list of possible integers and a list of possible fractions. This procedure caches the result as it finds them, which is worth it as it only needs to do the actual calculations 1/8 of the time (~12,000/80,275).

    I’m not sure if using fractions instead of floats is a time-save, I mainly did it to avoid the headache of figuring out whether I have an integer or not (because 1/3 = 0.3333333, and then 0.33333333*3 = 0.999999999)

    I also didn’t bother testing every permutation, I’ve just got this recursive procedure which takes 2-4 numbers and combines them every which way:
    a&b
    a&(b&c), b&(a&c), c&(a&b)
    (a&b)&(c&d), (a&c)*(b&d), (a&d)&(b&c)
    a&(b&c&d), b&(a&c&d), c&(a&b&d), d&(a&b&c)

  24. Cryptanalyse says:

    Hello,

    You can actually solve this problem much faster with a divide and conquer approach. First partition you 4-integer input in the same way it is done for quicksort, and you can combine the elementary elements to produce all the possible arithmetic expressions for the input list of 4 integers. This is very fast and much more elegant. This approach scales much better for say 5- of 6-integer problems like Countdown.
    Cheers!

  25. Rok Kralj says:

    Hey, you listed 5 permutations, but you made a mistake, you have one duplicate and you missed one option. I have replaced op+ with op-, since it is not commutative for clarity.

    These two are duplicates:

    a-b-(c-d)
    (a-b)-(c-d)

    And you missed this one:
    a – (b – (c – d))

  26. Frank Mullin says:

    Rok,
    I’m a great believer in full use of parentheses to clarify equations. The original presentation list five equations as the full set of alternatives, but some of these are actually ambiguous. But the equations that have been implemented are not. If you take the ope function to actually add parentheses, you will find the following permutations:
    – ((a o b) o c) o d
    – ( a o (b o c)) o d
    – a o ((b o c) o d)
    – a o (b o (c o d))
    – (a o b) o (c o d)
    I’m satisfied that this list is complete.

  27. Frank Mullin says:

    Kristian,
    I don’t know if you’re still reading comments on an old problem, but I’ll try.
    I believe the best result should be 51 not 52.
    That’s what my program came up with.
    So I copied your code and ran it. I examined what the state was when you saved that best result. I discovered that your result array was true for 1 through 51, but false for 52 (you can’t get 52 using 1,2,5,8 — at least I can’t).
    If you look at your code for computing the bestcount, you’ll see you start your counter off at 1 rather than 0.
    Frank

  28. Antonio says:

    I think people here need to be a bit more careful, as there are some incorrect assumptions being made but still happen to result in the correct answer. IF all the operators were commutative, and IF we will eventually permute all groups of four digits, then there are only two trees that need to be considered:

    1: ((A*B)*(C*D)) AB*CD**
    2: (((A*B)*C)*D) AB*C*D*

    Any other bracketing will result in one of the above two with the letters permuted. e.g. ((A*(B*C))*D) can be re-arranged to (((B*C)*A)*D), which is the same as 2 above. Unfortunately, minus and divide are not commutative, so we were not justified in re-arranging the order of the bracketed terms. To get around this, we can define two new “reverse” operators: rminus(a,b)=b-a and rdivide(a,b)=b/a. With these now 6 possible operators, we can swap orders of any terms, since for every operator * there is another operator & such that A*B=B&A. With this approach, the total number of possibilities is 210*24*6^3*2 = 2177280. However, this is worse than Kristian’s solution.

    To avoid the issue with commutitivity, we can instead generate all possible bracketings (as Kristian did). As most people here have determined, there are 5 of these:

    1: (A*(B*(C*D))) ABCD***
    2: (A*((B*C)*D)) ABC*D**
    3: ((A*B)*(C*D)) AB*CD**
    4: (((A*B)*C)*D) AB*C*D*
    5: ((A*(B*C))*D) ABC**D*

    Because we still have to permute the letters, there are 210*24*4^3*5 = 1612800 possibilities. The only way to reduce this number is to use the fact that most of the operators are commutative, and to remove the need to permute (A,B,C,D). We can do this by generating more trees:

    ((A*B)*(C*D))
    (D*(C*(A*B)))
    (C*(D*(A*B)))
    (B*(A*(C*D)))
    (A*(B*(C*D)))

    ((A*C)*(B*D))
    (D*(B*(A*C)))
    (B*(D*(A*C)))
    (C*(A*(B*D)))
    (A*(C*(B*D)))

    ((A*D)*(B*C))
    (C*(B*(A*D)))
    (B*(C*(A*D)))
    (D*(A*(B*C)))
    (A*(D*(B*C)))

    These binary trees contain evaluations between all pairs, so you now no longer need to consider any permutations of the 4 digits. The only issue now is the non-commutative nature of subtraction/division, so we’re back to needing 6 operators (the two “reverse” operators for minus and divide). The total number of possibilities is: 210*6^3*15 = 680400, which is an improvement by just over a factor of 2.3.

  29. Akshay Khanna says:

    Sorry to say but a solution that takes 4000+ seconds is not a solution is any sense. It sucks. Mine runs in 0.137 seconds.

     
    public static void main(String args[]) {
    		String ret="";
    		int ans=0;
    		long startTime = System.nanoTime();
    		for(int i=1;i<10;i++) {
    			for(int j=i+1;j<10;j++) {
    				for(int k=j+1;k<10;k++) {
    					for(int l=k+1;l<10;l++) {
    						ArrayList<HashSet<Double>> dp=new ArrayList<HashSet<Double>>();
    						for(int ii=0;ii<=15;ii++)
    							dp.add(ii,new HashSet<Double>());
    						dp.get(0).add((double)0);
    						double a[]=new double[4];
    						a[0]=i;a[1]=j;a[2]=k;a[3]=l;
    						for(int p=0;p<16;p++) {
    							for(int m=0;m<4;m++) {
    								if((1<<m & p)==0) {
    									Iterator<Double> it = dp.get(p).iterator();
    									while(it.hasNext()) {
    										double n=it.next();
    										dp.get((1<<m)|p).add(n*a[m]);
    										if(a[m]!=0)
    											dp.get((1<<m)|p).add(n/a[m]);
    										if(n!=0)
    											dp.get((1<<m)|p).add(a[m]/n);
    										dp.get((1<<m)|p).add(n+a[m]);
    										dp.get((1<<m)|p).add(n-a[m]);
    										dp.get((1<<m)|p).add(a[m]-n);
    									}
    								}
    							}
    						}
    						int n;
    						for(n=1;(n<=10000 && dp.get(15).contains((double)n));n++);
    						n--;
    						if(n>=ans) {
    							ret=i+""+j+""+k+""+l;
    							System.out.println(n+" "+ret);
    						}
    						ans=Math.max(ans, n);
    					}
    				}
    			}
    		}
    		long endTime = System.nanoTime();
    		System.out.println("Took "+(endTime - startTime) + " ns"); 
    		System.out.println(ret);
    	}
    
  30. Steven says:

    Not sure if you’re still reading comments on here, but you definitely but like Rok Kralj mentioned in a previous comment you are missing a permutation of parenthesis.

    If you write the equation as A 1 B 2 C 3 D where 1, 2, 3 are the operators its a simple permutation of order:
    1, 2, 3 => a + b + c + d
    1, 3, 2 => (a + b) + (c + d)
    2, 1, 3 => (a + (b + c)) + d
    2, 3, 1 => a + ((b + c) + d)
    3, 1, 2 => (a + b) + (c + d)
    3, 2, 1 => a + (b + (c + d))

    1, 3, 2 and 3, 1, 2 are equivalent because 1 and 3 are done in isolation then operation 2 is performed on the results. Ultimately it does give you 5 permutations to try, but in your example you miss one and duplicate one giving you the wrong set.

Trackbacks For This Post

  1. Project Euler 93: Using four distinct digits and the rules of arithmetic, find the longest sequence of target numbers.

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.