# Euler project - P 164

Hi,

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

``````

This is the execution code

``````consecutive_3(10000000000000000000,19999999999999999999)
``````

https://projecteuler.net/problem=164

Donâ€™t push to array just keep a counter for one.

thanks running the new code now!

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?

2 Likes

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.

8 Likes

I agree, finding ways to abstract my thinking about 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

``````truth_array = Int[]
``````

@DNF: Thank you! This is a very helpful tip. Since I do that a lot

Also, any number with a 9 in it is automatically out.

The sum canâ€™t be greater than 9, so 1009001 would be fine, for example.

I misrea the question
Should ve

900900â€¦

I thought so, just wanted to make sure no one goes off on the wrong track

By the way @AlexanderChen , thanks for getting me back into Euler problems, fun problem!

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

Hehe. Happy to share my solution if u want. Itâ€™s sub second performance

I also can share my solution which is unbelievably fast, `25 ÎĽs`, but contains some black magic of course .

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

Thanks. Wouldnt hurt to DM to share a soln in private to provide another perspective

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.

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

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