問題と他の方の解答
問題: L被覆 〜 横へな 2013.12.7 参考問題
他の方の解答: 第16回オフラインリアルタイムどう書くの参考問題＋
私の解答 in Clojure
ord16ref.clj
(ns ord16ref
(:require [clojure.test :refer (deftest are run-tests)]
[clojure.string :as string]))
(defn solve [width height points-str]
(let [points (map (partial map #(Integer/parseInt (str %)))
(string/split points-str #","))
[l t r b] (for [mm [min max] fs [first second]]
(apply mm (map fs points)))
[w h] (map inc [(- r l) (- b t)])]
(#(if % (str %) "-")
(cond
(= w h 1) 3
(every? #(some (partial = %) points) [[l t] [r t] [l b] [r b]])
(if-not (and (= w width) (= h height)) (inc (* w h)))
:else
(apply min
(for [i (range 1 w) j (range 1 h)
:when (some not
(for [xc [#(< % (+ l i)) #(< (- r i) %)]
yc [#(< % (+ t j)) #(< (- b j) %)]]
(some (fn [[x y]] (and (xc x) (yc y)))
points)))]
(- (* w h) (* i j))))))))
(deftest solve-test
(are [i o] (= (solve 10 10 i) o)
"41,33,26,55,74,58,68" "39"
"00,99,09,90" "-"
"09" "3"
"05,05,05" "3"
"45" "3"
"38,39" "3"
"38,47" "3"
"45,66" "4"
"12,34,56,78" "33"
"12,34,56,78,45" "37"
"00,09,00" "11"
"00,90" "11"
"99,09" "11"
"99,90" "11"
"11,12,21,22" "5"
"42,45,92,95,83,62" "25"
"42,45,92,83,62" "14"
"34,38,78,74,56,35,77,48,54" "26"
"38,78,74,56,35,77,48,54" "23"
"31,41,21,71,21" "7"
"46,45,42,44,45" "6"
"00,99,09" "19"
"99,09,90,24" "64"
"99,16,61,34,17,24,42,26,18,71,19,91,81,43,33,62,52,25" "75"
"55,43,16,91,61,19,24,18,33,34,71,81,42,62,52,26,17,25" "53"
"71,26,81,62,17,16,25,42,33,52,19,18,91,24,61,34,43" "45"
"39,49,19,93,78,58,48,91,95,29,68,92,86,87,94,77" "39"
"69,89,25,26,58,12,37,36,68,24,11,13,48,14,79" "37"
"58,67,92,38,83,29,91,76,84,57,75,48,85,19,66" "51"
"00,83,76,85,48,19,75,29,92,57,66,67,91,58,38,84" "91"
"11,92,57,38,58,66,91,67,84,48,83,19,75,85,76,29" "72"
"36,07,45" "9"
"57,23,24,74" "21"
"92,20,32,12,65" "39"
"24,54,66,48,54,15" "21"
"05,17,42,20,48,22,13" "39"
"53,84,55,56,25,14,84,43" "26"
"06,77,56,59,15,24,09,66,71" "51"
"53,36,47,45,45,67,66,46,63,75" "21"
"35,53,93,33,02,84,83,48,54,32,28" "50"
"55,74,32,84,41,64,24,44,15,14,26,53" "39"
"47,60,34,32,19,67,24,83,94,38,47,05,79" "88"
"63,32,42,74,66,64,35,41,74,25,48,62,44,54" "42"
"00,86,16,19,09,92,51,10,68,23,14,63,21,46,03" "91"
"56,46,54,14,15,25,53,84,58,85,44,37,54,76,26,76" "42"
"71,87,39,43,76,38,91,69,98,33,43,26,56,69,73,52,89" "66"
"43,26,84,64,52,48,36,23,66,53,41,57,76,36,84,57,35,41" "47"
"81,02,85,93,36,46,80,27,72,28,02,99,13,41,36,40,18,97,38" "91"
"63,46,75,58,42,26,58,37,14,75,35,63,32,36,52,46,85,14,48,23" "47"
"66,92,64,12,17,33,10,28,75,05,81,05,42,86,52,57,56,78,87,81,10" "82"
"48,25,58,76,15,74,43,44,24,62,33,67,34,34,42,48,37,33,51,43,46,67" "50"))
テスト実行結果
Clojure 1.6.0
user=> (ns ord16ref)
nil
ord16=> (require 'ord16ref :reload-all)
nil
ord16=> (run-tests)
Testing ord16ref
Ran 1 tests containing 51 assertions.
0 failures, 0 errors.
{:type :summary, :fail 0, :error 0, :pass 51, :test 1}
解説
(defn solve [width height points-str]
(let [points (map (partial map #(Integer/parseInt (str %)))
(string/split points-str #","))
[l t r b] (for [mm [min max] fs [first second]]
(apply mm (map fs points)))
[w h] (map inc [(- r l) (- b t)])]
(#(if % (str %) "-")
(cond
(= w h 1) 3
(every? #(some (partial = %) points) [[l t] [r t] [l b] [r b]])
(if-not (and (= w width) (= h height)) (inc (* w h)))
:else
(apply min
(for [i (range 1 w) j (range 1 h)
:when (some not
(for [xc [#(< % (+ l i)) #(< (- r i) %)]
yc [#(< % (+ t j)) #(< (- b j) %)]]
(some (fn [[x y]] (and (xc x) (yc y)))
points)))]
(- (* w h) (* i j))))))))
(defn solve [width height points-str] ...)
問題では, 縦横 10 マスに固定されていますが, 一応 width と height で指定できることにしておきます. それぞれ 2 以上の整数を仮定しており, その検査はしていません.
points-str に 2桁の数字をカンマで区切って並べた文字列として座標の集合が与えられるものとします.
(let [points (map (partial map #(Integer/parseInt (str %)))
(string/split points-str #","))
...]
...)
入力文字列をばらし, 座標の集合 points を, x 座標の数値と y 座標の数値を並べたシーケンスのシーケンスとします.
各部分は以下の例のように機能します.
user=> (require '[clojure.string :as string])
nil
user=> (string/split "41,33,26" #",")
["41" "33" "26"]
user=> (map #(Integer/parseInt (str %)) "41")
(4 1)
user=> (map (partial map #(Integer/parseInt (str %))) ["41" "33" "26"])
((4 1) (3 3) (2 6))
(let [...
[l t r b] (for [mm [min max] fs [first second]]
(apply mm (map fs points))
...]
...)
points に含まれる座標のうち, x の最小値を l, y の最小値を t, x の最大値を r, y の最大値を b とします.
これは
(let [...
l (apply min (map first points))
t (apply min (map second points))
r (apply max (map first points))
b (apply max (map second points))
...]
...)
と同等です.
例えば, x の最小値であれば以下の例のように機能します.
user=> (map first [[4 1] [3 3] [2 6]])
(4 3 2)
user=> (apply min (map first [[4 1] [3 3] [2 6]]))
2
(let [...
[w h] (map inc [(- r l) (- b t)])]
...)
点群を囲む長方形の幅 w と高さ h を求めておきます.
(#(if % (str %) "-")
...
以下で, L被覆が存在する場合はその最小の面積を「数値」で, 存在しない場合は nil を返すことにし, ここでは, それぞれを指定されたフォーマットの文字列, つまり前者は 10進表記の文字列, 後者は文字列 "-" にします.
例です.
user=> (#(if % (str %) "-") 39)
"39"
user=> (#(if % (str %) "-") nil)
"-"
(cond
(= w h 1) 3
...)
点群を囲む長方形の幅と高さが両方 1 の場合は, 最小の L被覆の面積は 3 です. これには width と height がいずれも 2以上である必要がありますが, ここではその検査は省略します.
(cond
...
(every? #(some (partial = %) points) [[l t] [r t] [l b] [r b]])
(if-not (and (= w width) (= h height)) (inc (* w h))
...
点群を囲む長方形の四隅の座標 [l t], [r t], [l b] および [r b] の全てが, 元の点群に存在する場合 (every? #(some (partial = %) points) ... は,
- 長方形が, 与えられた盤自体と一致している
(and (= w width) (= h height))のでなければ, 長方形の面積に 1 を足したもの(inc (* w h))になります.
- 長方形が, 与えれた盤自体と一致している場合は L被覆が作れません.
if-notで else 節を省略し, 暗黙にnilを返しています.
(cond
...
:else
(apply min
(for [i (range 1 w) j (range 1 h)
:when (some not
(for [xc [#(< % (+ l i)) #(< (- r i) %)]
yc [#(< % (+ t j)) #(< (- b j) %)]]
(some (fn [[x y]] (and (xc x) (yc y)))
points)))]
(- (* w h) (* i j)))))
それ以外の場合, つまり面積 1でなく, 四隅とも点があるわけではない場合.
四隅のいずれかが必ず面積 1以上, 削る事ができます.
幅 i, 高さ j の長方形を削れるか試験します.
(for [i (range 1 w) j (range 1 h)]
...]
...)
で i を 1 から w - 1, j を 1 から h - 1 まで変化させた場合の全ての組合せを与えます.
for の利用例です.
user=> (for [i (range 1 3) j (range 1 4)] [i j])
([1 1] [1 2] [1 3] [2 1] [2 2] [2 3])
(for [...
:when ...]
...)
for の :when 句を使って, 条件に合致するもののみ抽出します.
条件は
(some not
(for [xc [#(< % (+ l i)) #(< (- r i) %)]
yc [#(< % (+ t j)) #(< (- b j) %)]]
(some (fn [[x y]] (and (xc x) (yc y)))
points))
です.
これは for と無名関数の適用を展開すると以下と同等です.
(some not
[(some (fn [[x y]] (and (< x (+ l i)) (< y (+ t j)))) points)
(some (fn [[x y]] (and (< x (+ l i)) (< (- b j) y))) points)
(some (fn [[x y]] (and (< (- r i) x) (< y (+ t j)))) points)
(some (fn [[x y]] (and (< (- r i) x) (< (- b j) y))) points)])
(some (fn [[x y]] (and (< x (+ l i)) (< y (+ t j)))) points) の部分は
points の中に, 長方形の左上を幅 i, 高さ j 削った時に, 削った側に含まれてしまう点があるかどうかを調べています.
以下の例のように機能します.
user=> (some (fn [[x y]] (and (< x 2) (< y 2))) [[2 2] [3 3]])
nil
user=> (some (fn [[x y]] (and (< x 2) (< y 2))) [[1 1] [2 2] [3 3]])
true
さて, 他はそれぞれ, 左下, 右上, 右下から削れない (削れない場合に true) か検査します.
四隅の検査結果を (some not ...) で調べ, 結果的に四隅のうちいずれかは, 幅 i, 高さ j の長方形を削れるならばという条件になります.
その場合の面積は W * h - i * j になります.
(- (* w h) (* i j))
(apply min ...)
で最小値を求めます.