読者です 読者をやめる 読者になる 読者になる

びったんびったん

ユーザビリティ・プログラミングについて。

Chokudai Contest 3 考えたこと

問題文 A: ○×ブロック - Chokudai Contest 003 | AtCoder

5864点18位でした。

. + -ブロックひとつを異なる種類の. + -ブロックに変えてスコアが上がるようなら保持、下がるようなら元に戻す山登りをした。

遷移でスコアが変わらなくても、連結ブロック数の2乗和が大きくなるときは遷移した(スコアに関係ない連結ブロックが成長したら良さそう)

上下にooもしくはxxで挟まれた空間にはブロックを新設しない方がよさそうだった。連結を分断しやすそうなので。ただ間に合わなかったので確かめてない。

下の方からブロックを変えていくというのを2周した。

ブロックを変更していない列の落下処理はキャッシュして省略することで高速化(差分計算)、元に戻るときの情報を残しておいて元に戻すのを高速化などをして、試行回数は22万回くらいだった。

ブロックは落下するので下の方にかたよる。なので落下しない-ブロックを上の方に置くのはよくない。なのでそもそも遷移を試さない。

むずかしかったー

MM92 考えたこと

問題文 https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16857&pm=14485

感想

CutTheRootsに高速化焼きなましって意味で似てるなー、CutTheRootsってたしか最上位厳密スコア求めてるんだよなーこれも厳密スコアかなーで突っ走った結果、近似スコアだったでござる。 初日で方針ミスって、しかも下手に良いスコアとってしまい方針ミスに気付けなかったので次からは気をつけたい。

自分の方針だと色んな箇所に色んな高速化をしていて高速化ゲー(もちろん高速化だけでは厳しいけど)としてはかなり楽しい(そして練習になる)問題だと思いました。(ただこの記事ではほとんど省略されてます)

焼きなまし

近傍はライトを1つ動かす。 焼きなまし序盤はライトを大きく動かして、終盤は小さく動かす。動かす距離は時間の経過とともに指数的に小さくした(試行回数の少なさを補うにはこれが良いと思った)。


壁の近くはすぐにライトがカットされるので良い位置ではないだろうと遷移しないようにしてみたがあまり効果なし。


遷移先に偏りのない605Kでるプログラムでinner_xとinner_y(小数点以下の座標)の分布を見ると、ものっそい偏ってた。

f:id:hakomof:20170119224502p:plain

ヒートマップの色はテキトーだけど光源の45%がinner_x == 0 || inner_y == 0だった。おそらくライトの半径が整数で壁も整数刻みなので、inner_x == 0 || inner_y == 0だと壁と壁の間にすっぽりぴったし収まりやすいのだと思われる。なのでinner_x == 0 || inner_y == 0に遷移しやすくしてみたのだけどあまり効果なし(がーん)。

山登り

CutTheRootsしかりTerrainCrossingしかり座標が広い問題は最後に極端に狭い近傍で山登りというのをみなさまやってらっしゃる。のでライトを1つ周囲8dotに動かす山登りを最後にした。

高速化

100dot x 100dot(1セル)をunsigned long long[100][2]の格ビットで表現する。

f:id:hakomof:20170119224504p:plain

放射光のビットパターンと円形の光のビットパターンのandビット演算をすれば1つのライトのビットパターンが求まる。ライトとライトのorビット演算をすればライトが重なったビットパターンが求まる。あとはビットの数を数えれば(__builtin_popcountll)厳密なスコアが求まる。

f:id:hakomof:20170119224506p:plain

円形の光のビットパターンは事前に計算して持ってくる。

放射光のビットパターンは、 まず、放射光の境界線の角度が、光源から外に向かって貰うDPで求まる。 次に、境界線の角度と光源の座標から境界線の直線の式が求まる。 そして、直線の式に求めたいビット列のy座標を代入すれば何ビット目から何ビット目まで立ってるかがわかるのでビット列を求める。

他の(でも重要な)高速化

あるセルをあるライトが完全に照らしているとき、他のライトの処理の省略、代替、遅延、枝刈による高速化(これが重要だけど説明できず)。

壁による遮蔽なしライトの重なりなしなセルのスコアは2次元累積和でO(1)で求まる。

差分計算もしてます(これも重要だけど説明できず)。

Codeforces Marathon Round1 Online Exam

問題文 http://codeforces.com/contest/684/problem/A2

タイトルのマラソンで考えたことが書いてあります。過程を書いたので長いです。
暫定スコアは77261点、暫定順位は3位でした!がんばった!

69000点

2つのアイデアが必要でした。

1.ビット区間を反転してスコアが下がったら戻す

テキトーなビット列をクエリに投げてスコアを確認します。
1.そのビット列の一部を反転したものをクエリに投げます。
2.その結果、スコアが上がればビット列は反転したまま、スコアが下がればビット列を元に戻します。
1.2.をくりかえせばスコアは上がり続けます。

