なんちゃってランレングス圧縮

view plainprint?

1. #include <iostream>  
2. #include <string>  
3. #include <cstring>  
4. #include <fstream>  
5. using namespace std;  
6.   
7. void Compress(string inputFileName, string outputFileName);  
8. void UnCompress(string inputFileName, string outputFileName);  
9.   
10. int main(int argc, char** argv)  
11. {  
12.     if (argc < 3)  
13.         return 0;  
14.   
15.     if (! strcmp(argv[1], "nz"))  
16.     {  
17.         Compress(argv[2], argv[2]);  
18.         cout << "Compressed file is " << argv[2] << ".nz" << endl;  
19.     }  
20.     else if (! strcmp(argv[1], "unz"))  
21.     {  
22.         string outputFileName(argv[2]);  
23.         string::size_type index = outputFileName.rfind(".nz");  
24.         if (index != string::npos)  
25.             outputFileName = "Unz" + outputFileName.substr(0, index);  
26.         else  
27.             return 1;  
28.   
29.         UnCompress(argv[2], outputFileName);  
30.         cout << "Extracting file is " << outputFileName << endl;  
31.     }  
32.   
33.     return 0;  
34. }  
35.   
36. void Compress(string inputFileName, string outputFileName)  
37. {  
38.     outputFileName += ".nz";  
39.     ifstream fin(inputFileName.c_str(), ios::in | ios::binary);  
40.     ofstream fout(outputFileName.c_str(), ios::out | ios::binary);  
41.   
42.     if (! fin || ! fout)  
43.         return;  
44.   
45.     int delimiterPre = 0;  
46.     int delimiterPost = 0;  
47.     int rawByte, preByte, num = 0;  
48.     preByte = fin.get();  
49.   
50.     while ((rawByte = fin.get()) != EOF)  
51.     {      
52.         if(rawByte != preByte || num == 255)  
53.         {  
54.             if (num > 1)  
55.             {  
56.                 fout.write((char*) &delimiterPre, sizeof(char));  
57.                 fout.write((char*) &delimiterPost, sizeof(char));  
58.                 fout.write((char*) &num, sizeof(char));  
59.             }  
60.             fout.write((char*) &preByte, sizeof(char));  
61.             preByte = rawByte;  
62.             num = 1;  
63.         }  
64.         else if (rawByte == preByte)  
65.             num++;  
66.   
67.     }  
68.     if (num > 1)  
69.     {  
70.         fout.write((char*) &delimiterPre, sizeof(char));  
71.         fout.write((char*) &delimiterPost, sizeof(char));  
72.         fout.write((char*) &num, sizeof(char));  
73.     }  
74.     fout.write((char*) &preByte, sizeof(char));  
75.   
76.     fin.close();  
77.     fout.close();  
78. }  
79.   
80. void UnCompress(string inputFileName, string outputFileName)  
81. {  
82.     ifstream fin(inputFileName.c_str(), ios::in | ios::binary);  
83.     ofstream fout(outputFileName.c_str(),ios::out | ios::binary);  
84.     if (! fin || ! fout)  
85.         return;  
86.   
87.     int rawByte, preByte;  
88.     preByte = fin.get();  
89.   
90.     while ((rawByte = fin.get()) != EOF)  
91.     {  
92.         if (preByte == 0 && rawByte == 0)  
93.         {  
94.             while ((preByte = fin.get()) == 0)  
95.                 fout.write((char*) &preByte, sizeof(char));  
96.   
97.             rawByte = fin.get();  
98.    
99.             for (int i = 0; i < preByte; i++)  
100.                 fout.write((char*) &rawByte, sizeof(char));  
101.   
102.             if ((preByte = fin.get()) == EOF)  
103.                 break;  
104.         }  
105.         else  
106.         {  
107.             fout.write((char*) &preByte, sizeof(char));  
108.             preByte = rawByte;  
109.         }  
110.     }  
111.   
112.     if (preByte != EOF)  
113.          fout.write((char*) &preByte, sizeof(char));  
114.   
115.     fin.close();  
116.     fout.close();  
117. }  

#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
using namespace std;

void Compress(string inputFileName, string outputFileName);
void UnCompress(string inputFileName, string outputFileName);

int main(int argc, char** argv)
{
    if (argc < 3)
        return 0;

    if (! strcmp(argv[1], "nz"))
    {
        Compress(argv[2], argv[2]);
        cout << "Compressed file is " << argv[2] << ".nz" << endl;
    }
    else if (! strcmp(argv[1], "unz"))
    {
        string outputFileName(argv[2]);
        string::size_type index = outputFileName.rfind(".nz");
        if (index != string::npos)
            outputFileName = "Unz" + outputFileName.substr(0, index);
        else
            return 1;

        UnCompress(argv[2], outputFileName);
        cout << "Extracting file is " << outputFileName << endl;
    }

    return 0;
}

