こちらは僕が好きでよく見ている動画です。まじかる☆ベーカリーというボードゲームで遊ぶ動画です。
このゲームは「パン」を焼き上げて得点をもらうゲームとなっており、パンにはそれぞれ焼き上げるための条件が書かれています。たとえばコッペパンは「サイコロを2つ振って合計8以上」なら焼き上げ成功となります。
しかし、動画を見ているうちにふと「あれ?確率がどれも1/2以下なのでは?」と気になってしまったのでプログラミングをして計算してみました。
続きを読むこちらは僕が好きでよく見ている動画です。まじかる☆ベーカリーというボードゲームで遊ぶ動画です。
このゲームは「パン」を焼き上げて得点をもらうゲームとなっており、パンにはそれぞれ焼き上げるための条件が書かれています。たとえばコッペパンは「サイコロを2つ振って合計8以上」なら焼き上げ成功となります。
しかし、動画を見ているうちにふと「あれ?確率がどれも1/2以下なのでは?」と気になってしまったのでプログラミングをして計算してみました。
続きを読むHaskell的な書き心地を再現しようと試みてみました。結果、かなりいい感じに仕上がりました。
// Haskellでは // Just 3 >>= return . (+ 3); // JSだと Maybe.Just(3) .bind (compose(return_, v => v+3) ); // 似てる!!
結構えらい実装になりました。
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と書いた気がします。
使い心地はかなり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がデフォルトで部分適用できなかったり、演算子を関数として使えなかったり、言語仕様の時点でかなり再現が難しいので、こんなことはしなくて良いと思いました。
問題という形でまとめてみました。
httpbin.org/get
にGETメソッドでリクエストname=John
、age=29
というパラメータを渡す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
フィールドに適当な画像を添付まず、$ python -m http.server
などでローカルにwebサーバーを建ててください。そして、建てたサーバーへアクセスしてください。
localhost:8000
へGETメソッドでリクエストhttpbin.org/get
へGETメソッドでリクエストX-API-Token: 3
というヘッダを付け加えるhttpbin.org/digest-auth/auth/username/password
にGETメソッドでリクエストhttpbin.org/redirect/2
にGETメソッドでリクエスト水色記念に書いておきます
AtCoder歴は半年…というと微妙ですが、ちゃんと取り組みだしてから半年ですね。高校生のときに蟻本で挫折しているので、競プロにはじめて触れたの自体はAtCoderができるより前です。
ABCの300点問題、400点問題をだいたい埋めました。ただ、difficultyが1600以上の問題はあまり解けていないです…
あとは螺旋本に取り組んでいます。ただ、後半に差し掛かってから手が止まってしまっています。あまりコンテストで見たことのない範囲でやる気が出ないのが原因ですね…
最近実力が停滞してきている感じがするので、なんとか打破したいのですが、思考力を鍛えるという抽象的なことにどう取り組めばいいのですかね…とりあえず500点問題を埋めていったりするのが早い気がしますが。
ここからちょっと愚痴になります。緑になってから水色になるまで停滞している期間があったのですが、その期間についてですね。
この赤で囲った部分が停滞している部分です。なんとこの期間にABCに2回しか参加できなかったのです!土曜日にバイトを入れていたのが大きな原因ではあったのですが、シフトがなくなっても日曜日にABCがズレて参加できなかったり、ABCではなく高レート帯向けのコンテストだったり、ABCと全然噛み合いませんでした。
ここまでABCと噛み合わないとさすがに嫌がらせみたいでだいぶ気が滅入りましたね…というか未だにあまり立ち直れてません。
この停滞期間にもう少しABCがあればもっと早く水色になれていたんじゃないかと思うとなんだかやるせないですね…つらい。
以上です。学生のうちになんとか水色になれてよかったです。
まずは青になりたいです。ここ最近のコンテストを見ていると、だいたい
このくらいが1500〜1700パフォくらいのようなので、まずは400点までの早とき、そして500点を2回に1回は通せるくらいの実力を目指します。
オートマトンから正規表現への変換方法について、「7の倍数」を表す正規表現 - Qiitaをもとに書きます。
状態(計算の途中結果)をもっていて、値が入力されると現在の状態と入力値をもとに次の状態へ遷移します。入力を受けるたびに「受理状態」「非受理状態」のどちらかになります。
ちょっと分かりづらいので、例をみていきいます。
たとえば「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)なので、非受理状態です。
なんとなく掴めてきたところで、いよいよオートマトンから正規表現を生成していきます。
10進法で考えると状態の遷移パターンが多くなってしまうので、ここでは2進法で考えます。2進数でも状態は余りの種類と同じ7つ用意すればいいです。遷移は次のとおりです。
この図の各マスは状態を表しており、辺が遷移を表します。たとえば今の状態が1のときに1が入力されたら3へ遷移することが見るだけで分かるようになっています。
ここから状態を減らしていき、正規表現へ持ち込みます。まず、状態6に止まるべきだった入力はそもそも受け付けない(非受理とする)ことにして、状態6を削除します。すると、3 -> 6 -> 5
という遷移が3 -> 5
にまとめられます。
このように状態数を減らしていきます。ただ、この作業、恐ろしく面倒くさくて大変なので、状態数が2になった場面まで飛ばします。
辺に書かれている正規表現が大変なことになっています。
最後に状態2も削除して、正規表現に落とし込んで完了です。
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
の結果が同じことがわかります。
2進数よりも遷移表が大きくなるぶん複雑になる…と思いきや、めちゃくちゃカンタンな正規表現で書けます。
/0$/
以上です(当たり前)。
実は上の正規表現では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)$/;
まあほぼ同じです。