Carlos Reves

Ranch Hand

Posts: 116

10

posted 4 months ago

Good morning guys and gals!

I've been away for a bit but i'm returning with a pled for some help...

I did a challenge in Hackerrank and i'm having some problems with timeouts...

The problem there is this one: Project Euler #176: Rectangular triangles that share a cathetus.

It's a programming version of Problem 176 from projecteuler.net.

After some research i found this integer sequence that gives the required number of rectangular triangles wich share a cathetus. If you see there in the

So the code is:

I used

The commented lines in my code are the ones needed in Hackerrank to get the input values. I left them just for reference and hardcoded the number of tests (line 7) and the number of triangles (line 12) for testing purposes.

This code works fine. If you run it like it is, it gives the correct answer for the cathetus that is in 4 rectangular triangles (12). The problem is that there can be many tests and numbers can get very large and, therefore, i'm geting timeouts.

I think that the main situation here is that for every test i'm computing the Tau sequence from the start. So i thought that it could help if i memorized all the sequence elements allready computed and, in every next test, only compute the next ones if the answer wasn't found in the allready computed.

What do you think? Should i use an

Are there any other improvements that can be made?

Thanks for your help.

Best regards

Carlos

I've been away for a bit but i'm returning with a pled for some help...

I did a challenge in Hackerrank and i'm having some problems with timeouts...

The problem there is this one: Project Euler #176: Rectangular triangles that share a cathetus.

It's a programming version of Problem 176 from projecteuler.net.

After some research i found this integer sequence that gives the required number of rectangular triangles wich share a cathetus. If you see there in the

`FORMULA`section, we can get this sequence using the Tau function (also known as Divisor Function). After this i needed a way to count the divisors of a given number and found this page at mathschallenge.net. I used this method in my code.So the code is:

I used

`long`varibles since the numbers can exceed the`Integer`maximum value.The commented lines in my code are the ones needed in Hackerrank to get the input values. I left them just for reference and hardcoded the number of tests (line 7) and the number of triangles (line 12) for testing purposes.

This code works fine. If you run it like it is, it gives the correct answer for the cathetus that is in 4 rectangular triangles (12). The problem is that there can be many tests and numbers can get very large and, therefore, i'm geting timeouts.

I think that the main situation here is that for every test i'm computing the Tau sequence from the start. So i thought that it could help if i memorized all the sequence elements allready computed and, in every next test, only compute the next ones if the answer wasn't found in the allready computed.

What do you think? Should i use an

`ArrayList`since a common`Array`has fixed length?Are there any other improvements that can be made?

Thanks for your help.

Best regards

Carlos

Campbell Ritchie

Marshal

Posts: 55793

164

posted 4 months ago

Well done getting that far and for all the searches you have done. I think your effort so far merits recognition.

Is that conceptually a pure function with no side‑effects? If so, it is reasonable to make all methods static. Or is there some piece of information linked to several sizes of triangle, in which case you should maybe consider an object solution. I think you should move all that code out of the main method, anyway. Consider making the methods smaller, but more of them. Have a look at the loop in lines 17‑34. That looks complicated, but I think it can be simplified. You know you can speed up i % 2 by using (i & 1) == 0 (or != 0 or similar)?

Is there a faster way of finding τ0 than a linear search? What is that about prime numbers in the integer list link you gave us? Why are you specifying a particular kind of List? I would have thought that a List was better than an array for most things, but I'll let you work out the details for yourself. Yes, there is no point in working out the same numbers twice, but please work out why a List would be a better store for numbers than something like a Map.

Note how choice of names for booleans makes the loop hard to read; it would be easier to read with needsFinding instead of notFound.

Are you sure that all numbers will fit within the bounds of a

Is that conceptually a pure function with no side‑effects? If so, it is reasonable to make all methods static. Or is there some piece of information linked to several sizes of triangle, in which case you should maybe consider an object solution. I think you should move all that code out of the main method, anyway. Consider making the methods smaller, but more of them. Have a look at the loop in lines 17‑34. That looks complicated, but I think it can be simplified. You know you can speed up i % 2 by using (i & 1) == 0 (or != 0 or similar)?

