2017-11-16

ガチャ、オートマトン、オイラー積分 - Analytic Combinatoricsが面白い

Analytic Combinatoricsがめちゃくちゃ面白い。場合の数という離散的なものを数えるのに、連続的世界から生まれた解析学の知見を用いる分野だ。階乗をガンマ関数で表示するだとかいうレベルではなく、マクローリン展開の係数を調べることで場合の数を知るようなことをしている。

オートマトン

ハマった発端は「オートマトン理論再考」（新屋, 2017 *1 ）というサーベイ論文。有限状態オートマトンを定めると、そのグラフの形から直接「 $a_i=$ 出力文字列のうち $i$ 文字のもの」の $a_i$ 係数とする母関数が構成でき、それをマクローリン展開すると、 $i$ 文字となる出力の場合の数が直ちにわかるという内容を紹介していた。この結果は文脈自由言語にも拡張でき、生成規則から母関数が機械的に計算でき、その展開係数が $i$ 文字の場合の数になっているという。場合の数を数えるのになんとマクローリン展開！一体どういうことなのか。

例えば、[1]中では「正しく対応する括弧の文字列」の集合で構成されるDyck言語

$\displaystyle \xrightarrow{R} : S = \varepsilon \mid (S)S$

を取り上げていた。この規則は、例えば

$\displaystyle \varepsilon,\ ( ) ,\ ( ( ) ) ,\ ( ) ( ) ,\ ( ( ( ) ) ) ,\ ( ( ) ( ) ) ,\ ( ( ) ) ( ) ,\ ( ) ( ( ) ) ,\ ( ) ( ) ( ) ,\ \cdots$

のような文字列を生成する（ $\varepsilon$ は空文字列。また、生成規則中の括弧は文字を表すことに注意）。

さて、上記を見ると、Dyck言語では2文字の場合は1通り、4文字の場合は2通り、6文字の場合は5通り存在する。では、一般の文字数では何通りあるのか？普通、この問に答えるには、漸化式や場合分けなどが沢山必要だろうというイメージがあった。しかし、なんと文脈自由言語の生成規則を機械的に母関数化する操作 $\Xi$ を用いて、

$\displaystyle \Xi (\xrightarrow{R}): S = 1 + zSzS$

となり、母関数 $S$ に関する方程式

${\displaystyle z^{2} S - S + 1 = 0, \, \, i.e. \, \, S = \frac{1 \pm \sqrt{1-4z^{2}}}{2z^{2}} }$

がわかり、さらにそれをマクローリン展開すると

$\displaystyle S = \sum_{i=0}^\infty C_{i}z^{2i}$

と、カタラン数 *2 $C_{i}$ で書けることから、Dyck言語のうち $2i$ 文字の場合は $C_{i}$ 通りであることがわかるのである。

これを初めて見た時の感想は「あ・・・ありのまま今起こったことを話すぜ・・・！！」だった。あの場合の数の細かい操作が、全て解析的操作に押し込められていた。離散的なものを解析するのに、解析学の知見を使う系の物が好きな上に、複雑な対象が代数的に、かつ機械的に処理できるようなものが昔からかなり好きなのだけど、これはもう驚きの連続で見ているだけで幸せになれた。

一番感動したのは、Kleene Starが母関数の無限等比級数を取る操作に等しいことだ。 $a^{*}$ という正規表現にマッチする文字列において、 $i$ 文字のものは常に1通りだ。したがって、 $a^{*}$ の母関数は

$\displaystyle \Xi[a^*] = 1 + 1 \cdot z + 1 \cdot z^{2} + \cdots = \frac 1 {1-z}$

となることがわかる。

しかし、これだけでは終わらない。なんとこれが一般の場合に拡張できるのである！ $(a|ba)^{*}$ という正規表現があったとき（ここではDyck言語における括弧とは意味が異なり、括弧は文字としてカウントしていないことに注意）、なんと

$\displaystyle \Xi[(a|ba)^{*}] = \frac{1}{1 - \Xi[(a|ba)]} = \frac{1}{1 - (z+z^{2})}$

のようになるのだ。このマクローリン展開の一般項は、なんとフィボナッチ数列になることが、[1]の中で触れられている。つまり、正規表現 $(a|ba)^*$ にマッチする文字のうち、 $i$ 文字のものは $i$ 番目のフィボナッチ数通りあるのだ。

また、[1]中では他にも正規言語 $\iff$ 母関数が有理関数、文脈自由言語 $\iff$ 母関数が代数関数となることから、言語の母関数の極が無限にあればそれは文脈自由言語や正規言語ではないことがわかるなどの結果が紹介されていた。これは、正規表現でマッチしうる場合の数の性質と、文脈自由言語の性質が、解析学的には有理関数と代数関数の差として表現できるという、もうこれ哲学じゃん！！という内容だった。他にも、まだ読めていないがいわゆる無限の猿定理のフォーマルな証明などを紹介している。

ガチャの数

続いて見かけたのはアイテムコンプに必要なガチャの回数の期待値を厳密に計算する方法 (sxarp, 2017, ブログ記事)。ここではCoupon Collector's Problem を一般化し、異なる確率で得られるクーポンを集めるまでの回数の期待値を、マルコフ連鎖を用いて計算している。

この問題のモデルは重み付き有限状態オートマトンで書けるので、母関数法を用いてもっと簡単に解けないかと論文を探していたら、Math Overflowの質問から Flajolet, et al., 1992 *3 を見つけた。そこには正規言語の話など見慣れた話題が載っていた。この論文の定理4.1が、問題の期待値を求める式を与えている。

更に、この定理の元となる定理3.1を見ると、どうもKlamkin and Newman, 1967 *4 の Extensions of the Birthday Surprise という論文が出典らしい。

この論文では、所望の期待値を求めるために、なんと道具がガンマ関数の定義式であるオイラー積分にまで発展しているのだ！！

$\displaystyle \Gamma(x) = \int_0^\infty t^{z-1}e^{-t}dt$

これが、階乗を連続的に扱うためにガンマ関数で表示する、とかいう生半可な使い方ではないのだ。これをどう使うかというと、ある母関数を考えるのに、それに $\frac{t^{N}}{N!}$ をかけた補助的な関数を考え、色々いじったあとに、 $\frac{t^{N}}{N!}$ を消去するのに $e^{-t}$ 倍してオイラー積分を行うのだ。「え、ここでそれするの！？」と、久々に感動した。最初多項式の話をしていたと思ったら、みるみるうちに話が解析的になっていき、最後にはガンマ関数が出てきて度肝を抜かれた。

この感動は是非元論文を読んで体験していただきたい。4ページで、アイデアもわかりやすいので、非常に読みやすい。

Analytic Combinatoricsスライド

もっとKlamkin and Newmanのような結果を読みたい！この分野は、どうもAnalytic Combinatoricsという名前がついているらしい。そこで、Analytic Combinatoricsで検索すると、Robert Sedgewick のFrom Analysis of Algorithms to Analytic Combinatorics - a journey with Philippe Flajolet *5 という発表スライドを見つけた。スライドを見ると "This talk is dedicated to the memory of Philippe Flajolet" とあり、更に "Philippe Flajolet 1948-2011" とあった。どこかで見覚えのある名前だなと思ったら、なんと [3] の著者だった！！一気に親しみを覚えると同時に少し寂しくなってしまった。どんな方だったのだろうか。

このスライドでは、PSET, MSETなどの生成規則に関する演算と、その母関数表示上での演算の対応規則が書かれており、 $N$ ノードある二分木の数え上げなどが行われていた。Kleene Starが $1/(1-z)$ と等価、を更に推し進めたような規則が沢山書いてあるのだ。

中でも心を打たれたのが、 "If you can specify it, you can analyze it" という格言だった。これは、正に「オートマトン理論再考」[1]を読んだ時の感動の源泉そのものだった。オートマトンのグラフ構造や文脈自由言語の生成規則からほぼ直接的に母関数を構成でき、更にその展開係数そのものが場合の数だという、この直接的な関係。機械的・機能的美しさと神秘を兼ね備えた感動をそのまま言い表していて、スライドの著者にとても同意した。

更に、このスライドでは Donald Knuth の The Art of Computer Programming など、Knuth に関して重点的に触れていたり、世界初の機械式コンピュータ "Difference Engine" をデザインした「コンピュータの父」Charles Babbageの言葉を引用していた：

"As soon as an Analytic Engine exists, it will necessarily guide the future course of the science. Whenever any result is sought by its aid, the question will arise - By what course of calculation can these results be arrived at by the machine in the shortest time?" - Charles Babbage, as quoted by R. Sedgewick [4]

なぜKnuthやBabbageのこの言葉を引用していたかというと、スライドによるとAnalytic Combinatoricsによる数え上げによってアルゴリズムの計算クラスを証明したりするらしい。このような美しい理論に実用的な使い道があるとますます嬉しくなる。

Analytic Combinatorics本

そして更に検索していると、Flajolet and Sedgewickの本 Analytic Combinatoricsを発見した。こちらは、826ページにも亘るにもかかわらずオンラインで無料で全ページ公開されている。

p.2 によると、このようなAnalytic Combinatoricsの流れは、1881年にDésiré André というフランスの数学者が、隣接する位の数字の大小が毎度交代する整数の場合の数が、 $\tan x$ のマクローリン展開の係数になっていることを発見したことから始まったという。

更にこの本のp.35では、凸多角形の三角形分割の場合の数がカタラン数で与えられることの直感的説明を紹介している。Dyck言語もカタラン数で与えられるため、三角形分割もDyck言語と同じような規則が存在するはずであると思ってこの本を読む前までしばらく悩んでいたのだが、このような複雑な構造をここまで直感的に説明できるものなのかと思った。

どんどん読み進めていくと、そもそもこの分野を調べるきっかけとなったオートマトンの話などが載っており、目が幸せになりつつ、現在この本を読み進めている途中である。

Babbageから現代まで

先程出てきたBabbageが設計したDifference EngineのレプリカはMountain ViewのComputer History Museumに展示 *6 されている。Charles Babbageは、Wikipediaによると1791-1871年を生きており、Analytic Combinatoricsの幕開けである1881年は彼の没後となる。彼のDifference Engineは、実はBabbageの生前は実装することができず、2002年に初めて実装されたとある。（つまり、Difference Engineはバグが無かったことが、100年以上越しに示されたことになる！）以前博物館を訪れた際そのDifference Engineのレプリカの一つを見たが、改めて、そんな「コンピュータの父」の「アルゴリズムを最小時間で実行することが興味の対象となるだろう」という予想、そしてDifference Engineの黎明期的雰囲気から、Analytic Combinatoricsという大変美しい理論によってアルゴリズムの計算量が測られる現代までの、風が吹くような勢いの変遷を見て、計算機科学に待ち受けるまだ見ぬ面白さにますます大きな期待を僕は寄せている。

*1:https://www.jstage.jst.go.jp/article/jssst/34/3/34_3_3/_article/-char/ja/

*2:https://ja.wikipedia.org/wiki/%E3%82%AB%E3%82%BF%E3%83%A9%E3%83%B3%E6%95%B0

*3:Flajolet, et al. (1992), Birthday paradox,coupon collectors,caching algorithms and self-organizing search.

*4:http://www.sciencedirect.com/science/article/pii/S0021980067800759

*5:https://www.cs.princeton.edu/~rs/talks/AofA2AC.pdf

*6:http://www.computerhistory.org/babbage/

2024-04-10

4x4x4ルービックキューブの攻略法

本記事では4x4x4ルービックキューブをなるべく少ない知識で揃える方法をまとめる。

筆者は2ヶ月ほど前に3x3x3ルービックキューブの解き方を覚えた。そこから今日新たに4x4x4ルービックキューブの解き方を覚えたので、筆者の覚えた4x4x4ルービックキューブの解き方をまとめる。

前提知識

3x3x3 ルービックキューブの解き方

4x4x4ルービックキューブ（RC）は、まず4x4x4 RCを並び替えて自分で 3x3x3 RCを作り、それを3x3x3の方法を使って揃えることで解く。そのため、途中で3x3x3 RCの解き方の知識が必要となる。

筆者は新・高橋メソッド https://www.youtube.com/watch?v=Z8Qc5Nq90bU を覚えた。この動画では使う手順が最小限になっている上に手順の覚え方なども解説されており、筆者にとっては覚えやすかった。

3x3x3 RCを解ける方法なら何を使っても良い。ただし、上記以外の方法を用いると、もしかすると解いている最中に遭遇する例外（パリティが異なるとわかる配置）としてこの記事に書いてあるもの以外が出現する可能性がある。

3x3x3 ルービックキューブの配色

4x4x4 RCでは最初に自分で3x3x3 RCを作らなければいけないが、その時3x3x3 RCの配色（つまり展開図）を知っていなければならない。この展開図を間違えたまま進めても、3x3x3 RCとして解けない配置が出てきてしまう。

上記が3x3x3 RCの展開図である。自分が覚えた時の覚え方は次の通り：

似た色同士が対面している。白と黄、赤とオレンジ、青と緑。
上記の展開図で、対面している白と黄を上下に並べ、間にオレンジを入れる。すると、左側に来るのは緑となる。

記法

本記事で用いる回転の記法は下記の通り。

3x3x3と同様のもの
- $RLFBUD$ : 一番外側の1層を自分に向けた状態で時計回りに回す。
- : キューブ全体を、その軸の伸びる方向を自分に向けた状態で時計回りに回す。
  - 本稿では $x$ のみ登場する。 $x$ は、キューブ全体を $F$ の面が $U$ に置き換わるように奥側へ回転させる動作を表す。これは、 $x$ 軸に沿って時計回りに90度回転している動作に相当する。
