Как я могу обобщить мой код, чтобы найти номер палиндрома для двух чисел с большим количеством цифр 4,5 или 6 и что я могу сделать, чтобы он работал быстрее?

Question

Я хочу, чтобы код палиндрома работал не только для 3 цифр, но и для 4, 5 или 6, и как я могу работать быстрее?

to = 999
from = 100
palindroms = []
for i in from..to do
  p i
  for j in 1..to do
    k = i * j
    palindroms << k if k.to_s == k.to_s.reverse
  end
end
puts palindroms.max

Answer 1

Вот еще одно решение:

class PalindromeGenerator
  def initialize(length)
    raise ArgumentError if length <= 1

    @length = length
  end

  def run
    length.odd? ? run_odd : run_even
  end

  private

  attr_reader :length

  def run_even
    halves.map { |half| "#{half}#{half.to_s.reverse}".to_i }
  end

  def run_odd
    halves.each_with_object([]) do |half, memo|
      middles.each do |middle|
        memo << "#{half}#{middle}#{half.to_s.reverse}".to_i
      end
    end
  end

  def halves
    half_length = length / 2
    min = 10**(half_length - 1)
    max = 10**half_length
    (min...max)
  end

  def middles
    (0..9)
  end
end

Он строит левые половины палиндрома из заданного length.Затем он строит список палиндромов:

• Если length четный, просто map и зеркально отразить левую половину.
• Если length нечетно, для каждой половиныВы должны построить 10 палиндромов, добавив любое число в середине.

---

Например, если length = 5:

• half_length равно 2.
• Все левые половины - это числа от 10 (10**(2-1)) до 99 (10**2 - 1).
• Поскольку 5 нечетно, список можно построить следующим образом:
  • half = 10 -> [10001, 10101, 10201, 10301, 10401, 10501, 10601, 10701, 10801, 10901]
  • half = 11 -> ...
  • ...

Я так думаюможно было бы немного оптимизировать, но это уже намного лучше, чем наивный подход.

Answer 2

Возможно, это неэффективно, но основная идея состоит в том, чтобы разбить число на массив цифр ( Integer # digits ) и проверить половинки:

n = 12421

digits = n.digits
digits[0...digits.size / 2] == digits.reverse[0...digits.size / 2]
#=> true

Answer 3

Решение:

def palindrome(nb, exlude_zeros = true)
  raise ArgumentError, 'nb should be >= 1' if nb < 1
  num_permutation = nb / 2
  should_generate_middle_column = nb.odd?
  # Process
  if should_generate_middle_column
    # In this part we'll generate 101 111 121 131 141 151 161 171 181 191
    # The middle column is 0 1 2 3 4 5 6 7 8 9 for 1x1
    # Before generating the middle column we'll generate the permutation like in the else part.
    result = (0..9).to_a.repeated_permutation(num_permutation).collect do |arr|
      rev = arr.reverse
      (0..9).collect { |i| (arr.clone << i).concat(rev).join.to_i }
    end
    result.flatten!
  else
    # In this part we'll only find the permutations (for nb / 2) 
    # and mirror the permutations givin the palindrome.
    result = (0..9).to_a.repeated_permutation(num_permutation).collect do |arr|
        arr.concat(arr.reverse).join.to_i
    end
  end
  result.reject! { |i| i.to_s.size != nb } if exlude_zeros
  return result
end

Вы можете назвать это так:
палиндром (1)
палиндром (2)
палиндром (3)
и т. Д ...

Будет возвращен список номеров палиндрома того размера, который вы указали в качестве входного номера.

Answer 4

Предположим, мы хотим идентифицировать все палиндромы между from = 27 и to = 3345. Вместо того, чтобы исследовать каждое число от from до to, чтобы определить палиндромы, я сгенерирую все палиндромы между 20 и 3999 рекурсивно и комбинаторно, а затем использую два двоичных поиска, чтобы исключить все палиндромы между 20 и 26 (то есть, только 22) и все палиндромы между 3346 и 3999.

Код

def palindromes(from, to)
  arr = ranges(from, to).each_with_object([]) do |(n,f,t),arr|
    arr.concat(pals(n,f,t))
  end.map { |a| a.join.to_i }                                                                          
  is = arr.bsearch_index { |n| n >= from }
  ie = arr.bsearch_index { |n| n > to }
  ie = ie.nil? ? arr.size-1 : ie-1
  arr[is..ie]
end

def ranges(from, to)
  *a, from_first_digit = from.digits
  from_nbr_digits = a.size + 1
  *a, to_first_digit = to.digits
  to_nbr_digits = a.size + 1
  (from_nbr_digits..to_nbr_digits).each_with_object([]) { |ndigits, a|
    a << [ndigits, from_nbr_digits == ndigits ? from_first_digit : 1,
          to_nbr_digits == ndigits ? to_first_digit : 9] }
end

def pals(ndigits, first, last)
  case ndigits
  when 1
    (first..last).to_a
  when 2
    (first..last).map {|d| [d,d]}
  else
    a = pals(ndigits-2, 0, 9)
    (first..last).each_with_object([]) { |d,arr|
      a.each {|b| arr << [d,*b,d] } }
  end
end

Примеры

palindromes(27, 3345)
  #=> [                    33,   44,   55,   66,   77,   88,   99,
  #     101,  111,  121,  131,  141,  151,  161,  171,  181,  191,
  #     202,  212,  222,  232,  242,  252,  262,  272,  282,  292,
  #     ...
  #     909,  919,  929,  939,  949,  959,  969,  979,  989,  999,
  #    1001, 1111, 1221, 1331, 1441, 1551, 1661, 1771, 1881, 1991,
  #    2002, 2112, 2222, 2332, 2442, 2552, 2662, 2772, 2882, 2992,
  #    3003, 3113, 3223, 3333]

palindromes(1141, 3345)
  #=> [            1221, 1331, 1441, 1551, 1661, 1771, 1881, 1991,
  #    2002, 2112, 2222, 2332, 2442, 2552, 2662, 2772, 2882, 2992,
  #    3003, 3113, 3223, 3333]

require 'time'

t = Time.now 
(a = palindromes(27, 34_564_824_166)).size
  #=> 445635 (number of palindromes within range)
puts "Elapsed time = #{(Time.now-t).round(2)} seconds"
  # Elapsed time = 2.77 seconds
a.first(20)
  #=> [                33,  44,  55,  66,  77,  88,  99,
  #    101, 111, 121, 131, 141, 151, 161, 171, 181, 191,
  #    202, 212, 222] 
a.last(10)
  #=> [34563836543, 34563936543, 34564046543, 34564146543, 34564246543,
  #    34564346543, 34564446543, 34564546543, 34564646543, 34564746543] 

Объяснение

(в разработке)