8 ms·
I just wrote a script to do this in, like, 5 minutes :) And the whole thing runs in 7 seconds on my machine. https://github.com/adtac/123456789/blob/master/out
by adtac 10y ago
I just wrote a script to do this in, like, 5 minutes :) And the whole thing runs in 7 seconds on my machine.
https://github.com/adtac/123456789/blob/master/output https://github.com/adtac/123456789/blob/master/output
Admittedly, it doesn't have every number. I suspect it's because I haven't included bracketed expressions.
- 7373737373 10y agoWhat happens if you allow for 0?
- metaphor 10y agoFor ascending solution taking a lazy approach, it appears to be a trivial inclusion, considering for any n with a solution using 1-9, a solution which includes 0 will simply take the form: n = 0 + <ascending_solution_n> without any additional consideration. Similarly for descending solution: n = <descending_solution_n> + 0 The descending case also looks like it'll produce a crap ton of solutions for n = 1 of the form: 1 = <arbitrary_descending_permutation> ^ 0
- 7373737373 10y agoMultiplication makes a difference here
- metaphor 10y ago3 = 123+4+5-6*7^89 First verifiable instance of error? Did a little fishing for overflow candidates with the following regex: [1-9]{3,}\^[1-9]{3,} ...caught 58 results between 266 and 10940: 266 = 123^456-78-9 ... 10940 = 12345^6789 My kung fu isn't Python so I don't know how types are handled. That eval() function sure smells suicidal for anything remotely serious though.
- witty_username 10y agoNo, Python doesn't have integer overflow. "^" is the XOR operator. GP's code has that bug. > That eval() function sure smells suicidal for anything remotely serious though. Yes, ast.literal_eval() should be used.
- adtac 10y agoUgh, fixed it. Using * * is not really an option now because it takes insane amounts of time to compute something like `123456789`. And this is just a tiny script - `eval` shouldn't really be an issue. And yes, I know it's evil, generally. But if you think about it, Python itself is just one big eval loop :P
- Phemist 10y agoI think a good idea might be to do it for postfix/prefix notation, rather than infix. This will also get rid of the need for parentheses.
- dastbe 10y agoThe ordering of numbers will be different between infix, prefix, and postfix representations.
- baristaGeek 10y agoReminds me so much of competitive programming
- questerzen 10y agoI added division and brackets. This gets every number up to 5397, with only about 400 numbers still missing overall (<5%), but run time goes up to 40 minutes. Potentiation is a problem though (particularly when combined with brackets) as Python becomes impossibly slow using bignums. (I estimate it will take several days of compute time to test all 250 million possibilities, unless I put some effort into speeding it up significantly.) But at least it would prove definitively whether 10958 is possible. If the only goal were to search for a solution to 10958 though, it should be fairly straightforward to re-order the search in approximately ascending order of compute cost so that if a simple solution exists it will be found quickly.