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.
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 ...
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.
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!
Having started, I saw that one-sign palindromes were missing, and added a simple cycle to the first nine numbers.
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.
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.
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:
I settled on the latter as the fastest and got this code.
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!
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:
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:
PS. Continuation of optimization from ilyanik see in this article
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
- 3
- 5
- 7
- 9
- 33
- 99
- 313
- 585
- 717
- 7447
- 9009
- 15351
- 32223
- 39993
- 53235
- 53835
- 73737
- 585585
- 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. | Palindrome | Search (sec) | Palindrome dec generation (sec) | Palindrome bin generation (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 |
eleven | 7447 | 0.0026609897613525 | 0.0001828670501709 | 0.00027918815612793 | thirteen |
12 | 9009 | 0.0031960010528564 | 0.00020384788513184 | 0.00030112266540527 | 14 |
thirteen | 15351 | 0.0053460597991943 | 0.0002899169921875 | 0.00034999847412109 | 14 |
14 | 32223 | 0.011164903640747 | 0.00038385391235352 | 0.00047707557678223 | fifteen |
fifteen | 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 | thirty |
29th | 910373019 | 0.090998888015747 | 0.051257133483887 | thirty | |
thirty | 939474939 | 0.096122026443481 | 0.05202817916870 | thirty | |
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 | |
fifty | 552212535212255 | 87.537031888962 | 49.897539138794 | 49 | |
51 | 933138363831339 | 134.56801986694 | 62.49614405632 | fifty | |
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 |
PS. Continuation of optimization from ilyanik see in this article