去年の末に解いたやつです。
条件に合う数列を新しく作る問題
これ、かなり悩んだ。 102を解いたあと、すぐに手を付けたんだけど、解きかたわからず/思いつかずで、放置している間に数年経ってしまった。
まあ<結局、初期の頃に思いついた、「全部やってみる」方式で解いてみることにして、実際やってみたら、時間はたいしてかからなかったという。
- 真ん中の数字を先頭にして新しい数列を作る
- 含まれる数を前後にいくつかずらした数列を全て生成
- 昇順になっていないものを除外
これで、候補を作って、条件に合うかどうかチェックというやりかた。
条件に合う数列を新しく作る問題
これ、かなり悩んだ。 102を解いたあと、すぐに手を付けたんだけど、解きかたわからず/思いつかずで、放置している間に数年経ってしまった。
まあ<結局、初期の頃に思いついた、「全部やってみる」方式で解いてみることにして、実際やってみたら、時間はたいしてかからなかったという。
- 真ん中の数字を先頭にして新しい数列を作る
- 含まれる数を前後にいくつかずらした数列を全て生成
- 昇順になっていないものを除外
これで、候補を作って、条件に合うかどうかチェックというやりかた。
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
| (ns euler.pe_103 | |
| (:require [clojure.math.combinatorics :as combo])) | |
| ;; Prablem 103 | |
| ;; "Elapsed time: 5387.0654 msecs" | |
| ;; rule 1: S(B) != S(C) | |
| (defn verify-rule-1 [target-set] | |
| (->> (combo/subsets target-set) | |
| (map #(apply + %) ,,) | |
| ((juxt #(count %) #(count (set %))) ,,) | |
| (apply = ,,))) | |
| ;; rule 2: S(B) > S(C) | |
| (defn verify-rule-2 [target-set] | |
| (let [center-num (quot (+ 1 (count target-set)) 2) | |
| front-half (take center-num target-set) | |
| tail-half-1 (drop (+ center-num (if (even? (count target-set)) 1 0)) target-set)] | |
| (> (apply + front-half) | |
| (apply + tail-half-1)))) | |
| ;; create next level near optimal sequence | |
| (defn middle-element [target-set] | |
| (let [half (/ (count target-set) 2) | |
| center-pos (if (int? half) half (int (- half 0.5)))] | |
| (nth target-set center-pos))) | |
| (defn next-level-s [prev-s] | |
| (let [center (middle-element prev-s) | |
| new (vec (conj (map #(+ center %) prev-s) center))] | |
| new)) | |
| ;; create all candidate sequence list with depth 'level' | |
| (defn all-candidate [s level] | |
| (->> s | |
| (mapv #(vec (range (- % level) (+ % level 1))) ,,) | |
| (apply combo/cartesian-product ,,))) | |
| ;; check if it meet the criteria | |
| (defn matched-seq? [s] | |
| (and (apply < s) | |
| (verify-rule-2 s) | |
| (verify-rule-1 s))) | |
| ;; search next level optimal sequence with window 'expand-level | |
| (defn find-next-optimal-list [current-s expand-level] | |
| (let [next-near-optimal-list (next-level-s current-s)] | |
| (->> (for [s (all-candidate next-near-optimal-list expand-level)] | |
| (if (matched-seq? s) s)) | |
| (remove nil? ,,) | |
| (sort-by #(apply + %) ,,) | |
| (#(vector (apply + (first %)) (first %) ,,))))) |
0 コメント:
コメントを投稿