やっとこさ90番まで来ました。
ダイスの目を使って、2桁までの2乗数を作る問題です。
結果的には総当たりで解いたのですが、うまい方法ほないかなーっとつらつら考えていたりして、そこそこ時間はかかりました。
一番考えたのは、あるダイスがあったときに、題意を満たすもう一方のダイスの目を特定できないかということなのですが、条件を絞ることができずにあきらめました。
さて、解きかたは、全てのダイスの組み合わせを作り出して、それぞれの組み合わせについて、全ての2乗数を表せるかどうかを確認するというものです。6と9が互換であるという部分は、判定ロジックの方ではなく、ダイスに「6が入っていれば9を追加」「9が入っていれば6を追加」してから判定するという方式を取りました。
ダイスの種類は、10個から6個取る組み合わせで210通り、2つのダイスの組み合わせは、210個から2個取る組み合わせで21945通りとなり、全数アタックでも数秒だろうと予測しました。
実際2秒以下で答えが出ています。
以下がソースです。題意に合うかどうかの判定(match-pe90?)がベタな作りなのが気にいらないのですが、これもうまい方法を思いつかず。
たいして難しくないので、解説無しです。
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 90 | |
| ;; "Elapsed time: 1277.115881 msecs | |
| (require '[clojure.test :as test]) | |
| (require '[clojure.math.combinatorics :as combo]) | |
| (defn add-6-or-9 [dice] | |
| (cond (empty? dice) | |
| [] | |
| (= 6 (first dice)) | |
| (distinct (conj dice 9)) | |
| (= 9 (first dice)) | |
| (distinct (conj dice 6)) | |
| :t (conj (add-6-or-9 (next dice)) (first dice)))) | |
| (test/is (= (sort (add-6-or-9 [1 2 3])) | |
| (sort [1 2 3]))) | |
| (test/is (= (sort (add-6-or-9 [1 2 6])) | |
| (sort [1 2 6 9]))) | |
| (test/is (= (sort (add-6-or-9 [1 2 9])) | |
| (sort [1 2 9 6]))) | |
| (test/is (= (sort (add-6-or-9 [1 2 3 6 9])) | |
| (sort [1 2 3 6 9]))) | |
| (defn match-pe90? [[dice-a dice-b] pair-nums] | |
| (loop [dice-a (add-6-or-9 dice-a) | |
| dice-b (add-6-or-9 dice-b) | |
| pair-nums pair-nums] | |
| (if (empty? pair-nums) | |
| true | |
| (let [num-x (first (first pair-nums)) | |
| num-y (second (first pair-nums))] | |
| (if (or (and (some #(= num-x %) dice-a) | |
| (some #(= num-y %) dice-b)) | |
| (and (some #(= num-x %) dice-b) | |
| (some #(= num-y %) dice-a))) | |
| (recur dice-a dice-b (next pair-nums)) | |
| false))))) | |
| (test/is (= true | |
| (match-pe90? [[0, 5, 6, 7, 8, 9] [1, 2, 3, 4, 8, 9]] pair-nums))) | |
| (test/is (= false | |
| (match-pe90? [[1 2 3 4 5 6] [0 9 7 6 5 4]] pair-nums))) | |
| (let [pair-nums [[0 1] [0 4] [0 9] [1 6] [2 5] [3 6] [4 9] [6 4] [8 1]] | |
| dices (combo/combinations (range 10) 6) | |
| selections (combo/combinations (range (count dices)) 2)] | |
| (count | |
| (filter #(match-pe90? % pair-nums) | |
| (for [[a b] selections] [(nth dices a) (nth dices b)])))) | |
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 90 | |
| (require '[clojure.test :as test]) | |
| (require '[clojure.math.combinatorics :as combo]) | |
| ;;user> (combo/combinations [1 2 3] 2) | |
| ;;((1 2) (1 3) (2 3)) | |
| ;;user> (count (combo/combinations (range 10) 6)) | |
| ;;201 | |
| ;; | |
| ;; 01, 04, 09, 16, 25, 36, 49, 64, 81 | |
| ;; 0 -> (1 4 9) | |
| ;; 1 -> (0 6 8) | |
| ;; 2 -> (5) | |
| ;; 3 -> (6) | |
| ;; 4 -> (0 9 6) | |
| ;; 5 -> (2) | |
| ;; 6 -> (1 4 6) | |
| ;; 7 -> () | |
| ;; 8 -> (1) | |
| ;; 9 -> (0 4) | |
| (sort (into #{} [ 0 1 0 4, 0 9, 1 6, 2 5, 3 6, 4 9, 6 4 8 1])) | |
| (def oposite-nums {0 [1 4 9] | |
| 1 [0 6 8] | |
| 2 [5] | |
| 3 [6] | |
| 4 [0 9 6] | |
| 5 [2] | |
| 6 [1 4 6] | |
| 7 [] | |
| 8 [1] | |
| 9 [0 4]}) | |
| (map oposite-nums [0 1 2 3 4 5]) | |
| ;;=> ([1 4 9] [0 6 8] [5] [6] [0 9 6] [2]) | |
| (sort (distinct (mapcat oposite-nums [0 1 2 3 4 5]) )) | |
| ;;=>(0 1 2 4 5 6 8 9) | |
| (defn oposite-data [dice1] | |
| (let [oposite-nums {0 [1 4 9] | |
| 1 [0 6 8] | |
| 2 [5] | |
| 3 [6] | |
| 4 [0 9 6] | |
| 5 [2] | |
| 6 [1 4 6] | |
| 7 [] | |
| 8 [1] | |
| 9 [0 4]} | |
| ] | |
| [(into #{} (mapcat oposite-nums [0 1 2 3 4 5])) | |
| (map (juxt oposite-nums identity) dice1)])) | |
| (oposite-data [0 1 2 3 4 5]) | |
| ;;->([0 [1 4 9]] [1 [0 6 8]] [2 [5]] [3 [6]] [4 [0 9 6]] [5 [2]]) | |
4 コメント:
この問題。
6と9が同じ立方体に書かれている場合。
6しか書かれてない場合。
9しか書かれてない場合。
の３つは区別されるのか同じとみるのか？
片方の面に6、片方の面に9とある場合の区別はどうするか？
また一つ目と二つ目の立方体を入れ替えた場合。
[1,2,3,4,5,6,9],[2,3,4,5,6,7,9]
[2,3,4,5,6,7,9],[1,2,3,4,5,6,9]
の２つは別の組とみなしてよいのか？
[1,2,3,4,5,6],[1,2,3,4,5,6]は一通りと考えるのか？
何だか解釈に困りますね、私はよくわからない状態なのですがアドバイスをいただけないでしょうか？
コメントありがとうございます。
たまに解釈に迷うような問題ってありますよね。
僕の解釈で回答します。 答が合っていたので間違っていはいないと思います。
最初の質問について
「6しか書かれてない場合」と「9しか書かれてない場合」は、立方体としては別のものと捉え、別に数えます。 ですが、問題を解く上では同じものとみなせます。
また、6と9が両方書かれているものも立方体としては別のものですし、他の数字が違うはずなので、問題を解く上でも違うものということになります。
問題文にも、{1, 2, 3, 4, 5, 6} と {1, 2, 3, 4, 5, 9}は別のものであるが、2桁の数を作るときには両方とも論理的に{1, 2, 3, 4, 5, 6, 9}であると見なすことができる、ということが書いてあります。
6と9の位置関係
この問題では、立方体への数字の配置の違いは考慮しないことになっています
(we are interested in the digits on each cube, not the order.)
ので、ある数字の組がどこにどのように書いてあったとしても、それはその組が書いてある1種類の立方体と数えます。6と9を含む場合でも同様で、{1, 2, 3, 4, 6, 9}が書かれた立方体は1つになります。
というよりも、この問題は、立方体の数を数えるのでなくて、立方体に書く数字の組を見つける問題だと考えたほうがいいと思います。
入れ替えについて
2つの立方体は赤青のように区別をしていないので、例示された2組は同じものです。
同一のものの組について
同一のものの組み合わせも、題意を見たすのであれば、1つと数えます。
気持ちの良い丁寧な返答ありがとうございます。
この問題自力で解けました。
感謝です。
別の問題で問い93が解けたのですがa～ｄは1～9になりそうだとこの範囲で全探索し一番長い数列を生成できた数を答えとしたのですが、偶々運良く解けただけで最小だという保証が全くもてない状態です。
お暇な時があればこれについてもお返事をいただけたらと思います。
問い92は簡単だったので1000万を一兆に変更した場合を計算時間1秒以内で求めるコードを書いたりしました
93については、特によい方法も思い浮ばなかったので、記事にした通り力づくで解いてしまったので、残念ながらお教えできるようなことはないのです。
コメントを投稿