Commentaires sur le programme Lisp pour le projet euler 4

Question

Je viens de commencer à apprendre le Lisp commun et j'ai donc travaillé sur des problèmes de projet euler. Voici ma solution (avec de l'aide de https://github.com/qlkzy/project-euler-cl). Est-ce que vous avez des suggestions pour des changements stylistiques et le genre pour le rendre plus lisp-y?

; A palindromic number reads the same both ways. The largest palindrome made 
; from the product of two 2-digit numbers is 9009 = 91 99. 
; Find the largest palindrome made from the product of two 3-digit numbers. 

(defun num-to-list (num) 
    (let ((result nil)) 
     (do ((x num (truncate x 10))) 
      ((= x 0) result) 
      (setq result (cons (mod x 10) result))))) 

(defun palindrome? (num) 
    (let ((x (num-to-list num))) 
     (equal x (reverse x)))) 

(defun all-n-digit-nums (n) 
    (loop for i from (expt 10 (1- n)) to (1- (expt 10 n)) collect i)) 

(defun all-products-of-n-digit-nums (n) 
    (let ((nums (all-n-digit-nums n))) 
     (loop for x in nums 
      appending (loop for y in nums collecting (* x y))))) 

(defun all-palindromes (n) 
    (let ((nums (all-products-of-n-digit-nums n))) 
     (loop for x in nums 
      when (palindrome? x) collecting x))) 

(defun largest-palindrome (n) 
    (apply 'max (all-palindromes 3))) 

(print (largest-palindrome 3)) 

Answer 1

(setq list (cons thing list)) 

peut être simplifié à:

(push thing list) 

Mes autres commentaires sur votre code ne sont pas tellement sur le style Lisp sur l'algorithme. Créer toutes ces listes intermédiaires de nombres semble être un mauvais moyen de le faire, il suffit d'écrire des boucles imbriquées qui calculent et testent les nombres.

(defun all-palindromes (n) 
    (loop for i from (expt 10 (1- n)) to (1- (expt 10 n)) 
    do (loop for j from (expt 10 (1- n)) to (1- (expt 10 n)) 
      for num = (* i j) 
     when (palindrome? num) 
      collect num))) 

Mais LOOP a une fonctionnalité que vous pouvez utiliser: MAXIMIZE. Ainsi, au lieu de recueillir tous les palindromes dans une liste avec COLLECT, vous pouvez:

(defun largest-palindrome (n) 
    (loop with start = (expt 10 (1- n)) 
     and end = (1- (expt 10 n)) 
     for i from start to end 
    do (loop for j from start to end 
      for num = (* i j) 
     when (palindrome? num) 
      maximize num))) 

Voici une autre optimisation:

(defun largest-palindrome (n) 
    (loop with start = (expt 10 (1- n)) 
     and end = (1- (expt 10 n)) 
     for i from start to end 
    do (loop for j from i to end 
      for num = (* i j) 
     when (palindrome? num) 
      maximize num))) 

Faire le début de la boucle interne de i au lieu de start évite la redondance de vérifier à la fois M*N et N*M.

Answer 2

L'exemple ci-dessous est un peu artificiel, mais il trouve le palindrome dans beaucoup moins d'itérations que votre approche originale:

(defun number-to-list (n) 
    (loop with i = n 
    with result = nil 
    while (> i 0) do 
     (multiple-value-bind (a b) 
      (floor i 10) 
     (setf i a result (cons b result))) 
    finally (return result))) 

(defun palindrome-p (n) 
    (loop with source = (coerce n 'vector) 
     for i from 0 below (floor (length source) 2) do 
     (when (/= (aref source i) (aref source (- (length source) i 1))) 
     (return)) 
     finally (return t))) 

(defun suficiently-large-palindrome-of-3() 
    ;; This is a fast way to find some sufficiently large palindrome 
    ;; that fits our requirement, but may not be the largest 
    (loop with left = 999 
    with right = 999 
    for maybe-palindrome = (number-to-list (* left right)) do 
     (cond 
     ((palindrome-p maybe-palindrome) 
      (return (values left right))) 
     ((> left 99) 
      (decf left)) 
     ((> right 99) 
      (setf left 999 right (1- right))) 
     (t        ; unrealistic situation 
             ; we didn't find any palindromes 
             ; which are multiples of two 3-digit 
             ; numbers 
      (return))))) 

(defun largest-palindrome-of-3() 
    (multiple-value-bind (left right) 
     (suficiently-large-palindrome-of-3) 
    (loop with largest = (* left right) 
     for i from right downto left do 
     (loop for j from 100 to 999 
      for maybe-larger = (* i j) do 
       (when (and (> maybe-larger largest) 
         (palindrome-p (number-to-list maybe-larger))) 
       (setf largest maybe-larger))) 
     finally (return largest))))  ; 906609 

Il tente également d'optimiser un peu la façon dont vous mesurez ce nombre est un palindrome , pour un coût supplémentaire de mémoire cependant. Il divise également le nombre en une liste en utilisant un peu plus de code, mais en faisant moins de divisions (ce qui est un peu coûteux en calcul).

L'idée est basée sur le concept que le plus grand palindrome sera quelque part plus vers les ... plus grands multiplicateurs, donc, en commençant par 99 * 99 vous aurez beaucoup de mauvais matchs. Au lieu de cela, il essaie d'aller de 999 * 999 et d'abord trouver un palindrome, qui semble bon, le faire d'une manière «bâclée». Et ensuite, il s'efforce d'améliorer la découverte initiale.

Answer 3

solution de Barnar est grande mais il y a juste une petite faute de frappe, pour renvoyer un résultat, il devrait être:

(defun largest-palindrome (n) 
    (loop with start = (expt 10 (1- n)) 
     and end = (1- (expt 10 n)) 
     for i from start to end 
     maximize (loop for j from i to end 
         for num = (* i j) 
         when (palindrome? num) 
         maximize num)))