0.予防線
(※ MAOというゲームを知っている人は3からどうぞ。)
(※ この記事はネタバレを多く含みます。)
(※ 前半のわからない人にも説明する部分がわかりにくいかもしれません。また、マルコフアルゴリズムそのものの説明をきちんとしていないです。）
(※ 基本感想ベースなのでですます調ではありません。偉そうです。）
(※ なんか間違ってたら教えてください。）
1.謎のパズルゲーム
最近「MAO」というワードが僕のTLでちょこちょこみられるなあと思っていた。
MAOと言っても市道真央さんのことでもなければドラえもんの曲歌ってる歌手でもなければ漫画のタイトルでもない。
どうもMarkov algorithmというアルゴリズム(ウィキペディア説明)をもとにしたゲームらしい。ここでそのゲームをプレーできる。
全くわからない人のためにめちゃくちゃ雑に説明すると
「文字列を変換する規則を作成してお題に答える」というものである。全くわからない人が読んでも全くわからないままな気がする表現だけど。
作った規則は「マルコフアルゴリズム」と呼ばれるものに基づいて動作する。
このマルコフアルゴリズムの考案者は機械学習とかやってる人だとよく耳にする「マルコフ連鎖」の考案者の息子らしい。
マルコフアルゴリズム自体の性質や論文などは興味がある人が各自調べてもらうこととして、（僕も詳しくは知らない）
MAOというゲームにおいては「規則の個数」が評価項目であり、これを少なくすることが最終目標になる。もちろん最初の目標は解くことだけど。
ゲーム上の記述としては以下の二種類のみ
コロンが一つか二つか、の違いである。それぞれ
という意味になる。
これらの規則を自分で作っていくことになる。
最初聞いたときはSAOの親戚かと思ったけど全く関係ないし結構頭使いそうなゲームなんだな？
2.どんな問題があるの
・文字列を複製する
・文字列が回文かどうか判定する
・足し算や掛け算
などがある。意外といろいろできちゃう。
正直筆者はトップページにあるルールっぽいものを読んでも全然ピンとこなかったので数問やるのがお勧め。
あとはyoutubeにいくつか動画あるのでそれを参照するのも良いかも
��catupperさんの動画:https://www.youtube.com/watch?v=iMyB4ZCAnuA
解いてみた動画。最初に雑な説明あり。
��snukeさんの動画:https://www.youtube.com/watch?v=Pgf2cO9iz44
解説動画。
まあ最初の方の問題は答えも見れちゃうのでそれをみながら理解するのが一番楽しい。各問題のSolversとかかれた部分の一番下にSpoilerというボタンがあるので、これを押すと天才の解をカンニングできる。（ただし公開されるまでラグがある）
筆者は「プログラミングっぽいルールに基づいてあるパラメーターを最適にする」というパズルゲームとしてHOJ(http://herbert.tealang.info/ )やTGO(http://snuke.main.jp/turing/)にもすこし馴染みがあるのだが、
それらと比べると（現時点では）様々な入力に対応するという点で競技プログラミング要素が強く、問題を解くだけであれば平易だが、最適化には幅広い発想が必要になる、という印象を持っている。また、MAOは「操作を終了させた状態で出力を達成する」必要があり、正解状態が遷移に含まれているだけではダメという性質がある。
3.Min Digitという問題
この記事ではMAOのMin Digitという問題にのみ触れる。
問題ページはここ
というもの。
たとえば
といった具合である。このゲームの特徴として、あらゆる入力に対してその入力に応じた出力をする必要がある。
できればこの問題にある程度時間を割いてから以降を読んだ方が良いと思う。
実際筆者もこれほどいろいろやりようがある問題とは思っておらず、人の答えをガンガンみてしまったことをやや後悔しているので。
4.各種アプローチから見るこの問題の奥深さ
⓪~�イ力擦直匆陲垢襦５�則の行数は
である。
前にも書いたように以降ネタバレを非常に多く含む。
逆に始めたてと言う人はこれをみてこのゲームの面白さが伝わると嬉しい。
⓪原始的な解(25行)
隣り合う数字としてありうる組は25通りで、それぞれ小さい方を指定することで最小値を抽出できる。
こう言う愚直な書き方も大事ではある。各規則は何度も繰り返されるのでこれでうまく行く。
�”�者がなんとか思いついた解(17行)
数字列をソートした後、一番左以外全て消す という動作をがんばって書く。
・ソートに関してはバブルソートっぽいことができる（逆順のものを元に戻す規則を並べる）ため可能
・一番左以外全て消すことに関してはカーソル（チューリングっぽくいうとヘッド？）という技術を使用することでうまくいく。やや雑に言うと全く関係のない文字を追加しその文字との関係を記述することで左から順に操作を行うと言うもの。終了条件の記述も楽になる。
実はこれでは原始的なものとあまり差のないコードとなるため、重要な考察として、答えが5になる数字列は入力が全て5だった場合のみという性質に着目する。予め5を消しておけばソートに関する規則数が減り、行数を減らせる。以下の通り。アンダーバー'_'をカーソルとして使用している。
��snukeさんが放送で紹介していた解(16,15行)
マルコフアルゴリズムでは規則を上から順に実行する。
そこで、1を見つけたらその1の左右に印をつける→2を見つけたら左右に印をつける→…
という具合に規則を上から順に書くと初めて印がついたところが最小値、すなわち答えとなる。
この規則よりも前につけた印に依存した記述をする（具体的には左側と右側を消す）ことにより先ほど印をつけた数字のみが残り、印を消して停止することで答えとなる。
マルコフアルゴリズムでは文字列を左から順にチェックしていく性質があるため、
印よりも左には印をつけた数よりも大きなものしかない。よって「印より左の1を消す」は不要となる。
最後に先ほどの5の処理と同様のことを行うことで15行になる。以下の通り。この解に限らず言えることだが、わかりやすい文字を使うのは重要かもしれない。
<>をつけるのはわかりやすい。
��すこし天才的な発想に基づく解(12行)
「全ての文字に1を加えるという変換を行い、5に対しては削除する。」という操作を考える。
一度変換を行うごとにカウンター用の文字を蓄積させ、数字の列が空になった時のカウンターの数に応じて答えを出力するというもの。
操作そのものはカーソルの技術を使用すれば綺麗にかけて、
マルコフアルゴリズムの性質をふんだんに生かしていると言える。
前半が「全ての文字に1を加えるという変換を行い、5に対しては削除する。」
後半が「数字が空になった時のカウンターの状況に応じた答え」
最初に「判定用の動かないカーソル（動くカーソルを生やすカーソル生成機も兼任）」と「操作用の動くカーソル」を付与するのがポイントか
�い�なり天才的な発想に基づく解(11行)
実は数字x,yに対して小さい方を一律で計算する規則を以下のように作成することができる。
xをx個の+、x個の-に分解し、yをy個の+、y個の-に分解する。
+++---+++++----- (x=3,y=5の例)
この時-+という文字列を次々に消していくと、
+++---+++++----- -> +++--++++----- -> +++-+++----- -> +++++-----
なんとmax(x,y)個の+とmax(x,y)個の-が残るということが言える！
これではmaxになってしまうので、1>2>3>4>5となるように順序づけしなおせばminとなる(xに対し5-x個の+と5-x個の-を並べる）
答え見た時めちゃくちゃ感動した。
�サ蚕僖皀螢皀蠅硫�(=sugim48さんの解)(11行)
Top勢の解はほとんど全員�い世辰燭�よく見ると1人だけ異質な解を投稿している人がいた。sugim48さんである。
今回は先に解を貼る。(説明の都合上、実際のsugim48さんの解の一部の記号を変更した。)
仕組みに関しては実は��と全く同じで、��に書いたコードのうちx:x_(動くカーソルを生成する部分)と:x_(二つのカーソルを生成する部分)がよくわからない形に削減されている。��で紹介した操作を行う「動くカーソル」は健在で、カーソル生成機であったxが不在であり、その代わり動くカーソルの右に謎の数字列を追加している。
ひとまず_以外の文字列をxとおく。そもそも��の解は以下のように書き換えられる
最後の部分を少し変えた。xがカーソル_生成機ではなくカーソル_のストッパーになっている仕組みはほぼ同じである（この辺の変換の理論をあまりまだ持っていないので天下りである…）
課題としては「既存の規則で_x:_的なことを自動で行う」ことで1行削減するというところである。
カーソルによって発生する文字列変換の関数をfとする。
_string -> f(string)_
という変化をするというイメージである。xとして数字列を使用できれば既存の規則が適用できる。
_x -> f(x)_
と変化しこれに_xを追加した _xf(x)_を終了条件としたい。さらにこの文字列に_が作用すると
f(x)f(f(x))__となる。これを繰り返すと、終了条件として
_xf(x)f(f(x))f(f(f(x)))f(f(f(f(x))))f(f(f(f(f(x)))))_____:1
_xf(x)f(f(x))f(f(f(x)))f(f(f(f(x))))____:2
_xf(x)f(f(x))f(f(f(x)))___:3
_xf(x)f(f(x))__:4
_xf(x)_:5
としてしまえば良いことがわかる。これにより、xを適当な数字列にして当てはめれば解を得る。
（実際に本人がどのように考えたかは不明）
この性質をそれっぽく活かした答えも一応書いておく。
(ちょっと考察不足で申し訳ないのですがxは任意ではないようですね…)
以上がMin Digitという問題の様々な解法である。この問題一つだけでたくさんの技術が詰まっていてびっくりした。あれこれ試すのも楽しい上に、他にも人の答え見るだけで天才かってなる問題が沢山あって面白いので本当にオススメのゲーム。
(※ MAOというゲームを知っている人は3からどうぞ。)
(※ この記事はネタバレを多く含みます。)
(※ 前半のわからない人にも説明する部分がわかりにくいかもしれません。また、マルコフアルゴリズムそのものの説明をきちんとしていないです。）
(※ 基本感想ベースなのでですます調ではありません。偉そうです。）
(※ なんか間違ってたら教えてください。）
1.謎のパズルゲーム
最近「MAO」というワードが僕のTLでちょこちょこみられるなあと思っていた。
MAOと言っても市道真央さんのことでもなければドラえもんの曲歌ってる歌手でもなければ漫画のタイトルでもない。
どうもMarkov algorithmというアルゴリズム(ウィキペディア説明)をもとにしたゲームらしい。ここでそのゲームをプレーできる。
全くわからない人のためにめちゃくちゃ雑に説明すると
「文字列を変換する規則を作成してお題に答える」というものである。全くわからない人が読んでも全くわからないままな気がする表現だけど。
作った規則は「マルコフアルゴリズム」と呼ばれるものに基づいて動作する。
このマルコフアルゴリズムの考案者は機械学習とかやってる人だとよく耳にする「マルコフ連鎖」の考案者の息子らしい。
マルコフアルゴリズム自体の性質や論文などは興味がある人が各自調べてもらうこととして、（僕も詳しくは知らない）
MAOというゲームにおいては「規則の個数」が評価項目であり、これを少なくすることが最終目標になる。もちろん最初の目標は解くことだけど。
ゲーム上の記述としては以下の二種類のみ
文字列1 : 文字列2
文字列1 :: 文字列2
コロンが一つか二つか、の違いである。それぞれ
「文字列1が含まれていたら文字列2に書き換える」
「文字列1が含まれていたら文字列2に書き換え、操作を終了する」
という意味になる。
これらの規則を自分で作っていくことになる。
最初聞いたときはSAOの親戚かと思ったけど全く関係ないし結構頭使いそうなゲームなんだな？
2.どんな問題があるの
・文字列を複製する
・文字列が回文かどうか判定する
・足し算や掛け算
などがある。意外といろいろできちゃう。
正直筆者はトップページにあるルールっぽいものを読んでも全然ピンとこなかったので数問やるのがお勧め。
あとはyoutubeにいくつか動画あるのでそれを参照するのも良いかも
��catupperさんの動画:https://www.youtube.com/watch?v=iMyB4ZCAnuA
解いてみた動画。最初に雑な説明あり。
��snukeさんの動画:https://www.youtube.com/watch?v=Pgf2cO9iz44
解説動画。
まあ最初の方の問題は答えも見れちゃうのでそれをみながら理解するのが一番楽しい。各問題のSolversとかかれた部分の一番下にSpoilerというボタンがあるので、これを押すと天才の解をカンニングできる。（ただし公開されるまでラグがある）
筆者は「プログラミングっぽいルールに基づいてあるパラメーターを最適にする」というパズルゲームとしてHOJ(http://herbert.tealang.info/ )やTGO(http://snuke.main.jp/turing/)にもすこし馴染みがあるのだが、
それらと比べると（現時点では）様々な入力に対応するという点で競技プログラミング要素が強く、問題を解くだけであれば平易だが、最適化には幅広い発想が必要になる、という印象を持っている。また、MAOは「操作を終了させた状態で出力を達成する」必要があり、正解状態が遷移に含まれているだけではダメという性質がある。
3.Min Digitという問題
この記事ではMAOのMin Digitという問題にのみ触れる。
問題ページはここ
1,2,3,4,5のみからなる数字列がある時その中の最小値の数字に変換せよ
というもの。
たとえば
234523423 -> 2
345334 -> 3
5555555 -> 5
32415112 -> 1
といった具合である。このゲームの特徴として、あらゆる入力に対してその入力に応じた出力をする必要がある。
できればこの問題にある程度時間を割いてから以降を読んだ方が良いと思う。
実際筆者もこれほどいろいろやりようがある問題とは思っておらず、人の答えをガンガンみてしまったことをやや後悔しているので。
4.各種アプローチから見るこの問題の奥深さ
⓪~�イ力擦直匆陲垢襦５�則の行数は
⓪ 25行 ��17行 ��15行 ��12行 �き� 11行
である。
前にも書いたように以降ネタバレを非常に多く含む。
逆に始めたてと言う人はこれをみてこのゲームの面白さが伝わると嬉しい。
⓪原始的な解(25行)
隣り合う数字としてありうる組は25通りで、それぞれ小さい方を指定することで最小値を抽出できる。
こう言う愚直な書き方も大事ではある。各規則は何度も繰り返されるのでこれでうまく行く。
11:1
12:1
13:1
14:1
15:1
21:1
22:2
23:2
24:2
25:2
31:1
32:2
33:3
34:3
35:3
41:1
42:2
43:3
44:4
45:4
51:1
52:2
53:3
54:4
55:5
�”�者がなんとか思いついた解(17行)
数字列をソートした後、一番左以外全て消す という動作をがんばって書く。
・ソートに関してはバブルソートっぽいことができる（逆順のものを元に戻す規則を並べる）ため可能
・一番左以外全て消すことに関してはカーソル（チューリングっぽくいうとヘッド？）という技術を使用することでうまくいく。やや雑に言うと全く関係のない文字を追加しその文字との関係を記述することで左から順に操作を行うと言うもの。終了条件の記述も楽になる。
実はこれでは原始的なものとあまり差のないコードとなるため、重要な考察として、答えが5になる数字列は入力が全て5だった場合のみという性質に着目する。予め5を消しておけばソートに関する規則数が減り、行数を減らせる。以下の通り。アンダーバー'_'をカーソルとして使用している。
_5:_
5:
43:34
42:24
41:14
32:23
31:13
21:12
_1:_
_2:_
_3:_
_4:_
_::
1:1_
2:2_
3:3_
4:4_
::5
��snukeさんが放送で紹介していた解(16,15行)
マルコフアルゴリズムでは規則を上から順に実行する。
そこで、1を見つけたらその1の左右に印をつける→2を見つけたら左右に印をつける→…
という具合に規則を上から順に書くと初めて印がついたところが最小値、すなわち答えとなる。
この規則よりも前につけた印に依存した記述をする（具体的には左側と右側を消す）ことにより先ほど印をつけた数字のみが残り、印を消して停止することで答えとなる。
マルコフアルゴリズムでは文字列を左から順にチェックしていく性質があるため、
印よりも左には印をつけた数よりも大きなものしかない。よって「印より左の1を消す」は不要となる。
最後に先ほどの5の処理と同様のことを行うことで15行になる。以下の通り。この解に限らず言えることだが、わかりやすい文字を使うのは重要かもしれない。
>1:>
>2:>
>3:>
>4:>
2<:<
3<:<
4<:<
5:
>:
<::
1:<1>
2:<2>
3:<3>
4:<4>
::5
<>をつけるのはわかりやすい。
��すこし天才的な発想に基づく解(12行)
「全ての文字に1を加えるという変換を行い、5に対しては削除する。」という操作を考える。
一度変換を行うごとにカウンター用の文字を蓄積させ、数字の列が空になった時のカウンターの数に応じて答えを出力するというもの。
操作そのものはカーソルの技術を使用すれば綺麗にかけて、
マルコフアルゴリズムの性質をふんだんに生かしていると言える。
_1:2_
_2:3_
_3:4_
_4:5_
_5:_
x_____::1
x____::2
x___::3
x__::4
x_::5
x:x_
:x_
前半が「全ての文字に1を加えるという変換を行い、5に対しては削除する。」
後半が「数字が空になった時のカウンターの状況に応じた答え」
最初に「判定用の動かないカーソル（動くカーソルを生やすカーソル生成機も兼任）」と「操作用の動くカーソル」を付与するのがポイントか
�い�なり天才的な発想に基づく解(11行)
実は数字x,yに対して小さい方を一律で計算する規則を以下のように作成することができる。
xをx個の+、x個の-に分解し、yをy個の+、y個の-に分解する。
+++---+++++----- (x=3,y=5の例)
この時-+という文字列を次々に消していくと、
+++---+++++----- -> +++--++++----- -> +++-+++----- -> +++++-----
なんとmax(x,y)個の+とmax(x,y)個の-が残るということが言える！
これではmaxになってしまうので、1>2>3>4>5となるように順序づけしなおせばminとなる(xに対し5-x個の+と5-x個の-を並べる）
1:++++----
2:+++---
3:++--
4:+-
5:
-+:
++++----::1
+++---::2
++--::3
+-::4
::5
答え見た時めちゃくちゃ感動した。
�サ蚕僖皀螢皀蠅硫�(=sugim48さんの解)(11行)
Top勢の解はほとんど全員�い世辰燭�よく見ると1人だけ異質な解を投稿している人がいた。sugim48さんである。
今回は先に解を貼る。(説明の都合上、実際のsugim48さんの解の一部の記号を変更した。)
_1:2_
_2:3_
_3:4_
_45555_____::1
_45555____::2
_45555___::3
_45555__::4
_45555_::5
_4:5_
_5:_
:_4555
仕組みに関しては実は��と全く同じで、��に書いたコードのうちx:x_(動くカーソルを生成する部分)と:x_(二つのカーソルを生成する部分)がよくわからない形に削減されている。��で紹介した操作を行う「動くカーソル」は健在で、カーソル生成機であったxが不在であり、その代わり動くカーソルの右に謎の数字列を追加している。
ひとまず_以外の文字列をxとおく。そもそも��の解は以下のように書き換えられる
_1:2_
_2:3_
_3:4_
_4:5_
_5:_
_x_____::1
_x____::2
_x___::3
_x__::4
_x_::5
_x:_
:_x
最後の部分を少し変えた。xがカーソル_生成機ではなくカーソル_のストッパーになっている仕組みはほぼ同じである（この辺の変換の理論をあまりまだ持っていないので天下りである…）
課題としては「既存の規則で_x:_的なことを自動で行う」ことで1行削減するというところである。
カーソルによって発生する文字列変換の関数をfとする。
_string -> f(string)_
という変化をするというイメージである。xとして数字列を使用できれば既存の規則が適用できる。
_x -> f(x)_
と変化しこれに_xを追加した _xf(x)_を終了条件としたい。さらにこの文字列に_が作用すると
f(x)f(f(x))__となる。これを繰り返すと、終了条件として
_xf(x)f(f(x))f(f(f(x)))f(f(f(f(x))))f(f(f(f(f(x)))))_____:1
_xf(x)f(f(x))f(f(f(x)))f(f(f(f(x))))____:2
_xf(x)f(f(x))f(f(f(x)))___:3
_xf(x)f(f(x))__:4
_xf(x)_:5
としてしまえば良いことがわかる。これにより、xを適当な数字列にして当てはめれば解を得る。
（実際に本人がどのように考えたかは不明）
この性質をそれっぽく活かした答えも一応書いておく。
_543215432543545_____::1
_543215432543545____::2
_54321543254354___::3
_543215432543__::4
_543215432_::5
_1:2_
_2:3_
_3:4_
_4:5_
_5:_
:_54321
(ちょっと考察不足で申し訳ないのですがxは任意ではないようですね…)
以上がMin Digitという問題の様々な解法である。この問題一つだけでたくさんの技術が詰まっていてびっくりした。あれこれ試すのも楽しい上に、他にも人の答え見るだけで天才かってなる問題が沢山あって面白いので本当にオススメのゲーム。
