Next, in search of palindromes

Not so long ago on Habré there was an article about codebattle from hexlet.io . Well, we dragged on with friends, it's like a drug! It seems you are trying to distract yourself from work, and your hands are straining to go to the site, and all thoughts are about optimizing solutions.

And once I got a problem, it sounded like this: “The decimal number 585 is 1001001001 in binary. It is palindromic in both bases. Find n-th palindromic number ". And if in Russian, then: “the decimal number 585 in binary form looks like 1001001001. It is a palindrome in both number systems. Find the nth palindrome like. ” It is not complicated at all and was resolved quickly.

function is_palindrome($num) { return $num == strrev($num); } function solution($num) { $count = $i = 0; while($count<$num) { $i++; //     ,          if (is_palindrome($i) && is_palindrome(decbin($i))){ $count++; } } return $i; } 

But here is bad luck. Around that time, the site was attacked by habraeffekt, and the tests did not want to pass in any way, fell off at the timeout. In a local chat, discussion began on how to optimize the solution, but no one gave any practical advice. Then the site was released, all the tests passed, but the desire to optimize remained ...

We generate decimal palindromes

To begin with, I wondered how much I could find palindromes on my typewriter. Although I was not advised to search in the chat for more than 22, I calmly found 27 in just 5 seconds, but the next one came only after more than 4 minutes. I didn’t wait any longer - something long. To start optimizing, I decided to learn more about palindromes.
')
Generated a few pieces and began to consider.


In fact, a numeric palindrome is a certain number, which was taken, mirrored and attached to the end of the same number. Those. they took the number 235, mirrored, got 532 and connected - it turned out to be a wonderful palindrome - 235532. And it was decided: why go through all the numbers in search of a decimal palindrome, if you can just generate them. No sooner said than done!

 function solution($num) { $count = $i = 0; while($count<$num) { $i++; //            $palindrome = $i . strrev($i); //            . if (is_palindrome(decbin($palindrome))) { $count++; } } return $palindrome; } 

Having started, I saw that one-digit palindromes were missing, and added a simple cycle to the first nine numbers.

 for ($i = 1; $i < 10; $i++) { if (is_palindrome(decbin($i))) { $count++; if ($count == $num) return $i; } } 

Running again, I saw that my mistake was much stronger. After all, I completely forgot about palindromes with an odd number of signs, such as 313, 585 or 717! And here I had to think hard. Looking at the list of palindromes obtained, one can see that palindromes with an odd number of signs are the same even palindromes, only with a center mark. Those. we take the even palindrome, insert the numbers 1-9 in the center and voila - the odd palindromes are ready. But! If I insert them in this loop, I will lose the order of the numbers. Therefore, we had to make drastic changes to the code and start from the number of characters.

 function solution($num) { $count = 0; //  . for ($i = 1; $i < 10; $i++) { if (is_palindrome(decbin($i))) { $count++; if ($count == $num) return $i; } } $p_size = 1; while (true) { $min = 10**($p_size-1); $max = (10**$p_size)-1; // $min  max          for ($i = $min; $i <= $max; $i++) { //     -  $palindrome = $i . strrev($i); //       . if (is_palindrome(decbin($palindrome))) { $count++; if ($count == $num) return $palindrome; } } for ($i = $min; $i <= $max; $i++) { for ($j = 0; $j < 10; $j++) { //     -  $palindrome = $i . $j . strrev($i); //       . if (is_palindrome(decbin($palindrome))) { $count++; if ($count == $num) return $palindrome; } } } $p_size++; } } 

Actually, everything is simple. We first take one-digit numbers 1-9. We create two-digit palindromes. Following three-digit. Then simply increase the digit and take the numbers from 10-99. 4 and 5-bit palindromes will be obtained. Well, etc.

We are testing!

For a start, launched a look at the 28th palindrome. It turned out that for an improved function this is an absolutely fun task. The 28th was received in 0.15 seconds! This means that the speed was increased by more than 1500 times. I was pleased. In 5 seconds I could get more than 40 palindromes. The 50th was received in 2.5 minutes.

Drawing attention to the palindromes obtained, I noticed that they are all odd. And it's true! Even decimal palindromes in binary form will end at 0, and since they always begin with 1, they cannot be a palindrome. This means that they do not even need to be checked. And since we generate palindromes, we can skip all the numbers with the first even digit.

Simple continue by condition immediately dismissed. It doesn't even make sense for us to loop on them. We will scroll through them. Having tried several options:

 if(!(substr($i,0,1))%2)) $i += $min; 

 if(!((floor($i/$min))%2)) $i += $min; 

 if (!$limit){ $limit = $min; $i += $min; } $limit--; 

I settled on the latter as the fastest and got such a code.


By this we received acceleration about two times more. The 50th was received in 88 seconds and, in my opinion, it was a great result!

We generate binary palindromes

And now I was ready to stop and rejoice, as I had the idea to try to form binary palindromes. Why? The used numbers are less, even you are not even generating. Some advantages all around!

A little thought, I quickly changed the code and got:

 function solution($num) { if ($num==1) return 1; $count = 1; $p_size = 1; while (true) { $min = 2**($p_size-1); $max = (2**$p_size)-1; // $min  max             for ($i = $min; $i <= $max; $i++) { $half_palindrome = decbin($i); //     -     $bin_palindrome = ($half_palindrome) . strrev($half_palindrome); //       . $dec_palindrome = bindec($bin_palindrome); if (is_palindrome($dec_palindrome)) { $count++; if ($count == $num) return $dec_palindrome; } } for ($i = $min; $i <= $max; $i++) { $half_palindrome = decbin($i); for ($j = 0; $j < 2; $j++) { //     -     $bin_palindrome = $half_palindrome . $j . strrev($half_palindrome); //       . $dec_palindrome = bindec($bin_palindrome); if (is_palindrome($dec_palindrome)) { $count++; if ($count == $num) return $dec_palindrome; } } } $p_size++; } } 

After the tests, I realized that I did everything correctly. The 28th was received in 0.05 seconds. 50th in 48 seconds. When I took on this task, I did not expect such a result at all.

Here I have already decided that enough: I have already exceeded all my expectations. While lying, of course. Then he tried to think of how to increase the speed even more, but nothing came to mind. Tired already, and the night in the yard.

And finally, the pivot table:


Ps. Continued optimization from ilyanik, see this article.