void Compress(string inputFileName, string outputFileName)
{
    outputFileName += ".nz";
    ifstream fin(inputFileName.c_str(), ios::in | ios::binary);
    ofstream fout(outputFileName.c_str(), ios::out | ios::binary);

    if (! fin || ! fout)
        return;

    int delimiterPre = 0;
    int delimiterPost = 0;
    int rawByte, preByte, num = 0;
    preByte = fin.get();

    while ((rawByte = fin.get()) != EOF)
    {    
        if(rawByte != preByte || num == 255)
        {
            if (num > 1)
            {
                fout.write((char*) &delimiterPre, sizeof(char));
                fout.write((char*) &delimiterPost, sizeof(char));
                fout.write((char*) &num, sizeof(char));
            }
            fout.write((char*) &preByte, sizeof(char));
            preByte = rawByte;
            num = 1;
        }
        else if (rawByte == preByte)
            num++;

    }
    if (num > 1)
    {
        fout.write((char*) &delimiterPre, sizeof(char));
        fout.write((char*) &delimiterPost, sizeof(char));
        fout.write((char*) &num, sizeof(char));
    }
    fout.write((char*) &preByte, sizeof(char));

    fin.close();
    fout.close();
}

void UnCompress(string inputFileName, string outputFileName)
{
    ifstream fin(inputFileName.c_str(), ios::in | ios::binary);
    ofstream fout(outputFileName.c_str(),ios::out | ios::binary);
    if (! fin || ! fout)
        return;

    int rawByte, preByte;
    preByte = fin.get();

    while ((rawByte = fin.get()) != EOF)
    {
        if (preByte == 0 && rawByte == 0)
        {
            while ((preByte = fin.get()) == 0)
                fout.write((char*) &preByte, sizeof(char));

            rawByte = fin.get();
 
            for (int i = 0; i < preByte; i++)
                fout.write((char*) &rawByte, sizeof(char));

            if ((preByte = fin.get()) == EOF)
                break;
        }
        else
        {
            fout.write((char*) &preByte, sizeof(char));
            preByte = rawByte;
        }
    }

    if (preByte != EOF)
         fout.write((char*) &preByte, sizeof(char));

    fin.close();
    fout.close();
}

上のコードでの実行に起因する損害に関して責任を持ちません．

 あと，世の中の高専生はもっと賢いです．こんなコードは書きません．

上のコードは１バイト単位でデータのランレングス圧縮を行うようなものです．

俺，実は学校でデータ圧縮に関して何かやらなきゃいけない立場なようで，

バイナリでデータを扱う練習がてら作ってみたものなんですが，

圧縮になるときと，ならないときが出てきちゃう，ダメダメなものになってしまいました．

ここで簡単にランレングス圧縮の説明ー．
文字列Zeeeeeeeingってなのを考えたとき，

連続した文字に注目して文字列中に数字が出てこないとして，

数字＋文字で数字の数だけ文字があることを表すとすれば

文字列Zeeeeeeeingのeは7eと省略でき，最終的に

Z7eingとすることで文字列長を１０から６に圧縮でき，

確かこんな操作を行う圧縮をランレングス圧縮と呼ばれる（たぶん）．

で，上のコードも１バイト読み取ってそんな操作を行っているんですが，

デリミターで問題？が生じた結果， 圧縮にならないときが生じてしまいました．

ここでデリミターは繰り返しがある位置を表す区切り文字のこととします．

上のコードではデリミターを0x0000にしています．

で0x0000 (文字の繰り返し回数) (繰り返し文字) と 4バイトでランレングス圧縮を試みてるんですが，

これだと5回以上連続で文字が出現しない限り，圧縮にならないことになります．

そこで，4回以下はそのまま出力すればいいやと思っていたら，

0x0000 の表記があった場合それがデリミターか単なる?0x0000なのか

区別がつかなくなることに気がつき，どうしようもなく，そのままにしてあります．

おそらく2回連続は良くある？ので３回以上はランレングス圧縮するようにすれば良くなるかもですが・・・．

で，最終的に上のコードが言いたいことは，１バイト単位でやってもそんな圧縮にならんってことです（たぶん）．

圧縮に関しては， 卒研より相当締切り日的なものが近く，

どうにかしなければならないので，今からで遅すぎますが，

どうにかして行きたいと思います．

