Panda Noir

JavaScript の限界を究めるブログでした。最近はいろんな分野を幅広めに書いてます。

まじかる☆ベーカリーのパンはどれほどの確率で焼けるのか?

www.youtube.com

こちらは僕が好きでよく見ている動画です。まじかる☆ベーカリーというボードゲームで遊ぶ動画です。

このゲームは「パン」を焼き上げて得点をもらうゲームとなっており、パンにはそれぞれ焼き上げるための条件が書かれています。たとえばコッペパンは「サイコロを2つ振って合計8以上」なら焼き上げ成功となります。

しかし、動画を見ているうちにふと「あれ?確率がどれも1/2以下なのでは?」と気になってしまったのでプログラミングをして計算してみました。

続きを読む

JSでHaskellのMaybeモナドを再現してみた

Haskell的な書き心地を再現しようと試みてみました。結果、かなりいい感じに仕上がりました。

// Haskellでは
// Just 3 >>= return . (+ 3);

// JSだと
Maybe.Just(3) .bind (compose(return_, v => v+3) ); // 似てる!!

Maybeモナド

結構えらい実装になりました。

class Maybe {
    constructor(type, value) {
        this.type = type;
        this.value = value;
    }
    bind(f) {
        if (this.type == 'Nothing')
            return Maybe.Nothing();
        return f.bind(this)(this.value);
    }
    static Just(v) {
        return new Maybe('Just', v);
    }
    static Nothing(f) {
        return new Maybe('Nothing', '');
    }
}

ここまでは良いのですが、以下はかなりテクニカルな実装になりました。。

function liftM(f) {
    // liftM f m1 = do x1 <- m1; return $ f x1
    return this.bind(x1 => this.return(f(x1)));
}
function ap(m) {
    // ap f m1 m2 = do x1 <- m1; x2 <- m2; return $ f x1 x2
    return this.bind(x1 => m.bind(x2 => this.return(x1(x2))));
}
Maybe.prototype.return = Maybe.Just;

// instance Applicative Maybe where
//     pure  = return
//     (<*>) = ap
Maybe.prototype.pure = Maybe.prototype.return;
Maybe.prototype['<*>'] = ap;

// instance Functor Maybe where
//     fmap = liftM
Maybe.prototype.fmap = liftM;

まず、return関数をMaybe.prototype.returnとして組み込みました。returnをstatic関数でなくメソッドにしたのは、利用する関数側からコンストラクタの特定をするのが面倒だからです。たとえばreturnがstaticなら、ap関数のなかでthisのコンストラクタを特定して、それのreturnを呼び出す流れになります。それよりも、thisに生えているreturnをそのまま呼び出すほうが楽ですよね。

次に、apやreturn_を関数として定義しています。これらはメソッドとして利用する想定なので(m.fmap(f)のように使いたい)、アロー関数で定義するとthisを参照できなくなります。そのため、functionキーワードを用いて定義しました。久しぶりにfunctionと書いた気がします。

Maybeモナドを使ってみる

使い心地はかなりHaskellに近くなっています。

function return_(...args) {
    return this.return(...args);
}

function compose(...fs) {
    return function (v) {
        for (const f of fs.reverse()) {
            v = f.bind(this)(v);
        }
        return v;
    };
}

// Just 3 `fmap` (*3)
Maybe.Just(3) .fmap (v => v*3);

// Just (*3) <*> Just 3
Maybe.Just((v) => (v*3)) ['<*>'] (Maybe.Just(3));

// Just 3 `bind` return . (+ 3)
Maybe.Just(3) .bind (compose(return_, (v) => v*3));

結構似ていますよね!!!我ながら頑張ったと思います。

まあでも、JSがデフォルトで部分適用できなかったり、演算子を関数として使えなかったり、言語仕様の時点でかなり再現が難しいので、こんなことはしなくて良いと思いました。

HTTPieを使いこなすためのサンプル集

問題という形でまとめてみました。