- 逆回転: 逆向きに回す動きについては $R'$ のように $'$ を使って表す。 $R'$ は $R$ の逆回転となる。
- 複数回転: 同じ動作を2回行う場合は $R2$ のように後ろに数字を書いて表す。
4x4x4特有のもの
- $rlfbud$ : 一番外側層とその1つ下の層の合計2層を自分に向けた状態で時計回りに回す。（大きな2x2x2 RCのような回し方となる。）
- : 一番外側の層の1つ下の層のみの1層を自分に向けた状態で時計回りに回す。
  - $R_2$ を2回回す動きは $R_22$ と書く。

3x3x3 RCにおける記号の一例が https://tribox.com/3x3x3/solution/notation/ などに載っている。ただし、 $RLFBUD, xyz$ 以外の記号や表記法が本稿とは異なっているので注意。

知っていると役立つ知識

パリティ

3x3x3 RCをバラバラに分解して再び組み合わせると、ちゃんと解けるルービックキューブになる確率は実はわずか1/12となっている（https://math.stackexchange.com/questions/2269894）。それ以外の場合では、正規の方法を使っても決して解けないRCが出てきてしまう。

このことから、分解して実現可能な配置も含めた時のルービックキューブの配置は12個の「世界」に分かれており、ルービックキューブの基本動作 $RLFBUD$ だけを行っている限り、同じ世界の中のみを移動でき、異なる世界の間を移動できないことがわかる。異なる世界の間を移動するには、「ルービックキューブを分解する」という特別な動作が必要となる。

さて、4x4x4 RCを解く際には、まずキューブを寄せ集めてセンターキューブとエッジキューブを作ることで自分で3x3x3 RCを作ってからそれを解くという段階を踏む。この操作は3x3x3 RCにはない操作を使っているという意味で3x3x3 RCを分解するのと同じようなことを行っている。そのため、解けない3x3x3 RCが作られることがある。本稿では、4x4x4 RCを作っている最中に解けない3x3x3 RCが出てきた場合、「解けない3x3x3 RCから解ける3x3x3 RCへ移動する」操作を行うことで解ける配置に直すという方法を取る。

このように、パズルの配置を「そのパズルで正規に許されている動作のみを使って到達可能な状態」に基づいていくつかの行き来可能な「世界」に分類したとき、解くことができる世界（つまり、正解の状態を含む世界）とは異なる状態にいると、許された動作だけを行っている限りはその世界から脱出することはできない。そのため、「解けない世界から、解ける世界へ移動する」必要がある。このように解けない世界から解ける世界へい移動することを「パリティ (parity) を解消する」と呼ぶ。

本稿では、このパリティを解消するのに使うアルゴリズムが登場する。そのアルゴリズムを使うと、ぱっと見では何か変化が起きたようには見えないが、「解けない世界」から「解ける世界」への移行ができており、アルゴリズムの実行後、通常の3x3x3 RCの解き方を続行することでRCが解けるようになっている。

このような方法は速解きをする場合は適さないが、必要最小限の知識を用いて解くことを目指した場合は有効である。速解きをする場合は、配置に異変を発見しパリティの解消の必要性があると気づいた時点で、その異変のみを狙い撃ちして元に戻すアルゴリズムを覚えるのが良い。しかし解くことだけを目標にした場合、パリティの解消のみを行い、残りは通常の解き方を用いる方策を採用することで、覚えるべきアルゴリズムの数を減らすことができる。

パリティの考え方はルービックキューブ特有のものではなく、色々なパズルにおいても用いられている。パリティの詳細やその語源などについては、本稿末のおまけを参照。

CommutatorとConjugate

$ABA'B'$ の形のアルゴリズムをcommutator、 $ABA'$ の形のアルゴリズムをconjugateと呼ぶ。ここで $A'$ は $A$ を打ち消すような動作を表す。例えば、新高橋メソッドにおける「右動作」は $RUR'U'$ と書けるが、これはcommutatorの形をしている。本稿ではconjugateの形をしたアルゴリズムが登場する。

登場するアルゴリズムのまとめ

下記のアルゴリズムが登場する：

中心2x2マスを揃える時の基本動作: $R_2 \cdot U \cdot R_2'$
辺を揃える時の基本動作: $R_2' \cdot U' R U \cdot R_2$
最後の1辺のパーツの入れ替え: $d \cdot RF' \cdot U \cdot R'F \cdot d'$
1本のdedgeを反転する（OLL parityの解消）: $rU2 \cdot x \cdot rU2 \cdot (rU2 \cdot r'U2 \cdot lU2 \cdot r'U2 \cdot rU2 ) \cdot r'U2 \cdot r'$
対面するdedge同士を反転する（PLL parityの解消）: $(R_2 2 \cdot U2) \cdot (R_2 2 \cdot u2) \cdot (R_2 2 \cdot U_2 2)$

以下に詳細を記す。

中心2x2マスを揃える時の基本動作

$\displaystyle R_2 \cdot U \cdot R_2'$

使い方：FからUへ1マス移動する際に使う。 FとU以外の面の中心2x2マスが不変に保たれる（一切変わらない）ことがポイント。（エッジキューブは入れ替わる。）この性質を使って、中心2x2マスを作っていく時に注目している面（FとU）のみを書き換えながら中心2x2マスを作っていくことができる。

覚え方：

Conjugateになっている。
最初の $R_2$ で上げた2マスを $U$ で軌道上から退避してから、conjugateの $R_2'$ で戻す。

変種：上記を左右反転した動作も多用する。

辺を揃える時の基本動作

参考文献： https://macozy.com/rubik/4rc/step1_4.html

上記の配置のとき、下記で辺を揃える：

$\displaystyle R_2' \cdot U' R U \cdot R_2$

作用：図のa,bのキューブのペア同士が揃う。中心2x2マスは不変に保たれるのがポイント。

使い方：上側1層のみの回転（ $RLFBUD$ ）と中心2層のみの回転（ $R_2 L_2$ など）も中心2x2マスを不変に保ち、辺だけを移動する。これらの操作を使って上図の状態に揃えた後、上記を使って辺を揃える。

覚え方：

https://macozy.com/rubik/4rc/step1_4.html に非常に覚えやすい方法が載っている。それを改変したものが下記である：

aを揃える。
aをb側に移動する。
bの面を奥へ移動する。
上面を元に戻す（2の逆の操作を行う）。
中心面を見て、ずれている面を見つける。その面を戻すような動作（つまり、1.の逆の操作）を行う。

変種：

https://macozy.com/rubik/4rc/step1_4.html にて、bの位置が反対の辺にある場合が紹介されている。この場合も覚え方は上記と同じである。

最後の1辺のパーツの入れ替え

上記の配置のとき、下記で辺を揃える：

$\displaystyle d \cdot RF' \cdot U \cdot R'F \cdot d'$

作用：図のa,bのキューブのペア同士が揃い、他のキューブを全て不変に保つ。

覚え方：

舞台になぞらえる。観客席から舞台を見ている所を想像する。

$d$ : ステージを回転させる。
$R$ : 上手（かみて）から演者が入場する。
$F'$ : 観客から拍手が起こる。
$U$ : 天井が回転する。 5: $R'$ : 再び上手（かみて）から演者が入場する。 6: $F$ : 観客から拍手が起こる。 7: $d'$ : ステージを戻す。

また、間の $RF' \cdot U \cdot R'F$ の部分はconjugateになっていないのがポイントである。 $d \cdots d'$ に部分はconjugateになっているが、その間はconjugateになっていないというように覚える。

1本のdedgeを反転する（OLL parityの解消）

Dedgeとは、2つ組のエッジキューブで作られた、3x3x3 RCのエッジキューブに対応する2つ組のキューブのことである。1本のdedgeを反転するには、そのdedgeをFとUの間に持っていき、下記を行う：

$\displaystyle rU2 \cdot x \cdot rU2 \cdot (rU2 \cdot r'U2 \cdot lU2 \cdot r'U2 \cdot rU2 ) \cdot r'U2 \cdot r'$

このアルゴリズムが一番難しい。一見長くて覚えづらいように見えるが、実はある程度規則的な形になっている。

使い方：3x3x3 RCを解くフェーズの途中で使う。新高橋メソッドでは、「時計の3時、6時、9時」の動作を行っている際の異変の有無で必要性に気づくことができる。通常の3x3x3 RCでは、エッジキューブが1個のみ反転した状態は決して作ることができない（http://www.rubiksplace.com/cubes/4x4/）。したがって、「時計の3時、6時、9時」の状態から1辺のみが欠けていることに気づいた場合、その時点ですぐに上記のアルゴリズムを適用して辺を戻すことで、3x3x3 RCの解き方を続行できる。

覚え方：

全部で8回の $\alpha U2$ がある。最後だけ $U2$ が無く $r'$ 単体となっている。
最初の $rU2 \cdot x \cdot rU2$ はconjugateもどきになっている。
間の $rU2 \cdot r'U2 \cdot lU2 \cdot r'U2 \cdot rU2$ はABCBAという山のような形になっている。間の $l$ と $r'$ はどちらも自分側への回転で、これらが間で呼応するように出現する。

対面するdedge同士を反転する（PLL parityの解消）

$\displaystyle (R_2 2 \cdot U2) \cdot (R_2 2 \cdot u2) \cdot (R_2 2 \cdot U_2 2)$

使い方：下記の場合に使える：

対面しているdedge同士を入れ替えたい場合
- この場合、対面している辺のうちのどちらか1方を $F, U$ 面の交線に配置して上記を行う。
新高橋メソッドを完走した後、2つのコーナーキューブのみが入れ替わっており、他は全て揃っている場合がある。
- この場合、PLL parityが不正になっているので、parityを解消する必要がある。
- この場合、入れ替えたい2つのコーナーキューブを $F, U$ 面の交線上に配置して上記を行うとPLL parityが解消され、解ける3x3x3の配置になる。最後の1面のみが揃っていない状態になるはずなので、その時点から新高橋メソッドを使ってキューブを揃える。

覚え方：

全て $\alpha 2$ の形の回転になっている。そのため、向き（時計回りか反時計回りか）を覚えなくて良い。（どっち回りだったとしても2回適用した結果は変わらないため）
全ての形になっている。
- 入れ替えたいdedge同士を貫くような中間の層 $R_2 2$ を最初に回転させてから、上の面を回転させている。
$\alpha$ の部分が $U \to u \to U_2$ のように、「上・全部・下」のように上から下へ移動している。

解き方

参考文献：

解き方：

I: 3x3x3 RCを作る
- ステップ1: 白の中心2x2を揃える
  - 「中心2x2マスを揃える時の基本動作」を使う。
- ステップ2: 白の対面に黄の中心2x2を揃える
  - 「中心2x2マスを揃える時の基本動作」を使う。
- ステップ3: 配色（展開図）に注意しながら他の中心2x2を揃える
  - 「中心2x2マスを揃える時の基本動作」を使う。
- ステップ4: 辺を揃える。
  - 「辺を揃える時の基本動作」を主に使う。必要なら「最後の1辺のパーツの入れ替え」を使う。
    - 上側1層のみの回転（ $RLFBUD$ ）と中心2層のみの回転（https://macozy.com/rubik/4rc/step1_4.htmlに載っているもう一つの状態）に揃えた後、「辺を揃える時の基本動作」を使って辺を揃える。
  - dedgeのペアを上下反転させたいときは、中心2層を移動させると良い。例えば $FR$ 面のdedgeを上下反転させたいときは、 $D_2'U_2\cdot F2$ （中心2層を1/4回転してdedgeを反対側に持ってきた後、dedgeの位置を元に戻す）を使う。
II: 3x3x3 RCを、パリティに注意しながら解く
- ステップ5: 高橋メソッドを使って「3時、6時、9時」の時点まで解く。
  - ここで dedge 1辺のみが反転している場合、「1本のdedgeを反転する（OLL parityの解消）」を使ってdedge反転させる。
- ステップ6: 高橋メソッドを完走する
- ステップ7: 必要ならばPLL parityを解消する
  - この時点で、ある1辺上のエッジキューブ2つのみが反転しており他はすべて揃っている状態になることがある。この状態になった場合、エッジキューブが反転している辺を $FU$ 面の交線に持っていき、「対面するdedge同士を反転する（PLL parityの解消）」を行う。

この方法で4x4x4 RCが解けるはずである。

おまけ

パリティの詳細

パズルにおいて、配置を行き来可能な「世界」に分類するパリティの考え方は、ルービックキューブ特有のものではなく、他のパズルにおいても広く用いられる。パリティを用いることでパズルに関する色々な性質を証明できる。例えば、15パズルにおいて14と15のピースのみを入れ替えたものは決して解けないことが知られているが、この証明の際にもパリティを用いる。詳しくは 15パズルのパリティと転倒数 | Mathlog などを参照。

パリティの語源はpair = 2つ組である。数学においてparityと言った場合、主に整数が偶数であるか奇数であるかのことを指す。元々は、15パズルの場合において「世界」が2つしかなく、ある盤面がどちらの世界に属しているか判定するための計算に数の偶奇が用いられていたことからparityと呼ばれているようである。

このように、元々は「パリティ」は盤面の状態そのものではなく、盤面の状態に付随するある数（不変量と呼ばれる）が偶数か奇数であるか否かに由来し、そこから盤面自体が偶奇つまりパリティを持つと呼ばれるようになった。そこから更に転じて、盤面の分類つまり「世界」が2個より多い場合も、便宜上同じ用語「パリティ」が使われている。

CommutatorとConjugateの詳細

Commutatorは、動作 $A$ と $B$ の「差分」を表す動作である。 $A$ と $B$ が互いに無関係、例えば $A=L, ~ B=R$ の場合、 $ABA'B' = e$ （何もしない動作を $e$ と置いた）となる。これは $L$ と $R$ の動作範囲が全く交わらないからである。一方、動作範囲が互いに交わる $A=R, ~ B=U$ とおくと $ABA'B'$ は右動作となり、 $ABA'B' \neq e$ となる。

