Archive for the ‘sort’ Tag

projecteuler22

projecteuler22

 projecteuler問題22 は、names.txt にある名前をアルファベット順に並べ、全ての名前の順位と名前のアルファベットの値和と積を求め、その総量を求める問題。アルファベットの値は A, B, C,… が 1, 2, 3,… に相当。 
 url にあるデータは get-url で取り出し、sort でソートすれば、後は計算するだけ。繰り返しには dolist でも使いましょうか。文字列の分解には explode が使えます。
 さて、コードは、

(silent)
(setq names (replace "," (parse (get-url "https://projecteuler.net/project/resources/p022_names.txt"))))
(sort names)
(let (res 0)
  (dolist (n names)
    (++ res (* (+ $idx 1) (apply + (map (fn (x) (- x 0x40)) (map char (explode n)))))))
  (println res))

 こんな感じ。これを実行すれば、

871198282

 という答えが得られます。
 silent 文を外せば、names.txt にある名前がすべて表示されます。お好みでどうぞ。
 以上、如何でしょうか?

広告

projecteuler4...または、newLISP の繰り返し構文

 projecteuler も5回目。前回はちょっと飛びましたが、今回は順当(笑)に問題4。三桁の数同士を掛け算して、最大の回文数を求めるというもの。
 これをで力技でやると、

(let (lst)
  (for (i 100 999)
    (for (j i 999)
      (let (str (string (* i j)))
        (if (and (= 6 (length str))
                 (= (0 3 str) (reverse (3 3 str))))
          (push str lst -1))
      )
    )
  )
  ((sort lst) -1)
)

 こんな感じ。newLISP には組込で for がありますから楽です。
 組込関数string は引数を文字列に変換します。
 掛け算した結果が6桁なら、文字列にも暗黙のインデックス機能(Implicit indexing)が使えるので、前半と後半を分け、比較します。
 同じなら、変数 lst に入れておいて、最後に組込関数 sort で並べ替えます。この関数は数値でも文字列でもなんでも並べ替えます。
 そして、最後の値(文字列)を取り出せば、答えに 906609 が得られます。
 まっ、これで終了ですが、もう一つ解答例を、

(define-macro (memoize mem-func func) 
  (set (sym mem-func mem-func) 
    (letex (f func  c mem-func) 
      (lambda () 
        (or (context c (string (args))) 
            (context c (string (args)) (apply f (args))))))))
(define (make-sublist lst)
  (let (res '(()()))
    (dolist (x lst)
      (push $idx (if x (res 0) (res 1)) -1))
  res))
(memoize divide2 (lambda (n)
  (let (res)
    (for (x 1 (- (/ (pow 2 n) 2) 1))
      (let (lst (bits x true))
        (push (if (< (length lst) n) (append lst (dup nil (- n (length lst)))) lst)
              res -1))
    )
  (map make-sublist res))))
(define (judge numbers digit)
  (letn (max-num (pow 10 digit)
         sublist (divide2 (length numbers))
         res)
    (dolist (x sublist res)
      (let (n1 (apply * (select numbers (x 0)))
            n2 (apply * (select numbers (x 1))))
        (if (and (< n1 max-num) (< n2 max-num)) (push (list n1 n2) res)))
     )
    res
  ))
(letn (digit 3
       max-num (pow 10 digit)
       numbers (sequence (pow 10 (- digit 1)) (- max-num 1))
       strings1 (map string numbers)
       strings2 (map reverse strings1)
       palindromes (map int (map append strings1 strings2))
       res)
  (dolist (x (reverse palindromes) res)
    (let (primes (factor x))
      (when (< (apply max primes) max-num)
        (if (judge primes digit) (setq res x)))))
  res
)

 コードは長いですが、実行時間は二桁早くなります。
 やっているのは、最初に回文数のリストを作って、大きい方から三桁同士の掛け算になるかどうかを判定するというもの。
 解説は、、、次回に。

 以上、如何でしょうか?