Project Euler Problem 13 #mitori_clj

problem_13.clj

;;; Project Euler Problem 13
;;; 「50桁の数字100個の和の上位10桁を求めよ」
;;; http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2013

(ns projecteuler-answers.problem-013
  (:require [clojure.math.numeric-tower :as math]
            [clojure.test :refer [are]]))

(def nums
  [37107287533902102798797998220837590246510135740250
   46376937677490009712648124896970078050417018260538
   74324986199524741059474233309513058123726617309629
   91942213363574161572522430563301811072406154908250
   23067588207539346171171980310421047513778063246676
   89261670696623633820136378418383684178734361726757
   28112879812849979408065481931592621691275889832738
   44274228917432520321923589422876796487670272189318
   47451445736001306439091167216856844588711603153276
   70386486105843025439939619828917593665686757934951
   62176457141856560629502157223196586755079324193331
   64906352462741904929101432445813822663347944758178
   92575867718337217661963751590579239728245598838407
   58203565325359399008402633568948830189458628227828
   80181199384826282014278194139940567587151170094390
   35398664372827112653829987240784473053190104293586
   86515506006295864861532075273371959191420517255829
   71693888707715466499115593487603532921714970056938
   54370070576826684624621495650076471787294438377604
   53282654108756828443191190634694037855217779295145
   36123272525000296071075082563815656710885258350721
   45876576172410976447339110607218265236877223636045
   17423706905851860660448207621209813287860733969412
   81142660418086830619328460811191061556940512689692
   51934325451728388641918047049293215058642563049483
   62467221648435076201727918039944693004732956340691
   15732444386908125794514089057706229429197107928209
   55037687525678773091862540744969844508330393682126
   18336384825330154686196124348767681297534375946515
   80386287592878490201521685554828717201219257766954
   78182833757993103614740356856449095527097864797581
   16726320100436897842553539920931837441497806860984
   48403098129077791799088218795327364475675590848030
   87086987551392711854517078544161852424320693150332
   59959406895756536782107074926966537676326235447210
   69793950679652694742597709739166693763042633987085
   41052684708299085211399427365734116182760315001271
   65378607361501080857009149939512557028198746004375
   35829035317434717326932123578154982629742552737307
   94953759765105305946966067683156574377167401875275
   88902802571733229619176668713819931811048770190271
   25267680276078003013678680992525463401061632866526
   36270218540497705585629946580636237993140746255962
   24074486908231174977792365466257246923322810917141
   91430288197103288597806669760892938638285025333403
   34413065578016127815921815005561868836468420090470
   23053081172816430487623791969842487255036638784583
   11487696932154902810424020138335124462181441773470
   63783299490636259666498587618221225225512486764533
   67720186971698544312419572409913959008952310058822
   95548255300263520781532296796249481641953868218774
   76085327132285723110424803456124867697064507995236
   37774242535411291684276865538926205024910326572967
   23701913275725675285653248258265463092207058596522
   29798860272258331913126375147341994889534765745501
   18495701454879288984856827726077713721403798879715
   38298203783031473527721580348144513491373226651381
   34829543829199918180278916522431027392251122869539
   40957953066405232632538044100059654939159879593635
   29746152185502371307642255121183693803580388584903
   41698116222072977186158236678424689157993532961922
   62467957194401269043877107275048102390895523597457
   23189706772547915061505504953922979530901129967519
   86188088225875314529584099251203829009407770775672
   11306739708304724483816533873502340845647058077308
   82959174767140363198008187129011875491310547126581
   97623331044818386269515456334926366572897563400500
   42846280183517070527831839425882145521227251250327
   55121603546981200581762165212827652751691296897789
   32238195734329339946437501907836945765883352399886
   75506164965184775180738168837861091527357929701337
   62177842752192623401942399639168044983993173312731
   32924185707147349566916674687634660915035914677504
   99518671430235219628894890102423325116913619626622
   73267460800591547471830798392868535206946944540724
   76841822524674417161514036427982273348055556214818
   97142617910342598647204516893989422179826088076852
   87783646182799346313767754307809363333018982642090
   10848802521674670883215120185883543223812876952786
   71329612474782464538636993009049310363619763878039
   62184073572399794223406235393808339651327408011116
   66627891981488087797941876876144230030984490851411
   60661826293682836764744779239180335110989069790714
   85786944089552990653640447425576083659976645795096
   66024396409905389607120198219976047599490197230297
   64913982680032973156037120041377903785566085089252
   16730939319872750275468906903707539413042652315011
   94809377245048795150954100921645863754710598436791
   78639167021187492431995700641917969777599028300699
   15368713711936614952811305876380278410754449733078
   40789923115535562561142322423255033685442488917353
   44889911501440648020369068063960672322193204149535
   41503128880339536053299340368006977710650566631954
   81234880673210146739058568557934581403627822703280
   82616570773948327592232845941706525094512325230608
   22918802058777319719839450180888072429661980811197
   77158542502016545090413245809786882778948721859617
   72107838435069186155435662884062257473692284509516
   20849603980134001723930671666823555245252804609722
   53503534226472524250874054075591789781264330331690])