Commutatorは次のような特徴を持っている：

とが可換 (commutative) ならば、が成り立つ。ここでとが可換であるとは、が成り立つことを表す。
- この対偶より、 $ABA'B' \neq e$ ならば $A$ と $B$ は可換ではないことがわかる。

このような特徴から、commutatorは $A$ と $B$ がどれだけ可換であるかを測っていると言える。

また、 $A$ と $B$ の動作範囲が交わらない部分の効果は打ち消される。したがって、commutatorはその作用の動作範囲を最小限に留めるようなアルゴリズムとなりやすい。

Conjugate $ABA'$ は、行列の相似変換 (https://ja.wikipedia.org/wiki/%E8%A1%8C%E5%88%97%E3%81%AE%E7%9B%B8%E4%BC%BC) や、行列の対角化 (https://ja.wikipedia.org/wiki/%E5%AF%BE%E8%A7%92%E5%8C%96) の際に用いる変換と同じ作られ方をしている。行列の対角化の意味からの類推を行うと、conjugate $ABA'$ は「 $A$ の座標系に座標変換し、その世界の中で $B$ を行い、再び座標系を戻すために $A'$ を行う」ような動作を表していると言える。

2022-02-05

CPU対戦型の高難易度版ポケモンWordle「後出しポケモンWordle」を作りました

qntmさん作のWordleのadversarial版 Absurdleから着想を得て、ポケモンWordleのCPUとの対戦型の高難易度版「後出しポケモンWordle」を作りました。

このゲームはCPUとの対戦型ゲームになっていて、なるべく正解にたどり着かせたくないCPUと対戦するというルールになっています。どのような対戦要素があるかというと、通常のポケモンWordleでは予めポケモンの名前が決まっていますが、相手はプレイヤーの 予想を見た上で、 これまでのパネルの結果と 矛盾しない範囲で次々と正解を変え、なるべく少ない情報しか出さないようにパネルの結果を出してきます。すでに表示された回答やパネルの結果が変わることはありません。

あなたはCPUの戦略を乗り越え、正解に辿り着くことができるでしょうか？

後出しポケモンWordleはこちらで遊ぶことができます：

woodrush.github.io

原作のWordleおよびポケモンWordleと違って、好きな回数だけポケモンの名前を予想することができます。正解候補のポケモンはソード・シールドまでに登場する5文字のポケモン、予想として使えるのはソード・シールドまでに登場する5文字以内の全てのポケモンです。

モード

更に難易度を上げるためのモードが２つあります。

ハードモード
- これまでに得られたヒントに合致するポケモンのみを回答に使用することができるモードです。
ウルトラハードモード
- ウルトラハードモードでは、最初にお題のポケモンがランダムで提示され、 お題のポケモンが正解となるように回答を行います。お題のポケモンが正解候補からいなくなってしまうとゲーム終了となります。

ポケモンWordle関連記事

平均情報量（エントロピー）最大化に基づいてポケモンWordleの有効な初手を考察する記事を公開しています。

woodrush.hatenablog.com

また、ソースコードを下記のGitHubレポジトリにて公開しています。

github.com

Credits

このゲームはqntmさん作のWordleのadversarial版 Absurdleから着想を得ています。プログラムはHikaru Ikuta (@woodrush) が書いています。

2022-02-04

ポケモン名前当てゲーム「ポケモンWordle」「Pokedle」の初手はどのポケモンが強い？平均情報量最大化による攻略方法と有効初手考察

この記事ではポケモン名前当てゲーム「Pokedle」「ポケモンWordle」の有効な初手は何か？という考察を行います。

ポケモン名前当てゲーム「Pokedle」「ポケモンWordle」

つい先日、ポケモン名前当てゲーム「Pokedle」が登場しました。

pokedle.vercel.app

Pokedleはちゅうさん*1が制作*2しているゲームで、9回以内で日本語で5文字のポケモンの名前を当てるというゲームになっています。このゲームは後に説明するようにWordleというゲームが原作となっています。

このゲームが面白いのは、ただ毎回名前をランダムに当てるのではなく、回答する度にどの文字が正解に近かったのかのヒントが毎回もらえるということです。つまり回答する度にヒントが増え、そのヒントを元に名前を当てる謎解きのようになっていて、いかに上手いポケモンを回答し、良いヒントを引き出せるかがポイントになっています。

そしてその後、ポケモンWordleというゲームが登場しました。

世界で流行中の単語当てクイズゲーム「Wordle」のポケモンバージョンを作りました！
本家と同じ日替わり問題だけでなく、友達と合言葉を決めて同じ問題に挑戦できる「エンドレスモード」もあります！
みんなもポケモンゲットだぜ！https://t.co/4RT3RXRh7y #ポケモンWordle
— やど (@giga_yadoran) 2022年1月30日

ポケモンWordleはやどさん*3が制作しているゲームで、こちらも10回以内で日本語で5文字のポケモンの名前を当てるというゲームになっています。こちらでは予想回数が10回になっている他、4文字以下のポケモンも予想として使用可能で、更に何回でも挑戦可能なエンドレスモードも遊ぶことができます。

原作：Wordle

このゲームはWordleというゲームが原作になっています。皆さんは最近下記のようなツイートを見たことがあるのではないでしょうか。

Wordle 229 6/6

⬜⬜🟨🟨🟨
🟨🟨⬜🟨⬜
🟨⬜🟨⬜⬜
🟩⬜⬜🟩🟩
🟩⬜🟩🟩🟩
🟩🟩🟩🟩🟩
— Hikaru Ikuta (@woodrush924) February 3, 2022

この何やら謎な四角のツイートは、最近流行っているWordle *4というゲームの結果ツイートです。

WordleはJosh Wardleさん*5が個人制作している単語当てゲームで、5文字の英単語を6回以内で当てるという内容になっています。ただ単語を当てるのではなく、単語を予想する度に下記のような情報を得ることができます。

🟩：予想した文字が正しい場所に配置されている。
🟨：予想した文字は単語中に含まれているが、正しい場所に配置されていない。
⬜：予想した文字は単語中のどこにも含まれていない。

アルファベットは全部で26文字あり、5文字の単語を6回予想できるので、上手く予想すれば6回以内でクリアできるようになっている絶妙なゲームバランスになっているというわけです。隠された単語は毎日0時に変わるようになっており、毎晩0時になると多くのWordleの結果ツイートを目にする機会が増えています。

Wordleは個人制作のゲームでありながら、New York Timesに取り上げられたり*6、Googleで「Wordle」と検索すると専用のロゴ表示が出るようになるなど、大きな盛り上がりを見せています。

このWordleのポケモン版が「Pokedle」そして「ポケモンWordle」です。

ちなみに私の初回のPokedleの結果はこのような感じ*7で、ポケモンWordleの結果はこのような感じ*8でした。これまでのポケモン人生の全てが試されているような感じがして、ポケモンマスター魂が燃えるゲームです。

問題設定

さて、ゲームがあるというのなら、一番上手くクリアする方法は何かが気になるというものです。この記事では、初手に選ぶべき最適なポケモンはどのようなポケモンかを考察します。

「最適、最適」と言われたら、何が評価関数なのかを明確にするのが世の情けです。この記事では下記のような問題を考えます。

問題: ポケモンWordle/Pokedleにおいて、全ての正解候補ポケモンがランダムに出題される時、その後の平均の予想回数を最小化すると思われる最初の一手のポケモンは何か？

ただし、この記事で用いるエントロピー最大化の方法はヒューリスティクスに基づく方法なので、真の最適解は得られません。しかし、最適解に近いと思われる近似解は得ることができます。

ポケモン名前当てゲーム「Pokedle」「ポケモンWordle」
- 原作：Wordle
問題設定
目次
番外編先行研究 - その日つぶやかれたWordleのパネル列からその日の単語を一発で推定する方法
ポケモンWordleの有効初手の考察 - 準備
初手に一番良いポケモンは何か？エントロピーによる考察
- 上記の表のエントロピーは初手においてのみ有効
- Pokedleにおけるエントロピーの計算
「ピカチュウ」という名前の構成音の珍しさ
最後に
付録
- Pokedleのデータの収集
- Pokedleにおけるパネルのフィードバックのルール

番外編先行研究 - その日つぶやかれたWordleのパネル列からその日の単語を一発で推定する方法

この記事の趣旨とは異なるのですが、原作であるWordleに関して面白い先行研究があるので紹介します。

なんとBen Hamnerさんはその日につぶやかれたWordleの結果からその日の単語を一発で推定する方法を作り公開しています。この方法では、twitterからその日のパネルの情報を載せた冒頭で紹介したようなツイートを収集し、その情報を使ってその日の単語を推定します。

https://www.kaggle.com/benhamner/wordle-1-6/notebook

こちらはKaggleで公開されているだけに深層学習に基づいているのかと思いきや、なんとWordleの全正解候補単語と使用可能単語を用いてWordleのセッションのシミュレーションを多数行い、正解候補に対するパネルのパターンの出現頻度を単語ごとに計測し、パネルの全組み合わせの頻度のベクトルを特徴として最近傍探索を含む3つの指標を用いてその日の単語を推定しています。

ポケモンWordleの有効初手の考察 - 準備

以下ではポケモンWordleの初手を考えていきます。この記事ではエントロピーの最大化による方法で有効な初手を考えます。

この記事で紹介するチャートは平均回答数を真に最少にする最適なものではなく、他のポケモンが真に最適な可能性があります。しかし、この記事で紹介する方法を参考にすると、「その後の分割を均等にするようなポケモンを選ぶのが概ね良い」というポケモンWordleを攻略する上での一つの方針を得ることができます。

データの収集

まずポケモンWordleの説明によると、下記のようなルールが記されています。

お題のポケモンは必ず５文字です

回答には５文字以下のポケモンも入力することができます

回答には剣盾までのポケモンが使えます

（ポケモンWordle https://wordle.mega-yadoran.jp/ より引用）

そこで全国ポケモン図鑑順のポケモン一覧 - Wikipedia から該当するポケモンの名前を収集します。回答に使えるポケモンと、正解候補のポケモンの２つのデータを収集します。

また、ニドラン♂・♀、ポリゴン２・Ｚに必要な「♂・♀・２・Ｚ」がキーボードに存在せず入力できないため、これらのポケモンは除外します。

こうして収集したデータを見ると、正解候補ポケモンは511匹、回答可能ポケモンは847匹となりました。正解候補ポケモンはたまたま $2^{9}-1$ 匹になっていますが、今回はその事実は特に使いません。

ポケモンWordleにおけるパネルのフィードバックのルール

ポケモンWordleをプレーしてみた結果、パネルのフィードバックのルールはWordle同様下記のようになっていると思われます。

まず回答と正解の両方において位置と内容が一致している文字を全て探し、それらを緑色のパネルとする。
次に位置は合っていないが正解の名前中に含まれている文字を全て探し、それらを黄色のパネルとする。
- ただし、同じ文字が重複している場合は、緑色＋黄色のパネルの枚数が正解単語におけるその文字の文字数以下になるように黄色のパネルを表示する。
- たとえば「ああいうえ」が正解で「あおああお」と回答した場合、結果は「緑灰黄灰灰」となる。回答に「あ」は3つ含まれているが、正解には「あ」が2つしか含まれていないので、緑色＋黄色のパネルの枚数は２枚となっている。
名前中に含まれていないパネルは全て灰色のパネルとする。

この記事では上記のルールに従っていると仮定して初手を考察します。

分割の質

さて、この記事では以下のような方法によって初手を考察していきます。ここでは回答の結果得られるパネル列をフィードバックのパネルの列と呼ぶことにします。

正解候補ポケモンと使用可能ポケモンの集合をそれぞれ用意する。
全使用可能ポケモンでの回答をシミュレーションする。
フィードバックのパネル列によって正解候補ポケモンは分割されるが、 最も質が良い分割 を与えてくれる回答を１匹選ぶ。このポケモンを有効な初手とする。

さて、ここで問題になるのが「最も質が良い分割」とは何か、つまり「分割の質」を測るにはどのようにすれば良いのかという問題です。

まず最初に考えられるのは得られるフィードバックの種類の多さです。回答の結果得られるパネル列の種類が多い方が、多くの場合分けが生じるためより良く絞り込めると考えられます。しかし、例えば同じ4分割でも、(508匹、1匹、1匹、1匹)という分割より(128匹、128匹、128匹、127匹)という分割の方が一般的に性能が良いと言えます。なぜならば、一発で1匹に絞り込める場合を引いたなら良いのですが、508匹のフィードバックを引き当てた場合、ほぼ絞り込んでいないのと同じになってしまうからです。これに対して後者の分割では、どのようなフィードバックが得られた場合でも128匹程度に絞り込めることが確実なので、絞り込みの性能、つまり分割の質は高いと言えます。

分割の質を測るエントロピー

このような意味で分割の質を測るのにエントロピーを使うことができます。以下ではその理由を説明します。

まず、今回興味があるのは全ポケモンの平均回答数を最小化することです。そこで、ある状態から正解に至るまでの回答数の見積もりを計算する方法を考えます。

そのために、次のような仮定を置きます。

このゲームでは回答を行うごとに候補数が $p \lt 1$ 倍される。

このように考えると、例えば現在の正解候補数が $M$ 匹だった場合は、回答するごとに候補数が $p$ 倍になっていくので、 $M$ 匹になった時点からの残りの手番数の見積もり $n$ は残りの候補数が1となる時の $n$ であるため、

$\displaystyle \begin{align} p^n M &= 1 \\ % n \log p &= \log \frac 1 M \\ n &= \frac 1 {\log p} \log \frac 1 M \end{align}$

と見積もることができます。

