Generalised Project Euler Problem 4

README.md

Largest Palindrome Product

Условие оригинальной задачи можно прочитать здесь. Я решил немного усложнить задание и сделать алгоритм для работы на произвольном n, где n - количество цифр во множителях.

Простое решение

С наскоку получается алгоритм вроде этого:

1. Взять множество Int от 10 ^ n - 1 до 0, упорядоченое от большего до меньшего
2. Найти Декартово произведение этого множества самого на себя [(x, y)| x <- xs, y <- xs]
3. Найти пару с найбольшим числом, которое является палиндромом и получено из умножения первого на второй элеметов пары.

Проблемы

Если до 2 пункта включительно все было понятно то на 3-м явно проблемы.

1. Полный перебор всех пар, фильтрование по критерию "палиндромности" и нахождение большего - наиболее точный но слишком затратный способ;
2. Упрощение до первой пары с наибольшим первым числом - потеря правильного результата

Примеры

Допустим n = 3 и пары у нас следующие [(999, 999), (999, 998), (999, 997), .. (998, 999), (998, 998), .. (100, 100)] Во-первых сразуможно отрезать половину пар ибо (999, 998) == (998, 999) и т.д. Во-вторых первый найденый палиндром в этом множистве будет 580085, который является произведением 995 * 583, но он не самый большой.

Решение

Во-первых, ограничимся в паре (x, y) x >= y. Во-вторых надо просматривать результаты после нахождения первого палиндрома. Можно проверять множество просто со следующей пары но эффективней будет сразуперейти на следующее число по первому элементу пары.

Пример

1. Мы нашли первый палиндром 580085 для пары (995, 583)
2. Уменьшили пару до (994, 994) и продолжили поиск (* помним, часть пар мы уже отсекли)

Логика размышлений такая, если мы и найдем палиндром больше, первое число будет не 995 (считаем, что для [996 .. 999] мы ничего не нашли), а какое-то другое и можно смело отнимать 1. Если быть доконца честным искомый палиндром может быть только в пределах 995 <= x,y <= 584, т.к. для данного y пару с максимальным результатом мы тоже нашли.

Быстродействие для n=7

Я довольно плохо знаю C и это решение - первое, что пришло в голову, после перерыва почти в 5 лет, за которые я не трогал этот язык. С Haskell только знакомлюсь и тоже не знаю всех возможностей оптимизации, даже C знаю лучше. Python (3.6.0) - первая пришедшая в голову реализация, на данный момент мой рабочий язык.

• Haskell 87.36s
• C 19.13s
• Python 94.48s

UPD

Заменив проверку со строки на числодробилку в Haskell получаем более чем двукратное повышение производительности

• Haskell 41.45s

Palindrome.hs

module Palindrome where

-- Solution for Project Euler Problem 4
-- https://projecteuler.net/index.php?section=problems&id=4

import Safe (headMay)


data Result 
  = Result { getFirst      :: Int 
           , getLast       :: Int 
           , getPalindrome :: Int 
           } deriving (Show)

instance Eq Result where
  a == b = getPalindrome a == getPalindrome b

instance Ord Result where
  compare a b = compare (getPalindrome a) (getPalindrome b)


getNPalindrome :: (Integral n, Show n) => n -> Result
getNPalindrome n = getMaxPalindrome f l r
  where
    l = floor . sqrt $ 10 ^ (2 * n) / 2
    f = 10 ^ n - 1
    r = Result f l 0


getMaxPalindrome :: Int -> Int -> Result -> Result
getMaxPalindrome f l r
  | f < l     = r
  | otherwise = getMaxPalindrome nf nl cr
  where
    cr = maybe r (max r) nr
    nf = pred $ maybe f getFirst nr
    nl = succ $ maybe l getLast nr
    nr = maxPalindromeInRange f l


reverseInt :: Int -> Int
reverseInt = go 0
  where go r 0 = r
        go r x = let (x', r') = x `quotRem` 10
                 in go (r * 10 + r') x'


maxPalindromeInRange :: Int -> Int -> Maybe Result
maxPalindromeInRange f l 
  = headMay
  . filter isPalindrome
  $ [Result f i (f * i)| i <- [f, f - 1 .. l]]
  where
    isPalindrome :: Result -> Bool
    isPalindrome x = let x' =  getPalindrome x
                     in x' == reverseInt x'

palindrome.py

import math

def get_palindrome(n):
    rf = f = 10 ** n - 1
    l = math.floor(math.sqrt(10 ** (2 * n) / 2))
    r = 0
    while f > l:
        for i in range(f, l, -1):
            rt = f * i
            srt = str(rt)
            if srt == srt[::-1] and rt > r:
                r = rt
                l = i
                rf = f
                break
        f -= 1
    return (rf, l, r)