マラソン系プロコンでコンソールでビジュアライズする話

これは何？

マラソン系のプログラミングコンテスト（Topcoder Marathon Match(MM)、AtCoder Heuristic Contest(AHC)など)で、コンソールでビジュアライズするのはいかがですか？とお勧めする記事です。 上記のようなコンテストではグラフィカルなビジュアライザーが公式に提供されることが多いですが、コンソールで見られるビジュアライザーを提出コードに書くことで、コードを実行するだけで動作を確認できる、公式ビジュアライザー以上の情報を盛り込むことができる、などのメリットがあります。

環境はwsl、プログラミング言語はC++ですが、他の言語でも応用できると思います。

まず初めに

AHC011を題材に進めていきます。

atcoder.jp

まずは入力を読み込んで、盤面を標準エラー出力に出力してみます。

// 前略
// ソルバー
class Solver
{
    public:
    vector<int> grid;
    string answer;
    
    Solver() {};
    
    void init() {
        srand(time(NULL));
        cin >> N >> T;
        grid.resize(N * N);

// 中略
    }

    void input() {
        rep(r, N) {
            string s;
            cin >> s;
            rep(c, N) {
                grid[r * N + c] = s[c];
            }
        }
    }

    void output() {
        cout << answer << endl;
    }

    void show()
    {
        rep(r, N) {
            rep(c, N) {
                cerr << (char)grid[r * N + c];
            }
            cerr << endl;
        }
    }
    
    void solve() {
        init();
        input();
#ifdef LOCAL
        show();
#endif
        output();
    }
};

Solver solver;

int main()
{
    solver.solve();
}

コード全体はこちら。 Solver クラスの中で grid という int の vector に盤面を読み込みます。show()関数が標準エラー出力に盤面を出力します。呼び出しを #define LOCAL ～ #endif で囲うことで、コンパイル時に -DLOCAL オプションをつけた時だけ盤面出力をするようにし、このまま提出できるようにしています。 -DLOCALオプションを付けてコンパイルし実行した結果はこのようになります。

入力をそのまま出力しているだけですが、まず入力をきちんと読み込み保持出来ているか確認するのは、特に初心者には大事だと思います。

ちょっと動かしてみる

AHC011はスライドパズルで木を作る問題です。とりあえず空きマスをランダムに動かしてみましょう。

class Solver
{
    public:
    //    int N, T;
    vector<int> grid;
    
    Solver() {};
    string answer;
    
    void init() {
        srand(time(NULL));
        cin >> N >> T;
        grid.resize(N * N);
        nei4.resize(N * N);
        nei4rc.resize(N * N);

        // ４近傍事前計算
        rep(r, N) {
            rep(c, N) {
                rep(dir, 4) {
                    int r0 = r + DR[dir];
                    int c0 = c + DC[dir];
                    if(!inside(r0, c0)) continue;
                    nei4[r * N + c].push_back(dir);
                    nei4rc[r * N + c].push_back(r0 * N + c0);
                }
            }
        }
    }
// 中略
    void modify()
    {
        // 0 を探す
        int r0, c0; // 0 の位置
        rep(i, N * N) {
            if(grid[i] == '0') {
                r0 = i / N;
                c0 = i % N;
            }
        }
        // 動かす
        int rc0 = r0 * N + c0;
        int dir = nei4[rc0][rand() % nei4[rc0].size()];
        int r1 = r0 + DR[dir];
        int c1 = c0 + DC[dir];
        int rc1 = r1 * N + c1;
        swap(grid[rc0], grid[rc1]);
        answer.push_back(DIREC[dir]);
    }
    
    void solve() {
        int totaltime;
        init();
        input();
#ifdef LOCAL
        show();
#endif
        rep1(loop, LOOP_MAX) {
            modify();
#ifdef LOCAL
            cerr << "\nloop:" << loop << endl;
            show();
#endif
        }
        output();
    }
};

Solver solver;

int main()
{
    solver.solve();
}

ソース全体はこちらです。 ランダムに空きマスを移動しているのは modify()関数です。事前にnei4配列にセルごとに4近傍のうち移動可能な方向をリストアップしてあるので、その中からランダムに移動先を選びgridの値をswap()関数で入れ替えています。また移動方向をあらわす文字 DIREC[] を解を保持する変数 answer に追加しています。

そしてsolve()関数の中ではmodify()関数を呼び出してループ回数とgridの表示を LOOP_MAX 回繰り返しています。移動を確認できればいいので、とりあえず3回ループしてみましょう。

0が空きマスを表しています。初期状態から0が下→上→左と移動していて、最後に移動を表す"DUL"という文字列が標準出力に出力されています。よく見ると正しく操作が行われているのがわかりますが、ループ回数を上限のT回(2 * N ^ 3回)まで増やすと大量の表示があっという間にスクロールしていってしまいます。