さて、回答 $x$ から得られるフィードバックによって候補が $\left( M_1, M_2, \cdots, M_m \right)$ 匹に分割されるとします。また、 $M_i$ の合計、つまり正解候補数の総数 $\sum_i M_i = N$ とします。

この時、正解候補ポケモンの選出率が均等だとすると、それぞれの分割が得られる確率は $\left( \frac {M_1} N, \frac {M_2} N, \cdots, \frac {M_m} N \right)$ となります。また、それぞれの分割の後における残り手番数の期待値の見積もり $n_i$ も上記の $n$ の式で計算することができます。つまり、回答 $x$ を行った後の平均の残り手番数の見積もり $\hat n$ は、各分割の出現率と、その分割における残り手番数の見積もりの期待値として次のように書けます：

$\displaystyle \begin{align} \hat n &= \sum_i \frac {M_i} N n_i \\ &= \sum_i \frac {M_i} N \frac 1 {\log p} \log \frac 1 {M_i} \\ &= \frac 1 {\log p} \sum_i \frac {M_i} N \log \frac 1 {M_i} \\ \end{align}$

これを少し変形すると、

$\displaystyle \begin{align} \hat n % \left(M_1, M_2, \cdots, M_m \right) &= \frac 1 {\log p} \sum_i \frac {M_i} N \log \frac 1 {M_i} \\ &= \frac 1 {\log p} \sum_i \frac {M_i} N \left( - \log {M_i} + \log N - \log N\right) \\ %&= \frac 1 {\log p} \sum_i \frac {M_i} N \left( - \log \frac {M_i} N - \log N\right) \\ %&= \frac 1 {\log p} \sum_i - \frac {M_i} N \log \frac {M_i} N + \frac 1 {\log p} \sum_i \frac {M_i} N \log N \\ &= \frac 1 {\log p} \sum_i - \frac {M_i} N \log \frac {M_i} N + \frac 1 {\log p} \log N \\ \end{align}$

が得られます。

さてここで、下記の事実に着目します：

どのような分割に対しても、
- それらの合計 $N$ は不変である。
- 仮定として置いている $p$ の値は不変である。

したがって、 $\hat n$ の和の係数、および第二項はどのような分割を選んでも値が不変であることがわかります。

したがって、 $\hat n$ を最小化するためには、次のような関数 $\tilde n$ を最小化すれば良いことになります：

$\displaystyle \begin{align} \tilde n \left(M_1, M_2, \cdots, M_m \right) %H \left(M_1, M_2, \cdots, M_m \right) &= - \sum_i \frac {M_i} N \log \frac {M_i} N, \ \ N = \sum_i M_i \end{align}$

これを離散確率分布 $\left( \frac {M_1} N, \frac {M_2} N, \cdots, \frac {M_m} N \right)$ の平均情報量またはエントロピーと呼びます。この量は一般の離散確率分布 $\left(p_1, p_2, \cdots, p_m \right)$ に対しても次のようにのように定義されます：

$\displaystyle \begin{align} H \left(p_1, p_2, \cdots, p_m \right) &= - \sum_i p_i \log p_i \end{align}$

さて、今行いたいのは一番質の良い分割を与えてくれる回答可能ポケモンを探すことでした。今回で言う質の良い分割とは、全ポケモンの平均回答手番数を最小化してくれるような分割です。その近似値として残り手番数の近似値 $\hat n$ を計算しましたが、その値を最小化するような分割を知りたいわけです。そしてそれを達成するのは、 $H$ を最小化するような分割、つまりエントロピーを最大化するような分割を与えてくれる回答ポケモンです。

したがって、分割の質としてエントロピーを使い、そのエントロピーを最大化するようなポケモンを選ぶことが有効初手導出の方法として使えます。

どのような分割がエントロピーを最大化するか

さて、候補数の合計 $N$ が一定の時、どのような分割 $\left( \frac {M_1} N, \frac {M_2} N, \cdots, \frac {M_m} N \right)$ がその後の平均手番数を最小化すると思われるか、つまりエントロピーを最大化するかが気になります。これは一般に確率分布 $\left( \frac {M_1} N, \frac {M_2} N, \cdots, \frac {M_m} N \right)$ が一様分布であるときであることが知られています。このようなエントロピーの性質は一般の離散確率分布にも適用することができ、ラグランジュの未定乗数法という方法によって導出することができます。

今回の問題で言い換えると、これは全ての分割における候補数が均等である時であると言いかえられます。先程例として同じ4分割でも(508匹、1匹、1匹、1匹)という分割より(128匹、128匹、128匹、127匹)という分割の方が一般的に性能が良いと言えるだろうという話をしましたが、この時の性能は分割のエントロピーの大小で比べることができます。実際にエントロピーを計算してみると、

$\displaystyle \begin{align} % \tilde n \left(M_1, M_2, \cdots, M_m \right) H \left(\frac {508} {511}, \frac {1} {511}, \frac {1} {511}, \frac {1} {511} \right) &= 0.042466 \\ H \left(\frac {128} {511}, \frac {128} {511}, \frac {128} {511}, \frac {127} {511} \right) &= 1.386289 \end{align}$

後者の分割ではエントロピーが32倍近くとなっています。エントロピーは期待手番数に概ね比例する量と言えるので、後者の分割のほうが32倍も少ない手番数で正解に到達できると見積もれることがわかります。もちろんこれは近似に近似を重ねているので正確ではないのですが、いかに均等な分割の方が手番数を少なくできるかがわかると思います。

したがってここから得られる重要な方針は、なるべく分割が均等になるポケモンを選ぶとその後の期待手番数を少なくすることができるだろうという方針です。

初手に一番良いポケモンは何か？エントロピーによる考察

さて、エントロピーという道具を手に入れた今、初手で一番良く候補を絞ることができるポケモンが何であるかを導くことができます。先程の考察によると、何も回答していない状態でエントロピーを最大にするようなポケモンが初手として一番良いポケモンになります。*9

以下の表は、初手において一番良く候補を絞り込んでくれる順に並んだポケモンの名前たちです。左から順位、名前、エントロピーの値、得られるパネル列の種類、そして各パネル列が得られた時に正解候補として残るポケモンの数が記されています。この表の一番上が初手にエントロピーの意味で最適なポケモンで、その次が初手の選択として2番目に良いポケモン、その次が3番目…となっています。