ちなみに上のコードでC++で書いたHelloを出力する
実行ファイルを圧縮してみたところ，7783 bytesとから 6365 bytesと
見事に微妙に圧縮されました．
他のファイルではデリミッター問題？で元より増加してしまいました（ダメダメです）．

使い方

コンパイル

g++ -o RunLength このコードファイル名.cpp

圧縮 (例としてhelloファイルの圧縮)

./RunLength nz hello

でhello.nzってな圧縮ファイルが作成される．

解凍（伸長）

./RunLength unz hello.nz

でUnzhelloってな解凍ファイルが作成される．

helloとUnzhelloが同じファイルであることを切に願います．

5五将棋ってなボードゲームがあります

5五将棋 （Minishogi） の初期配置

現在ゲーム情報学で取り扱われているゲームの一つに

5五将棋と呼ばれる物があります．英語名ではMinishogiらしく，

その名の通り， 上図のような普通の？将棋を小さくしたようなボードゲームです．

今年日本で開催されるComputer Olympiad 2010でもShogi (5×5) 部門として開催されるようです．

UEC杯も開催されていて， 今年は12月4日に開催が予定されています．

囲碁は11月27日， 28日なので， 囲碁よりも遅い日程なんすね．

ルールは将棋と （駒の動きとか）は同じですが，細かいルールは

電通大の伊藤研究室が運営されてる5五将棋PORTALをご参照ください．

ゲームの探索空間は10⁶⁰より少ない程度だと考えられていて，

オセロより少ない位だと考えられているそうです．俺にはオセロより難しく見えるけど・・・．

今の状況として， 柿木さんが作成されているK55が強いみたいです．

確か学習ベースでRLGOみたいに， 自己対戦により評価方法を学習しているらしい．

噂によれば， 指せば指すほど強く（勝ち方を学習する）らしく， K55に勝つには一発勝負が大事とか・・・．

ちなみに上の図は，Qt 4.6.3 LGPL版で作成しているもので， 手抜き感maxですが作成してます．

理由は， Qtの導入です・・・． 前x3回のブログでQtに関する書籍少ないと書きましたが，

サンプルが結構充実してたりするんで， 何とかなりそうです．

AOJ Volume 0 Problem 0077 : Run Length

view plainprint?

1. #include <iostream>  
2. using namespace std;  
3.   
4. int main()  
5. {  
6.     char ch, n;  
7.     while (cin.get(ch))  
8.     {  
9.         n = '1';  
10.         if (ch == '@')  
11.             cin >> n >> ch;  
12.   
13.         for (int i = 0; i < n - '0'; ++i)  
14.             cout << ch;  
15.     }  
16.   
17.     return 0;  
18. }   

#include <iostream>
using namespace std;

int main()
{
    char ch, n;
    while (cin.get(ch))
    {
        n = '1';
        if (ch == '@')
            cin >> n >> ch;

        for (int i = 0; i < n - '0'; ++i)
            cout << ch;
    }

    return 0;
} 

まともに解きすぎてると思う．
もっと柔らかく思いつきたい．

てへっ

Hello with Qt

IDEの一つ，Qt Creatorを使ってみました．
動作は意外にサクサクしていて，雰囲気はVisual Studioと同じ感じでした．
QtってLGPLになってから結構普及したんだと思うのですが，実際どうなんだろう．
書籍は少ないし，やっぱ国内はVisual Studioで十分ってことなのかなぁ・・・。

AOJ Volume 1 Problem 0105 : Book Index

view plainprint?

1. #include <iostream>  
2. #include <string>  
3. #include <set>  
4. #include <map>  
5. using namespace std;  
6.   
7. int main()  
8. {  
9.     int n;  
10.     string str;  
11.     map<string, set<int> > m;  
12.     map<string, set<int> >::iterator p;  
13.   
14.     while (cin >> str>> n)  
15.         m[str].insert(n);  
16.   
17.     for (p = m.begin(); p != m.end(); p++)  
18.     {  
19.         cout << p->first << endl;  
20.         set<int>::iterator q = (p->second).begin();  
21.         for (; q != (p->second).end(); )  
22.         {  
23.             cout << *q;  
24.             cout << (++q != (p->second).end() ? ' ' : '\n');  
25.         }  
26.     }  
27.   
28.     return 0;  
29. }  

#include <iostream>
#include <string>
#include <set>
#include <map>
using namespace std;

int main()
{
    int n;
    string str;
    map<string, set<int> > m;
    map<string, set<int> >::iterator p;

    while (cin >> str>> n)
        m[str].insert(n);

    for (p = m.begin(); p != m.end(); p++)
    {
        cout << p->first << endl;
        set<int>::iterator q = (p->second).begin();
        for (; q != (p->second).end(); )
        {
            cout << *q;
            cout << (++q != (p->second).end() ? ' ' : '\n');
        }
    }

    return 0;
}

 一つの書き方としてありかも．