表示位置を固定してみる

show()関数の表示位置を固定してループごとに上書きしてみましょう。コンソールで表示位置を指定するにはANSI エスケープシーケンスが使えます。ANSI エスケープシーケンスについてはこちらを参考にさせていただいてます。

qiita.com

エスケープ文字(プログラム中では '\e')に続けて所定の文字列を出力することでカーソル位置の指定や文字色背景色の変更、画面消去などができます。これはコンソール側の機能なのでプログラミング言語によらず利用することが出来ます。一方で利用するターミナルソフトによってANSI エスケープシーケンスへの対応に違いがあり、利用できないものがある場合もあります。 プログラム中でよく使いそうなものは関数にしておくと便利です。

// ANSI エスケープシーケンス関数
// カーソルを上へ移動
void escUp(int a)
{
    fprintf(stderr, "\e[%dF", a);
}

// 文字色を変更
void escColor(int c)
{
    fprintf(stderr, "\e[3%dm", c);
}

// 文字色を変更（拡張）
void escColorEx(int c)
{
    fprintf(stderr, "\e[38;5;%dm", c);
}

// 背景色を変更
void escBColor(int c)
{
    fprintf(stderr, "\e[4%dm", c);
}

// 背景色を変更（拡張）
void escBColorEx(int c)
{
    fprintf(stderr, "\e[48;5;%dm", c);
}

// 表示属性をリセット
void escReset()
{
    fprintf(stderr, "\e[0m");
}

// 画面消去
void escClear()
{
    fprintf(stderr, "\e[2J");
}

// カーソル位置を移動
void escLocate(int r, int c)
{
    fprintf(stderr, "\e[%d;%dH", r + 1, c + 1);
}

上記の関数を使って次のように変更します。

// ソルバー
class Solver
{
    public:
    //    int N, T;
    vector<int> grid;
    
    Solver() {};
    string answer;
    
    void init() {
        srand(time(NULL));
        cin >> N >> T;
        grid.resize(N * N);
        nei4.resize(N * N);
        nei4rc.resize(N * N);

        // ４近傍事前計算
        rep(r, N) {
            rep(c, N) {
                rep(dir, 4) {
                    int r0 = r + DR[dir];
                    int c0 = c + DC[dir];
                    if(!inside(r0, c0)) continue;
                    nei4[r * N + c].push_back(dir);
                    nei4rc[r * N + c].push_back(r0 * N + c0);
                }
            }
        }
#ifdef LOCAL
        escClear();
#endif
    }

// 中略

    void show()
    {
        escLocate(0, 0); // 画面左上にカーソルを移動
        rep(r, N) {
            rep(c, N) {
                cerr << (char)grid[r * N + c];
            }
            cerr << endl;
        }
        usleep(250 * 1000); // 250ms のウェイト
    }
    
// 中略

    void solve() {
        int totaltime;
        init();
        input();
#ifdef LOCAL
        show();
#endif
        rep1(loop, T) {
            modify();
#ifdef LOCAL
            show();
#endif
        }
        output();
    }
};


Solver solver;

int main()
{
    solver.solve();
}

初期化関数 init() の中でescClear()関数を呼び出し画面消去しています。また show()関数で初めにカーソル位置を(0, 0)(左上隅)に移動してから表示してます。そのままだと一瞬で表示が終わってしまうので usleep()関数で250msのウェイトを入れています。 実行すると次の様になります。

youtu.be

0がランダムに移動していることがわかりますが見づらいですし、グラフの繋がり具合もパッと見ただけではわかりません。

グラフを表示してみる

タイルを分かりやすく表示するにはどうしたらいいでしょうか。1文字で各タイルを表現できる文字があれば比較的簡単ですが、そのような記号文字はなさそうです。今回は各タイルを3×3文字で表現してみます。中心の頂点は'*'、縦横に伸びる枝は'|'と'-'を使います。今までの様に上の行から順番に出力しようとするとプログラムが複雑になりそうなので、表示用のバッファを用意しタイルごとにバッファに書き込んだ上で出力します。 これまでは盤面を表すgridを読み込んだ文字のまま保持していましたが、扱いやすいよう読み込んだ段階で'0'から'f'の文字を0から15の数値に変換しておきます。show()関数は次の様になります。

    void show()
    {
        int N3 = N * 3;
        vector<string> buf(N3 * N3);
        escLocate(0, 0);
        rep(r, N) {
            rep(c, N) {
                int rc = r * N + c;
                // 空白で初期化
                rep(r1, 3) {
                    rep(c1, 3) {
                        int rc1 = (r * 3 + r1) * N3 + (c * 3 + c1);
                        buf[rc1] = " ";
                    }
                }
                if(grid[rc] != 0) {
                    int rc1 = (r * 3 + 1) * N3 + (c * 3 + 1);
                        buf[rc1] = "*";
                }
                
                rep(dir, 4) {
                    if(grid[rc] & (1 << dir)) {
                        int rc1 = (r * 3 + 1 + DR[dir]) * N3 + (c * 3 + 1 + DC[dir]);
                        buf[rc1] = "-|"[dir%2];
                    }
                }                
            }
        }

        rep(r, N * 3) {
            rep(c, N * 3) {
                int rc = r * N3 + c;
                cerr << buf[rc];
            }
            cerr << endl;;
        }
        
        usleep(250 * 1000);
    }

