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