4つの数字を加減乗除して作れる数を求める問題です。
しばらく考えてはみたのですが、総当たり以外にやりかたはなさそうなので、それで実装してます。
2分くらいかかってしまっていますが、まあ、よしとします。
対象となる数字の組み合わせは、0から9までの数から4つです。10C4=210通りです。
それぞれについて、数字を並べ変えたものは、4P4=24通りです。
加減乗除は3つなので、4^3=64通りです。
括弧の付けかたは、すごくたくさんありそうでうんざりしていたのですが、作ってみると意外に少なくて、
演算子を？とすると、
a ? b ? c ? d
a ? (b ? c) ? d
a ? b ? (c ? d)
a ? (b ? c ? d)
の4つであることがわかりました。他の括弧の組み合わせは、他の数字の並び換えで登場するか、
上記のどれかと同じになります。
結局 210*24*64*4=1290240通りの組み合わせを計算すればよさそうなので、それほど時間はかからないはずです。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ;; Problem 93 | |
| ;; "Elapsed time: 12728.056388 msecs" | |
| (require '[clojure.math.combinatorics :as combo]) | |
| (defmacro calc [ex] | |
| `(try | |
| (let [res# ~ex] | |
| (cond ((complement integer?) res#) nil | |
| (<= res# 0) nil | |
| :t res#)) | |
| (catch Exception e# nil))) | |
| (defn calc-all-paren-combo [op-list num-list] | |
| (let [[o1 o2 o3] op-list | |
| [a b c d] num-list] | |
| (filter (complement nil?) | |
| [(calc (o3 (o2 (o1 a b) c) d)) ;a?b?c?d | |
| (calc (o3 (o1 a (o2 b c)) d)) ;a?(b?c)?d | |
| (calc (o2 (o1 a b) (o3 c d))) ;a?b?(c?d) | |
| (calc (o1 a (o3 (o2 b c) d))) ;a?(b?c?d) | |
| ]))) | |
| (defn calc-all-patterns [num-set operator-pleces] | |
| (->> (for [num-list (combo/permutations num-set) | |
| operator-list operator-pleces] | |
| (calc-all-paren-combo operator-list num-list)) | |
| (flatten ,,) | |
| (distinct ,,) | |
| (sort ,,))) | |
| (defn count-seq-from-1 [lst] | |
| (count | |
| (take-while #(= % 0) | |
| (map - lst (iterate inc 1))))) | |
| (defn pe-93 [] | |
| (let [nums (range 10) | |
| num-combinations (combo/combinations nums 4) | |
| operator-place (combo/selections [+ - * /] 3)] | |
| (reduce (fn [a b] (if (> (first a) (first b)) | |
| a b)) | |
| [0 []] | |
| (map #(vector (count-seq-from-1 (calc-all-patterns % operator-place)) | |
| %) | |
| num-combinations)))) | |
演算子のリストと数字のリストを与えると、全ての括弧のパターンで計算した結果を返します。
・calc
マクロです。
計算式を与えると、以下の場合にnilを返します。
-0での除算が発生したとき
-答えが正の整数でないとき
・calc-all-patterns
数字のリストと演算子の組み合わせリストを与えると、全ての数字の組替えについての計算結果を返します。
結果は、重複を除いて、昇順にならべます。
・count-seq-from-1
数字のリストがどこまで1から順になっているか数えます。
ちょっとclojureっぽい？
0 コメント:
コメントを投稿