Вперед, на поиски палиндромов

Не так давно на Хабре была статья про codebattle от hexlet.io. Ну и затянуло же нас с друзьями, это как наркотик! Вроде пытаешься на работу отвлечься, а руки прям сами тянутся зайти на сайт, и все мысли — об оптимизации решений.

И вот однажды попалась мне задачка, звучала она так: «The decimal number 585 is 1001001001 in binary. It is palindromic in both bases. Find n-th palindromic number». А если по-русски, то так: «десятичное число 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;
}

Но вот незадача. Примерно в то время на сайт напал хабраэффект, и тесты ни в какую не хотели проходить, отваливались по timeout. В местном чате началось обсуждение по оптимизации решения, но никто дельного совета так и не дал. Потом сайт отпустило, все тесты прошли, но желание оптимизировать осталось…

Генерируем десятичные палиндромы

Для начала мне стало интересно, сколько же я смогу найти палиндромов на своей машинке. Хоть в чате и не советовали искать больше 22-х, я спокойно нашел 27 всего за 5 секунд, а вот следующий пришел только через 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;
}

Запустив, я увидел, что пропущены однознаковые палиндромы, и добавил простой цикл на первые девять чисел.

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. Создаем двухразрядные палиндромы. Следом трёхразрядные. Потом просто увеличиваем разряд и берем числа от 10-99. Получатся палиндромы 4-х и 5-тиразрядные. Ну и т.д.

Тестируем!

Для начала запустил посмотреть 28-ой палиндром. Оказалось что для улучшенной функции это абсолютно плёвая задача. 28-ой был получен за 0.15 секунды! А это значит, что скорость была увеличена больше чем в 1500 раз. Я был доволен. За 5 секунд я мог получить уже более 40-а палиндромов. 50-ый был получен за 2.5 минуты.

Обратив внимание на полученные палиндромы, я заметил, что все они нечетные. И ведь правда! Четные десятичные палиндромы в двоичном виде будут заканчиваться на 0, а так как они всегда начинаются с 1, то и палиндромом быть не могут. А это значит, что их даже проверять не нужно. А так как палиндромы мы генерируем, мы можем пропускать все числа с первой четной цифрой.

Простой continue по условию сразу отмёл. Нам даже не имеет смысла крутить на них цикл. Будем их пролистывать. Попробовав несколько вариантов:

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

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

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

Я остановился на последнем как на самом быстром и получил вот такой код.


Этим мы получили ускорение ещё примерно в два раза. 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 секунды. 50-ый за 48 секунд. Когда брался за эту задачу, такого результата я совсем не ожидал.

Тут я уже решил, что хватит: я и так превзошел все свои ожидания. Хотя вру, конечно. Потом ещё пытался придумать как можно увеличить скорость ещё больше, но уже ничего в голову не пришло. Устал уже, да и ночь на дворе.

Ну и напоследок сводная таблица:


PS. Продолжение оптимизации от ilyanik смотрите в этой статье