私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「ジョブの実行順序を決めよう」（CodeIQ）を参照してください。
あなたが所属しているプロジェクトでは、日々のバッチ処理をジョブ管理ツールで運用していましたが、より細かな要求に応えられるよう、一部の機能を自前の実装に置き換えることになりました。
具体的な依頼内容は、ジョブの実行順序をジョブ同士の依存関係を考慮したうえで決めるというもので、例えばジョブA, B, C, Dがあり以下の依存関係とあるとします。
ジョブBとジョブCの実行が完了した後に、ジョブAとジョブDを実行する
ジョブBが完了した後に、ジョブCを実行する
このとき、適切なジョブな実行順序は、B → C → A, Dとなります。
ジョブAとジョブDの間には依存関係がないため同時実行しても構いません。
このように、ジョブ同士の依存関係を適切に解釈し、ジョブを同時実行可能なグループに分けた上で、無駄なく漏れなく実行順にジョブ名を列挙することが本設問のミッションになります。
求められるプログラムの前提条件は、以下の通りとなります。
標準入力から、Makefileの依存関係行のような以下２パターンの書式の文が複数行送られる
ジョブ名
ジョブ名 : 依存ジョブ名1 依存ジョブ名2 ...
ジョブ名は、１文字以上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)
入力値を1行ずつ取得し、addInput()に渡し、
inputs = {
親要素1 => [子要素, 子要素, …]
親要素2 => [子要素, 子要素, …]
…
}
の連想配列にします。
retは答えとなるジョブの集合の配列で、48行目でIpnutsのキーの配列を最初の要素とします。
50〜58行目のループでretの最後の要素の配列に対してその子要素の配列を追加し、親となった要素の配列から子要素の集合を除きます。
子要素の集合が空集合になったらループを終了します。
最終的にprintResult()でretを印字して終了します。
引数nowにlineをパースして「親=>子」にした要素を追加し、追加したnowを返却します。
入力値に":"が含まれていたら":"で分割し、左側を子要素（child）とし右側をparentsとします。parentsをスペースで分割し配列nodesにします。
入力値に":"がなかったらその値をnodesの唯一の要素とし、childはnilにしておきます。
nodesの要素でループして「親 => 子」の形でnowに追加します。nowがすでに同じ親要素を持っていたら子要素の配列に追加し、ない場合は新規に追加します。
追加が終わったらnowを返却します。
親要素となる要素の集合からその子の集合を作って返却します。
引数inputsは{親=>[子, 子, …], …}の格好にした入力値、parentsは親要素の集合です。
やっていることは単純で、parentsの要素でループしてinputsから子要素の集合を取得し、retに追加してゆくだけです。
最終的にretは重複を削除してソートして返却します。
問題の書式に従って結果を印字します。
当初、問題の出力形式の仕様が曖昧なのでパスしようかと思いました。
問題の仕様も曖昧ですが、テストケースも3つしかない上、入力値は例と同じく数値だけ（問題文にある様な文字数は無意味）、ジョブ数も100には全然届かない、という明らかに不十分と思えるものでした。
せめて問題文の仕様はある程度チェックできるテストケースを用意すべきではないかと思います。