Go search for palindromes

    Not so long ago on Habré there was an article about codebattle from hexlet.io . Well, it dragged us along with friends, it's like a drug! It seems that you are trying to get distracted by work, and your hands are directly drawn to go to the site, and all thoughts are about optimizing solutions.

    And then one day 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 this: “the decimal number 585 in binary form looks like 1001001001. It is a palindrome in both number systems. Find the nth similar palindrome. " It is not at all complicated and was quickly resolved.

    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 this is bad luck. Around that time, the website was attacked by the habraeffect, and the tests didn’t want to pass, fell off on timeout. In the local chat, a discussion began on optimizing the solution, but no one gave any practical advice. Then the site let go, all the tests passed, but the desire to optimize remained ...

    We generate decimal palindromes


    To begin with, I was wondering how much I can find palindromes on my typewriter. Although I was not advised in the chat to search 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 further - for a long time something. To start the optimization, I decided to learn more about the palindromes.

    Generated a few pieces and began to consider.

    Palindromes
    1. 1
    2. 3
    3. 5
    4. 7
    5. 9
    6. 33
    7. 99
    8. 313
    9. 585
    10. 717
    11. 7447
    12. 9009
    13. 15351
    14. 32223
    15. 39993
    16. 53235
    17. 53835
    18. 73737
    19. 585585
    20. 1758571


    In fact, a numerical palindrome is a certain number that is taken, mirrored and attached to the end of the same number. Those. they took the number 235, mirrored it, got 532 and connected it — it turned out to be a beautiful palindrome - 235532. And the decision was made: 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-sign 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 it again, I saw that my mistake was much stronger. I completely forgot about palindromes with an odd number of characters, such as 313, 585 or 717! And here I had to think hard. Looking at the list of received palindromes, you can see that palindromes with an odd number of signs are the same even palindromes, only with a center sign. Those. take an 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 numbers. Therefore, I had to make fundamental changes to the code and build on 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 here. First we take one-digit numbers 1-9. We create two-digit palindromes. Next three-digit. Then just increase the rank and take numbers from 10-99. 4 and 5-digit palindromes will turn out. Well, etc.

    Testing!


    To start, I started to look at the 28th palindrome. It turned out that for an improved function this is an absolutely trifling task. The 28th was received in 0.15 seconds! This means that the speed has been increased more than 1,500 times. I was pleased. In 5 seconds I could get more than 40 palindromes. The 50th was received in 2.5 minutes.

    Paying attention to the received palindromes, I noticed that they are all odd. And the truth is! Even decimal palindromes in binary form will end with 0, and since they always start with 1, then they cannot be a palindrome either. And this means that they do not even need to be checked. And since we generate palindromes, we can skip all numbers with the first even digit.

    A simple continue conditionally swept away immediately. It doesn’t even make sense for us to cycle on them. We will flip 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 this code.

    Full code
    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 с каждым проходом цикла будут увеличиваться на один разряд
          $limit = $min;
          for ($i = $min; $i <= $max; $i++) {
             // Условие чтобы перескочить числа с чётной первой цифрой
             if (!$limit){
                $limit = $min;
                $i += $min;
             }
             $limit--;
             // Генерируем палиндром с четным кол-вом знаков
             $palindrome = $i . strrev($i);
             //проверяем является ли он палиндромом в двоичном виде.
             if (is_palindrome(decbin($palindrome))) {
                $count++;
                if ($count == $num) return $palindrome;
             }
          }
          $limit = $min;
          for ($i = $min; $i <= $max; $i++) {
             if (!$limit){
                $limit = $min;
                $i += $min;
             }
             $limit--;
             for ($j = 0; $j < 10; $j++) {
                // Генерируем палиндром с нечетным кол-вом знаков
                $palindrome = $i . $j . strrev($i);
                //проверяем является ли он палиндромом в двоичном виде.
                if (is_palindrome(decbin($palindrome))) {
                   $count++;
                   if ($count == $num) return $palindrome;
                }
             }
          }
          $p_size++;
       }
    }
    


    With this we got an acceleration of about twice as much. The 50th was received in 88 seconds and, in my opinion, it was an excellent result!

    We generate binary palindromes


    And now I was ready to stop and be glad as I had the idea to try to form binary palindromes. What? There are fewer used digits, you cannot even even numbers. Some pluses around!

    With 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 right. The 28th was received in 0.05 seconds. 50th in 48 seconds. When I undertook this task, I did not expect such a result at all.

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

    And finally, the summary table:

    Summary table
    No.PalindromeSearch (sec)Palindrome dec generation (sec)Palindrome bin generation (sec)number of bits
    116.9141387939453E-65.0067901611328E-61
    235.1975250244141E-54.887580871582E-54.2200088500977E-52
    355.8889389038086E-55.5074691772461E-56.0081481933594E-53
    476.4849853515625E-56.103515625E-56.6041946411133E-53
    596.9856643676758E-56.6041946411133E-57.4148178100586E-54
    6338.2969665527344E-57.1048736572266E-59.0122222900391E-56
    7990.000112056732177738.6069107055664E-50.000102996826171887
    83130.000205039978027340.000103950500488280.000126123428344739
    95850.000330924987792970.000123977661132810.0001451969146728510
    107170.00039696693420410.000130891799926760.000152111053466810
    eleven74470.00266098976135250.00018286705017090.00027918815612793thirteen
    1290090.00319600105285640.000203847885131840.0003011226654052714
    thirteen153510.00534605979919430.00028991699218750.0003499984741210914
    14322230.0111649036407470.000383853912353520.00047707557678223fifteen
    fifteen399930.0138409137725830.000486850738525390.0005211830139160216
    16532350.0183570384979250.000535964965820310.0005710124969482416
    17538350.0185859203338620.000546932220458980.000589132308959916
    18737370.0252549648284910.000660896301269530.0006551742553710917
    195855850.196464061737060.00116705894470210.001551151275634820
    2017585710.592638015747070.00260591506958010.002489089965820321
    2119343910.652742862701420.0028920173645020.002650022506713921
    2219797910.668315887451170.00298500061035160.002700090408325221
    2331292131.05898594856260.003234863281250.003252029418945322
    2450717051.72170996665950.00467300415039060.004043102264404323
    2552595251.78634786605830.00498294830322270.004142045974731423
    2658414851.98603796958920.00591897964477540.004393100738525423
    27135005314.59910106658940.00979089736938480.006405115127563524
    28719848917254.434272050860.0748970508575440.046326160430908thirty
    29th9103730190.0909988880157470.051257133483887thirty
    thirty9394749390.0961220264434810.05202817916870thirty
    3112908809210.112391948699950.06114697456359931
    3274511115470.169254064559940.1551511287689233
    33100509050010.199224948883060.1806252002716134
    34184621264810.363782882690430.238993167877235
    35324792974230.44276499748230.3330211639404335
    36750151510570.887769937515260.4871730804443437
    371109488490111.209517955780.6090040206909237
    381365255256311.26376104354860.6963500976562537
    3912341040143212.69412398338322.028050184249941
    4014138999831413.07818007469182.186210155487141
    4114749222947413.20892286300662.240367174148641
    4217927040729713.88743686676032.519950151443541
    4317940969049713.89042305946352.52121019363441
    4419999252999914.32877802848822.701833009719841
    4556526222625657.98124790191654.444355010986343
    4672275262572279.2854259014135.142831087112443
    4772847171748279.41209888458255.168857097625743
    48948487478484912.1002409458165.99822020530744
    493414138831414316.40152192115811.61456513404845
    fifty55221253521225587.53703188896249.89753913879449
    51933138363831339134.5680198669462.49614405632fifty
    521793770770773971171.4510390758590.22687101364151
    533148955775598413180.56048107147119.8572452068352
    5410457587478575401293.4983189106224.4536139965154
    5510819671917691801303.29767894745227.3886291980754
    5618279440804497281506.18344306946287.7762150764555
    5734104482028440143410.0452971458455
    5837078796869787073428.895541191156
    5937629927072992673431.1542971134256
    6055952637073625955506.288716077856


    PS. Continuation of optimization from ilyanik see in this article

    Also popular now: