I am doing some small algorithmic puzzles from the Euler Project. I have a working solution in code for P164 but it is so slow that I fear that I am doing something wrong. Could someone give me tips how to make my code perform better?
function iterate_3(number)
truth_array = []
array = reverse(digits(number))
for i in 1:(length(array) - 2)
+(array[i],array[i+1],array[i+2]) <= 9 ? continue : push!(truth_array,1000)
end
if isempty(truth_array)
return number
end
end
function consecutive_3(begin_point,end_point)
results = []
for i in begin_point:end_point
if iterate_3(i) != nothing
push!(results,i)
end
end
return length(results)
end
First of all, I suggest checking your performance with @btime from BenchmarkTools. This way you can see if you are making any performance improvements with your code changes.
If I do that with n = 1000000, you clock in at 345.713 ms (4348978 allocations: 422.86 MiB) … wait what, 4 million allocations for counting something?
If you have a function like iterate_3 the usual way to do something like that is
for a in b
if the_thing_is_not_like_I_want_it
return false
end
end
# if we are still here that means the thing must be fine!
return true
Currently you use an array, but you push a value you don’t care about (1000) to the array, and you only ever check if anything is there.
Also, why do you reverse your array? This allocates a new array every time you do it. If you really need to reverse it, you can use reverse!, which reverses in place without allocating a new array. Speaking of which, the same is possible for digits -> digits!.
All of that aside. You want to count through roughly 1e19 numbers. Lets say you can do each check in 1ns (not true, but let’s assume). That means you need 1e10 seconds or roughly 300 years to do this.
This means (as it is almost always the case with Euler Project problems) you need to think of a clever algorithm to do this. Simply going through every number won’t cut it.
As a pointer: you go from 10000000000000000000 to 19999999999999999999. By just looking at the last number, I know that you will be checking roughly 999999999999999999 numbers too many, because if your number starts with 19 we are done already. You can only go up to 180.... Also, what’s up with 20000000000000000000? You stop just shy of that, but this number is okay, no?
Instead of thinking about the performance of your code snippet, you’ll have to look more closely at your algorithm first.
Btw. just a tiny remark: you are more or less doing the bruteforce solution for the problem, basically transforming the problem description one by one to computer instructions. Project Euler problems can be solved quite nicely by doing some maths first which often highly reduce the computational complexity by redefining the way you address the problem.
In regards to the range, I was testing. It would go further. I will update the code, I am interested to see the gain. However, I agree with @tamasgal that the brute force approach is ineffective.
@AlexanderChen I was having fun with this problem and I think the largest you need to count up to is
largest = Int128(sum(Int128.(exp10.(0:19)).*8)) |> digits
largest[1:2:end-1] .= 0
sum([largest[k]*Int128(10)^(k-1) for k=1:length(largest)])
which is
80808080808080808080
This should cut down 10% of running time in the brute-force approach. Any number larger than the above is automatically failing the condition (I think).
Also, any number with a 9 in it is automatically out. So you just need to count the number with 9 as a digit? Actually, it’s easier to count the number of number WITHOUT 9 and deduce the number with 9.
So you can choose from nine digits (0, 1, 2, …, 8) and place them into 20 digits, so that’s 9^20 choices, but the first digit can only be (1,…8) so that’s 8*9^19.
Hopefully that’s not too many hints. Actually there is no guarantee these hints are useful. But those are my first thoughts. Hope it’s at least another perspective for you to consider. Have fun!
I agree that you should not create an array, unless you care about its contents (which you don’t do here). But whenever you are using arrays, don’t do this:
If your code contains a line like this, it’s a bad sign for performance. This creates a Array{Any, 1} which is the slow kind of array. Make sure that the array is appropriately typed, in this case it should be
@Karajan, your welcome! I have implemented your adjustments and I see a gain in performance. But I need to find a more abstract solution because, thinking recursive but not sure if that is the right approach yet.
@xiaodai@Seif_Shebl as an FYI Project Euler requests that you not share your answers to questions in public so that others can have the experience of solving them themselves. I think they said somewhere on the site that accounts can be banned for violating that rule. Looking around the internet, that ship has probably sailed, but do with this info as you will.
I agree, don’t post the 25 microsecond solution. I wrote one that takes on the order of an hour. Much better than 300 years, but I’ve got some ideas to crank up the speed and don’t want a spoiler!
@Seif_Shebl: I agree with @xiaodai that it wouldn’t hurt to see another perspective.
Having said that I have formulate two possible approaches.
randomly choose the first two digits 1-9, 0-9 which combined less or equal to 9 and than randomly add a digit from a selected range. e.g. if we begin with 14 then we randomly select between the range [0:4]. this continues until we have 20 digits which will be stored. Repeat X times.
starting point is identical but the main difference is that all valid permutations will be calculated. E.g. if we begin with 14 than all the elements of the range of [0:4] will be calculated until we reach the 20 digits. So you get a very dense tree structure.
In option 1, I think the main problem is that we leave to much over to randomness and as a result it needs to run a lot.
in option 2, this way I think you can truly calculate all the possibilities. But I am not sure how this should be coded + if this type of recursive method is something Julia will like to do.
.