CodeIQ/スペーストーキー問題

スペーストーキー問題†

• CodeIQで結城浩先生が出題されていた、スペーストーキー問題に挑戦します
• 解説を書く予定ですが、問題提出の締め切りが終わったあとに、このページで公開します。
• なお、問題の詳細はこちら&note{codeiq-spacetalky:挑戦者求む！【アルゴリズム】スペーストーキー社の危機を救え！ by The Essence of Programming 結城 浩│CodeIQ, 2014-04-15公開, 2014-04-15閲覧};
• 結城先生のCodeIQのページはこちら&note{codeiq-hyuki:CodeIQの問題に挑戦しよう！, 2013-04-02更新, 2013-05-28閲覧};

突然ひらめきが†

• ずーっと画面とにらめっこしていて、
  • aが大量に挿入される
  • たまにbが追加され、その時は文字の並びが乱れる（？）
• ぐらいしか気づいていませんでした。
• しかし、ふと唐揚げを食べながら閃きました。「Run Length Encoding じゃね？」

Run Length Encodingについて†

• Run Length Encodingとは、可逆圧縮方式の一種です。
• 同じ符号が連続で現れるときに特に効果を発揮する符号化の方法で、画像の符号化にも使われます。
• 例えば、「1000000円」という文字を読むときに
  • 「いち、ぜろ、ぜろ、ぜろ、ぜろ、ぜろ、ぜろ、えん」と読む人はまずいません
  • 「ひゃくまんえん」と読んだ方が、圧倒的に速い（＝圧縮されている）からです
• これがRun Length Encoding です

今回も問題のポイント†

• 試しに、WebAPIを使って幾つかエコーバックを見てみましょう。

  foo	faob
  hello	haealboa
  run	rauana

• こんな具合に、aがそこかしこに挿入されますが、たまにbが追加されてるのも確認できます。
• よく見れば、対応する入力する場所では同じアルファベットが連続しています。
  • foo -> faob
  • hello -> haealboa
• んで、何故bなのか？実は同じ文字が「2回」連続してることを表す記号が「b」なのです
• じゃあ、同じアルファベットが3回連続してる部分は無いのか！？と調べますが、3文字連続する英語なんて、そうそう無いです。
• しかしそこはWebAPIの出番！実際に入力してみれば良いわけです。
• 例えば aaa は ac に変換されます。
• どうやら、本当に文字を繰り返せば繰り返しただけ、次のアルファベットが1つずつずれていくようです。

符号化できる/できない†

• Run Length Encoding は、シンボルの桁数が偶数でなければなりません。
• デコードする際に、なんという符号を、何回繰り返すか、という意味になっているからです。
• 先ほどの「1000000円」の例で言えば、
  • 「ひゃくまん」で、
  • 1が1回、
  • 0が6回、
  • それぞれ繰り返す事を表しています。
• しかし、今回は繰り返される符号も、繰り返す回数も、どちらもアルファベットで表現されています。

1. 2文字ずつ取得し、
2. 1文字目を
3. 2文字目に該当する回数だけ繰り返す

• 事を繰り返します。
• 自然と、奇数長の符号は復号化できないことになります。
• これが今回の「対応する入力がない場合」に相当します。

エンコードでなく、デコード†

• 今回の問題のポイントは
  • 復号化することで期待のコマンドになるような入力を考える
• という点です
• なので、コマンドが既に符号化された記号と見立てて、それらを復号化してやる必要があります。
• 先ほどの符号化の手順をもとに、復号化の手続きを考えると

1. 先頭から2文字ずつ切り出してくる
2. 2文字目を数字Xに置き換える
3. 1文字目をX回繰り返す
4. 次の2文字をまた取ってくる

• の繰り返しで表現できます。

ソースコード†

• 私が書いたコードは以下の通りです。
• C++で書きました

#geshi(c++,number){{

#include <iostream>

#include <vector>