(defn high-order-digits
  "整数 n の上位 m 桁を返します"
  [n m]
  (->> n
    math/abs
    str
    (take m)
    (apply str)
    bigint))

(are [n m expected]
  (= (high-order-digits n m) expected)
  123 1 1
  123 2 12
  123 3 123
  -123 3 123)

(defn solve
  "整数列の和の上位 n 桁を返します"
  ([] (solve nums 10))
  ([nums n]
   (high-order-digits (apply +' nums) n)))

(are [nums n expected]
  (= (solve nums n) expected)
  [100 20 3] 1 1
  [100 20 3] 2 12
  [100 20 3] 3 123
  [-100 -20 -3] 3 123)

(time (solve))
; "Elapsed time: 0.133 msecs"

解説

数値の上位 n 桁を取得するために、数値を符号無しの文字列に変換し、文字列の先頭から n 文字を取得し、数値に戻す。

high-order-digits

Math/abs は BigInt に対応していないため、clojure.contrib.math/abs を使用しています。

文字列を先頭から n 文字取得する処理としては、

(.substring s 0 n)

でもよいと思います。

solve

数値の合計を計算するために + ではなく +' を使用しています。
+ は 整数のプリミティブ型同士の計算結果がオーバーフローした場合に、 BigInt 型への自動変換を行なわず例外を投げます。
今回の問題では全ての整数が BigInt 型であるため、この手の問題は発生しませんが、一応対応を行なっています。

「総和の上位 10桁を求めよ」ということで解法自体は

(->> nums
  (apply +)
  str
  (take 10)
  (apply str))

でだいたい決まりで,

• 入力の形式を何にしておくか
• BigInt 対応をどこに入れるか
• 関数をどこで分けるか, 分けないか
• 最後は 10桁文字列が出た時点で解答とするか, 数値にするべきか.

など, 問題の解法の外に悩みどころが多く, 色がでるところですね.
high-order-digits という切り分け (と名前) は分かりやすくてとても良いと思います.

---

一応「実行環境 clojure 1.4」ってことなので, clojure 1.4 向けの clojure.contrib がリポジトリにあれば, lein の dependency 行を書くか, もしなければ, abs については math.numeric-tower に引き継がれているようですのでそちらを使うのが良いかと思います.

@kohyama の解答が私もベストだと思いますが，この問題は golf できます．文字列は java.lang.String なので先頭 10 文字取るのに .substring メソッドが使えます．さらに，ほとんど見向きされない clojure.core の忘れ去られた関数 subs を使うと，

(-> (apply +' nums)
    str
    (subs 0 10))

と書けます．しかし，この subs 存在理由がよくわかりません．

• .substring() があるのになぜ?l
  • CLR などとのソースコードレベルの互換性向上を目指していた?
  • だとすればもっと他にも欲しい関数はたくさんある．
• clojure.string にないのはなぜ
  • この関数だけ clojure.core にある．
  • おかげで clojure.string 探していて見つからない．

@kohyama

一応「実行環境 clojure 1.4」ってことなので, clojure 1.4 向けの clojure.contrib がリポジトリにあれば, lein の dependency 行を書くか, もしなければ, abs については math.numeric-tower に引き継がれているようですのでそちらを使うのが良いかと思います.

指摘ありがとうございます。math.numeric-tower を使用するようにしました。(ついでに、clojure.test も最小限のものを require するようにしました)

問題の解法の外に悩みどころが多く, 色がでるところですね.

関数の入出力や切り分け、どこまで汎用的に作るのかなど毎回悩みます。
今回の場合は、正の整数だけを受け取るならば、abs 相当の処理は必要ありませんし、文字列をそのまま返しても答えを得ることは可能ですし。
また、high-order-digits という名前ならば、数値そのものよりも、各桁のシーケンスを返すべきではないのか、などなど……。

Clojure を使うようになってからは、その辺りのことを意識する機会が増えたなあと感じています。

@tnoda

おお、clojure.core にあったのですね。
clojure.string を見て、それらしい関数が無かったので .substring を呼ぶしかないと思っていました。

存在意義という点については、

• Java の型をなるべく意識させなくて済む
• 関数(第一級オブジェクト)として扱える
• タイプ数が減る

とかでしょうか。(subs の使用頻度はそこまで高くないだろう、他に関数化すべきものがあるだろう、というのは置いておいて)
clojure.string ではなく clojure.core にあるのは謎のままですが……。