Developers Club geek daily blog

1 year, 10 months ago
Not so long ago on Habré there was article about codebattle from hexlet.io. Well also tightened us with friends, it as drug! It seems you try to be distracted by work, and hands it is direct last to visit the website, and all thoughts — about optimization of solutions.

And once the problem got to me, it sounded so: "The decimal number 585 is 1001001001 in binary. It is palindromic in both bases. Find n-th palindromic number". And if in Russian, then so: "the decimal number 585 in a binary type looks as 1001001001. It is a palindrome in both numeration systems. Find n-y a similar palindrome". It's not true difficult was also solved 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 ill luck. Approximately at that time attacked the website habraeffekt, and tests in any did not want to pass, fell off on timeout. In a local chat discussion on optimization of a solution began, but nobody gave a practical advice. Then released the website, all tests were passed, but the desire needed to be optimized …

We generate decimal palindromes


For a start it became interesting to me how many I will be able to find palindromes on the machine. Though in a chat also did not advise to look for more than 22, I quietly found 27 in only 5 seconds, and here following came only in more than 4 minutes. Farther I did not begin to wait — long for something. To begin optimization, I decided to learn palindromes in more detail.

Generated to itself several 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 the numerical palindrome is a certain number which was taken, otzerkalit and attached in the end of the same number. I.e. took number 235, otzerkalit, received 532 and connected — the fine palindrome — turned out 235532. Also the decision was made: why to touch all numbers in search of a decimal palindrome if it is possible just to 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 are passed, and added a simple loop on the first nine numbers.

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

Having started once again, I saw that my error was much stronger. I absolutely forgot about palindromes with odd quantity of signs, such as 313, 585 or 717! And here I had to reflect strong. Having looked at the list of the received palindromes, it is possible to see that palindromes with odd quantity of signs are the same even palindromes, only with a center sign. I.e. we take an even palindrome, we insert into the center of digit 1-9 and voila — odd palindromes are ready. But! If I insert them in this cycle, I will lose an order of numbers. Therefore it was necessary to make cardinal changes to a code and to make a start from quantity of signs.

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, here everything is simple. We take at first one-bit numbers 1-9. We create two-bit palindromes. Afterwards three-bit. Then simply we increase discharge and we take numbers of 10-99. Palindromes of the 4th and 5-tirazryadny will turn out. Well, etc.

We test!


For a start started to look at the 28th palindrome. It turned out that for the improved function it is absolutely trifling task. the 28th was received in 0:15 seconds! And it means that speed was increased more than by 1500 times. I was happy. In 5 seconds I could receive already more than 40 palindromes. the 50th was received in 2.5 minutes.

Having paid attention to the received palindromes, I noticed that all of them are odd. And truth! Even decimal palindromes in a binary type will come to an end on 0 and as they always begin with 1, and cannot be a palindrome. And it means that they even do not need to be checked. And as we generate palindromes, we can pass all numbers with the first even digit.

Simple continue on a condition swept aside at once. Even it does not make sense to twist to us on them a cycle. We will glance over 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 stopped on the last as on the fastest and received here such code.

Complete 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++;
   }
}


It we received acceleration still approximately twice. the 50th was received in 88 seconds and, in my opinion, it was the excellent result!

We generate binary palindromes


And here I was already ready to stop and be glad as the thought came to my mind to try to create binary palindromes. And what? It is less used digits, even you will not generate. One pluses around!

Having a little thought, I fast changed a code and received:

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 tests I understood that I made everything correctly. the 28th was received in 0:05 seconds. the 50th in 48 seconds. When undertook this task, I did not expect such result at all.

Here I already decided what will be enough: I already exceeded all the expectations. Though I lie, of course. Then still tried to think up as it is possible to increase speed even more, but already nothing came to mind. Was tired already and night outside.

Well and finally pivot table:

Pivot table
Palindrome Search (sec.) Generation of dec of palindromes (sec.) Generation of bin of palindromes (sec.) number of bits
1 1 6.9141387939453E-6 5.0067901611328E-6 1
2 3 5.1975250244141E-5 4.887580871582E-5 4.2200088500977E-5 2
3 5 5.8889389038086E-5 5.5074691772461E-5 6.0081481933594E-5 3
4 7 6.4849853515625E-5 6.103515625E-5 6.6041946411133E-5 3
5 9 6.9856643676758E-5 6.6041946411133E-5 7.4148178100586E-5 4
6 33 8.2969665527344E-5 7.1048736572266E-5 9.0122222900391E-5 6
7 99 0.00011205673217773 8.6069107055664E-5 0.00010299682617188 7
8 313 0.00020503997802734 0.00010395050048828 0.00012612342834473 9
9 585 0.00033092498779297 0.00012397766113281 0.00014519691467285 10
10 717 0.0003969669342041 0.00013089179992676 0.0001521110534668 10
11 7447 0.0026609897613525 0.0001828670501709 0.00027918815612793 13
12 9009 0.0031960010528564 0.00020384788513184 0.00030112266540527 14
13 15351 0.0053460597991943 0.0002899169921875 0.00034999847412109 14
14 32223 0.011164903640747 0.00038385391235352 0.00047707557678223 15
15 39993 0.013840913772583 0.00048685073852539 0.00052118301391602 16
16 53235 0.018357038497925 0.00053596496582031 0.00057101249694824 16
17 53835 0.018585920333862 0.00054693222045898 0.0005891323089599 16
18 73737 0.025254964828491 0.00066089630126953 0.00065517425537109 17
19 585585 0.19646406173706 0.0011670589447021 0.0015511512756348 20
20 1758571 0.59263801574707 0.0026059150695801 0.0024890899658203 21
21 1934391 0.65274286270142 0.002892017364502 0.0026500225067139 21
22 1979791 0.66831588745117 0.0029850006103516 0.0027000904083252 21
23 3129213 1.0589859485626 0.00323486328125 0.0032520294189453 22
24 5071705 1.7217099666595 0.0046730041503906 0.0040431022644043 23
25 5259525 1.7863478660583 0.0049829483032227 0.0041420459747314 23
26 5841485 1.9860379695892 0.0059189796447754 0.0043931007385254 23
27 13500531 4.5991010665894 0.0097908973693848 0.0064051151275635 24
28 719848917 254.43427205086 0.074897050857544 0.046326160430908 30
29 910373019 0.090998888015747 0.051257133483887 30
30 939474939 0.096122026443481 0.05202817916870 30
31 1290880921 0.11239194869995 0.061146974563599 31
32 7451111547 0.16925406455994 0.15515112876892 33
33 10050905001 0.19922494888306 0.18062520027161 34
34 18462126481 0.36378288269043 0.2389931678772 35
35 32479297423 0.4427649974823 0.33302116394043 35
36 75015151057 0.88776993751526 0.48717308044434 37
37 110948849011 1.20951795578 0.60900402069092 37
38 136525525631 1.2637610435486 0.69635009765625 37
39 1234104014321 2.6941239833832 2.0280501842499 41
40 1413899983141 3.0781800746918 2.1862101554871 41
41 1474922294741 3.2089228630066 2.2403671741486 41
42 1792704072971 3.8874368667603 2.5199501514435 41
43 1794096904971 3.8904230594635 2.521210193634 41
44 1999925299991 4.3287780284882 2.7018330097198 41
45 5652622262565 7.9812479019165 4.4443550109863 43
46 7227526257227 9.285425901413 5.1428310871124 43
47 7284717174827 9.4120988845825 5.1688570976257 43
48 9484874784849 12.100240945816 5.998220205307 44
49 34141388314143 16.401521921158 11.614565134048 45
50 552212535212255 87.537031888962 49.897539138794 49
51 933138363831339 134.56801986694 62.49614405632 50
52 1793770770773971 171.45103907585 90.226871013641 51
53 3148955775598413 180.56048107147 119.85724520683 52
54 10457587478575401 293.4983189106 224.45361399651 54
55 10819671917691801 303.29767894745 227.38862919807 54
56 18279440804497281 506.18344306946 287.77621507645 55
57 34104482028440143 410.04529714584 55
58 37078796869787073 428.8955411911 56
59 37629927072992673 431.15429711342 56
60 55952637073625955 506.2887160778 56


This article is a translation of the original post at habrahabr.ru/post/270325/
If you have any questions regarding the material covered in the article above, please, contact the original author of the post.
If you have any complaints about this article or you want this article to be deleted, please, drop an email here: sysmagazine.com@gmail.com.

We believe that the knowledge, which is available at the most popular Russian IT blog habrahabr.ru, should be accessed by everyone, even though it is poorly translated.
Shared knowledge makes the world better.
Best wishes.

comments powered by Disqus