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

少し前に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分以上たってから届きました。 私はそれ以上待たなかった-長い間何か。 最適化を開始するために、回文についてさらに学ぶことにしました。



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





実際、数値パリンドロームは特定の番号であり、同じ番号の末尾に取得、ミラーリング、およびアタッチされます。 つまり 彼らは数字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--;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

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





これにより、約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番目。 この仕事を引き受けたとき、私はそのような結果をまったく期待していませんでした。



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



そして最後に、要約表：





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