Clojure で超簡単な問題を解いてみる

正月休みの最終日だが、また Clojure をいじってみた。

今日は、Project Euler の Problem 4をやってみる。問題の内容は、3桁の数を二つ掛け合わせて得られる最大の回文数は何かというもの。

まあ、使い慣れた言語だったら何てことない問題だけど、始めたばかりなの Clojure なので何かと難航する。 とりあえず効率は無視して書いたのがこんな感じ。

(ns euler.pe004
  (:use clojure.contrib.generic.math-functions))

(def digits 3)
(def max' (int (dec (pow 10 digits))))
(def min' (int (pow 10 (dec digits))))

(defn palindromic? [n]
  (let [original (str n)
        reversed (apply str (reverse original))]  
    (= original reversed)))

(defn solve [] 
  (apply max (for [x (range min' (inc max')) 
                   y (range x (inc max'))
                   :when (palindromic? (* x y))]
               (* x y))))

ほぼ総当たりのかなり遅いコードだけど、これだけでも、:use と :require の違いや project.clj での dependencies の指定の仕方だとか、Clojure での リスト内包表記のやり方だとかが、だんだんわかってきて面白い。

ただ、この手の問題で非効率なのはやはり気になるので、無駄な計算を排して瞬時に答えが得られるように修正してみた。

(ns euler.pe004
  (:use clojure.contrib.generic.math-functions))

(def digits 4)
(def max' (int (dec (pow 10 digits))))
(def min' (int (pow 10 (dec digits))))

(defn palindromic? [n]
  (let [original (str n)
        reversed (apply str (reverse original))]  
    (= original reversed)))

(defn cols [row] (range max' (dec row) -1))

(defn find-col [row cols max']
  (let [[col & cols'] cols 
        product (* col row)]
    (if (< product max') 0 
      (if (palindromic? product) product
        (if (seq cols') (find-col row cols' max') 0)))))
      
(defn find-product [current-max rows] 
  (let [[row & rows'] rows
        product (find-col row (cols row) current-max)
        larger (max product current-max)]
    (if (and (seq rows') (< larger (* max' (first rows')))) 
        (find-product larger rows')
        larger))) 

(defn solve [](find-product 0 (range max' min' -1)))

これだと桁数が4桁でも、元のコードで数分かかる計算が、ほぼ一瞬で終わる

しかしやっぱり、効率のために「手続き」を考慮するようになると、宣言的に書いた時の表現力が失わるっつうのは、何かと惜しいがまあしょうがないんだな。