W杯出場国しりとり
awkネタ
2014年の大会の出場国でしりとりしましょう。 2014年大会の出場国は32か国です。
2014年FIFAワールドカップ出場国
国名 | 国名 | 国名 |
---|---|---|
Brazil | Croatia | Mexico |
Cameroon | Spain | Netherlands |
Chile | Australia | Colombia |
Greece | Cote d'lvoire | Japan |
Uruguay | Costa Rica | England |
Italy | Switzerland | Ecuador |
France | Honduras | Argentina |
Bosnia and Herzegovina | Itran | Nigeria |
Germany | Portugal | Ghana |
USA | Belgium | Algeria |
Russia | Korea Republic |
例えば、以下のようにすると3か国で終わってしまいます。 「Japan」→「Netherlands」→「Switzerland」 どの国名も一度しか使うことが出来ない時、最も長く続けられる 順を求め、使用した国名の数を答えて下さい。
再帰を使っております。
再帰で配列を使うときは、仮引数に変数を入れることで局所変数
になるので、入れておく必要があります。
(今回だと配列の要素のiです)
後は、使用済みのフラグをセットします。
#!/usr/bin/awk -f BEGIN{ true = 1; false = 0; # ワールドカップ出場国を配列にセット country[0] = "Brazil"; country[1] = "Croatia"; country[2] = "Mexico"; country[3] = "Cameroon"; country[4] = "Spain"; country[5] = "Netherlands"; country[6] = "Chile"; country[7] = "Australia"; country[8] = "Colombia"; country[9] = "Greece"; country[10] = "Cote d'lvoire"; country[11] = "Japan"; country[12] = "Uruguay"; country[13] = "Costa Rica"; country[14] = "England"; country[15] = "Italy"; country[16] = "Switzerland"; country[17] = "Ecuador"; country[18] = "France"; country[19] = "Honduras"; country[20] = "Argentina"; country[21] = "Bosnia and Herzegovina"; country[22] = "Itran"; country[23] = "Nigeria"; country[24] = "Germany"; country[25] = "Portugal"; country[26] = "Ghana"; country[27] = "USA"; country[28] = "Belgium"; country[29] = "Algeria"; country[30] = "Russia"; country[31] = "Korea Republic"; # すべての国から開始 max_depth = 0; for(i in country){ is_used[i] = true; search(country[i], 1); is_used[i] = false; } # 深さの最大値を表示 print max_depth; } function search(prev,depth, is_last,i){ is_last = true; for(i in country){ # 前回の最後と今回の最初の文字が同じなら if(substr(country[i],1,1) == toupper(substr(prev,length(prev),1))){ if(!is_used[i]){ # 今回の文字が未使用なら is_last = false; # まだ終わらない is_used[i] = true; # 今回の文字は使用済み search(country[i], depth + 1); # 1カウント is_used[i] = false; # 探索したので未使用に戻す } } } if(is_last){ if(max_depth < depth){ max_depth = depth; } } }
実行してみます。
awk -f q14.awk 8