ではどんな一部を反転すればよいでしょうか。

1回のクエリで反転するビットの数は際限なく多いほうがよいです。
1つのビットを反転させたときのスコアの改善は高々1
2つのビット~は高々2
3つのビット~は高々3
...と反転するビットの数が多いほどスコアの改善が大きいことが期待できます。

また、スコア番目以降のビットを反転してもスコアは変わりません。つまり情報がとれない。そして初期スコアはK*2の4000前後で、クエリごとに上がるので4000ちょっとのビットから情報がとれます

また、最初のクエリは初期ビット列のスコアの確認に使いますし、最後のクエリの結果を元にさらにクエリを投げることもできません。なので使えるクエリの数は98で、めいっぱい使います。

また、同じビットを何度も調べるのは意味がない(一度調べて改善したビットを反転しても半分以上の確率でスコアが下がるため)のでクエリごとに反転するビットは重複しないほうがよさそうです。

以上より4000ちょっとのビット列を等しく98分割してクエリごとに順番に反転するという方針が立ちます。 4000 / 98 = 40.8... なので長さ41のビット区間×98あたりのスコアが一番よくなります。

f:id:hakomof:20160622203717p:plain

2.クエリの結果-1番目のビットは確実に誤答

左端から順番に採点して誤答の数がKになったら即座に終了ですから当然直前のビットは必ず誤答です。

この誤答はクエリを投げた直後に正し、以降このビットは不変としたほうがよいです。というのも正さずに放っておくと以降のクエリでこのビットが間違ってるやで~とまた言われてしまうので(間違っていることはすでにわかっているのでもったいない)。

1つのビットを正したときのスコアの上昇期待値は+2 です。1つのビットを正しているので確実に+1され、次のビットも正しければ+2、その次のビットも正しければ+3と続きます。次以降のビットが正しい確率は半分なので 1 * 0.5 + 2 * 0.25 + 3 * 0.125 + 4 * 0.0625 ... = 2 になります。+2点×99クエリ×100ケースで19800点くらい上がります。

上述のビット区間の反転と組み合わせるときにずれるので補正します。
1.あるビット列のクエリを投げて古いスコアをゲット
2.確実な誤答を正す
3.ビット区間を反転してクエリを投げて新しいスコアをゲット。新しいスコアと古いスコアを比較
このとき古いスコアは確実な誤答を正す前のスコアなのでその分ずれます。じゃあ期待値分+2すればよいかというと+1.333くらいがよいようです。たいていは+1か+2のどちらかだからだと思います。

また、上述のビット区間の反転とこれが重なってしまうのももったいないです。上述のビット区間の反転の全体の範囲が4000ちょっとが最適なのは(もっと広くてもよさげなのに)これが効いてるやも。んで、できるだけ重ならないようにするには速やかにビット列のスコアを4200くらいまで上げればよい、これはビット列をクエリごとに改善してれば十分か。あるクエリであるビット区間を反転したほうがスコアが上がることがわかったときに、あえて反転せずにためてためて最後のクエリでどばっと反転させてどばっとスコアを上げるテク(後述)を使ったときにやりすぎて(1~99クエリ目でほとんどスコアを上げなかったときに)死んだ。


この2つをやると69300点くらい出ました。

74000点

69000点の時点で75000点の人がいたのでその差を考えると1ケース60ビットの差があり、これは1クエリや2クエリの差ではないことがわかります。毎クエリやっていることが違う、毎クエリもっとたくさんの情報が得られると考えました。

そこでクエリを観察するとスコアが大きく変わるときと小さく変わるときがあります。この大きく変わるときとは正誤が偏っている(めっちゃ当たってるかめっちゃ外れてる)ということです。そして小さく変わるときは正誤が半分ずつに近いということです。

f:id:hakomof:20160622222459p:plain

このことよりスコアの変化量から正誤の偏りが推定できます正誤の偏りはずばりそのビット区間の改善の余地を意味します。偏りが小さいほど改善の余地が大きいです。たとえば長さ100のビット区間のうち90が当たっているときはあと10しか改善できませんし、90が外れているときは反転すれば90が当たっているときと同じですし、長さ100のビット区間のうち50が当たっているときは50も改善の余地があります。

そこで改善の余地が大きい偏りが小さいビット区間に優先的にクエリを投げるとよさそうということがわかります。あるビット区間にクエリを投げるべきかどうかはある区間を含むより広い区間の偏りがわかっていないといけない、つまりそのより広い区間にクエリが投げられていないといけないです。

そこでこのようなクエリが考えられます。

f:id:hakomof:20160622222501p:plain

誤答率というのは正誤の偏りの言い換えです、同じことを言っています。んでこのクエリの投げ方は以下のクエリの投げ方と同じクエリ数で同じ情報量が得られます。つまりその情報群から最適な戦略をとったきにまったく同じスコアになります(誤差を無視すれば)。

f:id:hakomof:20160622222504p:plain

この2つのクエリの投げ方からは同じ情報量が得られ、相互に入れ替えが可能です。ここで69000点解法を思い出してみます。4000ビットを98分割して等間隔にクエリを投げていましたね。

これを

f:id:hakomof:20160622222505p:plain

こうして

f:id:hakomof:20160622222508p:plain

こうして

f:id:hakomof:20160622222509p:plain

こうじゃ!

f:id:hakomof:20160622222510p:plain

なんか Binary Indexed Tree っぽいな? BIT 違いですあんまり関係ないです。これはまだ等価な置き換えをしただけなのでスコアは変わりません。ここで改善の余地が大きい偏りが小さいビット区間に優先的にクエリを投げるように変えます。

f:id:hakomof:20160622222458p:plain

投げているクエリの数(赤線の数)が変わっていないこと、ビット区間を仕切る黒縦線がばらついているのに注目してください。これで同じクエリの数で改善の余地が少ないビットへのクエリを節約して、改善の余地の大きいビットにたくさんクエリを投げれています。

これを実装すれば74000点が・・・出ません。誤差が大きくなりすぎます。このマラソンは誤差との壮絶な戦いでした。この誤差マラソン中にやってよかったことは誤差を無視したらどうなるのかを常に意識するとです。それは正解ビット列をカンニングしながら推定値を使うところをすべて真値を使うプログラムを書くことです。これをすると実装がバグってるのか誤差が大きすぎるかの切り分けができる、誤差0のときのスコアつまり誤差に対する上界がわかる、上界を元に1位に届くか判断できる、誤差でどのぐらいスコアが下がっているのかがわかるです。

でまあ以上のようなことをやって上界が78000点(1位オーバー)ですが誤差ありでは71000点くらいしかでず誤差が大きいことがわかりました。そこで誤差を小さくできれば1位に届くと思い、誤差が大きい箇所を調べました。誤差が大きい箇所は3つでした。

1.広いビット区間の反転は誤差が大きい
さっき述べましたがたくさんビットを反転するとスコアの変化量が大きいのでそれにともない誤差も大きくなります。広いビット区間のクエリは控えたいですね。

2.区間ACの誤答率と区間ABの誤答率から区間BCの誤答率を算出推定するときに誤差が累積する
クエリ値からの推定は1次ソースなので誤差は常に一定値以下ですが区間区間から区間の誤答率を求めるたびに誤差が累積します。ビット区間が狭くなるほど深くなるほど誤差が大きくなります。あまり深くしなければよさそうですね。

3.区間BCの誤答率がわかった時点で区間BCを反転した方がスコアが上がるかどうかがわかりますがこれを即時反転してしまうと誤差る
少し前に後述って言ってたやつです。わかった時点で反転してスコアを改善してしまうとスコアの上昇量を推定しないといけなくなり誤差がでます。反転したほうがスコアが上がるという情報を覚えておいて最後のクエリの直前にまとめて反転すると誤差を0にできます

1.2.より長さ88の区間46個を初期ビット区間集合として深さを3に制限する。3.をやる。パラメーター調整をする。これで74000点がでました。上界が78000点なので軽減したとはいえ結構誤差がのこってます。

77000点

誤差は限界まで小さくしたので他に何か問題がないか考えてます。反転するビット区間が広すぎると誤差が大きすぎてよくないことがわかりました。逆に狭すぎるとスコアの変化量が小さすぎるのでよくないこともわかっています。

このことから誤差が大きすぎず(長さが広すぎず)、スコアの変化量が小さすぎない(長さが小さすぎない)最適なビット区間の長さがあるのではと考えました。74000点解法は広い区間から徐々に狭い区間に狭めていくという解法でこの考察が正しいとするとよくないですね。なんとかしたい。

そこで広い区間を狭い2つの区間分割した後にもう一度統合すれば最適な区間の長さを保持できるのではと考えました。ここで統合という概念がでてきたのでここからは区間(連続している)という表現は正しくなくなったので以降ビット部分列という表現に変わります。

問題はどのビット部分列と部分列を統合するかです。これは誤答率ができるだけ近しい部分列と部分列を統合するのがよいです。理由は情報量の減少が小さいから。たとえば誤答率が10%の部分列と90%の部分列を統合してしまうと誤答率が50%になり情報がうすまってしまいます。

以上のことから偏りが小さく、かつ誤答率が近しい部分列を2つ選んで統合、分割して片方のビットを反転してクエリを投げるというのを繰り返すと改善の余地が大きいところを集中的に最適な長さのビット部分列で殴り続けられるので76000点がでました。

あとパラメーター調整とかヒューリティスとか誤差を小さくしたりあやしげな工夫をいろいろして77000点がでました。

リファクタしまくってたら100行くらいになった。

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

const int N = 5000, K = 2000, X = 100;
bool a[N + 1];
bool b[N + 1];

void invert(const vector<int>& v) {
    for (int i : v) {
        if (!b[i])
            a[i] = !a[i];
    }
}

int query(double prev, const vector<int>& v) {
    invert(v);

    for (int i = 0; i < N; ++i)
        cout << (int)a[i];
    cout << endl;
    cout.flush();
    int p;
    cin >> p;

    a[p - 1] = !a[p - 1];
    b[p - 1] = true;
    if (p < prev)
        invert(v);
    return p;
}

struct S {
    vector<int> v;
    double w;
    double score(const S& s, int t) const {
        return s.w - w + abs(s.w + w - v.size()) *
            (t < 3 ? 0.74 : t < 9 ? 0.5 : 0.3);
    }
    bool operator < (const S& s) const {
        return w < s.w;
    }
};

int main() {
    const int NUM = 42;
    const int LEN = 98;
    const int LEN2 = LEN / 2;
    const int Q = 3954;
    const double P = 1.34;
    const double DIFF = 4.8;

    vector<int> v;
    for (int i = 0; i < N; ++i)
        v.emplace_back(i);
    int p = query(K * 2, v);
    double prev = (p < Q ? query(0, vector<int>()) : max(p, K * 4 - p)) + P;
    S q[NUM];

    for (int i = 0; i < NUM; ++i) {
        for (int j = i * LEN; j < (i + 1) * LEN; ++j)
            q[i].v.emplace_back(j);
        int p = query(prev, q[i].v);
        q[i].w = LEN2 - abs(p - prev) / DIFF;
        prev = min<double>(max(prev + P, p + P), N);
    }

    for (int t = X - (p < Q) - NUM - 3; t; --t) {
        sort(q, q + NUM);
        S* s = q;
        for (int i = 2; i < NUM; ++i) {
            if (s[0].score(s[1], t) > q[i - 1].score(q[i], t))
                s = q + i - 1;
        }
        S ns[2];
        for (int i = 0; i < LEN * 2; ++i)
            ns[i < LEN].v.emplace_back(s[i % 2].v[i / 2]);
        int p = query(prev, ns[0].v);
        double diff = p - prev;
        for (int i = min(p, (int)prev); i < max(p - 1.0, prev); ++i)
            diff += b[i] && (p > prev ? -1 : 1);
        ns[0].w = LEN2 - abs(diff) / DIFF;
        ns[1].w = s[0].w + s[1].w - LEN2 - diff / DIFF;
        s[0] = ns[0];
        s[1] = ns[1];
        prev = min<double>(max(prev + P, p + P), N);
    }

    auto& s = *min_element(q, q + NUM, [LEN2](const S& a, const S& b) {
        return abs(a.w - LEN2) < abs(b.w - LEN2);
    });
    p = query(prev, vector<int>(s.v.begin(), s.v.begin() + LEN2));
    if (s.w - (p - prev) / DIFF > LEN2)
        invert(vector<int>(s.v.begin() + LEN2, s.v.end()));
    s.w = 0;

    for (auto& s : q) {
        if (s.w > LEN2)
            invert(s.v);
    }
    query(0, vector<int>());
    return 0;
}

MM89 考えたこと

マラソン参加3回目、がっつり参加したのは初めてだけれど楽しかったです。
暫定 72.34点 15位 Python

問題文 https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16494&pm=10967


全部Sにしたら100%になるよねーと思って上からSE以外をSにする。
38点


初期解(ランダム解)でなぜ迷路がほとんどできないのか考えてみる。

境界からスタートしてランダムに動いてもその場からあまり動かない。迷路の中心に向かう力がない。大きな迷路ができにくい。

ビジュアライザを無効なパスを表示するように変えてみる。
Uに突っ込んでる。Uを変えればよい。
くるっと回転して自分のパスに突っ込んでる。回転しなければよい。直進すればよい?やっぱりSが強い?

直進すれば迷路の中心に向かって迷路が大きくなり、回転して死ぬこともなくなる?


紙にいろいろ書いて思いつく。

f:id:hakomof:20151027204511p:plain

LとRが交互に並ぶようなライン(間にSやEはあってもよい)はどこから進入しても下から入れば上へ、上から入れば下へ抜ける。蛇行しながら直進する。

このラインを下端から上端まで積めば下端から上端、上端から下端へ抜ける迷路がたくさんできる。

このLとRが交互になるような修正をX座標が小さい順にF個とる。
64点

f:id:hakomof:20151027204509p:plain