あと， 書き方を変えてみました． こっちの方が一般的？
確かFuegoも書き方はこんな感じだったと思う．
いろいろ見て， 見習っていきたい．

HTTP/1.1 400 Bad Request

これのお蔭で結構時間を無駄にした．
バグは単純なもので，GET要求の中でHTTP/1.1のところをHTTP1.1ってしてた・・・．
ま，これで当分はこのミスをしないってことで．

 時間は大切に．

AOJ Volume 5 Problem 0501 : Data Conversion

view plainprint?

1. #include <iostream>  
2. #include <map>  
3. using namespace std;  
4.   
5. int main() {  
6.     int n;  
7.     while (cin >> n, n) {  
8.         map<char, char> conversion;  
9.         map<char, char>::iterator p;  
10.         for (int i = 0; i < n; i++) {  
11.             char pre, post;  
12.             cin >> pre >> post;  
13.             conversion[pre] = post;  
14.         }  
15.   
16.         cin >> n;  
17.         for (int i = 0; i < n; i++) {  
18.             char ch;  
19.             cin >> ch;  
20.             p = conversion.find(ch);  
21.             cout << (p == conversion.end() ? ch : p->second);  
22.         }  
23.         cout << endl;  
24.     }  
25.   
26.     return 0;  
27. }  

#include <iostream>
#include <map>
using namespace std;

int main() {
    int n;
    while (cin >> n, n) {
        map<char, char> conversion;
        map<char, char>::iterator p;
        for (int i = 0; i < n; i++) {
            char pre, post;
            cin >> pre >> post;
            conversion[pre] = post;
        }

        cin >> n;
        for (int i = 0; i < n; i++) {
            char ch;
            cin >> ch;
            p = conversion.find(ch);
            cout << (p == conversion.end() ? ch : p->second);
        }
        cout << endl;
    }

    return 0;
}

mapを使ってキーが見つからない場合はマップの末尾を指す反復子を返すことを利用している．
全然，コンピュータ囲碁プログラムの話題ができなくて，テーマ変わっちゃいそうですが，今必死に考え中です・・・．

AOJ Volume 0 Problem 0051 : Differential Ⅱ

view plainprint?

1. #include <iostream>  
2. #include <string>  
3. #include <algorithm>  
4. using namespace std;  
5.   
6. int main() {  
7.     int n, min;  
8.     cin >> n;  
9.   
10.     for (int i = 0; i < n; i++) {  
11.         string str;  
12.         cin >> str;  
13.         sort(str.begin(), str.end());  
14.         min = atoi(str.c_str());  
15.         sort(str.rbegin(), str.rend());  
16.         cout << atoi(str.c_str()) - min  << endl;  
17.     }  
18.   
19.     return 0;  
20. }  

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    int n, min;
    cin >> n;

    for (int i = 0; i < n; i++) {
        string str;
        cin >> str;
        sort(str.begin(), str.end());
        min = atoi(str.c_str());
        sort(str.rbegin(), str.rend());
        cout << atoi(str.c_str()) - min  << endl;
    }

    return 0;
}

ショートコーディングすると，241byteでC++の中では一番短いみたいですが，

Cで書かれた一番短いコードとは100byte近く離されてる・・・。

AOJ Volume 1 Problem 0157 : Russian Dolls

view plainprint?

1. #include <iostream>  
2. #include <map>  
3. using namespace std;  
4.   
5. int main()  
6. {  
7.     int n, r, h;  
8.     while (cin >> n, n)  
9.     {  
10.         // longest increasing subsequence: lis  
11.         int k = 0, lis[200] = {0};  
12.         multimap<int, int> dolls;  
13.   
14.         for (int i = 0; i < 2; i++)  
15.         {  
16.             for (int j = 0; j < n; j++)  
17.             {  
18.                 cin >> r >> h;  
19.                 dolls.insert(pair<int, int>(r, h));  
20.             }  
21.             if (! i)  
22.                 cin >> n;  
23.         }  
24.   
25.         for (multimap<int, int>::iterator p = dolls.begin();  
26.              p != dolls.end(); p++)  
27.         {  
28.             for (multimap<int, int>::iterator q = dolls.begin();  
29.                  q != p; q++)  
30.             {  
31.                 if (p->first > q->first && p->second > q->second)  
32.                 {  
33.                     if (lis[distance(dolls.begin(), p)]   
34.                         <= lis[distance(dolls.begin(), q)])  
35.                     {  
36.                         lis[distance(dolls.begin(), p)]   
37.                             = lis[distance(dolls.begin(), q)] + 1;  
38.                         if (k < lis[distance(dolls.begin(), p)])  
39.                             k = lis[distance(dolls.begin(), p)];  
40.                     }  
41.                 }  
42.             }  
43.         }  
44.         cout << k + 1 << endl;  
45.     }  
46.   
47.     return 0;  
48. }  