Is there a faster way of finding τ0 than a linear search? What is that about prime numbers in the integer list link you gave us? Why are you specifying a particular kind of List? I would have thought that a List was better than an array for most things, but I'll let you work out the details for yourself. Yes, there is no point in working out the same numbers twice, but please work out why a List would be a better store for numbers than something like a Map.

Note how choice of names for booleans makes the loop hard to read; it would be easier to read with needsFinding instead of notFound.

Are you sure that all numbers will fit within the bounds of a

`long`? What about τ0, which looks a bit like a factorial. Do you need a BigInteger object to handle those numbers?
Carlos Reves

Ranch Hand

Posts: 116

10

posted 4 months ago

Many questions here... I'll try to answer...

I talked about an

The good thing i can remember about using

Thanks for the insights Campbell!

Best regards

Carlos

Thanks for the cow Campbell. Appreciate it!Campbell Ritchie wrote:Well done getting that far and for all the searches you have done. I think your effort so far merits recognition.

Many questions here... I'll try to answer...

The choice of having the methodsCampbell Ritchie wrote:Is that conceptually a pure function with no side-effects? If so, it is reasonable to make all methods static. Or is there some piece of information linked to several sizes of triangle, in which case you should maybe consider an object solution.

`static`is not mine. It's the way Hackerranks works internally. I can't change the

`class`name (must be Solution) and since main is given as

`static`, so the methods must be otherwise it won't compile in the site.

The main purpose there isn't the "beauty" of the code but the results. I agree with you though. By the way, will this type of changes affect the speed? (newbie question ).Campbell Ritchie wrote:I think you should move all that code out of the main method, anyway. Consider making the methods smaller, but more of them.

It's a bit complicate yes. But it's due to the way we get the values in the sequence. It's different for odd and even numbers. But i'll think about ways of simplifying it.Campbell Ritchie wrote:Have a look at the loop in lines 17-34. That looks complicated, but I think it can be simplified. You know you can speed up i % 2 by using (i & 1) == 0 (or != 0 or similar)?

Thanks for the info. Now that you mention it, makes sense that a bit manipulation would be faster than a remainder operation...Campbell Ritchie wrote:You know you can speed up i % 2 by using (i & 1) == 0 (or != 0 or similar)?

If there is than didn't find it yet... Must think about it.Campbell Ritchie wrote:Is there a faster way of finding τ0 than a linear search?

This one i didn't understand... What prime numbers? I use prime factorization in τ0 yes. But i did that cause i think it is faster than finding the divisors using the brute force remainder opperation from 2 toCampbell Ritchie wrote:What is that about prime numbers in the integer list link you gave us?

`sqrt()`of the number... Other than that i don't see any other primes... Of course it would be good and faster if i simply assigned

`divisors = 2`if the number is prime... But that would mean that i would need to test the number to see if it is prime... And that means calculating the divisors again...

I didn't even consider using a Map. I can use the indexes of theCampbell Ritchie wrote:Why are you specifying a particular kind of List? I would have thought that a List was better than an array for most things, but I'll let you work out the details for yourself. Yes, there is no point in working out the same numbers twice, but please work out why a List would be a better store for numbers than something like a Map.

`List`or

`ArrayList`or

`Array`(whatever i use) to indicate the original number and the corresponding entry as the number of divisors...

I talked about an

`ArrayList`because i assumed (maybe wrong) that it creates a

`List`... Isn't

`ArrayList`an interface? Can't we declare it like this:

The eternal question of variable names...Campbell Ritchie wrote:Note how choice of names for booleans makes the loop hard to read; it would be easier to read with needsFinding instead of notFound.

Well maybe... Since we need to square the number to calculate τ0 i guess that at some point it will go beyond the limits ofCampbell Ritchie wrote:Are you sure that all numbers will fit within the bounds of along? What about τ0, which looks a bit like a factorial. Do you need a BigInteger object to handle those numbers?

`long`... Honestly i keep getting timeouts before that...

The good thing i can remember about using

`BigInteger`(apart from the limits issue) is its

`isProbablePrime`method... Would speed up the primes fiding i talked before...

Thanks for the insights Campbell!

Best regards

Carlos

posted 4 months ago

Yeah, but how you can find a places to improve for performance if code is hardly readable? When code will become straightforward and obvious, you could easier spot which steps are might repetitive or not necessary. Always try write readable code and only then start worrying about the performance if that's the concern.

Campbell Ritchie wrote:I think you should move all that code out of the main method, anyway. Consider making the methods smaller, but more of them.

Carlos Reves wrote:The main purpose there isn't the "beauty" of the code but the results. I agree with you though. By the way, will this type of changes affect the speed? (newbie question ).

Yeah, but how you can find a places to improve for performance if code is hardly readable? When code will become straightforward and obvious, you could easier spot which steps are might repetitive or not necessary. Always try write readable code and only then start worrying about the performance if that's the concern.

Always check a module in cleaner than when you checked it out. *- Uncle Bob*

Campbell Ritchie

Marshal

Posts: 55793

164

posted 4 months ago

There is an implementation which is a combination between a Map and a List; searching a List like that isn't very fast, but I think there is an optimisation which starts searching from the end if the index sought is large. Since you will probably be looking for the last entry to continue calculations from, that might make the search faster. In both cases, it might be a good idea to specify the capacity of the collection in advance.

It is unfortunate when a website forces you into bad style, but you are stuck with it. Obviously written by people who write procedural codeCarlos Reves wrote:. . . The choice of having the methodsstaticis not mine. . . . I can't change theclassname . . .

Don't know. Probably no difference.. . . By the way, will this type of changes affect the speed? . . .

That's a pleasure.. . . Thanks for the info. . . .

In the website about encyclopedia of number sequences, it said something about prime numbers. I didn't read any moreWhat prime numbers? . . .

I don't know whether a Map will help you; it was just an idea which came randomly into my head. But it never does any harm to consider other suggestions.I didn't even consider using a Map.

It is the other way round; List is the interface and ArrayList the class (=implementation). Yes, that is how you create such a List object, but since Java7 you can probably miss out the second occurrence of Integer.. . . Isn'tArrayListan interface? Can't we declare it like this:

There is an implementation which is a combination between a Map and a List; searching a List like that isn't very fast, but I think there is an optimisation which starts searching from the end if the index sought is large. Since you will probably be looking for the last entry to continue calculations from, that might make the search faster. In both cases, it might be a good idea to specify the capacity of the collection in advance.

I had forgotten about the prime number methods. The cow was well merited, I think Good luck with the rest of the project.. . .isProbablePrimemethod... Would speed up the primes fiding i talked before...

Thanks for the insights Campbell!

Best regards

Carlos

Tobias Bachert

Ranch Hand

Posts: 85

18

posted 4 months ago

A bruteforce approach is most likely not able to solve this problem in reasonable time (the number has 47 binary digits*) - the problem can be solved with a mathematical approach (hint: its based on the prime factors of the

(*your current implementation would overflow; changing only the tau0 method won't be sufficient as your outer loop iterates from 2 to this number -> runs quite often)

Regarding your current implementation: The tau0 method should not iterate to

*divisors*value).(*your current implementation would overflow; changing only the tau0 method won't be sufficient as your outer loop iterates from 2 to this number -> runs quite often)

Regarding your current implementation: The tau0 method should not iterate to

*n*but to*sqrt(n)*. Additionally you could use a wheel to reduce the count of numbers to check and thus modulo operations (2er wheel -> 50%, 2x3er wheel = 33%, ...), below a bit faster version with a 2x3 wheel:
Piet Souris

Rancher

Posts: 1984

67

posted 4 months ago

A very fast algorithm to find the primes of a number is that of Pollard (https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm.

A method that I picked from the internet (http://introcs.cs.princeton.edu/java/99crypto/PollardRho.java.html) and added a little to it is:

A method that I picked from the internet (http://introcs.cs.princeton.edu/java/99crypto/PollardRho.java.html) and added a little to it is:

Carlos Reves

Ranch Hand

Posts: 116

10

It is sorta covered in the JavaRanch Style Guide. |