ここでかなり迷走したので数多のソースが生まれそして死んでいった。

複数の迷路が密に重なっているのがよくないのではと思った。
複数の迷路で修正を共有しているのはメリットだけれど、マスを共有しているのはデメリットなのでトータル損してそう。もっと高効率な迷路をばらけさせたい。

LとRが交互になるような修正を全体にしたうえで有効な迷路を列挙する。
厳密に列挙すると指数時間になってしまうので、上左右の移動だけ、下左右の移動だけでできる迷路を列挙する。列挙漏れはEがからむときだけなので見なかったことにする。この制限でメモ化ができるようになってるはずなんだけど今自分の実装見るとしてない。あれ?

で、列挙した迷路をFを超えない範囲で近似スコアが最大になるように選択する組み合わせ問題になった。

最初DPしようとしたけどマスが共有されているのでできなんだ。

迷路ごとのマス数/修正数が大きい順にFを超えない範囲で選んでいく(貪欲)。
71点

f:id:hakomof:20151027204505p:plain


選択した迷路をひとつのぞいて別の迷路を選択して近似スコアが上がれば採用(山登り)。
72点

焼きなまそうと思ったけどよくわからず。

おわり


その他

方針さえあってれば Python でも探索時間減るだけやし上位狙わなければへーきへーきと思ったけど全然きつい。終わる前提の処理が終わらない終わらない。配列使いまわしたり、boolの2次元配列を整数の1次元配列に圧縮したり、なくなく迷路集合カットするなどした。

LとRを交互にするというアイデアに固執しすぎた感。マラソン終わるまで現解法の発展が上位の解法だと信じて疑わなかった。反省。

EとEを優先的につなぐように修正してみたけど微増だったのでやめた。テストケースごとのスコアは大きく上下するのがたまにある感じでWHFに特徴がみられなかった。今思うとEの割合とかもっとよく見ればよかった。平均じゃなくてFが多いとか少ないとか個々のテストケース見るの大事。

結局乱数使わなかったんだけどこれでいいのか。


Python 240 行

from copy import deepcopy
from itertools import compress, count, product, starmap
from time import time

class MazeFixing:
    def improve(self, maze, F):
        reverse = len(maze[0]) < len(maze)

        if reverse:
            maze = transpose(maze)
        else:
            maze = list(map(list, maze))

        fixes = createFixes(maze)
        paths = createPaths(maze, F, fixes)
        pair = climb(maze, F, paths, *greed(maze, F, paths))

        pair.fixed.i = -1

        fixes = [(y, x, fixes[y][x])
            for y in range(len(maze))
                for x in range(len(maze[0]))
                    if maze[y][x] is not '.' and pair.fixed.get()]

        if reverse:
            fixes = ((y, x, dest) for x, y, dest in fixes)
        return list(starmap('{} {} {}'.format, fixes))

def transpose(maze):
    return list(map(list, zip(*maze)))

def createFixes(maze):
    fixes = [[''] * len(maze[0]) for _ in range(len(maze))]
    ux = -1

    for y, line in enumerate(maze):
        for x, cell in enumerate(line):
            if cell in '.LRE':
                if ux >= 0:
                    if left is cell is 'L':
                        line[ux] = 'R'
                        fixes[y][ux] = 'R'
                    elif left is cell is 'R':
                        line[ux] = 'L'
                        fixes[y][ux] = 'L'
                    else:
                        line[ux] = 'S'
                        fixes[y][ux] = 'S'

                    ux = -1
                left = cell

            elif cell is 'U':
                if ux >= 0:
                    line[ux] = 'S'
                    fixes[y][ux] = 'S'
                ux = x

    xs = []

    for y, line in enumerate(maze):
        for x, cell in enumerate(line):
            if cell in '.E' or cell in 'LR' and xs and cell is not line[xs[0]]:
                for i in xs[1:-1:2]:
                    line[i] = 'R' if line[i] is 'L' else 'L'
                    fixes[y][i] = line[i]

                if xs and not len(xs) % 2:
                    line[xs[-1]] = 'S'
                    fixes[y][xs[-1]] = 'S'
                xs = []

            if cell in 'LR':
                xs.append(x)
    return fixes

def createPaths(maze, F, fixes):
    width = len(maze[0])
    height = len(maze)

    paths = []
    visited = [[False] * width for _ in range(height)]
    fixed = deepcopy(visited)

    for y, x, d in product(range(height), range(width), (1, 3)):
        if maze[y][x] is not '.' and maze[y + dy[d]][x + dx[d]] is '.':
            search(maze, fixes, visited, fixed, x, y, (d + 2) % 4, d)

            path = BoolsPair((width - 2) * (height - 2))

            for i, j in product(range(height), range(width)):
                if maze[i][j] is not '.':
                    path.append(visited[i][j], fixed[i][j])
                visited[i][j] = False
                fixed[i][j] = False

            if any(path.fixed.a):
                paths.append(path)
    return paths

