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

#stub

*突然ひらめきが [#s5d19a64]
-ずーっと画面とにらめっこしていて、
--aが大量に挿入される
--たまにbが追加され、その時は文字の並びが乱れる(?)
-ぐらいしか気づいていませんでした。
-しかし、ふと唐揚げを食べながら閃きました。「Run Length Encoding じゃね?」 

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

*今回も問題のポイント [#j4d6b2c8]
-試しに、WebAPIを使って幾つかエコーバックを見てみましょう。
|foo|faob|
|hello|haealboa|
|run|rauana|
-こんな具合に、aがそこかしこに挿入されますが、たまにbが追加されてるのも確認できます。
-よく見れば、対応する入力する場所では同じアルファベットが連続しています。
--f''oo'' -> fao''b''
--he''ll''o -> haeal''b''oa
-んで、何故bなのか?実は同じ文字が「2回」連続してることを表す記号が「b」なのです
-じゃあ、同じアルファベットが3回連続してる部分は無いのか!?と調べますが、3文字連続する英語なんて、そうそう無いです。
-しかしそこはWebAPIの出番!実際に入力してみれば良いわけです。
-例えば aaa は ac に変換されます。
-どうやら、本当に文字を繰り返せば繰り返しただけ、次のアルファベットが1つずつずれていくようです。


*符号化できる/できない [#b6b75717]
-Run Length Encoding は、シンボルの桁数が偶数でなければなりません。
-デコードする際に、なんという符号を、何回繰り返すか、という意味になっているからです。
-先ほどの「1000000円」の例で言えば、
--「ひゃくまん」で、
--1が1回、
--0が6回、
--それぞれ繰り返す事を表しています。
-しかし、今回は繰り返される符号も、繰り返す回数も、どちらもアルファベットで表現されています。
+2文字ずつ取得し、
+1文字目を
+2文字目に該当する回数だけ繰り返す
-事を繰り返します。
-自然と、''奇数長の符号''は復号化できないことになります。
-これが今回の「対応する入力がない場合」に相当します。

*エンコードでなく、デコード [#x02f8efa]
-今回の問題のポイントは
--復号化することで期待のコマンドになるような入力を考える
-という点です
-なので、コマンドが既に符号化された記号と見立てて、それらを復号化してやる必要があります。
-先ほどの符号化の手順をもとに、復号化の手続きを考えると
+先頭から2文字ずつ切り出してくる
+2文字目を数字Xに置き換える
+1文字目をX回繰り返す
+次の2文字をまた取ってくる
-の繰り返しで表現できます。

*ソースコード [#lcf36c68]
-私が書いたコードは以下の通りです。
-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;

}
}}  

*入力のあるなし [#f8f177ba]
-先ほど、入力がない場合がある、とサクッと書きましたが、その点についてもう少し考察します
-今回、Run Length Encodingは可逆圧縮です。
-可逆圧縮ですので、ある記号Xが符号化でYという記号になった状況をX→Yで表すと、Yから必ずXが導けます。
-今回の問題では、Aという記号になるような入力ですから、X→Aとなる入力Xを調べることに意味があります。
-先ほど、Run Length Encodingは可逆圧縮は必ず復元できるということですから、X→Aが存在する場合はAに対応するXがぢ一つだけそんざいする、といういみです
ですから文中では「複数ある場合はひとつだけ答えてください」と書いてありますが、
前述のとおり、複数入力が存在する記号はありえません。

一方で、入力が存在しない記号もあります。
入力の集合をAとおくと、Aから矢印が出て、符号化され、かならず矢印が戻ってきます。
しかし、だからといって、必ず存在しないとは限りません。



トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS