中級その2

こんにちは!このページは「コンピュータサイエンスと魔法のYコンビネータ」という記事の9ページ目です。1ページ目から読むにはこちらからどうぞ

コンピュータサイエンスと
魔法のYコンビネータ

中級その3: 天才サヤちゃん

スライド 1 / 12

サヤちゃん現る

ラムダ村の村人たちは、前回の問題に四苦八苦していました。

どのような法則に基づいて に料理を入れると…
13
2
23
1
1を足す効果 がある弁当箱になる?
13
2
23
1

だめだ…全然分からない!

これを解かないと計算箱を返してもらえないのに…どうしよう…

その時です。ラムダ村に暮らす少女のサヤちゃん が、問題に苦戦している村人たちに話しかけてきました。

ラムダ村に暮らす少女のサヤちゃん

ねえねえ、みんな何してるの?

おお、サヤちゃんか。実は、にっくき悪魔 に計算箱を奪われてしまったんだ。

奴が出題した問題を解かないと計算箱を返してもらえないんだけど、俺らには難しくて解けないんだよ。

ふーん、どんな問題なの?

じゃあ、手短に説明するね。

以下の弁当箱の に、どのような法則に基づいて料理を入れると…

以下の弁当箱の に、
どのような法則に基づいて料理を入れると…
13
2
23
1

1を足す効果 」がある弁当箱になるか、という問題なんだ。

すなわち、 を計算できるようにしないといけないんだ。

に変換できる弁当箱と合体させて
実行してから 計算箱に変換 した時、
1
に変換できる弁当箱
1
13
2
23
1
結果が になる?
(すなわち「1を足す効果 」がある?)

ふーん、じゃあサヤも解くのを手伝うよ!

手伝ってくれるのはありがたいけど、この問題はママゴトじゃないんだよ。俺らがどれだけ頑張っても分からなかったんだ。

他のページをお探しですか?

中級その2·
·中級その4
スライド 2 / 12

サヤちゃんの弁当箱

サヤちゃんは少し考えた後、 に料理を入れてみました。

ねえねえ、サヤも に料理を入れてみたんだけど、見てくれる?

サヤちゃんの弁当箱
13
2
23
1

ふむふむ…どうせ上手くいかないと思うけど、試してみるか。

前回もやったように、 に変換できる弁当箱と合体させて、

右下には がついた が「1
→ 計算箱に変換すると になる
1
1

実行してから 計算箱に変換 して、結果が になるか確かめてみよう。どうせムリだろうけど!

に変換できる弁当箱と、
サヤちゃんの弁当箱を合体させ…
1
1
1
1
13
2
23
1
実行してから 計算箱に変換
して、結果が になれば成功
それ以外なら失敗

じゃあ、実行 してみよう!

スライド 3 / 12

実行 してみると…

それでは、 サヤちゃんの弁当箱を実行してみましょう!

まず、1 のペアが左右ふたつ以上あるので、一番左の 1 のペアからはじめます。早送り を押してみてください一回ずつ進める場合は、 を押してください。

1 のペアが左右ふたつ以上ある場合は、
一番左の 1 のペアからはじめる
1
1
1
1
13
2
23
1

続いて、また 1 のペアからはじめたいのですが、1 のペアの一番下の段にひとつの料理(サンドイッチ )しかないので不可能です。

というわけで、次は 2 のペアからはじめます。

下段にひとつの料理しかなく、
1 のペアからはじめられない場合、
2 のペアからはじめる
13
2
23
1
1
1

次も前回と同じく、2 のペアからはじめます。

下段にひとつの料理しかなく、
1 のペアからはじめられない場合、
2 のペアからはじめる
12
2
1
1
1

つまり、最終的に以下のようになりました!

実行 した結果
12
2
1

こ、これはもしや…?

スライド 4 / 12

に変換できる

この弁当箱は、 に変換できます!

右下には がついた が「2
→ 計算箱に変換すると になる
12
2
1

ということは、サヤちゃんの弁当箱は…

に変換できる弁当箱と合体させ、実行してから 計算箱に変換 すると、結果が になるということですね。

に変換できる弁当箱と、
サヤちゃんの弁当箱を合体させ…
1
1
1
1
13
2
23
1
実行してから 計算箱に変換
すると、結果が になる

つまり、 が計算できたので、成功です!

やったー!

そんなバカな…!俺らがどれだけ頭をひねっても分からなかったのに、サヤちゃんにいとも簡単に解かれるなんて!

スライド 5 / 12

はできる?

いや、まだ分からんぞ。 ができるからといって、他の数字に対しても1を足す効果 があるとは限らない。

たとえば、 も計算できるのかどうか確かめてみないと。

これも計算できる?

じゃあ、 に変換できる弁当箱と、

右下には がついた が「2
→ 計算箱に変換すると になる
12
2
1

サヤが考えた弁当箱を合体させてみるね!

サヤちゃんの弁当箱
13
2
23
1

合体したものを実行してから 計算箱に変換 して、結果が になればいいんだよね。

に変換できる弁当箱と、
サヤちゃんの弁当箱を合体させ…
1
12
2
1
1
13
2
23
1
実行してから 計算箱に変換
して、結果が になれば成功
それ以外なら失敗

まずは実行してみるね。早送り を押してみて

今回は、最後まで止まらずに早送りします!

1
12
2
1
1
13
2
23
1

結果はこうなったよ!

実行 した結果
123
3
2
1

この弁当箱は、 に変換できます!

右下には がついた が「3
→ 計算箱に変換すると になる
123
3
2
1

つまり、 が計算できたので、またしても成功です!

わーい、わーい!

す、すごい…!

スライド 6 / 12

1を足す効果 がある法則

ではここで正解を言いましょう。サヤちゃんが考えた弁当箱は、1を足す効果 がある弁当箱です。

だから、サヤちゃんの答えが正解です!おめでとうございます!

サヤちゃんが考えた弁当箱には
1を足す効果 がある
13
2
23
1

わーい、ミニオンさんありがとう!

さらに言うと、サヤちゃんが考えた弁当箱以外にも、以下の法則に当てはまる弁当箱であれば、 どれでも1を足す効果 があります。

この法則に当てはまる弁当箱であれば、
1を足す効果 がある
13
2
23
1

サヤが考えた弁当箱の場合、

  • お寿司
  • サンドイッチ
  • ハンバーガー

ということかな?

お寿司
サンドイッチ
ハンバーガー
13
2
23
1

その通りです。サヤちゃんが考えた弁当箱は、ちゃんとこの法則に当てはまっているのです。

この法則に当てはまる弁当箱であれば、
1を足す効果 がある
13
2
23
1
スライド 7 / 12

同じ法則の、他の弁当箱も試してみる

じゃあ、たとえばこの弁当箱でも、同じ法則に沿っているから、1を足す効果 があるってこと?

同じ法則で料理を入れてみた。
1を足す効果 はあるか?
13
2
23
1

には サラダ には ホットドッグ には カレー を当てはめてみたよ。

はい、1を足す効果 はありますよ。

試しに、 に変換できるこちらの弁当箱と合体させて実行 してみましょう。

右下には がついた が「3
→ 計算箱に変換すると になる
123
3
2
1

実行したとき、結果が に変換できる弁当箱になれば、 を計算できたので成功になります。

早送り を押してみてください最後までスキップすることも可能です。

1
123
3
2
1
1
13
2
23
1

結果、 に変換できる弁当箱が残りました!

右下には がついた が「4
→ 計算箱に変換すると になる
1234
4
3
2
1

つまり、 を計算できたというわけです。

なるほど、やっぱりこちらの弁当箱にも1を足す効果 があるということか。

サヤちゃんの弁当箱と同じく、こちらの
弁当箱にも1を足す効果 がある
13
2
23
1
スライド 8 / 12

立ち止まって振り返ろう

俺らふだん頭を使っていないから、情報量が多すぎて疲れてしまった…

ちょっとひと休みしてもらえないか?

いいですよ!

ちなみに現時点で、中級編も半分を終えました。つまり、本稿の折り返し地点を越えたということです。残るは中級編の残り半分と、上級編のみです。

いい機会なので、少し立ち止まって振り返ってみましょう。

まずこちらをご覧ください。これは、 を計算できる計算箱ですね。

を計算できる計算箱。
実行すると になる

これまで学んだことを一言でまとめると、上の計算箱にあるような「1を足す機能 」は、弁当箱で「再現」できる、ということです。

計算箱の「1を足す機能 」は、
弁当箱で「再現」することができる

再現」できる、とはどういうことでしょうか?先ほどの計算箱の例で説明しますね。

これを弁当箱で再現します

ステップ1: まず、計算箱の の代わりに、 に変換できる弁当箱を用意します。

これの代わりに…
に変換できる弁当箱を用意
1
1

ステップ2: 次に、計算箱の の代わりに、1を足す効果 がある弁当箱を用意します。

これの代わりに…
1を足す効果 がある弁当箱を用意
( サヤちゃんが考えた弁当箱です)
13
2
23
1

ステップ3: このふたつを合体させた弁当箱は、先ほども説明した通り、実行してから 計算箱に変換 すると になりますね。

に変換できる弁当箱と
1を足す効果 がある弁当箱を合体
1
1
1
1
13
2
23
1