Skip to content

Instantly share code, notes, and snippets.

@kohyama
Created December 19, 2012 10:19
Show Gist options
  • Save kohyama/4335755 to your computer and use it in GitHub Desktop.
Save kohyama/4335755 to your computer and use it in GitHub Desktop.
Project Euler Problem 17
(require '[clojure.test :refer (is)])
(defn in-words
"Represents the given number in English words without spaces nor hyphens.
This works with a number in the range from 1 to 1000"
[n]
(cond
(< n 20)
(["" "one" "two" "three" "four" "five" "six" "seven" "eight"
"nine" "ten" "eleven" "twelve" "thirteen" "fourteen"
"fifteen" "sixteen" "seventeen" "eighteen" "nineteen"] n)
(< n 100)
(str
(["twenty" "thirty" "forty" "fifty" "sixty" "seventy"
"eighty" "ninety"] (- (quot n 10) 2))
(in-words (mod n 10)))
(< n 1000)
(let [nmod100 (mod n 100)]
(str
(in-words (quot n 100))
"hundred"
(if (zero? nmod100) ""
(str "and" (in-words nmod100)))))
(= n 1000) "onethousand"))
(is (= (in-words 18) "eighteen"))
(is (= (in-words 746) "sevenhundredandfortysix"))
(defn pep017
"Counts letters of words representing numbers from 1 to the given number"
([n] (apply + (map (comp count in-words) (range 1 (inc n)))))
([] (pep017 1000)))
(is (= (pep017 5) 19))
(pep017)
@kohyama
Copy link
Author

kohyama commented Dec 19, 2012

#clojure 入門者向け勉強会 #mitori_clj 第三週担当分
Project Euler Problem 17
「1 から 1000 までの数を英単語で書いた場合の文字数はいくらか. ただし空白やハイフンは除く」ということです.

空白とハイフンを除いた英単語表記を返す汎用関数を用意して数えています.
文字数のみが要ることを利用した最適化は施していません.

@ypsilon-takai
Copy link

僕の現状の回答を見てみたら、下の桁から順にループで回してました。
再帰的に適用する手法は参考になります。

各単語には出現パターンがあるので、それを利用して計算できるんじゃないかと思っているのですが、未挑戦です。

@tnoda
Copy link

tnoda commented Dec 22, 2012

最初見たときには,どうしてこれ動くんだろうと思っていたのですが,よく見てみると,

  • ベクタを関数として使っている.
    • (nth v n) 相当.
  • 再帰を使って上の桁から順に刈っている.
    • いいかえると下の桁からスタックに積んでいっている.
  • cond の条件の順番が絶妙

で,巧妙にできていることがわかりました.書き方としては自然に思えますし,私もすんなりとこういう関数を書けるようになりたいのですが,現状そのレベルには達していないので,業務アプリ屋なりの方法で解いてみました.

(ns tnoda.projecteuler.problem-17
  (:import com.ibm.icu.text.RuleBasedNumberFormat ; [com.ibm.icu/icu4j "50.1"]
           java.util.Locale)
  (:use [clojure.test :only [is]]))

(def ^:private formatter (RuleBasedNumberFormat. Locale/ENGLISH RuleBasedNumberFormat/SPELLOUT))

(defn- spellout
  [^long n]
  (.format ^RuleBasedNumberFormat formatter n "%spellout-cardinal-verbose"))

(defn- solver*
  [n]
  (->> (range 1 (inc n))
       (mapcat spellout)
       (remove #{\- \space})
       count))

(def solver (partial solver* 1000))

(is (= 19 (solver* 5)))

ICU4J というライブラリを使っています.SE だったらこれが模範解答でしょう,と言いたいところですが,これを Java で書くのは難しいので,ちょっと模範解答にはできません.というのも, "%spellout-cardinal-verbose" が undocumented で,REPL で formatter をプリントしてみないと見つからないからです.Clojure には REPL がありますが Java にはありません.REPL で値を確認しながら開発できるというのは,Clojure の Java に対するアドバンテージの一つだと思います.

余談ですが,RuleBasedNumberFormat を作るときに Locale/JAPANESE を指定すると漢数字で書き下します.今後,そのような要求のある案件に当たったときには ICU4J の採用を検討してみてはいかがでしょうか.IBM 製だからそれなりに信頼できます.

@kohyama
Copy link
Author

kohyama commented Dec 23, 2012

@tnoda
ICU4J 知らなかったです. いいですね. ご紹介ありがとうございます.
数の書式に限らず国際化からみのいろいろをやってくれるんですね.

@plaster
Copy link

plaster commented Jan 3, 2013

私も @kohyama さんとほとんど同じ解き方になりました。20未満が特別扱いになること、かつ mod 10 や quot 100 の部品としても使えるのがいいですよね。
@tnodaさん紹介のICU4Jは、文字の扱い周りで名前だけ聞いたことがあった気がします。こんなことまでやってくれるのはびっくりです。

@emanon001
Copy link

僕も @plaster さんと同様に、@kohyama さんとほとんど同じ解き方でした。ローマ数字や漢数字と比べると、特別扱いする数が多いので、少し戸惑いました。

ベクタやマップ、キーワードが関数としても使用できることについては、Clojure を学び始めた当初、相当な違和感と気持ち悪さを感じていましたが、今ではすっかり便利な機能だと感じるようになりました。

あと、解答には直接関係ないのですが、cond のインデントが気に入りました。

(cond
  (test-a)
    (expr-a)
  (test-b)
    (expr-b))

VimClojure だと testexpr 間でインデントが変わらないため、手動でインデントを修正する必要がありますが……


おお、ICU4J すごい。毎度のことですが、@tnoda さんが Clojure から Java の既存ライブラリが使用できることの有用性を示してくれているのはとても有り難いです。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment