CodeIQ:ジョブの実行順序を決めよう

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「ジョブの実行順序を決めよう」(CodeIQ)を参照してください。

問題の概要

問題を引用します。
あなたが所属しているプロジェクトでは、日々のバッチ処理をジョブ管理ツールで運用していましたが、より細かな要求に応えられるよう、一部の機能を自前の実装に置き換えることになりました。

具体的な依頼内容は、ジョブの実行順序をジョブ同士の依存関係を考慮したうえで決めるというもので、例えばジョブA, B, C, Dがあり以下の依存関係とあるとします。

ジョブBとジョブCの実行が完了した後に、ジョブAとジョブDを実行する
ジョブBが完了した後に、ジョブCを実行する

このとき、適切なジョブな実行順序は、B → C → A, Dとなります。
ジョブAとジョブDの間には依存関係がないため同時実行しても構いません。

このように、ジョブ同士の依存関係を適切に解釈し、ジョブを同時実行可能なグループに分けた上で、無駄なく漏れなく実行順にジョブ名を列挙することが本設問のミッションになります。

求められるプログラムの前提条件は、以下の通りとなります。

標準入力から、Makefileの依存関係行のような以下2パターンの書式の文が複数行送られる
ジョブ名
ジョブ名 : 依存ジョブ名1 依存ジョブ名2 ...

ジョブ名は、1文字以上32文字以下の、スペースや制御文字を除くASCII文字で構成される
入力される行は、1024文字以下とする
ジョブ数は、2以上100以下とする
ジョブ間に循環参照はないものとする
同一のジョブに対し、重複する定義はないものとする
それぞれのジョブは同時実行可能なグループ(以降、ジョブグループと称する)にまとめる
依存関係のないジョブは、最初に実行するジョブグループにまとめる
標準出力に、実行順にジョブグループを改行区切りで出力すること。
ジョブグループについては、グループ内のジョブ名を文字コードの並び順で文字列ソートをしたものを、スペース区切りで出力すること。

以下が、入力と出力例になります。
No.入力例出力例
1 2
10
10 2
2 1 : 2
3 : 2
2
1 3
3 1
2 : 3
4
1 3 4
2

さて、ジョブ管理ツールは、世の中にたくさんありますが、分散環境があった場合にどう分散させるか、一時停止や途中再開をどうやって対応するか、管理画面でどこまで対応させるか、など要求内容があまりにも多岐にわたるため、内製しているケースも珍しくありません。

いざ既存のものを使うか、自前で書くか判断を迫られたときに、ベースとなる技術を知っていると心強いものです。
是非、挑戦してみてくださいね。

【問題】
標準入力から、Makefileの依存関係行のような「ジョブ名: 依存ジョブ名1 依存ジョブ名2 ...」という書式の文が複数行送られます。
これらの文からジョブ同士の依存関係を解釈し、ジョブを同時実行可能なグループに分けた上で、無駄なく漏れなく実行順にジョブ名を標準出力に返してください。

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

def addInput(now, line)
	if line.include?(":") then
		child, parents = line.split(":")
		child.strip!
		parents.strip!
		nodes = parents.split
	else
		nodes = [line]
		child = nil
	end

	for n in nodes
		now[n] = [] if now[n] == nil
		now[n] << child if child
	end

	return now
end

def getChilds(inputs, parents)
	ret = []

	for node in parents
#		printf("node=%s childs=%s\n", node, inputs[node].to_s)
		ret += inputs[node] if inputs[node] != nil
	end

	return ret.uniq.sort
end

def printResult(ret)
	for r in ret
		puts r.join(" ")
	end
end

# main
inputs = {}
ret = []

while line = gets
	line.strip!
	inputs = addInput(inputs, line)
end

ret << inputs.each_key.to_a.sort

loop do
	childs = getChilds(inputs, ret.last)

	if childs.empty? then break
	else
		ret[-1] -= childs
		ret << childs
	end
end

printResult(ret)

解説

問題に曖昧な部分が多いです。
例えば入力が、
c:a
d:b
e:d
f:c e
だったとします。
これは、
a b
c d
e
f
でも、
a b
d
c e
f
でも、
b
a d
c e
f
でも、問題の仕様上間違いでないはずです。「依存関係のないジョブは最初に実行するグループにまとめる」とありますが、この例は全てのジョブが依存関係を持っていますし、cの様に最初でも最後でもなく、複数の実行箇所の候補がある場合にどうすべきかの言及がありません。

結局、
実行可能箇所が複数ある場合は可能な限り前の方で実行する
ということで実装する必要がある様です。

考え方

真面目にやるとするとグラフを作るのでしょうが、グラフを作っても出力結果をまとめるのが結構面倒です。ルートが一つではないので辿るのが結構面倒臭い。
そこで次の様にしました。

まず、入力値を親子関係とすると「子ジョブ:親ジョブ1 親ジョブ2 …」となっていますが、これを「親ジョブ: 子ジョブ1 子ジョブ2 …」の形に整形します。
私が解説の最初に挙げた、
c:a
d:b
e:d
f:c e
だと、
a => c
b => d
d => e
c => f
e => f
となるわけです。

これをまず、親要素だけを配列にします。
[a, b, c, d, e]

次に、それぞれの子ジョブ(重複を除外)をまとめた配列を作ります。
親[a, b, c, d, e]
子[c, d, e, f]

そして、親の集合から子の集合の要素を除きます。
親[a,b]
子[c, d, e, f]

今度は子を親としてさらにその子の集合を作ります。
親1[a,b]
親2[c, d, e, f]
子 [e, f]

同じ様に親2から子の要素を除きます。
親1[a,b]
親2[c, d]
子 [e, f]

もう一度、子要素の集合を作ります。
親1[a,b]
親2[c, d]
親3[e, f]
子 [f]

もう一度、差集合をとります。
親1[a,b]
親2[c, d]
親3[e]
子 [f]

もう一度子要素の集合を作ると空集合になるので終わります。

この様にすることで答えを求めることができます。

main

入力値を1行ずつ取得し、addInput()に渡し、
inputs = {
 親要素1 => [子要素, 子要素, …]
 親要素2 => [子要素, 子要素, …]
 …
}
の連想配列にします。

retは答えとなるジョブの集合の配列で、48行目でIpnutsのキーの配列を最初の要素とします。

50〜58行目のループでretの最後の要素の配列に対してその子要素の配列を追加し、親となった要素の配列から子要素の集合を除きます。
子要素の集合が空集合になったらループを終了します。

最終的にprintResult()でretを印字して終了します。

addInput(now, line)

引数nowにlineをパースして「親=>子」にした要素を追加し、追加したnowを返却します。

入力値に":"が含まれていたら":"で分割し、左側を子要素(child)とし右側をparentsとします。parentsをスペースで分割し配列nodesにします。
入力値に":"がなかったらその値をnodesの唯一の要素とし、childはnilにしておきます。

nodesの要素でループして「親 => 子」の形でnowに追加します。nowがすでに同じ親要素を持っていたら子要素の配列に追加し、ない場合は新規に追加します。

追加が終わったらnowを返却します。

getChilds(inputs, parents)

親要素となる要素の集合からその子の集合を作って返却します。
引数inputsは{親=>[子, 子, …], …}の格好にした入力値、parentsは親要素の集合です。

やっていることは単純で、parentsの要素でループしてinputsから子要素の集合を取得し、retに追加してゆくだけです。
最終的にretは重複を削除してソートして返却します。

printResult(ret)

問題の書式に従って結果を印字します。

雑感

当初、問題の出力形式の仕様が曖昧なのでパスしようかと思いました。
問題の仕様も曖昧ですが、テストケースも3つしかない上、入力値は例と同じく数値だけ(問題文にある様な文字数は無意味)、ジョブ数も100には全然届かない、という明らかに不十分と思えるものでした。
せめて問題文の仕様はある程度チェックできるテストケースを用意すべきではないかと思います。