その表がこちらです。

  1 ジーランス 2.81552027301750 53 [136, 71, 55, 36, 24, 17, 16, 15, 14, 11, 10, 9, 8, 8, 7, 6, 6, 5, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  2 レントラー 2.80590281618208 46 [143, 54, 54, 38, 22, 21, 21, 15, 13, 12, 9, 9, 9, 7, 7, 7, 6, 5, 5, 5, 5, 5, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  3 ネンドール 2.76650256510168 44 [152, 57, 52, 30, 25, 22, 19, 15, 13, 10, 9, 8, 8, 7, 6, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  4 グラードン 2.75490681338029 58 [163, 78, 36, 30, 22, 16, 15, 12, 11, 11, 11, 10, 9, 7, 5, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  5 ランクルス 2.73260697699840 48 [152, 60, 53, 32, 31, 20, 17, 14, 14, 11, 10, 9, 8, 7, 7, 6, 5, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  6 ルナトーン 2.71418343665737 46 [145, 56, 47, 39, 34, 32, 18, 16, 11, 11, 10, 10, 9, 9, 8, 6, 5, 5, 4, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  7 ドータクン 2.68011040444398 49 [165, 75, 37, 33, 21, 16, 16, 15, 12, 10, 10, 10, 8, 8, 7, 7, 5, 5, 5, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  8 ムーランド 2.66205210039006 47 [166, 71, 50, 28, 21, 16, 15, 15, 12, 11, 10, 8, 6, 6, 6, 5, 5, 5, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  9 ヒードラン 2.65930190748349 53 [172, 76, 35, 33, 21, 18, 15, 11, 10, 10, 10, 9, 9, 7, 6, 6, 5, 5, 5, 4, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
 10 シンボラー 2.65678627841122 46 [168, 56, 54, 37, 22, 21, 19, 14, 10, 9, 7, 7, 7, 6, 5, 5, 5, 5, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
 11 エルフーン 2.65438392548458 47 [165, 52, 42, 36, 32, 31, 21, 17, 11, 10, 9, 9, 8, 6, 5, 5, 5, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
 12 キングラー 2.64903504033593 51 [167, 62, 55, 30, 28, 21, 15, 14, 12, 11, 8, 8, 7, 6, 5, 5, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
 13 ランドロス 2.61842964058585 55 [189, 63, 34, 31, 23, 22, 16, 12, 10, 9, 9, 7, 6, 5, 5, 5, 5, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
 14 ドンカラス 2.61396068008001 56 [197, 67, 34, 21, 20, 17, 16, 13, 11, 8, 8, 8, 5, 5, 5, 5, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
 15 ペンドラー 2.61321481279127 49 [174, 56, 53, 39, 21, 19, 18, 11, 11, 11, 9, 9, 9, 7, 6, 5, 4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
 16 デスカーン 2.61314725428816 43 [153, 62, 43, 43, 41, 37, 15, 11, 10, 10, 10, 6, 6, 6, 5, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
 17 デスバーン 2.60106990313566 45 [158, 63, 46, 42, 39, 35, 14, 10, 10, 7, 7, 6, 6, 6, 6, 5, 4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
 18 ドッコラー 2.58424752564100 46 [171, 72, 39, 38, 27, 19, 13, 13, 12, 12, 11, 8, 8, 8, 7, 5, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
 19 ハンテール 2.57962383823149 40 [163, 57, 57, 35, 31, 24, 19, 18, 12, 9, 8, 7, 7, 6, 6, 5, 5, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
 20 バクフーン 2.56037765802205 50 [183, 60, 42, 38, 34, 21, 17, 9, 8, 7, 7, 6, 6, 6, 6, 5, 5, 4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

！！！

さいしょは　ジーランス………

…いや、さいしょはホエルオーなのですが、この言葉を見て何かを思い出した方は多いと思います。そう、ポケモンルビー・サファイア版のおふれのせきしつに点字で書かれている、レジ系ポケモンを解放するための仕掛けを起動する手順を示した言葉です。

まさか、エントロピーを基準にした結果、ポケモンWordleの最初の一手として良いと思われるポケモンが「ジーランス」であることが明かされるとは…これにはかなり驚きました！

ジーランスの分割結果を見てみると、初手でジーランスと回答するだけで次の一手で即座に正解にたどり着けるポケモンが21匹もいることがわかります。ジーランス自身を含めると、さいしょに　ジーランスと答えるだけで22/511=4.5%の確率で2手以内で正解できることがわかります。（分割結果の中にジーランス自身が含まれているので、2手で正解可能なのは21匹になります。）

一番絞り込めない場合の候補数でも136匹で、これでも26.6%、つまり1/4近くにまで元の候補数から一手で絞ることができることになります。ジーランスがいかにポケモンWordleにおいて強力なポケモンであるかがわかります。

また、2位のレントラーも非常に僅差でエントロピーが高い値になっています。レントラーも2手目で即座に正解にたどり着けるポケモンが13匹も存在し、同じくらい初手として良いポケモンであると言えます。

また、ジーランスだけでなく、ネンドール、グラードン、ルナトーン、ドータクン、シンボラーなど伝説や古代に関わるポケモンが多くランクインしているのもアツいです。

ちなみにエントロピー下位20匹は下記の通りになります。

828 ユキハミ  0.69339811979023 11 [429, 37, 17, 15, 4, 2, 2, 2, 1, 1, 1]
829 ナゲキ   0.69246156345221  9 [433, 25, 16, 15, 11, 4, 4, 2, 1]
830 セレビィ  0.65904841055873 13 [442, 26, 10, 9, 6, 5, 5, 3, 1, 1, 1, 1, 1]
831 ポカブ   0.64736718136168 10 [437, 32, 20, 5, 5, 4, 3, 3, 1, 1]
832 ミュウ   0.64366617846590 13 [444, 25, 9, 9, 7, 6, 4, 2, 1, 1, 1, 1, 1]
833 メテノ   0.62855669184240 10 [445, 17, 12, 12, 9, 7, 6, 1, 1, 1]
834 パウワウ  0.62696439018523 11 [446, 19, 12, 11, 8, 5, 4, 3, 1, 1, 1]
835 ヨワシ   0.60924204727621 10 [439, 43, 8, 6, 4, 4, 2, 2, 2, 1]
836 エネコ   0.60375601579838  9 [445, 23, 12, 10, 10, 8, 1, 1, 1]
837 ポッポ   0.59089590679152  8 [431, 56, 14, 3, 3, 2, 1, 1]
838 ゴニョニョ 0.58629397390259 13 [454, 14, 13, 7, 6, 4, 3, 3, 2, 2, 1, 1, 1]
839 ピッピ   0.57428491795491  8 [431, 56, 18, 2, 1, 1, 1, 1]
840 マネネ   0.57162173645497  7 [440, 39, 19, 6, 4, 2, 1]
841 ベベノム  0.55402542215247 10 [454, 18, 12, 9, 7, 5, 2, 2, 1, 1]
842 ブビィ   0.53306539374617  9 [456, 17, 11, 10, 7, 5, 3, 1, 1]
843 モノズ   0.50979013067474  9 [460, 12, 10, 9, 9, 6, 2, 2, 1]
844 モココ   0.47050968698903  9 [463, 18, 11, 6, 6, 3, 2, 1, 1]
845 ミネズミ  0.46685706516407 10 [465, 11, 11, 10, 7, 2, 2, 1, 1, 1]
846 ツボツボ  0.31489085091216  8 [481, 13, 7, 4, 2, 2, 1, 1]
847 ピィ    0.21066133959411  5 [490, 14, 4, 2, 1]

エントロピー最下位はピィとなりました。ピィは名前が２文字しかなく、なおかつ珍しい文字が使われているので無理はありません。一番候補が絞り込めない場合は490匹候補が残り、全体の95.9%が候補として残ります。

名前が5文字のポケモンで最下位なのはゴニョニョで、こちらも「ゴニョ」という3文字だけが実質ヒントになっていて、なおかついずれも珍しい文字なのでこのようなランキングになっています。

エントロピーの一覧の全体は下記のリンクから閲覧することができます。

https://gist.github.com/woodrush/96e55db9a5472bbf781d7dd45ed8762f

以下は、全回答可能ポケモンのエントロピーの分布を示した図です。ランキング上位のポケモンが抜きん出てエントロピーが高いことがわかります。攻略チャートを使わずにプレーする場合、これらのポケモンはいずれも初手で有効なポケモンと思われます。

上記の表のエントロピーは初手においてのみ有効

ここで、先程の表で示したのは１手目におけるエントロピーであることに注意しなければなりません。初手で候補を絞り込んだ後の２手目における残りの候補ポケモンは初手とは異なるので、同じポケモンを回答として用いても得られる分割が異なるため、そのポケモンによる分割の質も異なってきます。例えば極端な話、いくらジーランスが強いと言えども、2回連続でジーランスと答えると初手と分割が変わらず全く情報が得られません。このことから、２手目以降は全く異なるポケモンが最適となっていることがわかり、つまり２手目以降は全く別の表が作られることがわかります。

２手目以降に関しても、その時の候補を調べることで同じようなエントロピーによる方針を立てることができます。それはつまり、その時点での残りの候補のポケモンをなるべく均等に分割するようなポケモンを選ぶという方針です。そのようなポケモンをいかに上手く選べるかは、トレーナーであるあなたの腕にかかっています。

Pokedleにおけるエントロピーの計算

ここで、もう一つのポケモン版WordleであるPokedleにおいても5文字のポケモンに制限されています。ただし、こちらではつい最近発売されたPokémon LEGENDS アルセウスに登場する図鑑番号が未判明のポケモンも回答に使用できたため、合計516匹のポケモンが正解候補ポケモンとになっています。

Pokedleにおいて同様のエントロピーの計算を行うと、やはりさいしょは　ジーランスが良いという結果が得られます。Pokedleにおいては出現ポケモンが異なるほか、黄色いパネルの出現仕様が少し異なるのですが、それでもはやりジーランスが最もエントロピーが高いポケモンとなりました。Pokedleの詳しい仕様については付録にて説明します。

Pokedleにおけるエントロピーの一覧、つまり有効な初手の一覧をまとめたものが下記のリンクです：

Pokedleのノーマルモードにおける初手回答ポケモンのエントロピー · GitHub

また、Pokedleには６文字以上のポケモンが入力可能なハードモードがあり、こちらのモードでは905匹全てのポケモンが入力可能となっています。更に回答手番数がなんと6手に制限されており、まさにトレーナー力が試される非常に難しいモードとなっています。

これだけ難しいハードモードなので、多くのトレーナーの方の一助となるよう、Pokedleのハードモードにおいても初手のエントロピーを計算しました。その一覧をまとめたものが下記のリンクです：

Pokedleのハードモードにおける初手回答のエントロピー · GitHub

こちらではジーランスではなくマンキーが最適となりました。これは、ハードモードでは6文字未満のポケモンは最後のスペースがフィードバックとして返され、なおかつ末尾にスペースを含んでいるポケモンは多いため、末尾にスペースを含むマンキーが最適であるという結果になったようです。

ちなみに、ノーマルモードとハードモードのいずれにおいてもゴニョニョが初手におけるエントロピーが最下位となっていました。これは先程説明した通りの理由であると思われるのですが、ゴニョニョは905匹の中でもオンリーワンな名前を持っていると言えます。

「ピカチュウ」という名前の構成音の珍しさ

さて、Pokedleのノーマルモードにおける初手エントロピーの下位20匹を見ると、次のようになっています：

497 ギギギアル 1.15679179888471 18 [364, 51, 39, 28, 8, 6, 6, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1]
498 ヒノヤコマ 1.14223671695414 26 [387, 40, 28, 11, 11, 7, 6, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
499 ジグザグマ 1.14035134784917 18 [381, 40, 24, 22, 10, 9, 9, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1]
500 チョロネコ 1.13346856658721 24 [387, 37, 23, 23, 9, 7, 6, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
501 フシギソウ 1.12389149293466 16 [384, 39, 23, 14, 12, 10, 9, 8, 6, 3, 2, 2, 1, 1, 1, 1]
502 フシギダネ 1.11803020812454 18 [388, 39, 16, 14, 12, 12, 9, 6, 5, 5, 2, 2, 1, 1, 1, 1, 1, 1]
503 ピカチュウ 1.10909905602434 24 [398, 29, 19, 16, 8, 7, 7, 5, 4, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
504 ウデッポウ 1.10416584531979 19 [383, 50, 20, 16, 14, 9, 4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1]
505 ビクティニ 1.10130255849240 20 [390, 39, 23, 14, 13, 8, 4, 4, 4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1]
506 レジエレキ 1.09800510234134 19 [393, 34, 21, 14, 11, 9, 7, 6, 5, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1]
507 マダツボミ 1.07879901160671 21 [396, 33, 17, 15, 15, 11, 6, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
508 カゲボウズ 1.05345690945028 18 [403, 22, 17, 16, 10, 9, 8, 8, 7, 4, 3, 2, 2, 1, 1, 1, 1, 1]
509 ヒポポタス 1.04618136093343 16 [385, 59, 18, 18, 7, 5, 5, 4, 3, 3, 3, 2, 1, 1, 1, 1]
510 ハハコモリ 1.04283042860577 18 [391, 54, 18, 10, 8, 7, 6, 5, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1]
511 エネコロロ 1.01433063287613 17 [403, 27, 19, 17, 12, 10, 7, 7, 4, 3, 1, 1, 1, 1, 1, 1, 1]
512 ユキメノコ 0.97541863359589 17 [402, 33, 28, 16, 15, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1]
513 タマゲタケ 0.96326915783888 17 [405, 42, 16, 11, 10, 9, 7, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1]
514 ナゾノクサ 0.95581647037521 20 [408, 41, 15, 14, 10, 6, 5, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1]
515 シュシュプ 0.79220765985007 14 [428, 36, 9, 9, 8, 7, 6, 5, 3, 1, 1, 1, 1, 1]
516 ゴニョニョ 0.59527491852947 13 [457, 15, 14, 7, 6, 4, 3, 3, 2, 2, 1, 1, 1]

なんと下から14位にピカチュウがランクインしています。

ピカチュウと言えば、ポケモンを代表すると言っても良い名前です。にも関わらずこれだけエントロピーが低いのは、ポケモン全体の名前で見ると珍しい音で構成されている名前であるからと言えるでしょう。

そこでポケモンWordleにおけるポケモンの文字を出現頻度順に並べると次のようになります：

    'ー', 'ン', 'ル', 'ラ', 'ス', 'ッ', 'リ', 'ド', 'イ', 'マ',
    'ト', 'ク', 'ロ', 'シ', 'オ', 'ア', 'キ', 'カ', 'バ', 'ジ',
    'レ', 'ガ', 'グ', 'コ', 'チ', 'ウ', 'タ', 'フ', 'ニ', 'ャ',
    'ブ', 'ム', 'ダ', 'デ', 'ゴ', 'ュ', 'ノ', 'テ', 'メ', 'ナ',
    'ミ', 'サ', 'エ', 'ハ', 'ヤ', 'ボ', 'ギ', 'パ', 'ゲ', 'モ',
    'ワ', 'ザ', 'ィ', 'ズ', 'ビ', 'プ', 'ケ', 'ネ', 'ツ', 'ポ',
    'ョ', 'ヒ', 'ベ', 'ペ', 'ホ', 'ヨ', 'ゼ', 'ソ', 'ピ', 'セ',
    'ユ', 'ェ', 'ヌ', 'ォ', 'ゾ', 'ァ', 'ヘ', '2',  'Z', 'ヂ',

このように、ピカチュウの「ピ」が下から12位であることがわかります。ピカチュウと言えば冒頭の「ピ」が目立ちますが、実はポケモン全体で見ると「ピ」はかなり珍しい文字なのです。

したがってポケモンを代表すると言っても良いピカチュウは、ポケモン全体の中で見ると珍しい構成音を持つ名前なのです。しかしだからこそ、ピカチュウはポケモンの中でも独特な響きを持つ名前として印象に残るのかもしれません。

最後に

エントロピーに基づいた考察の結果、ポケモンWordleおよびPokedleの有効な初手は「ジーランス」であることがわかりました。また、Pokedleのハードモードにおいては「マンキー」が有効であることがわかりました。そして初手および２手目以降において、なるべく次の候補が均等に分割されるようなポケモンを選ぶのが良いという方針が得られました。

また、エントロピーを考察した二次的な効果として、「ピカチュウ」という名前がポケモン全体の中で見てもかなり珍しい音で構成されていることがわかりました。だからこそ、ピカチュウはポケモンの中でも独特な響きを持つ名前として印象に残るのかもしれません。

さて、エントロピーの導出にて述べたように、エントロピーはその後の平均手番回数の見積もりでしかありません。なぜならば、エントロピーを使う時は「その後の選択肢は毎手番 $p \lt 1$ 倍になる」という非常に強い仮定を置いているからです。エントロピーの一覧を見ると、各ポケモンによって実際の候補の別れ方はバラバラで、綺麗に $p \lt 1$ 倍にはなっていないことがわかります。ここからもわかるように、エントロピーを使うのは現実と離れている見積りにすぎないため、この結果が最適である保証はどこにもありません。したがって、今後更なる良い戦略が見つかる可能性は存分に残されています。

そして上位のポケモンはエントロピーがかなりの僅差となっていました。そのため、初手におけるポケモンの選択にはその分の余地が残されています。更に、２手目以降はエントロピーの表が完全に書き換わるため、その時の残りの候補を考慮して良いポケモンを選ぶ能力が問われることになります。

これは、ポケモン金銀における次の名言を思い起こさせます。

つよいポケモン　よわいポケモン

そんなの　ひとの　かって

ほんとうに　つよい　トレーナーなら

すきなポケモンで　かてるように　がんばるべき

付録

以下では付録としてPokedleにおける内容について述べます。

Pokedleのデータの収集

Pokedleの作者のちゅうさんの製作記事*10によると、 Pokedleは5文字のポケモンに正解候補および回答候補が限定されているようです。そこで全国ポケモン図鑑順のポケモン一覧 - Wikipedia から5文字のポケモンの名前を収集します。

つい先日発売されたPokémon LEGENDS アルセウスに登場する図鑑番号が未判明のポケモンも含めると、 5文字の名前を持つポケモンは2022年2月1日現在全部で516匹いることがわかります。アルセウスに登場するポケモンを入力したところ有効だと判定されたので、これらのポケモンも正解候補に存在していると思われます。

Pokedleにおけるパネルのフィードバックのルール

Pokedleをプレーしてみた結果、パネルのフィードバックのルールは下記のようになっていると思われます。

まず回答と正解の両方において位置と内容が一致している文字を全て探し、それらを緑色のパネルとする。
次に位置は合っていないが正解の名前中に含まれている文字を全て探し、それらを黄色のパネルとする。
- ただし、同じ文字が重複して登場している場合でも、一度でも登場していれば全て黄色のパネルとする。
名前中に含まれていないパネルは全て灰色のパネルとする。

実際にPokedleをプレーしてみると、黄色のパネルの出現ルールが原作のWordleでの仕様とは異なっているようです。具体的には、1月31日の正解ポケモンは伸ばし棒「ー」が一つ含まれていたのですが、伸ばし棒が２つ含まれるポケモンを回答したところいずれの伸ばし棒も黄色いパネルになりました。これに対しWordleでは黄色いパネルは正解単語に含まれる文字数分だけ現れるようです。例えば正解単語にAが1つ含まれていて、予想単語にAが2つ含まれていた場合、黄色いパネルで表示されるAは1枚だけになるようです。これらはいずれも本記事の著者がプレーした結果なので確かではないのですが、このような仕様になっていると思われます。

*1:https://twitter.com/chuprod

*2:https://zenn.dev/chuprod/articles/6006664b03bb0f

*3:https://twitter.com/giga_yadoran

*4:Wordle - A daily word game

*5:https://twitter.com/powerlanguish

*6:https://www.nytimes.com/2022/01/03/technology/wordle-word-game-creator.html

*7:https://twitter.com/woodrush924/status/1488991273914892288

*8:https://twitter.com/woodrush924/status/1488991333591425025

*9:もちろん先読みを深く行うと真に最適なポケモンは違うポケモンになる可能性はあるのですが、ここではエントロピーに基づいた結果を示します。

*10:https://zenn.dev/chuprod/articles/6006664b03bb0f

2019-11-14

PARANOIA survivor MAX (鬼) SP のラストの滝たちは、互いに鏡像変換の関係にある譜面となっている

Dance Dance Revolution *1に関する記事です。

PARANOIA survivor MAX (鬼) SP のラストには長い滝が登場します。この滝は4つの部分に分けられますが、これらの滝は全て1つ目の滝に対して下記のような鏡像変換を適用したような配置になっていることに気付きました。

2つ目の滝では、←と→が互いに入れ替わり、他のポジションは固定（ただし、最後の一音だけ例外で、→が入れ替わらず→のままになっています。）
3つ目の滝では、↓と↑が互いに入れ替わり、他のポジションは固定
4つ目の滝では、上記の変換が両方適用される

この事実は目視では確認しづらいので、これを検証する下記のようなコードを書きました。言語はPythonです。実際、2つ目の滝の最後の音だけが入れ替わっていないことは、このコードを動かすことで初めて気付きました。

l = [
    "jhjkhlkjljhkjlhjklhjljklkjhlkjl",
    "jljklhkjhjlkjhljkhljhjkhkjlhkjl",
    "khkjhljklkhjklhkjlhklkjljkhljkl",
    "klkjlhjkhkljkhlk",
]

d_2 = {
    "h": "l",
    "j": "j",
    "k": "k",
    "l": "h",
}

d_3 = {
    "h": "h",
    "j": "k",
    "k": "j",
    "l": "l",
}

d_4 = {
    "h": "l",
    "j": "k",
    "k": "j",
    "l": "h",
}

stream_1 = l[0]
stream_2 = "".join([d_2[c] for c in l[1]])
stream_3 = "".join([d_3[c] for c in l[2]])
stream_4 = "".join([d_4[c] for c in l[3]])


assert stream_1 == stream_3
assert stream_1[:-1] == stream_2[:-1]
assert stream_1.startswith(stream_4)

print(stream_1)
print(stream_2)
print(stream_3)
print(stream_4)

なぜ二つ目の滝では最後の一音だけ→が入れ替わらず→のままになっているかという理由について、ここが←になっていた場合を考えると、3つ目の滝の冒頭の↑を右足で踏もうとした時に、すでに右足で←を踏んでしまっているため足が絡まってしまうことから、どうやらそのような事を防止するために最後の音だけ入れ替わらずにしてあるようです。

また、4つ目の滝は途中で曲が減速する部分に入り、滝が途中で終わってしまいます。この理由について、これは鏡像変換を二つ適用していることから、実は省略されている部分は難しい配置になっているため途中で切っているのではないかと予想したのですが、特にそうではありませんでした。下記のコードによって、1つ目の滝に4つ目の滝の変換を適用することで省略された残りの滝の譜面を生成し、矢印表記で表示してみたのですが、特に変わった様子はありませんでした。（下記のコードは、上記のコードの末尾にappendして使います。）

stream_4_dash = "".join([d_4[c] for c in l[0]])

def printstream (stream):
    c2arrow = {
        "h": "←",
        "j": " ↓",
        "k": "  ↑",
        "l": "   →",
    }
    print("←↓↑→")
    for c in stream:
        print(c2arrow[c])

printstream(stream_4_dash)

*1:DanceDanceRevolution A | KONAMI コナミアーケードゲーム製品・サービス情報サイト

2016-03-12

さけるチーズを避けるチーズによるラムダ計算・Lazy K入門

Functional Programming

純粋関数型言語「さけるチーズ」とは、難解プログラミング言語「Lazy K」の文法に束縛変数を導入することでラムダ計算風にし、自然言語的に意味が通るように文法を直した言語です：
woodrush.hatenablog.com

この記事では、「さけるチーズ」を用いてチャーチエンコーディングによる自然数やリストの表現について説明し、最後にさけるチーズ（というよりもLazy K）を用いたHello, world!プログラムの書き方を解説します。この記事は前回の記事の続きでもあり、また筆者自身のラムダ計算・Lazy K入門の過程をまとめた記事でもあります。Lazy Kはとても面白い言語なのですが資料が少ないので、この記事をラムダ計算・Lazy K入門の副読記事として活用して頂ければ幸いです。

ここでは、

自然数の表現
加算と累乗
リストの表現
Hello, World!プログラム

について解説します。

さけるチーズとLazy Kの相互翻訳法については、記事末尾の付録にて解説しています。

自然数の表現

まずはプログラミング上最も重要なデータの一つ、数を表現してみます。数字を含まない文法しか持たないさけるチーズで、どのようにして自然数を表現するのでしょうか？

さけるチーズでは、自然数をチャーチエンコーディング（究極の関数型言語による至高のHello, world! - Life Goes On参照）によって表現します。
これは端的に言うと、自然数Nを、「任意の構造物fとXを捧げられた時、XにfをN回捧げた物を返す構造物」で表すという事です。
つまり「Nに捧げるfに捧げるX」が

Nに捧げるfに捧げるX
= fに捧げる「fに捧げる「fに捧げる…「fに捧げるX」」」」…」」」」　　（fがN回登場）

に変換されるような構造物Nで、自然数Nを表します。

具体的には、これは以下のような構造物で実現できます：

0 = 「さけるチーズを避ける「裂けてるチーズ」」
1 = 「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」に捧げる「さけるチーズを避ける「裂けてるチーズ」」」
2 = 「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」に捧げる「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」に捧げる「さけるチーズを避ける「裂けてるチーズ」」」」
…

例えば

0に捧げるfに捧げるX
= 「さけるチーズを避ける「裂けてるチーズ」」に捧げるfに捧げるX
= 「fを避ける「裂けてるチーズ」」に捧げるX
= 「裂けてるチーズ」に捧げるX
= X

となり、確かにfにXを0回捧げた結果が返ってきます。
また、ここでは長くなるので割愛しますが、「2に捧げるfに捧げるX」という構造物を評価すると、実際に「fに捧げる「fに捧げるX」」となることが確認できます。

実はこの表現には規則性があり、後者関数

SUCC = 「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」

を定義すると、

0 = 「さけるチーズを避ける「裂けてるチーズ」」
1 = SUCCに捧げる0
2 = SUCCに捧げる1
3 = SUCCに捧げる2
…

のように計算できます。

このような数の表現方法（チャーチエンコーディング）におけるポイントは、どの数の表現の最上層部にも禁断の者が存在しているため、これ以上の変形ができないという事です。例えば 0 = 「さけるチーズを避ける「裂けてるチーズ」」では禁断の者さけるチーズがいます。また、1 = SUCCに捧げる0 では、SUCCがさけるチーズとチーズという2人の禁断の者を含んでいることから、0を捧げても禁断の者さけるチーズが残り、これ以上の変形ができません。
変形ができないことから、「最終的に計算結果の答えとして残す」ような使い方ができるのです。

加算と累乗

このような数の表し方の下で、数同士の演算も行うことができます。

まずX+Yという計算は、「XにSUCCをY回適用する」ことによって表すことができます。
そしてY自身、「与えられた関数をY回適用する」という機能を持つため、

「Yに捧げるSUCCに捧げるX」
= 「SUCCに捧げる「SUCCに捧げる…「SUCCに捧げるX」」」」」…」　　（SUCCがY回登場）

となります。
ここで、

ADD = 「「裂けてるチーズ」と「さけるチーズを避けるSUCC」と地図のある地、伊豆」

を定義すると、

ADDに捧げるXに捧げるY
= 「「裂けてるチーズ」と「さけるチーズを避けるSUCC」と地図のある地、伊豆」に捧げるXに捧げるY
= 「「裂けてるチーズ」と「さけるチーズを避けるSUCC」とXのある地、伊豆」に捧げるY
= 「裂けてるチーズ」に捧げるXに捧げる「「さけるチーズを避けるSUCC」に捧げるX」に捧げるY
= 「裂けてるX」に捧げる「「Xを避けるSUCC」」に捧げるY
= Xに捧げるSUCCに捧げるY
= 「SUCCに捧げる「SUCCに捧げる…「SUCCに捧げるX」」」」」…」　　（SUCCがY回登場）

となり、捧げ物をすることで足し算が行える構造物を得ることができました。

ここで、3を表す構造物に2を捧げたらどうなるでしょうか？
「3に捧げるfに捧げるX」=「fに捧げる「fに捧げる「fに捧げるX」」」であることから、

3に捧げる2に捧げるfに捧げるX
= 「2に捧げる「2に捧げる「2に捧げるf」」」に捧げるX　　（3の直後の捧げ物を2つ取るため、Xは余る）
= 2に捧げる「2に捧げる「2に捧げるf」」に捧げるX
= 「「2に捧げる「2に捧げるf」」に捧げる「「2に捧げる「2に捧げるf」」に捧げるX」」　　（※1）
= 「「2に捧げる「2に捧げるf」」に捧げる「2に捧げる「2に捧げるf」に捧げるX」」
= 「「2に捧げる「2に捧げるf」」に捧げる「「2に捧げるf」に捧げる「「2に捧げるf」に捧げるX」」」
= 「「2に捧げる「2に捧げるf」」に捧げる「2に捧げるfに捧げる「「2に捧げるf」に捧げるX」」」
= 「「2に捧げる「2に捧げるf」」に捧げる「2に捧げるfに捧げる「2に捧げるfに捧げるX」」」
= 「「2に捧げる「2に捧げるf」」に捧げる「2に捧げるfに捧げる「fに捧げる「fに捧げるX」」」」
= 「「2に捧げる「2に捧げるf」」に捧げる「fに捧げる「fに捧げる「fに捧げる「fに捧げるX」」」」」　　（※1）

A = 「fに捧げる「fに捧げる「fに捧げる「fに捧げるX」」」」とおくと、
= 「「2に捧げる「2に捧げるf」」に捧げるA

※1、※2より、
「「2に捧げる「2に捧げるf」」に捧げるA
= 「fに捧げる「fに捧げる「fに捧げる「fに捧げるA」」」」
となることがわかる。よって、Aを代入して

= 「fに捧げる「fに捧げる「fに捧げる「fに捧げる「fに捧げる「fに捧げる「fに捧げる「fに捧げるX」」」」」」」」

これは、Xにfを8回捧げたものになっています。
よって、「3に捧げる2」は、さけるチーズ言語でいう8に等しいことになります。
ここでいう8は2の3乗を表しています。「与えられた物を3回捧げる」機能を持つものに「与えられた物を2回捧げる」機能を持つものを与えた結果、2×2×2回捧げることになった、というわけです。

リストの表現

さて、これまでで一つの数を表すことができました。しかし、文字列や数の列を扱うには、列の概念、つまりリストの概念が必要です。

まず、

PAIRに捧げるXに捧げるYに捧げるf
= fに捧げるXに捧げるY

となるような構造物PAIRを考えます。
PAIRは、具体的には

PAIR = 「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「さけるチーズを避けるチーズ」」と「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「「裂けてるチーズ」とさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と「さけるチーズを避ける「さけるチーズを避けるチーズ」」と地図のある地、伊豆」

と表すことができます。（証明はとても長いのでここでは省略します。）

ここで、PAIRにXとYのみを捧げ、fを捧げず

PAIRに捧げるXに捧げるY

で捧げ物を止めてみましょう。この構造物にはfを捧げる余地の為の禁断の者が1人含まれるため、これ以上変形できません。
これは、XとYの組(X . Y)を表しています。

A,B,C,Dのリストを作る場合、

「PAIRに捧げるAに捧げる「PAIRに捧げるBに捧げる「PAIRに捧げるCに捧げる「PAIRに捧げるDに捧げるEND」」」」

これは、(A . (B . (C . (D . END))))という、入れ子になったペアを表しています。
ここで、ENDはリストの終わりを表す特別な構造物です。冒頭にて述べたように、さけるチーズはLazy Kをベースにしているため、ENDには256を用います。
（リストに関して、詳しくは究極の関数型言語による至高のHello, world! - Life Goes On参照。）

Hello, World!

さて、ここまでの知識が揃うと、いよいよHello, World!プログラムを書くことができます。

さけるチーズでは、実行結果として残った構造物をASCII文字コードの入ったリストとして解釈し、文字列として表示します。
つまり、Hello, World!を出力するには、

(72 . (101 . (108 . (108 . (111 . (44 . (32 . (119 . (111 . (114 . (108 . (100 . (33 . 256)))))))))))))
= 「PAIRに捧げる72に捧げる「PAIRに捧げる101に捧げる「…に捧げる256」」」」…」」」」

という構造物を作れば良いのです。

ここでややこしいことに、さけるチーズ（というよりもLazy K）では「プログラムに標準入力の値が捧げられる」ため、実行時には

「PAIRに捧げる72に捧げる「PAIRに捧げる101に捧げる「…に捧げる256」」」」…」」」」に捧げる標準入力

という構造物が評価されてしまいます。
そこで、この標準入力を右から左へ受け流すため、

「さけるチーズを避けるHELLO_WORLD」

というプログラムを書きます。これによって、

「さけるチーズを避けるHELLO_WORLD」に捧げる標準入力
= 「標準入力を避けるHELLO_WORLD」
= HELLO_WORLD
⇒ Hello, World!

のように、無事Hello, World!を表示することができます。

また、数を効率的に表現するために2進法を使います：

4 = 2に捧げる2
8 = 3に捧げる2 = (2+1)に捧げる2
16 = 4に捧げる2 = (2^2)に捧げる2
32 = 5に捧げる2 = (2^2+1)に捧げる2
64 = 2に捧げる8

72 = ADDに捧げる64に捧げる8
101 = ADDに捧げる64に捧げる「ADDに捧げる32に捧げる「ADDに捧げる4に捧げる1」」
…

このようにして書いたさけるチーズによるHello, World!プログラムが以下です：

「さけるチーズを避ける「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「さけるチーズを避ける「「「裂けてるチーズ」と「さけるチーズを避ける「「「裂けてるチーズ」と「さけるチーズを避ける「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」」」と地図のある地、伊豆」と「さけるチーズを避ける「「「裂けてるチーズ」と「さけるチーズを避ける「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズと
さけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「裂けてるチーズ」」」」」と地図のある地、伊豆」と「さけるチーズを避ける「「「裂けてるチーズ」と「さけるチーズを避ける「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ
」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」」」」」と地図のある地、伊豆」と「さけるチーズを避ける「「「裂けてるチーズ」と「さけるチーズを避ける「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」」」」」と地図のある地、伊豆」と「さけるチーズを避ける「「「裂けてるチーズ」と「さけるチーズを避ける「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と
地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」のある地、伊豆」に捧げる「裂けてるチーズ」」」」」」」と地図のある地、伊豆」と「さけるチーズを避ける「「「裂けてるチーズ」と「さけるチーズを避ける「「「「
「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」」」」と地図のある地、伊豆」と「さけるチーズを避ける「「「裂けてるチーズ」と「さけるチーズを避ける「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」」と地図のある地、伊豆」と「さけるチーズを避ける「「「裂けてるチーズ」と「さけるチーズを避ける「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを
避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」のある地、伊豆」に捧げる「裂けてるチーズ」」」」」」」と地図のある地、伊豆」と「さけるチーズを避ける「「「裂けてるチーズ」と「さけるチーズを避ける「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と
「裂けてるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」のある地、伊豆」に捧げる「裂けてるチーズ」」」」」」」と地図のある地、伊豆」と「さけるチーズを避ける「「「裂けてるチーズ」と「さけるチーズを避ける「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける
「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」」」」」と地図のある地、伊豆」と「さけるチーズを避ける「「「裂けてるチーズ」と「さけるチーズを避ける「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「「「さけるチーズを避ける「チーズとさけるチー
ズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」」」」」と地図のある地、伊豆」と「さけるチーズを避ける「「「裂けてるチーズ」と「さけるチーズを避ける「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」と「「「さけるチーズを避け
る「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」」」」と地図のある地、伊豆」と「さけるチーズを避ける「「「裂けてるチーズ」と「さけるチーズを避ける「「「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」に捧げる「裂けてるチーズ」」」と地図のある地、伊豆」と「さけるチーズを避ける「「裂けてるチーズ」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」のある地、伊豆」」と地図のある地、伊豆」」と地図のある地、伊豆」」と地図のある地、伊豆」」と地図のある地、伊豆」」と地図のある地、伊豆」」と地図のある地、伊豆」」と地図のある地、伊豆」」と地図のある地、伊豆」」と地図のある地、伊豆」」と地図のある地、伊豆」」と地図のある地、伊豆」」と地図のある地、伊豆」」と地図のある地、伊豆」」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と地図のある地、伊豆」」

結論：さけるチーズを避けるチーズでプログラミングをすることができる

あとがき

今回は、さけるチーズによる自然数の表現、加算と累乗計算、リストの表現、そしてHello, World!プログラムについて解説しました。
累乗以外にも加減乗除など様々な演算を行うことができます。さけるチーズはチューリング完全であるため、数にまつわる演算ならばいかなるものでも行うことができます。今回、Lazy Kの計算能力や方法には度々驚かされました。特に、404 Blog Not Found:Math - 言語はどこまで小さくなれるか - (unlambda|iota|jot) のすすめや究極の関数型言語による至高のHello, world! - Life Goes Onなどが非常に参考になります。

さけるチーズやLazy K自体を書くことは難しいのですが、究極の関数型言語による至高のHello, world! - Life Goes Onにあるように、Scheme内のDSLで記述したプログラムに対応するLazy Kコードを出力するプログラムがあり、それを用いると非常にさけるチーズ（Lazy K）開発が捗ります。

また、この記事の執筆にあたって筆者が最も嵌ったのは、Lazy Kではチャーチ数そのものを出力に用いることができず、単一の数字でも、必ずリストに入れて出力しなければいけないという事です。
例えば、65という数字（ASCIIのAに対応）を出力したい時、チャーチ数の65を使うと出力されず、

PAIRに捧げる65に捧げるEND

という65を唯一の要素に持つリストを出力しなければなりません。
これは仕様にしっかりと書いてあることなのですが、そもそもSKIコンビネータ計算におけるリストとは何なのか、という点から調べる必要があり、苦労しました。

付録 - さけるチーズとLazy Kの相互翻訳

まず、Lazy Kからさけるチーズに翻訳する場合、

1. SXYZ → 「XとYとZのある地、伊豆」
2. KXY　→　「Yを避けるX」　　（※YとXが逆な事に注意！これは、演算子の日本語的な意味を保存するため）
3. IX　→　「裂けてるX」
4. (式)XYZ　→　「「式」に捧げるAに捧げるBに捧げるC」

4つ目の式が一番特徴的で、関数適用を「に捧げる」の文法で表しています。

これを踏まえた上で、さけるチーズからLazy Kに翻訳する場合、

「XとYと地図のある地、伊豆」　→ (SXY)
裂けてる「Xを避けるチーズ」　→　I(KX)
「XとYと地図のある地、伊豆」に捧げるZ　→　(SXY)Z

のように、禁断の者（チーズ、さけるチーズ、地図）を空のコンビネータで置き換えることで翻訳が可能になります。
最後の「に捧げる」を用いた翻訳が最大のポイントで、これはコンビネータSXY（つまりラムダ式 λ a. SXYa ）にZを適用したものであるためこうなっています。言い換えると、禁断の者がラムダ計算における束縛変数を表していて（つまり「XとYと地図のある地、伊豆」 = λ Z. SXYZ）、更にLazy Kでは関数適用はコンビネータの直後に引数を置くだけで行えるということが、この翻訳の原理になっています。

参考文献

裂けてるさけるチーズを裂けて避けるチーズが載ってる裂けてる地図を裂けて避けるチーズ - Togetterまとめ
 The Lazy K Programming Language
究極の関数型言語による至高のHello, world! - Life Goes On
404 Blog Not Found:Math - 言語はどこまで小さくなれるか - (unlambda|iota|jot) のすすめ
 Lazy K Playground - iroriの日記
 Lazy K Playground
Lazy K - Wikipedia
Combinatory logic - Wikipedia, the free encyclopedia
B,C,K,Wシステム - Wikipedia
Lazy aKari：わぁいLazy K あかりLazyKインタプリタだいすき | ψ（プサイ）の興味関心空間
 The SKI Combinator Calculus a universal formal system

2016-03-12

さけるチーズを避けるチーズで作る関数型言語

Functional Programming

最近、「裂けてるさけるチーズを裂けて避けるチーズが載ってる裂けてる地図を裂けて避けるチーズ」が話題になりました。
togetter.com

「さけるチーズを避けるチーズ」において、チーズがさけるチーズを避けた結果、残るのはチーズ。
「さけるチーズを避けるチーズを避ける地図」において、さけるチーズとチーズが避けられた結果、残るのは地図。
では「裂けてるさけるチーズを裂けて避けるチーズが載ってる裂けてる地図を裂けて避けるチーズ」の「事の果て」には、何が残るのか？
この記事では、そのような疑問を追うこと、つまりさけるチーズや地図が従う法則を追う行為によって、チューリング完全な純粋関数型言語「さけるチーズ」を構成します。

（具体的には、Lazy Kと呼ばれる言語に束縛変数を導入することでラムダ計算風にし、自然言語的に意味が通るように中置記法に改めたものです。）

例えば以下は、さけるチーズで記述した素数を無限に出力し続けるプログラムです。

「さけるチーズを避ける「「裂けてるチーズ」と「裂けてるチーズ」と「「さけるチーズを避ける「「「さけるチーズを避ける「「裂けてるチーズ」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」とさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「「チーズとさけるチーズと地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」と「さけるチーズを避ける「さけるチーズを避けるチーズ」」のある地、伊豆」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「さけるチーズを避けるチーズ」」と「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「「「さけるチーズ
を避ける「チーズとさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「さけるチーズを避けるチーズ」」と「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「さけるチーズを避けるチーズ」」と「「裂けてるチーズ」と「裂けてるチーズ」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と「さけるチーズを避ける「「裂けてるチーズ」と「さけるチーズを避ける「さけるチーズを避けるチーズ」」と地図のある地、伊豆」」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と「さけるチーズを避ける「「さけるチーズを避ける「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「「裂けてるチーズ」とさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「さけるチーズを避けるチーズ」」と「「さけるチーズを避ける「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」
と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」と「「「裂けてるチーズ」と「裂けてるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」「に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」のある地、伊豆」」と「「裂けてるチーズ」と「さけるチーズを避ける「さけるチーズを避ける「裂けてるチーズ」」」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「さけるチーズを避けるチーズ」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と地図のある地、伊豆」
」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と「さけるチーズを避ける「「さけるチーズを避ける「さけるチーズを避けるチーズ」」と「「「裂けてるチーズ」と「さけるチーズを避ける「「「「「「チーズとさけるチーズと地図のある地、伊豆」と「さけるチーズを避けるチーズ」と「「裂けてるチーズ」と「さけるチーズを避ける「さけるチーズを避ける「裂けてるチーズ」」」と地図のある地、伊豆」のある地、伊豆」と「さけるチーズを避ける「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」と地図のある地、伊豆」のある地、伊豆」「「に捧げる「「さけるチーズを避ける「「「裂けてるチーズ」と「さけるチーズを避ける「さける
チーズを避ける「裂けてるチーズ」」」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」」に捧げる「さけるチーズを避ける「さけるチーズを避けるチーズ」」」」と地図のある地、伊豆」と「さけるチーズを避ける「さけるチーズを避けるチーズ」」と地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「「裂けてるチーズ」とさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「さけるチーズを避けるチーズ」」と「「さけるチーズを避ける「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」と「「裂けてるチーズ」と「さけるチーズを避ける「さけるチーズを避けるチーズ」」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と「さけるチーズを避ける「さけるチーズを避ける「さけるチーズを避ける「裂けてるチーズ」」」」と地図のある地、伊豆」と
地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「「裂けてるチーズ」とさけるチーズと地図のある地、伊豆」」と「「チーズとさけるチーズと地図のある地、伊豆」と「「裂けてるチーズ」とさけるチーズと地図のある地、伊豆」と「さけるチーズを避ける「さけるチーズを避けるチーズ」」のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と「「さけるチーズを避ける「さけるチーズを避けるチーズ」」と「「さけるチーズを避ける「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」と「「裂けてるチーズ」と「さけるチーズを避ける「さけるチーズを避ける「裂けてるチーズ」」」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」」と地図のある地、伊豆」と「さけるチーズを避ける「さけるチーズを避ける「さけるチーズを避ける「裂けてるチーズ」」」」と地図のある地、伊豆」と地図のある地、伊豆」」と地図のある地、伊
豆」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と「さけるチーズを避ける「さけるチーズを避ける「裂けてるチーズ」」」と地図のある地、伊豆」のある地、伊豆」」と「「裂けてるチーズ」と「さけるチーズを避ける「さけるチーズを避けるチーズ」」と地図のある地、伊豆」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「「さけるチーズを避ける「「さけるチーズを避ける「「「裂けてるチーズ」と「さけるチーズを避ける「「さけるチーズを避ける「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」」と「「「裂けてるチーズ」と「裂けてるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」のある地、伊豆」と地図のある地、伊豆」」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」と「さけるチーズを避
けるチーズ」と地図のある地、伊豆」」とさけるチーズと地図のある地、伊豆」」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「さけるチーズを避けるチーズ」」と「「裂けてるチーズ」と「裂けてるチーズ」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と「さけるチーズを避ける「「裂けてるチーズ」と「さけるチーズを避ける「さけるチーズを避ける「裂けてるチーズ」」」と地図のある地、伊豆」」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」のある地、伊豆」「に捧げる「「裂けてるチーズ」と「裂けてるチーズ」と「「さけるチーズを避ける「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「「「「裂けてるチーズ」と「さけるチーズを避ける「さけるチーズを避けるチーズ」」と地図のある地、伊豆」と「さけるチーズを避ける「裂けてるチーズ」」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」と「「チーズとさけるチーズと地図のある地、伊豆」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊
豆」」と「「さけるチーズを避ける「さけるチーズを避けるチーズ」」と「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「「裂けてるチーズ」とさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」と「さけるチーズを避ける「さけるチーズを避けるチーズ」」のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」とさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「「さけるチーズを避ける「さけるチーズを避けるチーズ」」とさけるチーズと地図のある地、伊豆」」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「さけるチーズを避けるチーズ」」と「「裂けてるチーズ」と「裂けてるチー
ズ」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と「さけるチーズを避ける「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と「さけるチーズを避ける「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「「「「裂けてるチーズ」と「さけるチーズを避ける「さけるチーズを避けるチーズ」」と地図のある地、伊豆」と「さけるチーズを避ける「裂けてるチーズ」」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「さけるチーズを避けるチーズ」」と「「さけるチーズを避ける「「裂けてるチーズ」と「裂けてるチーズ」と「「さけるチーズを避ける「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「「さけるチーズを避ける「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「「さけ
るチーズを避ける「さけるチーズを避けるチーズ」」と「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「「裂けてるチーズ」とさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と「さけるチーズを避ける「さけるチーズを避けるチーズ」」と地図のある地、伊豆」」とさけるチーズと地図のある地、伊豆」」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「さけるチーズを避けるチーズ」」と「「さけるチーズを避ける「「裂けてるチーズ」と「さけるチーズを避ける「さけるチーズを避けるチーズ」」と地図のある地、伊豆」」と「「裂けてるチーズ」と「さけるチーズを避ける「さけるチーズを避けるチーズ」」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と「さけるチーズを避ける「「裂けてるチーズ」と「さけるチーズを避ける「さけるチーズを避けるチーズ」」と地図のある地、伊豆」」と地図のある地、伊豆」と地図のある地、
伊豆」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」とさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「「さけるチーズを避ける「さけるチーズを避けるチーズ」」とさけるチーズと地図のある地、伊豆」」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「さけるチーズを避けるチーズ」」と「「裂けてるチーズ」と「裂けてるチーズ」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と「さけるチーズを避ける「「裂けてるチーズ」と「さけるチーズを避ける「さけるチーズを避ける「裂けてるチーズ」」」と地図のある地、伊豆」」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と「さけるチーズを避ける「さけるチーズを避ける「「裂けてるチーズ」と「さけるチーズを避ける「さけるチーズを避ける「裂けてるチーズ」」」と地図のある地、伊豆」」」と地図のあ
る地、伊豆」と地図のある地、伊豆」のある地、伊豆」」と「「さけるチーズを避ける「「裂けてるチーズ」と「裂けてるチーズ」と地図のある地、伊豆」」と「「さけるチーズを避ける「「さけるチーズを避ける「「裂けてるチーズ」と「さけるチーズを避ける「さけるチーズを避ける「裂けてるチーズ」」」と地図のある地、伊豆」」とさけるチーズと地図のある地、伊豆」」と「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「さけるチーズを避けるチーズ」」と「「裂けてるチーズ」と「さけるチーズを避ける「「さけるチーズを避ける「「「裂けてるチーズ」と「さけるチーズを避ける「さけるチーズを避ける「裂けてるチーズ」」」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と「さけるチーズを避ける「「さけるチーズを避ける「「「裂けてるチーズ」と「さけるチーズを避ける「さけるチーズを避けるチーズ」」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける
「さけるチーズを避けるチーズ」」と「「裂けてるチーズ」と「裂けてるチーズ」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と「さけるチーズを避ける「「裂けてるチーズ」と「さけるチーズを避ける「さけるチーズを避ける「裂けてるチーズ」」」と地図のある地、伊豆」」と地図のある地、伊豆」」と地図のある地、伊豆」と地図のある地、伊豆」のある地、伊豆」「「に捧げる「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と「裂けてるチーズ」と地図のある地、伊豆」」に捧げる「「裂けてるチーズ」と「裂けてるチーズ」と「「さけるチーズを避ける「「さけるチーズを避ける「「「裂けてるチーズ」と「さけるチーズを避ける「さけるチーズを避ける「裂けてるチーズ」」」と地図のある地、伊豆」とさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」」と「「裂けてるチーズ」と「
裂けてるチーズ」と地図のある地、伊豆」と地図のある地、伊豆」のある地、伊豆」」」」

（The Lazy K Programming LanguageのSample Codeをさけるチーズに変換しました。）

このチーズ達の「せめぎ合い」の果てに何が残るのか、それを探す過程が素数を求める事に対応するのです。
さけるチーズはチューリング完全であるため、これほど単純な文法を持ちながら、素数計算に限らず、計算機上で実行できるいかなる計算も実行することができます。

自然数すら現れないこのコードで、なぜ素数が計算できるのか…？本当にそうなのか？という疑問に答えるため、この記事では上記のコードを実際に実行するために必要なツールを用意しました。「さけるチーズ」は「Lazy K」と呼ばれる言語をベースにしているため、今回はさけるチーズ → Lazy K 翻訳器と Lazy K → さけるチーズ翻訳器を構成しました。上記のコードを実際に実行するには、翻訳器によってさけるチーズをLazy Kに翻訳し、Lazy Kインタプリタ（たとえば http://lazy-k.appspot.com/ など）を使用して下さい。（インタプリタ作成は今回は割愛しました。）翻訳器はGitHub - woodrush/ski2cheese: 純粋関数型言語「さけるチーズ」とLazy Kの相互翻訳器に載せています。

では、さけるチーズとはどのような言語なのでしょうか。

さけるチーズにおける4つの法則

世の中には数多の言語が存在し、それぞれ複雑な構文や規則を持っています。しかし、さけるチーズに存在するのはたった4つの構文です。
それは、

1. 「さけるチーズを避けるチーズ」
2. 「裂けてるチーズ」
3. 「Xに捧げるY」
4. 「チーズとさけるチーズと地図のある地、伊豆」

の4つです。
そしてこの言語の唯一の原則は、以上の語句が現れたタイミングで、自然の摂理に従った置き換えを行うという事です。

第一法則：さけるチーズを避けるチーズ

さけるチーズを避けるチーズ pic.twitter.com/RiBCo7SCNO
— ぽかり氏 (@riricc1998) March 5, 2016

まずは「さけるチーズを避けるチーズ」。
「Yを避けるX」という語句が現れたら、「X」に置き換えます。
なぜならば、YはXに避けられ、結果としてXが残るからです。これが第一の法則です。

例えば

「「Yを避けるX」を避けるZ」を避ける「Aを避ける「Bを避けるC」」

という構造物は、第一の法則に従って

「「Yを避けるX」を避けるZ」を避ける「Aを避ける「Bを避けるC」」
= 「Aを避ける「Bを避けるC」」
= 「Bを避けるC」
= C

のように変形できるため、「「Yを避けるX」を避けるZ」を避ける「Aを避ける「Bを避けるC」」の実行結果（評価結果）はCという事になります。

第二法則：裂けてるチーズ

@riricc1998 さけるチーズを裂けて避けるチーズ pic.twitter.com/MTKD47tnBW
— びすますですぷらとぅーん (@BismuthForever) March 5, 2016

続いて、「裂けてるチーズ」です。
「裂けてるX」という語句が現れたら、「X」に置き換えます。
なぜならば、裂けたXはやがて自らの力で修復され、元に戻るからです。これが第二の法則です。

例えば、

「「Yを避けるX」を避けるZ」を避ける「裂けてる「Aを避ける「「裂けてるB」を避ける「裂けてるC」」」」

は、第一・第二の法則を合わせて

「「Yを避けるX」を避けるZ」を避ける「裂けてる「Aを避ける「「裂けてるB」を避ける「裂けてるC」」」」
= 「裂けてる「Aを避ける「「裂けてるB」を避ける「裂けてるC」」」」
= 「Aを避ける「「裂けてるB」を避ける「裂けてるC」」」
= 「裂けてるB」を避ける「裂けてるC」
= 「裂けてるC」
= C

となり、「「Yを避けるX」を避けるZ」を避ける「裂けてる「Aを避ける「「裂けてるB」を避ける「裂けてるC」」」」の実行結果はCとなります。

第三法則：Xに捧げるY

さて、ここで事態は少し複雑になります。
この構文を説明する前に、この世界（言語）に関する重要な定めについて話す必要があります。それは、この世界には触れてはならぬ禁断の者が3人存在するということです。彼らはすなわち、「さけるチーズ」「チーズ」「地図」です。
そして実は、先ほどの第一、第二の法則、そして続く第四の法則では、これら禁断の者本人が存在する場合、置き換えを行ってはなりません。
例えば、

「Aを避ける「Bを避けるチーズ」」
= 「Bを避けるチーズ」
≠ チーズ　　（※禁断の者を含む構造物を変形してはいけない！）

と変形されます。
まず、一行目から二行目の変形は許されています。「Bを避けるチーズ」は禁断の者本人ではないため、「Aを避ける「Bを避けるチーズ」」は変形が可能なのです。
しかし、第二行目において「チーズ」は禁断の者であることから、これ以上変形ができません。

同様に、

裂けてる「「裂けてるチーズ」を避ける「Aを避ける「「裂けてるチーズ」を避けるチーズ」」」
= 「裂けてるチーズ」を避ける「Aを避ける「「裂けてるチーズ」を避けるチーズ」」
= 「Aを避ける「「裂けてるチーズ」を避けるチーズ」」
= 「裂けてるチーズ」を避けるチーズ
≠ チーズ　　（※禁断の者を含む構造物を変形してはいけない！）

のようになります。最後の一つ手前の行では、構造物が禁断の者チーズを含んでいるためこれ以上変形できません。

さて、ここで「Xを捧げるY」という構文が登場します。
「Xを捧げるY」は、「Xに含まれる最強の禁断の者を、Yで置き換える」という規則です。
禁断の者たちの強さの順番は、禁断の者の強さの順は「チーズ＞さけるチーズ＞地図」となっています。

例えば、

「さけるチーズを避けるチーズ」に捧げるXに捧げるY
= 「さけるチーズを避けるX」に捧げるY
= 「Yを避けるX」
= X

となり、この構造物の値はXとなります。
また、

「Aを避ける「Bを避けるチーズ」」に捧げるX
= 「Bを避けるチーズ」に捧げるX
= 「Bを避けるX」
= X

となります。
１行目から２行目の変形では、第一項（「Aを避ける「Bを避けるチーズ」」）の最上層部には禁断の者は存在しないため、「に捧げるX」は発動しません。
第二項内部の第二項「チーズ」は、１行目の最上層には存在しないため、禁断の者としてカウントされません。
しかし２行目にたどり着くと、第一項（「Bを避けるチーズ」）が変形できない形になっています。
ここで、「に捧げるX」という構文によって、２行目から３行目にかけて禁断の者チーズがXに置き換えられました。
そして第一の法則によって、最終的にこの値はXとなっています。

また、捧げ物同士で捧げあってはいけません。例えば、

「さけるチーズを避けるチーズ」に捧げるXに捧げるY
= Yを避けるX　　（※正しい変形）

「さけるチーズを避けるチーズ」に捧げるXに捧げるY
≠ 「さけるチーズを避けるチーズ」に捧げる「Xに捧げるY」　（※間違い！）
= さけるチーズを避ける「Xに捧げるY」　（※結果が正しい変形の場合と異なってしまっている）

ということです。（つまり、「〜に捧げる」は左結合な演算子です。）

（補足）
禁断の者を、以下のように空欄で置き換えると、この法則が明快になります。

「裂けてる「「裂けてるチーズ」を避ける「さけるチーズを避ける「さけるチーズを避けるチーズ」」」」に捧げるXに捧げるY
↓
「裂けてる「「裂けてる__1」を避ける「__1を避ける「__2を避ける__1」」」」に捧げるXに捧げるY

この構造物は、

「裂けてる「「裂けてる__1」を避ける「__1を避ける「__2を避ける__1」」」」に捧げるXに捧げるY
= 「「裂けてる__1」を避ける「__1を避ける「__2を避ける__1」」」に捧げるXに捧げるY
= 「__1を避ける「__2を避ける__1」」に捧げるXに捧げるY
= 「Xを避ける「__2を避ける__1」」に捧げるY
= 「__2を避ける__1」に捧げるY
= 「__2を避けるY」

と変形されます。
つまり、禁断の者に関するルールは、最上層に空欄が存在する構造物は変形してはいけないという事になります。

第四法則：「チーズとさけるチーズと地図のある地、伊豆」

さて、この法則がさけるチーズにおいて最も複雑な法則になります。
神聖なる地、伊豆では、古来から物を捧げる文化が発達してきました（要出典）。
そんな伊豆にまつわる第四の法則における変換規則は

「XとYとZのある地、伊豆」
= Xに捧げるZに捧げる「Yに捧げるZ」

です。
例えば、

「「さけるチーズを避けるチーズ」と「さけるチーズを避けるチーズ」と「裂けてるチーズ」のある地、伊豆」
= 「さけるチーズを避けるチーズ」に捧げる「裂けてるチーズ」に捧げる「さけるチーズを避けるチーズ」
= 「さけるチーズを避ける「裂けてるチーズ」」に捧げる「さけるチーズを避けるチーズ」
= 「「さけるチーズを避けるチーズ」を避ける「裂けてるチーズ」」
= 裂けてるチーズ

となり、答えは「裂けてるチーズ」となります。

さけるチーズによるプログラミング

さけるチーズの全ての文法が出揃った所で、さけるチーズによる実際のプログラミング方法を解説しながら、さけるチーズで実際にプログラミングが可能であることを示したいと思います。
具体的には、

自然数の表現
加算と累乗
リストの表現
Hello, World!プログラム

を扱います。
続きは、次の記事で！
woodrush.hatenablog.com

参考文献

裂けてるさけるチーズを裂けて避けるチーズが載ってる裂けてる地図を裂けて避けるチーズ - Togetterまとめ
 The Lazy K Programming Language （素数出力プログラムの出典）
究極の関数型言語による至高のHello, world! - Life Goes On
404 Blog Not Found:Math - 言語はどこまで小さくなれるか - (unlambda|iota|jot) のすすめ
 Lazy K Playground - iroriの日記
 Lazy K Playground
Lazy K - Wikipedia
Combinatory logic - Wikipedia, the free encyclopedia
B,C,K,Wシステム - Wikipedia
Lazy aKari：わぁいLazy K あかりLazyKインタプリタだいすき | ψ（プサイ）の興味関心空間
 The SKI Combinator Calculus a universal formal system

ガチャの数

Analytic Combinatoricsスライド

Analytic Combinatorics本

Babbageから現代まで

前提知識

3x3x3 ルービックキューブの解き方

3x3x3 ルービックキューブの配色

記法

知っていると役立つ知識

CommutatorとConjugate

登場するアルゴリズムのまとめ

中心2x2マスを揃える時の基本動作

辺を揃える時の基本動作

最後の1辺のパーツの入れ替え

1本のdedgeを反転する（OLL parityの解消）

対面するdedge同士を反転する（PLL parityの解消）

解き方

おまけ

パリティの詳細

CommutatorとConjugateの詳細

モード

ポケモンWordle関連記事

Credits

ポケモン名前当てゲーム「Pokedle」「ポケモンWordle」

原作：Wordle

問題設定

目次

番外編先行研究 - その日つぶやかれたWordleのパネル列からその日の単語を一発で推定する方法

ポケモンWordleの有効初手の考察 - 準備

データの収集

ポケモンWordleにおけるパネルのフィードバックのルール

分割の質

分割の質を測るエントロピー

どのような分割がエントロピーを最大化するか

初手に一番良いポケモンは何か？エントロピーによる考察

上記の表のエントロピーは初手においてのみ有効

Pokedleにおけるエントロピーの計算

「ピカチュウ」という名前の構成音の珍しさ

最後に

付録

Pokedleのデータの収集

Pokedleにおけるパネルのフィードバックのルール

自然数の表現

加算と累乗

リストの表現

Hello, World!

あとがき

付録 - さけるチーズとLazy Kの相互翻訳

参考文献

さけるチーズにおける4つの法則

第一法則：さけるチーズを避けるチーズ

第二法則：裂けてるチーズ

第三法則：Xに捧げるY

第四法則：「チーズとさけるチーズと地図のある地、伊豆」

さけるチーズによるプログラミング

参考文献