Loading...
Project Euler 93: Find a set of terms that produce longest set of consecutive digits
Problem Description
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.
Analysis
Well, this is just a complicated conglomeration of combinations, permutations and products of expressions that quickly finds a maximum sequence size and the associated terms that yield that maximum.
1. Define combinations of terms using the integers from 1 to 9. There aren’t that many, just 126 sets from (1,2,3,4) to (6, 7, 8, 9).
2. Permute each combination. (1,2,3,4), (1,2,4,3), (1,4,2,3), etc.
3. Create an iterator of operators using the product method that look like (+++, ++*, ++-, ++/, +*+, etc.) and calculate each expression in such a way that we avoid a div by zero. Oh, BTW, use truediv instead of div, that cost me some time not knowing the difference.
4. Collect a maximum sequence size, and sequence length.
5. Fin. This was a bit difficult to get my head around at first, but just stated coding and it fell together. Yeah, there are only two equations required – not five. Graph the possibilities and check out the relationship between nodes. This works perfectly to solve this problem.
Project Euler 93 Solution
Runs < 0.350 seconds in Python 2.7.
Use this link to get the Project Euler 93 Solution Python 2.7 source.
Afterthoughts
- Takes 195,536 iterations. Can probably be reduced some.
At first, let me tell you I really appreciate your posts about Project Euler. Your solutions are much shorter and mostly more elegant and even readable than the ones I came up with. Very educative!
For this problem, however, I’m pretty sure your analysis is flawed. You cannot get by with only 2 equations, you need all 5 for a correct algorithm. (Since the inputs are limited and the considered outputs as well, this doesn’t show in the result, but that’s just luck, I’m afraid.) The reason you need all 5 is probably that half of the available operators are not commutative (- and /).
This is one of the examples of a missing output my code came up with:
1345: 15 = 3/(1-(4/5)) = 5/((4/3)-1)
Posted by BartV | January 9, 2016, 3:52 PMSadly, you’re correct. I learned this when I helped my son write a KRYPTO solver. You can check it our here.
I also joined a contest at HackerRank that really tests these old solutions and realized I didn’t write them with much breadth, just kinda a quick get-the-answer hack.
I am going through each one and re-writing them to be more robust. I am still finishing the 70’s but will be re-visiting this soon.
Thanks for taking the time to write. I hope you check back in a week or two when I rewrite these. Also, sorry in advance for mentioning HackerRank, just another addictive (and fun) way to burn through the hours.
Posted by Mike Molony | January 10, 2016, 12:34 AMOK, thanks, I’ll check from time to time.
I also accept your apologies for forcing me to muster all of my willpower to resist the temptation of HackerRank. 😉
Posted by BartV | January 10, 2016, 7:20 AM