#include <iostream>
#include <map>
using namespace std;

int main()
{
    int n, r, h;
    while (cin >> n, n)
    {
        // longest increasing subsequence: lis
        int k = 0, lis[200] = {0};
        multimap<int, int> dolls;

        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin >> r >> h;
                dolls.insert(pair<int, int>(r, h));
            }
            if (! i)
                cin >> n;
        }

        for (multimap<int, int>::iterator p = dolls.begin();
             p != dolls.end(); p++)
        {
            for (multimap<int, int>::iterator q = dolls.begin();
                 q != p; q++)
            {
                if (p->first > q->first && p->second > q->second)
                {
                    if (lis[distance(dolls.begin(), p)] 
                        <= lis[distance(dolls.begin(), q)])
                    {
                        lis[distance(dolls.begin(), p)] 
                            = lis[distance(dolls.begin(), q)] + 1;
                        if (k < lis[distance(dolls.begin(), p)])
                            k = lis[distance(dolls.begin(), p)];
                    }
                }
            }
        }
        cout << k + 1 << endl;
    }

    return 0;
}

I fill my spare time on the Web site of "AOJ".
What's "AOJ?"
AOJ stands for Aizu Online Judge.

他にもオンラインジャッジはUva Online Judgeなどありますが，
会津大学のオンラインジャッジは，パソコン甲子園などの日本語の問題も幅広く取り扱っていて
高校， 高専， 大学のプログミング部や同好会は結構使っているんじゃないかなぁと思います．
コードを書いて基礎体力？とアルゴリズムを勉強していきたい人には打って付けだと思います．

上のコードはDPを用いて解いたものです．
最長増加部分列を求めるような問題でした．
たぶん，コードを見ればその人との力量が分かると思うんで，
今こんな感じですが， 今後も励んでちっとでも美しく書けるように頑張りたいと思います．

卒業研究

GoGuiを用いたデバック風景
黒番が自分で白番が作成中の囲碁プログラムによるもの

そう，卒業研究の内容が決まってないんです．

題材はコンピュータ囲碁で行こうと思うんですが・・・。

実際は決まってたんですけど上手く行ってなくて，

方向転換する 必要性が出てきた感じです．

できれば，この夏休み中にまだ上手く行ってないアイディアで

再度，勝負したいんですが・・・．

プログラミング言語と計算機はあるんで，ヤル気次第・・・？

別に自己対戦でパターンの評価をするようなプログラムを作成して

みたんですが，なかなか良い結果はでなくて，ちと休憩中な感じです．

他に考えられる研究としては，自分が現在所属している研究室は

機械学習を専門としているので，それの応用とかだと思います．

機械学習といえば強化学習を用いたプログラム，RLGOが有名です．

何にせよ，早くこのブログに棋譜が掲載できるような

プログラムを作ってやんよ，な強気な姿勢で夏を過ごしたいと思います．

ようやく夏休み

今週から，ようやく夏休みです．

いろいろ，楽しみたいと思います．

また，卒業研究の内容がまだ確定してないので，

できればこの休み中にいろいろ考えて行きたいと思います．

Hello, I'm hizz

Hello, I'm hizz. I'm a CS major.

な日本の学生です．英語は好きですが，苦手です．

The Periphery of Game Informatics （ゲーム情報学の周辺のつもり） では

その名の通り，ゲーム情報学の周辺について書いて行きたいと思っています．

ゲーム情報学とは， 科学的にゲームを捉えてゲームを題材として情報処理の

諸分野を研究する分野で， 例えば囲碁や将棋のボードゲームとかRoboCup

Soccerとか扱います．

具体的に今はコンピュータ囲碁に挑戦しています．

最近のコンピュータ囲碁は モンテカルロ法を上手く使うことにより，

棋力の向上に成功しています．

最近の主な研究対象は，そのモンテカルロ法の並列化とかです．

自分のプログラムはまだまだ強くなく， 正直弱いですが， 11 月27， 28日に
開催される第4回UECコンピュータ囲碁大会で予選通過するプログラムを

作ることを目標に頑張ってます．

このブログでは，その試行錯誤などを書いていければと思います． 

絶対不定期なブログですが， 暇な時に見て頂ければと思います．