def search(maze, fixes, visited, fixed, x, y, d, b):
    if maze[y][x] is '.':
        return d is (b + 2) % 4

    for i in range(4) if maze[y][x] is 'E' else [
            (d + 'SRUL'.index(maze[y][x])) % 4]:
        if not (i is b or i is (d + 2) % 4):
            visited[y][x] = search(maze, fixes, visited, fixed,
                x + dx[i], y + dy[i], i, b) or visited[y][x]

    if visited[y][x]:
        fixed[y][x] = bool(fixes[y][x])
    return visited[y][x]

def greed(maze, F, paths):
    src = BoolsPair((len(maze[0]) - 2) * (len(maze) - 2))
    dest = deepcopy(src)
    mx = deepcopy(src)

    compressed = [True] * len(paths)

    while any(compressed):
        mx.visited.count = 0
        mx.fixed.count = 1

        for i, path in compress(enumerate(paths), compressed):
            dest.merge(src, path)

            if src.visited.count == dest.visited.count or dest.fixed.count > F:
                compressed[i] = None

            elif (mx.visited.count / mx.fixed.count <
                    dest.visited.count / dest.fixed.count):
                mxI = i
                mx, dest = dest, mx

        if any(compressed):
            compressed[mxI] = False
            src, mx = mx, src

    return src, [c is False for c in compressed]

def climb(maze, F, paths, mx, mxAdded):
    timer.limit = 8

    while True:
        updated = False
        added = mxAdded[:]

        for i in compress(range(len(added)), added):
            if timer.elapses():
                return mx

            added[i] = False

            src = BoolsPair((len(maze[0]) - 2) * (len(maze) - 2))
            dest = deepcopy(src)

            for path in compress(paths, added):
                src.merge(src, path)

            for j, path in enumerate(paths):
                if not (i == j or added[j]):
                    dest.merge(src, path)

                    if (dest.fixed.count <= F and
                            mx.visited.count < dest.visited.count):
                        updated = True
                        mx, dest = dest, mx
                        mxAdded[i] = False
                        mxAdded[j] = True
            added[i] = True
        if not updated: break
    return mx

class BoolsPair:
    def __init__(self, n):
        self.visited = Bools(n)
        self.fixed = Bools(n)

    def append(self, visited, fixed):
        self.visited.append(visited)
        self.fixed.append(fixed)

    def merge(self, a, b):
        self.visited.merge(a.visited, b.visited)
        self.fixed.merge(a.fixed, b.fixed)

    def copy(self, a):
        self.visited.copy(a.visited)
        self.fixed.copy(a.fixed)