パラメータ付きGET

  • httpbin.org/getにGETメソッドでリクエスト
  • name=Johnage=29というパラメータを渡す

JSON形式でデータを渡す

  • httpbin.org/postにPOSTメソッドでリクエスト
  • リクエストのヘッダにContent-Type=application/application/jsonをつける
  • nameフィールドにJohn
  • ageフィールドに29(数字)
  • hobbiesフィールドに["http", "pies"]を入れる

フォーム形式でデータを渡す

  • httpbin.org/postにPOSTメソッドでリクエスト
  • リクエストのヘッダにContent-Type=application/x-www-form-urlencodedをつける
  • nameフィールドにJohn
  • ageフィールドに29を入れる

画像をフィールドに入れる

  • httpbin.org/anythingにPOSTメソッドでリクエスト
  • リクエストのヘッダにContent-Type=application/x-www-form-urlencodedをつける
  • imageフィールドに適当な画像を添付

localhostにリクエストをする

まず、$ python -m http.serverなどでローカルにwebサーバーを建ててください。そして、建てたサーバーへアクセスしてください。

  • localhost:8000へGETメソッドでリクエスト

HTTPヘッダを編集する

  • httpbin.org/getへGETメソッドでリクエスト
  • リクエストにX-API-Token: 3というヘッダを付け加える

Digest認証してみる

  • httpbin.org/digest-auth/auth/username/passwordにGETメソッドでリクエスト
  • Digest認証する

リダイレクト途中のリクエストをすべて表示する

  • httpbin.org/redirect/2にGETメソッドでリクエスト
  • 2回リダイレクトが起こるので、追従する
  • 途中のリクエストのヘッダも表示する

AtCoderで水色になりました

水色記念に書いておきます

f:id:panda_noir:20191222232006p:plain

競プロ歴

AtCoder歴は半年…というと微妙ですが、ちゃんと取り組みだしてから半年ですね。高校生のときに蟻本で挫折しているので、競プロにはじめて触れたの自体はAtCoderができるより前です。

水色になるまでに取り組んだこと

ABCの300点問題、400点問題をだいたい埋めました。ただ、difficultyが1600以上の問題はあまり解けていないです…

あとは螺旋本に取り組んでいます。ただ、後半に差し掛かってから手が止まってしまっています。あまりコンテストで見たことのない範囲でやる気が出ないのが原因ですね…

最近実力が停滞してきている感じがするので、なんとか打破したいのですが、思考力を鍛えるという抽象的なことにどう取り組めばいいのですかね…とりあえず500点問題を埋めていったりするのが早い気がしますが。

愚痴

ここからちょっと愚痴になります。緑になってから水色になるまで停滞している期間があったのですが、その期間についてですね。

f:id:panda_noir:20191222232236p:plain

この赤で囲った部分が停滞している部分です。なんとこの期間にABCに2回しか参加できなかったのです!土曜日にバイトを入れていたのが大きな原因ではあったのですが、シフトがなくなっても日曜日にABCがズレて参加できなかったり、ABCではなく高レート帯向けのコンテストだったり、ABCと全然噛み合いませんでした。

ここまでABCと噛み合わないとさすがに嫌がらせみたいでだいぶ気が滅入りましたね…というか未だにあまり立ち直れてません。

この停滞期間にもう少しABCがあればもっと早く水色になれていたんじゃないかと思うとなんだかやるせないですね…つらい。

以上です。学生のうちになんとか水色になれてよかったです。

次の目標

まずは青になりたいです。ここ最近のコンテストを見ていると、だいたい

  • 400点まで30分前後で早とき
  • 500点が解けている

このくらいが1500〜1700パフォくらいのようなので、まずは400点までの早とき、そして500点を2回に1回は通せるくらいの実力を目指します。

「7」の倍数を表す正規表現の解説

「7の倍数」を表す正規表現 - Qiita

オートマトンから正規表現への変換方法について、この記事をもとに書きます。

オートマトンとは?

