🤸🏼 👨‍🏫 🧟 パリンドロームの検索に行く ↕️ 🙇🏿 🚣🏽

少し前にHabréでhexlet.ioからcodebattleに関する記事がありました。まあ、それは友人と一緒に私たちを引きずりました、それは麻薬のようなものです！あなたは仕事に気を取られようとしているようで、あなたの手は直接サイトに行くように描かれており、すべての考えはソリューションの最適化に関するものです。

そして、ある日問題が発生したとき、次のように聞こえました。「10進数585は2進数で1001001001です。それは両方のベースでパリンドロームです。 n番目の回文数を見つけます。ロシア語の場合、次のようになります。「バイナリ形式の10進数585は、1001001001のように見えます。これは、両方の数値システムの回文です。 n番目の類似の回文を見つけます。それはまったく複雑ではなく、すぐに解決されました。

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

しかし、これは不運です。その頃、ウェブサイトはハラエフェクトに攻撃され、テストは合格したくなく、タイムアウトで落ちました。ローカルチャットで、ソリューションの最適化に関する議論が始まりましたが、実際的なアドバイスはありませんでした。その後、サイトは手放し、すべてのテストは合格しましたが、最適化への欲求は残りました...

10進パリンドロームを生成します

そもそも、タイプライターでパリンドロームをどれだけ見つけることができるのかと思っていました。チャットでは22個以上を検索するように勧められていませんでしたが、わずか5秒で落ち着いて27個を見つけましたが、次のものは4分以上たってから届きました。私はそれ以上待たなかった-長い間何か。最適化を開始するために、回文についてさらに学ぶことにしました。

いくつかのピースを生成し、検討し始めました。

パリンドローム

1
3
5
7
9
33
99
313
585
717
7447
9009
15351
32223
39993
53235
53835
73737
585585
1758571

実際、数値パリンドロームは特定の番号であり、同じ番号の末尾に取得、ミラーリング、およびアタッチされます。つまり彼らは数字235を取得し、それをミラーリングし、532を取得して接続しました。それは美しい回文であることが判明しました-235532。すぐに言ってやった！

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

開始すると、1文字の回文が欠落していることがわかり、最初の9つの数字に単純なサイクルが追加されました。

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

もう一度実行してみると、私の間違いがはるかに強いことがわかりました。 313、585、717などの奇数の文字を含む回文を完全に忘れてしまいました！そしてここで私は一生懸命に考えなければなりませんでした。受信したパリンドロームのリストを見ると、記号の数が奇数のパリンドロームは、同じ偶数のパリンドロームであり、中央の記号だけがあることがわかります。つまり偶数回文を作成し、中央に1〜9の数字を挿入して出来上がり-奇数回文を作成します。しかし！このループにそれらを挿入すると、数字の順序が失われます。そのため、コードに根本的な変更を加え、文字数に基づいて構築する必要がありました。

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

実際、ここではすべてが簡単です。まず、1〜9の1桁の数字を使用します。 2桁の回文を作成します。以下は3桁です。次に、ランクを上げて10〜99の数字を取得します。 4桁と5桁の回文が判明します。まあ、など

テスト中！

最初に、28回目の回文を調べ始めました。改善された機能のために、これは絶対に些細な作業であることが判明しました。 28日は0.15秒で受信されました！これは、速度が1,500倍以上に増加したことを意味します。嬉しかった。 5秒で40回以上の回文を取得できました。 50分は2.5分で受信されました。

結果として生じるパリンドロームに注意を払って、私はそれらがすべて奇妙であることに気づきました。そして真実は！バイナリ形式の10進パリンドロームでさえも0で終わり、常に1で始まるため、パリンドロームにもなり得ません。これは、チェックする必要さえないことを意味します。また、回文を生成するため、最初の偶数桁の数字をすべてスキップできます。

単純な継続は、条件付きですぐに却下しました。私たちがそれらを循環させることは意味がありません。それらをめくります。いくつかのオプションを試しました：

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

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

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

私は後者を最速として解決し、このコードを得ました。

完全なコード

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

これにより、約2倍の加速が得られました。 50秒は88秒で受信され、私の意見では、素晴らしい結果でした！

バイナリパリンドロームを生成します

これで、バイナリパリンドロームを形成しようと考えたので、停止して喜んで準備ができました。そして何？使用される数字が少ないため、偶数であってもできません。周りのいくつかのプラス！

少し考えて、私はすぐにコードを変更し、次のものを得ました：

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

テストの後、私はすべてが正しく行われたことに気付きました。 28秒は0.05秒で受信されました。 48秒で50番目。この仕事を引き受けたとき、私はそのような結果をまったく期待していませんでした。

それから私はすでにそれで十分だと決めました：私はすでにすべての期待を超えました。嘘をついていますが、もちろん。それから彼は速度をさらに上げる方法を考えようとしましたが、何も思い浮かびませんでした。すでに疲れていて、夜は庭で。

そして最後に、要約表：

要約表

いや	パリンドローム	検索（秒）	Palindrome dec generation（秒）	パリンドロームビン生成（秒）	ビット数
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

PS。 ilyanikによる最適化の継続については、この記事をご覧ください

パリンドロームの検索に行く

10進パリンドロームを生成します

テスト中！

バイナリパリンドロームを生成します

More articles: