На прошлой неделе друг представил мне эту задачу из Project Euler, и мы рассмотрели ее базовое решение.

«Палиндромное число одинаково читается в обоих случаях. Самый большой палиндром, составленный из произведения двух двузначных чисел, равен 9009 = 91 × 99.

Найдите самый большой палиндром, составленный из произведения двух трехзначных чисел».

Мы начали с осознания того, что нам потребуются два отдельных метода: один для перебора возможных произведений двух трехзначных чисел, начиная с самого большого, а второй — для проверки того, является ли каждое произведение палиндромом.

Наш метод расчета продукта выглядел так:

def product_calculator
 product = 0
 highest_product = 0
 three_digit = [*100..999].reverse
 second_array = [*100..999].reverse
three_digit.each do |num|
  second_array.each do |second_num|
   product = num*second_num
   if checkForPalindrome(product)
     highest_product = product
    end
   end
  end
 end
 highest_product
end

Есть две вещи, которыми я горжусь, узнав об этом методе. Первый заключался в создании массива из 999–100, а второй, который мы поняли после некоторого неавтоматического тестирования, заключался в том, что нам на самом деле нужны оба цикла — что если бы мы использовали только один массив, это было бы просто 999*999, а затем 998 * 998 и т. д., и что самый большой палиндром на самом деле может быть 991 * 998 или что-то в этом роде. Итак, он работает за время O(n2) — n в квадрате, но, по крайней мере, он действительно работает!

Кроме того, использование двух точек/десятичных точек/эллипсов, например, 0..99, делает массив включающим оба конца. три точки будут до последнего числа, но не включая его.

Чтобы проверить, является ли число палиндромом, я создал массив и перебрал только его половину, сравнивая массив [0] с массивом [-1], массив [1] с массивом [-2] и т. д. позже понял, что стек будет более эффективным, поэтому я продемонстрирую способ его кодирования в следующем посте!

вот метод проверки палиндрома:

def check_for_palindrome(int)
 array = int.to_s.chars
 half = (array.length/2)
 looping_array = [*0..half]
looping_array.each do |num|
  if !(array[num] == array[-1*(num+1)])
   return false
  end
 end
 return true
end

Когда я начал писать это на JavaScript, чтобы писать тесты (ждите следующего поста в блоге!), я понял, что перевод этого метода, который было легко закодировать на Ruby, будет проблемой, и что потребуется новая концепция.

Когда я обсудил это с другим другом, он предложил создать два массива, один с числами, записанными как обычно, а другой с числами, записанными наоборот, и сравнить их. Это казалось отличным планом, пока не стало ясно, что сравнение двух массивов никогда не вернет true, поскольку хранящие их переменные указывают на два разных места в памяти. Поэтому мы реализовали эту логику со строками:

function checkForPalindrome(number){
 const forward = number.toString()
 const reverse = forward.split('').reverse().join('')
 return forward === reverse
}

Какие красивые 4 строчки кода! Оставайтесь с нами, чтобы узнать, как это выглядит.