class Bools:
    def __init__(self, n):
        self.a = [0] * ((n + 62) // 63)
        self.i = 0
        self.count = 0

    def append(self, v):
        self.a[self.i // 63] = self.a[self.i // 63] | v << self.i % 63
        self.i += 1

    def merge(self, a, b):
        self.count = 0
        for i, a, b in zip(count(), a.a, b.a):
            self.a[i] = a | b
            self.count += bin(self.a[i]).count('1')

    def copy(self, a):
        self.count = a.count
        for i, a in enumerate(a.a):
            self.a[i] = a

    def get(self):
        self.i += 1
        return self.a[self.i // 63] >> self.i % 63 & 1

class Timer:
    def __init__(self):
        self.start = time()

    def elapses(self):
        return time() - self.start > self.limit

dx = 1, 0, -1, 0
dy = 0, 1, 0, -1

timer = Timer()

# maze = [raw_input() for _ in range(int(raw_input()))]
# F = int(raw_input())

# ret = MazeFixing().improve(maze, F)

# print(len(ret))
# print('\n'.join(ret))

Laravel 5 のデバッグ出力

Laravel 5 でデバッグ出力する3つのやり方についてまとめる。

ログファイルに書きだす

2通りの書き方がある。

ヘルパー関数 logger(), info()

<?php

Route::get('/', function() {

    $message = ['a' => 1, 'b' => 2, 'c' => 3];

    logger($message);
    info($message);

    // logger()->notice($message, $context);
    // logger()->warning($message, $context);
    // logger()->error($message, $context);
    // logger()->critical($message, $context);
    // logger()->alert($message, $context);
    // logger()->emergency($message, $context);

    return 'OK';
});

storage/logs/laravel.log に書き出される。

[2015-07-31 13:40:35] local.DEBUG: array (
  'a' => 1,
  'b' => 2,
  'c' => 3,
)  
[2015-07-31 13:40:35] local.INFO: array (
  'a' => 1,
  'b' => 2,
  'c' => 3,
)  

配列ライクは var_export() で、 Jsonable なクラスインスタンスJSON 文字列に内部で見やすく整形してくれる。なので、何も考えずに引数に渡してよい。

Log ファサード

<?php

namespace App\Http\Controllers;

use Log;

// ...

class MyController extends Controller {

    public function index() {

        $message = ['a' => 1, 'b' => 2, 'c' => 3];

        Log::debug($message);
        Log::info($message);

        // Log::notice($message, $context);
        // Log::warning($message, $context);
        // Log::error($message, $context);
        // Log::critical($message, $context);
        // Log::alert($message, $context);
        // Log::emergency($message, $context);

        return 'OK';
    }
}

ヘルパー関数と Log ファサードのやってることはまったく同じ。ただ、 Log ファサードはファイルの先頭で use Log; しないといけなかったり、 use Log; できない php ファイルがある?のでヘルパー関数の logger() のほうが便利。グローバル関数は最強だな。

ブラウザに表示する var_export()

<?php

Route::get('/', function() {

    $message = ['a' => 1, 'b' => 2, 'c' => 3];

    echo '<pre>' . var_export($message, true) . '</pre>';

    return 'OK';
});

Laravel と関係ない PHP おなじみのやり方。一応説明すると var_export() で見やすく整形して pre タグで改行を可視化している。

f:id:hakomof:20150801095107p:plain

ブラウザにリッチに表示する dd()

<?php

Route::get('/', function() {

    $message = view();

    dd($message);

    return 'OK';
});

dump and die の略。上述の2つと違ってクラスインスタンスとか複雑なものも表示できる。 die と名のつく通りアプリケーションの実行を停止する( OK が表示されてないよね)。なんかすごい。

f:id:hakomof:20150801095108p:plain

まとめ

logger($message, $context);

ログファイルに書きだすので残る。

echo '<pre>' . var_export($message, true) . '</pre>';

ブラウザに表示する。

dd($message);

ブラウザにリッチに表示する。クラスインスタンスとか複雑なものも表示できる。アプリケーションの実行を停止する。

以上です。それでは Laravel のよきデバッグライフを。

CoffeeScript と Phaser でゲームつくったよ!

f:id:hakomof:20150620084919p:plain

ゲーム インビジゴースト - 見えざる敵の居所を探り、迎え撃て!
ソース hakomo/InvisibleGhost · GitHub
遊んでみてね。

ゲームフレームワーク Phaser を使っていて思ったことを書きたい。

Atom を設定した

f:id:hakomof:20150505135647p:plain

Atom の正式版公開当初にさわって以来ごぶさただったのですが、最近話題をちらちら見るのでさわってみたらよかったので設定した。

Atom は主に CoffeeScript, Stylus, Slim, Markdown, メモを書くのに使うと思う。たまに Python, Ruby も。 Sublime からの乗り換え。

エディタはできるだけカスタマイズしないでデフォルトで使いたい人。

Settings

Settings で一般設定を、Packages でパッケージごとの設定が GUI でできる。

んで下記が GUI が出力したテキスト形式の設定。 CSON って言うらしい。 JSONCoffeeScript 版だそうな、はじめて知った。まあ JSON から徹底的にタイプ量減らしましたみたいな。

GUI じゃないと無理って人も、テキストベースで管理したいって人も配慮しているこのかんじ好きよ。

それで私の Setting がこちら。

"*":
  welcome:
    showOnStartup: false
  editor:
    tabLength: 4
    fontSize: 18
    lineHeight: 1.25
    scrollPastEnd: true
    fontFamily: "'Consolas' 'Meiryo'"
    invisibles: {}
    softWrap: true
  whitespace:
    ignoreWhitespaceOnCurrentLine: false
  "bracket-matcher":
    autocompleteBrackets: false
  "autocomplete-plus": {}
  core: {}

順番に見ていく。

tabLength: 4
どんな言語でもインデントはスペース4つ。らくちん。

fontSize: 18
lineHeight: 1.25
テキトーに自分の Sublime の設定に似せた。

scrollPastEnd: true
最下行以降もスクロールできるので最下行付近も画面中央で見れる。

fontFamily: "'Consolas' 'Meiryo'"
Windows だとおされな Atom の中で MS ゴシック さんがぶいぶいしちゃうのでなんとかする。

f:id:hakomof:20150505135650p:plain

CSS の font-family プロパティに英字フォント、日本語フォントの順に指定すると英字は英字フォント、日本語は日本語フォントで表示されるというテクがある。そこで好みの等幅英字フォント、好みの日本語フォントの順にクォーテーションで囲んで指定する。この場合、( CSS font-family なら)囲まなくても動くと思うんだけど囲まないとなぜか動かない。

エディタのカスタマイズってエディタ固有の知識が多すぎて闇が深いなあと思っていたので、ブラウザベースの Atom なら闇を晴らしてくれるかと少し期待してみたけどだめだったよ。。。

softWrap: true
折り返す。

whitespace: ignoreWhitespaceOnCurrentLine: false
デフォルトでは保存時に行末のスペースを削除してくれるんだけどカーソル行のスペースは削除しない。おそらく、保存してから入力しようと思ったらスペースが削除されてスペースを打ち直すっていうのをなくす配慮だろうけど、行末にスペースを残しかねないので無効。

"bracket-matcher": autocompleteBrackets: false
( を入力したら ) を補完する。あらゆるエディタ・ IDE についてるけど邪魔だと思ったことこそあれ、便利だと思ったことはない。無効。

Your Keymap

ショートカットキーを変えられます。デフォルトが使いやすいのであまり変えていません。

'.platform-win32 atom-text-editor, .platform-linux atom-text-editor':
    'f4': 'find-and-replace:replace-next'
    'shift-f4': 'find-and-replace:replace-all'

置換を F4 に割り当てています。これは置換する、これはしない、これはする・・・とスッスッスーとやりたい。 F3 のスキップとあわせてできるようになります。 ctrl-enter で replace-all できるのですが、エディタ外の特殊なキーバインドのせいで ctrl-enter が押せないので割り当てています。

Your Stylesheet

Atom はブラウザベースなので外観を Stylesheet で記述する。ようするに、タグやクラス名とセレクターで要素を限定し、 CSS プロパティで色などを指定する。んで AtomCSS の代替 LESS で記述する。いやあ Stylus 使いにはつらいぜ。

それで私の Stylesheet がこちら。

.tree-view {
    font-family: Meiryo;
}

atom-text-editor.is-focused::shadow .cursors .cursor {
    opacity: 1;
}

atom-text-editor::shadow .lines .line.cursor-line {
    background-color: transparent;
}

順番に見ていく。


上述の記述だけでは MS ゴシック を根絶やすには不完全だったようで Tree View からこんにちは。

f:id:hakomof:20150505135649p:plain

Tree View は等幅でなくてよいので Meiryo のみ指定。

.tree-view {
    font-family: Meiryo;
}

それでもまだ Markdown Preview でこんにちはするし、他にもこんにちはするかもしれない。あとで直そう。。。


atom-text-editor.is-focused::shadow .cursors .cursor {
    opacity: 1;
}

カーソルの点滅をなくす。
Blinking Cursor - Atom Discussion
URL 先を参考に改変。


atom-text-editor::shadow .lines .line.cursor-line {
    background-color: transparent;
}

カーソル行のハイライトをなくす。
Where is the active line background color? - Atom Discussion
URL 先をコピペ。


カーソルの点滅とかカーソル行のハイライトって、カーソルを見失ったときに探しやすくするためですよね。カーソルが見つかっているのであれば、入力行に色がついて見づらいだけやし、周辺視野でチッカチッカする害悪だと思うんですよ。なので消します。

見失ったときは上キー押して下キー押せばカーソルが動いてすぐ見つかるので十分です。

Packages

あとから入れたパッケージ。設定も一通り見たがすべてデフォルト。

autocomplete-plus
デフォルトだと ctrl-space しないと補完候補がポップアップしないが、キー入力と同時にポップアップする。

autocomplete-snippets
補完候補にスニペットを含める。

japanese-wrap
日本語の折り返しを修正する。 Core Settings の Soft Wrap を有効にする必要がある。

language-slim
HTML の代替 Slim のシンタックスハイライトなど。

これとほぼ同じダウンロード数のパッケージに ruby-slim があったが ruby まわりでエラーを吐いた。 Slim のコンパイルは Node.js + gulp.js でやっていて Atom ではやらないので language-slim を採用した。

sort-lines
CSS のプロパティのような順番が(ほぼ)何でもよいときに、わかりやすい順番を考える時間が無駄なので無思考にソートする用。

Stylus
CSS の代替 Stylus のシンタックスハイライトなど。セレクター行で改行してもインデントしないのが Sublime に比べて使いづらい。

カスタマイズする上で役に立ちそうなもの

ctrl-,
Settings をすばやく開く。

alt-ctrl-i
Google Chrome でおなじみ Developer Tools を開く。

f:id:hakomof:20150505135652p:plain

ctrl-shift-p
Command Palette を開く。すべてのコマンドを検索・実行できる。

ctrl-.
Keybinding Resolver を開く。開いた状態でキーを押すと、実行されたコマンドとコンテキストが表示される。

Command Palette と Keybinding Resolver を使うとショートカットキーの設定がはかどるかもしれない。

Menu -> Packages -> Timecop -> Show
起動にかかった時間が表示される。重いパッケージを無効化するときなどに。

Packages の各言語には Setting ボタンがないがクリックすると設定できる。戻る欲しい。

以上です。おつかれさまでした。