問題と他の方の解答
問題: フォークじゃない 〜 横へな 2014.2.1 問題
他の方の解答: 第18回オフラインリアルタイムどう書くの問題
私の解答 in Clojure
(ns ord18
(:require [clojure.test :refer (deftest are run-tests)]))
(defn- append [lines customer]
(let [len (comp count second)
min-len (apply min (map len lines))
[k v] (first (filter #(= (len %) min-len) lines))]
(assoc lines k
(if (= customer \x)
(conj v \x)
(reduce conj v (repeat (Integer/parseInt (str customer)) \o))))))
(defn- proc [tps lines]
(reduce #(assoc %1 %2
(let [[d r] (split-at (tps %2) (%1 %2))]
(vec (concat (drop-while (partial not= \x) d) r))))
lines (keys tps)))
(defn- proc-event [tps lines event]
(if (= event \.)
(proc tps lines)
(append lines event)))
(defn solve [tps events]
(->> (reduce (partial proc-event tps)
(reduce #(assoc %1 %2 []) (sorted-map) (keys tps))
events)
(map (comp count second))
(interpose ",")
(apply str)))
(deftest solve-test
(are [i o] (= (solve {1 2, 2 7, 3 3, 4 5, 5 2} i) o)
"42873x.3." "0,4,2,0,0"
"1" "1,0,0,0,0"
"." "0,0,0,0,0"
"x" "1,0,0,0,0"
"31." "1,0,0,0,0"
"3x." "1,1,0,0,0"
"99569x" "9,9,6,6,9"
"99569x33" "9,9,9,9,9"
"99569x33." "7,2,6,4,7"
"99569x33.." "5,0,4,0,5"
"12345x3333." "4,0,3,2,3"
"54321x3333." "3,0,3,0,4"
"51423x3333." "3,4,4,0,4"
"12x34x." "1,0,1,0,2"
"987x654x.32" "7,6,4,10,5"
"99999999999x99999999.......9." "20,10,12,5,20"
"997" "9,9,7,0,0"
".3.9" "1,9,0,0,0"
"832.6" "6,6,0,0,0"
".5.568" "3,5,6,8,0"
"475..48" "4,8,0,0,0"
"7.2..469" "1,4,6,9,0"
"574x315.3" "3,3,1,7,1"
"5.2893.x98" "10,9,5,4,1"
"279.6xxx..4" "2,1,4,1,1"
"1.1.39..93.x" "7,1,0,0,0"
"7677749325927" "16,12,17,18,12"
"x6235.87.56.9." "7,2,0,0,0"
"4.1168.6.197.6." "0,0,3,0,0"
"2.8.547.25..19.6" "6,2,0,0,0"
".5.3x82x32.1829.." "5,0,5,0,7"
"x.1816..36.24.429." "1,0,0,0,7"
"79.2.6.81x..26x31.1" "1,0,2,1,1"
"574296x6538984..5974" "14,13,10,15,14"
"99.6244.4376636..72.6" "5,6,0,0,3"
"1659.486x5637168278123" "17,16,16,18,17"
".5.17797.x626x5x9457.3." "14,0,3,5,8"
"..58624.85623..4.7..23.x" "1,1,0,0,0"
"716.463.9.x.8..4.15.738x4" "7,3,5,8,1"
"22xx.191.96469472.7232377." "10,11,18,12,9"
"24..4...343......4.41.6...2" "2,0,0,0,0"
"32732.474x153.866..4x29.2573" "7,5,7,8,5"
"786.1267x9937.17.15448.1x33.4" "4,4,8,4,10"
"671714849.149.686852.178.895x3" "13,16,13,10,12"
"86x.47.517..29621.61x937..xx935" "7,11,8,8,10"
".2233.78x.94.x59511.5.86x3.x714." "4,6,10,8,8"
".793...218.687x415x13.1...x58576x" "8,11,8,6,9"
"6.6x37.3x51x932.72x4x33.9363.x7761" "15,13,15,12,15"
"6..4.x187..681.2x.2.713276.669x.252" "6,7,8,6,5"
".6.xx64..5146x897231.x.21265392x9775" "19,17,19,20,17"
"334.85413.263314.x.6293921x3.6357647x" "14,14,12,16,10"
"4.1..9..513.266..5999769852.2.38x79.x7" "12,10,13,6,10"))
テスト実行結果
Clojure 1.6.0
user=> (ns ord18)
nil
ord18=> (require 'ord18 :reload-all)
nil
ord18=> (run-tests)
Testing ord18
Ran 1 tests containing 52 assertions.
0 failures, 0 errors.
{:type :summary, :fail 0, :error 0, :pass 52, :test 1}
解説
データ構造を決めます.
全レジの処理能力は, レジ番号をキー, 各レジの処理能力を値とするマップで参照する形式にします.
問題の例であれば {1 2, 2 7, 3 3, 4 5, 5 2} です.
これは関数の中にハードコードしたり, グローバルにして直接参照したりせず, 必要な時に引数として与えられるものとします.
全レジの状態は, レジ番号をキー, 各レジの状態を値とするマップとします.
ただし, キーの昇順に整列された状態を保つ sorted-map を使います.
各レジの状態は, 並んでいる客の列を表すベクタとし, 各要素は, 普通 (ordinary) の客 \o か, または, レジに無限大の負荷をかける客 \x のいずれかです.
例えば, 1~5番のレジがあった時に, "42873x" の入力があった後の状態は
{1 [\o \o \o \o],
2 [\o \o \x],
3 [\o \o \o \o \o \o \o \o],
4 [\o \o \o \o \o \o \o],
5 [\o \o \o]}
のようになるものとします.
(defn- append [lines customer]
(let [len (comp count second)
min-len (apply min (map len lines))
[k v] (first (filter #(= (len %) min-len) lines))]
(assoc lines k
(if (= customer \x)
(conj v \x)
(reduce conj v (repeat (Integer/parseInt (str customer)) \o))))))
append は, 全レジの状態 lines および, 来客 customer が与えられた時に, 来客がレジに並んだ後の状態を返す関数です.
来客 customer は, 同じ列に並ぶ普通の客の人数を表す数字, または, 無限の負荷を持つ客 \x のいずれかとします.
(let [len (comp count second)
min-len (apply min (map len lines))
[k v] (first (filter #(= (len %) min-len) lines))]
...)
各レジの列の長さを求める関数 len を (comp count second) で定義しておきます.
最短の列の長さ min-len を, (apply min (map len lines)) で求めます.
最短の列の長さと同じ長さの列を持つレジを (filter #(= (len %) min-len) ...) で抜き出します.
この時, lines はキーであるレジ番号の昇順で整列済みであると決めましたので, filter した後の最初のエントリ (first ...) が, 最短の列の長さと同じ列の長さを持つレジの中で一番若いレジ番号のレジ, すなわち, 次に客が並ぶレジです.
そのレジ番号を k に, 現在のそのレジの状態を v に束縛します.
以下の例のように機能します.
user=> (def lines (sorted-map 1 [\o \o \o]
2 [\o \o]
3 [\o \o]
4 [\o \o \o \o]))
#'user/lines
user=> (def len (comp count second))
#'user/len
user=> (apply min (map len lines))
2
user=> (filter #(= (len %) 2) lines)
([2 [\o \o]] [3 [\o \o]])
user=> (first '([2 [\o \o]] [3 [\o \o]]))
[2 [\o \o]]
次に客が並ぶべきレジのレジ番号 k と現在のそのレジの状態 v が得られたので, 全レジの状態 lines に対して
(assoc lines k 新しいレジの状態)
を新しい全レジの状態として返せば良いことになります.
新しいレジの状態 の部分は次のようになります.
(if (= customer \x)
(conj v \x)
(reduce conj v (repeat (Integer/parseInt (str customer)) \o)))
すなわち, customer が無限の負荷を持つ客 \x であれば, 列 v の末尾に \x を追加します.
そうでない場合, つまり customer が同じ列に並ぶ普通の客の人数を表す数字の場合, 数字を数値に直し (Integer/parseInt (str ...), その数だけの普通の客 \o のシーケンス (repeat ... \o) を v に追加します.
以下の例のように機能します.
user=> (conj [\o \o] \x)
[\o \o \x]
user=> (repeat (Integer/parseInt (str \4)) \o)
(\o \o \o \o)
user=> (reduce conj [\o \o] '(\o \o \o \o))
[\o \o \o \o \o \o]
append 関数の機能する様子です. 出力は整形しています. *1 は直前の式の返り値です.
ord18=> (append (sorted-map 1 [] 2 [] 3 [] 4 [] 5 []) \4)
{1 [\o \o \o \o],
2 [],
3 [],
4 [],
5 []}
ord18=> (append *1 \2)
{1 [\o \o \o \o],
2 [\o \o],
3 [],
4 [],
5 []}
ord18=> (append *1 \8)
{1 [\o \o \o \o],
2 [\o \o],
3 [\o \o \o \o \o \o \o \o],
4 [],
5 []}
ord18=> (append *1 \7)
{1 [\o \o \o \o],
2 [\o \o],
3 [\o \o \o \o \o \o \o \o],
4 [\o \o \o \o \o \o \o],
5 []}
ord18=> (append *1 \3)
{1 [\o \o \o \o],
2 [\o \o],
3 [\o \o \o \o \o \o \o \o],
4 [\o \o \o \o \o \o \o],
5 [\o \o \o]}
ord18=> (append *1 \x)
{1 [\o \o \o \o],
2 [\o \o \x],
3 [\o \o \o \o \o \o \o \o],
4 [\o \o \o \o \o \o \o],
5 [\o \o \o]}
(defn- proc [tps lines]
(reduce #(assoc %1 %2
(let [[d r] (split-at (tps %2) (%1 %2))]
(vec (concat (drop-while (partial not= \x) d) r))))
lines (keys tps)))
proc は, 全レジの処理能力 tps と全レジの状態 lines が与えられた場合に, 各レジがそれぞれの処理能力によって, 単位時間だけ客を処理した後の, 全レジの状態を返す関数です.
これは,
(reduce #(assoc %1 %2 新しいレジの状態)
lines
(keys tps))
という構造をしています.
与えられた全レジの状態 lines を初期値として, 全レジの処理能力 tps に登録されている全てのレジ番号 (keys tps) について, 各レジの状態を更新します.
reduce での処理中は, %1 に前のレジまで更新した後の全レジの状態, %2 に次に更新すべきレジのレジ番号が入っており, #(assoc %1 %2 新しいレジの状態) で各レジの状態を更新します.
各レジの 新しいレジの状態 の部分は
(let [[d r] (split-at (tps %2) (%1 %2))]
(vec (concat (drop-while (partial not= \x) d) r))))
のようになっています.
%2 番レジの状態 (%1 %2) の先頭から, %2 番レジの処理能力 (tps %2) の数だけ要素を取り出した列 d と, 残りの列 r について,
d の先頭から要素 \x が現れるまで全て削除したもの (drop-while (partial not= \x) d) と,
r を連結したものです.
この部分は, 以下の例のように機能します.
user=> (def tps {1 2, 2 3}) ; 1番レジは単位時間に2人, 2番レジは単位時間に3人処理できるとする.
#'user/tps
user=> (def lines {1 [\o \o \o \o \o], 2 [\o \x \o \o]}) ; 1番レジに普通の客 5人, 2番レジは \x を含む 4人が並んでいる
#'user/lines
user=> (split-at (tps 1) (lines 1)) ; 1番レジは 2人処理できるので, 最初の 2人と残り 3人を分ける.
[(\o \o) (\o \o \o)]
user=> (drop-while (partial not= \x) '(\o \o)) ; \x が現れないので 2人とも処理できた.
()
user=> (vec (concat '() '(\o \o \o))) ; 2人処理した後の空の列と, 残り 3人の列を連結したのが次の状態
[\o \o \o]
user=> (split-at (tps 2) (lines 2)) ; 2番レジは 3人処理できるので, 最初の 3人と残り 1人を分ける.
[(\o \x \o) (\o)]
user=> (drop-while (partial not= \x) '(\o \x \o)) ; 処理能力の人数以内でも \x が現れたら処理は止まる.
(\x \o)
user=> (vec (concat '(\x \o) '(\o))) ; 残りの列と連結したのが次の状態.
[\x \o \o]
proc 関数全体としては以下のように機能します.
ord18=> (def tps {1 2, 2 7, 3 3, 4 5, 5 2})
#'ord18/tps
ord18=> (proc tps (sorted-map 1 [\o \o \o \o],
2 [\o \o \x],
3 [\o \o \o \o \o \o \o \o],
4 [\o \o \o \o \o \o \o],
5 [\o \o \o]))
{1 [\o \o],
2 [\x],
3 [\o \o \o \o \o],
4 [\o \o],
5 [\o]}
(defn- proc-event [tps lines event]
(if (= event \.)
(proc tps lines)
(append lines event)))
proc-event は, 全レジの処理能力 tps, 全レジの状態 lines, イベント event を与えると, 次の全レジの状態を返す関数です.
イベント event は, 単位時間の消費 \. または来客 (\x または数字) のいずれかです.
それぞれの場合で, 各レジの処理能力で列を処理する proc, 来客を列に追加する append を呼び出します.
(defn solve [tps events]
(->> (reduce (partial proc-event tps)
(reduce #(assoc %1 %2 []) (sorted-map) (keys tps))
events)
(map (comp count second))
(interpose ",")
(apply str)))
全レジの処理能力 tps のとき, シーケンス events に与えられる全てのイベントを処理した後の状態は
(reduce (partial proc-event tps)
全レジの初期状態
events)
となります.
全レジの初期状態は, 全レジの処理能力に登録されている全てのレジ番号について, レジ番号をキーとし, 各レジの初期状態 [] を値にもつ整列済みマップ
(reduce #(assoc %1 %2 []) (sorted-map) (keys tps))
です.
以下の例のように機能します.
user=> (reduce #(assoc %1 %2 []) (sorted-map) (keys {1 2, 2 7, 3 3, 4 5, 5 2}))
{1 [], 2 [], 3 [], 4 [], 5 []}
解答では reduce で最終状態のみを得ますが, (partial proc-event tps) の機能を見るために,
reductions で途中の状態の変化を全て見る例を以下に示します.
ord18=> (def tps {1 2, 2 7, 3 3, 4 5, 5 2})
#'ord18/tps
ord18=> (reduce #(assoc %1 %2 []) (sorted-map) (keys tps))
{1 [], 2 [], 3 [], 4 [], 5 []}
ord18=> (def init *1)
#'ord18/init
ord18=> (require '[clojure.pprint :refer :all])
nil
ord18=> (pprint (reductions (partial proc-event tps) init "42873x.3."))
({1 [], 2 [], 3 [], 4 [], 5 []}
{1 [\o \o \o \o], 2 [], 3 [], 4 [], 5 []}
{1 [\o \o \o \o], 2 [\o \o], 3 [], 4 [], 5 []}
{1 [\o \o \o \o], 2 [\o \o], 3 [\o \o \o \o \o \o \o \o], 4 [], 5 []}
{1 [\o \o \o \o],
2 [\o \o],
3 [\o \o \o \o \o \o \o \o],
4 [\o \o \o \o \o \o \o],
5 []}
{1 [\o \o \o \o],
2 [\o \o],
3 [\o \o \o \o \o \o \o \o],
4 [\o \o \o \o \o \o \o],
5 [\o \o \o]}
{1 [\o \o \o \o],
2 [\o \o \x],
3 [\o \o \o \o \o \o \o \o],
4 [\o \o \o \o \o \o \o],
5 [\o \o \o]}
{1 [\o \o], 2 [\x], 3 [\o \o \o \o \o], 4 [\o \o], 5 [\o]}
{1 [\o \o], 2 [\x \o \o \o], 3 [\o \o \o \o \o], 4 [\o \o], 5 [\o]}
{1 [], 2 [\x \o \o \o], 3 [\o \o], 4 [], 5 []})
nil
(->> ...
(map (comp count second))
(interpose ",")
(apply str))
最後の全レジの状態から, 各レジの列の長さを抜き出し, "," を挟んで文字列化して出力とします.
以下のように機能します.
user=> (->> (sorted-map 1 [] 2 [\x \o \o \o] 3 [\o \o] 4 [] 5 [])
(map (comp count second))
(interpose ",")
(apply str))
"0,4,2,0,0"