状態(計算の途中結果)をもっていて、値が入力されると現在の状態と入力値をもとに次の状態へ遷移します。入力を受けるたびに「受理状態」「非受理状態」のどちらかになります。

ちょっと分かりづらいので、例をみていきいます。

7の倍数かを判定するオートマトン

たとえば「123456789」が7で割り切れるかは、筆算を使えば調べることができます。筆算はまず1桁みて7で割り、あまりを10倍して下の桁での計算に利用します。

 0 + 1 mod 7 -> 1
10 + 2 mod 7 -> 5
50 + 3 mod 7 -> 4
40 + 4 mod 7 -> 2
20 + 5 mod 7 -> 4

ここでいう「状態」は現在のあまりです(0 -> 1 -> 5 -> 4 -> 2 -> 4と遷移しています)。入力は各桁の数字です。状態が0の場合のみ受理します。

オートマトンの状態は以下のようになっています。

入力 現在の状態 次の状態
1 0 1
2 1 5
3 5 4
4 4 2
5 2 4
6 4 4
7 4 5
8 5 2
9 2 1

最終的な状態は1(123456789 mod 7 = 1)なので、非受理状態です。

なんとなく掴めてきたところで、いよいよオートマトンから正規表現を生成していきます。

7の倍数を判定するオートマトンの全容

10進法で考えると状態の遷移パターンが多くなってしまうので、ここでは2進法で考えます。2進数でも状態は余りの種類と同じ7つ用意すればいいです。遷移は次のとおりです。

f:id:panda_noir:20191212171736j:plain
遷移図

この図の各マスは状態を表しており、辺が遷移を表します。たとえば今の状態が1のときに1が入力されたら3へ遷移することが見るだけで分かるようになっています。

状態数を減らしていく

ここから状態を減らしていき、正規表現へ持ち込みます。まず、状態6に止まるべきだった入力はそもそも受け付けない(非受理とする)ことにして、状態6を削除します。すると、3 -> 6 -> 5という遷移が3 -> 5にまとめられます。

f:id:panda_noir:20191212171822j:plain
状態6を削除したあと

このように状態数を減らしていきます。ただ、この作業、恐ろしく面倒くさくて大変なので、状態数が2になった場面まで飛ばします。

f:id:panda_noir:20191212113127j:plain
状態数を2まで減らした遷移図

辺に書かれている正規表現が大変なことになっています。

最後に状態2も削除して、正規表現に落とし込んで完了です。

2進数で7の倍数を判定する正規表現

const reg = /^(11(01*00|01*0101)*1|0|(10|11(01*00|01*0101)*01*01(1|00))((0|11)(1|00)|(10|(0|11)01)(01*00|01*0101)*01*01(1|00))*(10|(0|11)01)(01*00|01*0101)*1)+$/;
console.log('検証スタート');
for (let i = 0; i < 1e6; ++i) {
    if ((i%7==0) !== reg.test(i.toString(2))) {
        throw new Error('正規表現で判定できていない数字が見つかりました');
    }
}
console.log('検証終了');

これで完成です。106まで検証していますが、reg.test(n.toString(2))n%7 == 0の結果が同じことがわかります。

7進法で7の倍数を判定する正規表現

2進数よりも遷移表が大きくなるぶん複雑になる…と思いきや、めちゃくちゃカンタンな正規表現で書けます。

/0$/ 以上です(当たり前)。

おまけ: 0000を受理しないようにする

実は上の正規表現では0000が受理されます。これを受理しないようにしてみます。

const reg = /^((11(01*00|01*0101)*1|(10|11(01*00|01*0101)*01*01(1|00))((0|11)(1|00)|(10|(0|11)01)(01*00|01*0101)*01*01(1|00))*(10|(0|11)01)(01*00|01*0101)*1)(11(01*00|01*0101)*1|0|(10|11(01*00|01*0101)*01*01(1|00))((0|11)(1|00)|(10|(0|11)01)(01*00|01*0101)*01*01(1|00))*(10|(0|11)01)(01*00|01*0101)*1)*|0)$/;

まあほぼ同じです。