#include <string>

#include <fstream>

std::string decode(const std::string& rawString) {

       std::string result;
       for(int i = 0;i < rawString.length()-1;i+=2)
       {
               char a, b;
               a = rawString[i  ];
               b = rawString[i+1];
               for(int j = 0;j <= b - 'a';j++)
               {
                       result.push_back(a);
               }
       }
       return result;

}

bool isFormatAcceptable(const std::string& rawString) {

       if((rawString.length() & 1) == 1){
               return false;
       }else{
               if(rawString.length() == 0){
                       return false;
               }else{
                       return true;
               }
       }

} int main(int argc, char** argv) {

       using namespace std;
       string inputFilename;
       if(argc <= 1)
       {
               inputFilename = "./words.txt";
       }else{
               inputFilename = string(argv[1]);
       }

       ifstream inputFile(inputFilename.c_str());
       if(inputFile.is_open() == false)
       {
               cerr << "Failed to open " << inputFilename << endl;
               return -1;
       }

       cout << "Succeeded to open " << inputFilename << endl;

       do{
               string temp;
               inputFile >> temp;
               if(isFormatAcceptable(temp) == false){
                       cout << "X:" << temp << endl;
               }else{
                       cout << decode(temp) << ':' << temp << endl;
               }
       }
       while(inputFile.eof() == false);
       return 0;

} }}

入力のあるなし/複数†

対応する複数の入力†

• 今回、Run Length Encodingは可逆圧縮です。
• 可逆圧縮ですので、ある記号Xが符号化でYという記号になった状況をX→Yで表すと、Yから必ずXが導けます。
  
• 図で表したのは、符号化された記号Yと、そのれを復号化したコマンドXの組です。
• 「可逆圧縮」という意味は、「Yに対応するXが必ず1つだけ存在する」という意味です。
• 今回の問題は、符号化することで特定のコマンドXになるような入力を考えます
  • ここで、仮に、特定のコマンドになるなる入力AとBが存在したとしましょう。
  • このAとBは両方コマンドXと等価な符号に「符号化」されます。
  • 先ほどの、「可逆圧縮」という特性から、この符号Xは必ず複号化されなければなりませんが、Aに復号化するのか？Bに復号化するのか？矛盾が生じます。
  • ですので、そんな符号AとBは存在しない訳です。
• 問題文中に「入力が複数ある場合はひとつだけ答えてください」と書いてありますが、前述のとおり、複数入力が存在する記号はありえません。

対応する入力なし†

• 一方で、入力が存在しない記号もあります。
• サクッと書きましたが、その点についてもう少し考察します
• 元符号の集合をX、符号化された集合をYとおくと前述の図のように、対応関係が連結で表されます。
• ここで、全集合の数を考えてみます。
  • 今、encoderに入力できる文字列は
  • アルファベット小文字のみ
  • 最長1024文字
  • と定義されています
• しかし、encoderの出力はどうでしょうか。
  • 試してみると分かりますが、符号Yの長さは最長2048文字までありえます。
    
• 図で示したように、元符号Xと、符号化された符号Yでは、集合の大きさが違います
  • 可逆圧縮なので、Y→Xとなる対応関係は保証されています。
  • しかし、集合の大きさで言えば符号Yの集合の方が大きいので、符号Yの中には、対応する入力Xが存在しない符号が存在してしまいます。
  • 今回の例で言えば、符号長が奇数文字のコマンドがそれに当たります。
• なので、「対応する入力が存在しない」ことに疑心暗鬼になってる挑戦者も多かったと思います
• 前述の図の通り「対応する入力が存在しない」ことは十分あり得る事態なので「対応する入力が存在しないからと言って誤りとは決めつけられない」
  • 当然、私の解答が正解であるかどうか、まだ決まってない訳ですが。

追記†

• 18:00追記
• 採点結果が届いて、残念ながら評価3だった。悔しい！

最新の20件