ソース全体はこちらです。 実行するとこのようになります。

youtu.be

もうちょっと見栄えをよくする

グラフの繋がりが分かるようにはなりましたが、もう少し見栄えをよくするために背景色で表示してみます。またタイルが縦長なので、正方形に近づけるためにバッファの１要素を半角の空白1文字から2文字にします。さらにタイルの境界が分かりやすいように背景をグレーの濃淡で市松模様にしてみましょう。ANSIエスケープシーケンスによる色の指定などをバッファに追加できるように、これまで標準エラーに出力していたANSIエスケープシーケンスをstring型で返す関数を用意しました。

    void show()
    {
        char sb[255];
        int N3 = N * 3;
        vector<string> buf(N3 * N3);
        int back_color[] = {0xEC, 0xEF};
        
        escLocate(0, 0);
        rep(r, N) {
            rep(c, N) {
                int rc = r * N + c;
                // 空白で初期化
                rep(r1, 3) {
                    rep(c1, 3) {
                        int rc1 = (r * 3 + r1) * N3 + (c * 3 + c1);
                        buf[rc1] = escSBColorEx(back_color[(r + c) % 2]) + "  " + escSReset();
                    }
                }
                if(grid[rc] != 0) {
                    int rc1 = (r * 3 + 1) * N3 + (c * 3 + 1);
                    buf[rc1] = escSBColorEx(0x82) + "  " + escSReset();
                }
                
                rep(dir, 4) {
                    if(grid[rc] & (1 << dir)) {
                        int rc1 = (r * 3 + 1 + DR[dir]) * N3 + (c * 3 + 1 + DC[dir]);
                        buf[rc1] = escSBColorEx(0x82) + "  " + escSReset();
                    }
                }
            }
        }

        rep(r, N * 3) {
            rep(c, N * 3) {
                int rc = r * N3 + c;
                cerr << buf[rc];
            }
            cerr << endl;;
        }
        
        usleep(250 * 1000); // 250ms スリープ
    }

ソース全体はこちらです。 そして実行結果はこちらです。

youtu.be

とても見やすくなりテンションがあがりますね！コンテストへのやる気もアップするというものです。え？自分だけ？

ここまでで、プログラムを実行するだけでビジュアライザーで動作を確認できるようになりました。ですが、まだ公式のビジュアライザーに比べ最大の木を色を変えて表示出来てないので情報量としては負けています。さらに工夫して公式にはない情報を盛り込み、現状の解法の改善点を見つけやすくすることでスコアアップに繋げられるかどうかはあなた次第です！！

気を付けること

今回表示の更新速度を落とすためにusleep()関数でウェイトを入れています。実行時間制限いっぱいに解を探索しながらビジュアライズする場合、当然ですがビジュアライズしない場合より探索できる量が大幅に落ちてしまいます。あくまで動作の確認時にのみ表示するか、ビジュアライズ時は探索時間を延ばすなどの工夫が必要でしょう。

おわりに

男の子ってこういうのが好きなんでしょ？

これはA*ぽいので解を探している様子。ホントのA*だと最短解が見つかるらしいのですが、そもそもスライディングブロックパズルの最短解はNP困難だとかどこかで見たので、条件緩めて最短じゃなくても解が見つかれば、とアレコレいじってみましたがうまくいきませんでした。 #AHC011 pic.twitter.com/HlzTQzroDB

— もおあき (@moooaki) 2022年6月5日

自分も大好きです。普段のprintfデバッグもANSI エスケープシーケンスで色を付けるだけでもグッと視認性がよくなります。この記事で自作ビジュアライザー画像をシェアしてくれる方が増えると嬉しいです。エスケープシーケンス大好きおじさんなので。

おまけに

かっこいいビジュアライザーが出来たら、スクショを撮ってうまく切り抜いて一辺が2000pixくらいにサイズ調整して SUZURI というグッズ作成サイトでTシャツにしてみるのも楽しいですよ。