数学が好き？
Herbert をやりましょう！
プログラミングが好き？
Herbert をやりましょう！！
パズルが好き？ ニコリ依存症？
Herbert をやりましょう！！！
Advent Calendar からいらっしゃった方、こんにちは。
snuke と申します。(twitterは @the_nikaidoes です。)
ではさっそく、2007年から2009年まで Imagine Cup の公式競技だった「Herbert」について語ろうと思います^^
「Herbert」はmap上のTargetを全て回収するようなプログラムを、いかに短く書けるかを競う競技です。
Herbertで使われる「H言語」という言語は "おもちゃ" のような言語ですが、"おもちゃ" をあなどってはいけません。
レゴで船やロボットなどの様々なものが作れるように、
「H言語」でもまた、フィボナッチ数列、素数判定、放物線などの様々なものが書けます。
書けてしまいます！
Herbert はもう Imagine Cup の競技ではなくなってしまいましたが、id:quolc さんが Herbert Online Judge というサイトを作って下さったため、Herbertを今でも楽しむことが出来ます。
そして、最近は月一回のペースで「HOJコンテスト」が開催されており、12月10日(土)にも行われます。
今回は初の試みとして、topcoderのようなDiv制をつけようと思うので
腕に自信のない方も、どうぞお気楽にご参加ください！
詳細はこちら！
Herbert のルール等は、
Rule - Herbert Online Judge
snukeのHOJ動画講座
などのページをご覧下さい。
いまいち分かりにくいところがあれば、Edit上でいろいろ試してみたり、講座を読んだり(見たり)、質問したりして下さい^^
等差数列
ではまず、
0 1 2 3 4 5 6 ....
という等差数列を作ってみましょう。
a(A):Ara(sA) a()
こうなります。（各項の数だけ進んで右を向くようにしています。）
これを実行してみると、
このように渦を書いてくれます。
長さを測ってみると、ちゃんとさっきの数列になっています!
簡単に解説しますと、
a(A):Ara(sA)
というものを宣言し、
a()
を呼び出しているので、これを展開すると、
a() = ra(s)
となり、続いて
a(s) = sra(ss) a(ss) = ssra(sss) a(sss) = sssra(ssss) ....
となるので、実行部分をつなげると
rsrssrsssrssssr...
先ほどの数列が実現できるわけです。
フィボナッチ数列
1 1 2 3 5 8 13....
前の２項を足し合わせる数列なので、「今の項」「１つ前の項」の２つを引数に記録します。
a(A,B):Ara(AB,A) a(s,)
ちょっとややこしいので展開してみます。
a(s,) = sra(s,s) a(s,s) = sra(ss,s) a(ss,s) = ssra(sss,ss) a(sss,ss) = sssra(sssss,sss) .....
こんな感じです。
参考問題
割り算
10 20 30 40 50 60 70 80 90 100....
を7で割った商の数列
1 2 4 5 7 8 10 11 12 14....
を作ってみましょう。
b(B):sB(B-7) a(A):b(A)ra(A+10) a(10)
一見正しそうな雰囲気ですが、実はこのコードだとダメです。
解析してみましょう。
まず１行目です。
これは、「７で割った商」を「ある数から何回７を引くことが出来るか」と言い換えて、それを実現しています。
例えば、"b(10)" を実行したとします。
ルール上、引数が正でなくなると実行されないので、
b(10) = sb(10-7) = sb(3) b(3) = sb(3-7) = sb(-4) = s ↓ b(10) = ss
となります。
10÷7 の商は 1 なのに、"s" が２回も実行されてしまいました。
"b(30)" でも試してみると、
b(30) = sb(23) = ssb(16) = sssb(9) = ssssb(2) = sssssb(-5) = sssss
30÷7 の商は ４ なのに、"s" が５回も実行されてしまいました。
どうやら１個余分に実行してしまっているようです。
ということは、呼び出す前に "b(X-7)" のように７を引いておけば良さそうに見えます。
しかし、これも失敗します。
どういう時かというと、Xが７の倍数の時です。
例えば、X = 28 のとき "b(21)" が実行され、
b(21) = sb(14) = ssb(7) = sssb(0) = sss
28÷7 の商は 4 なのに、"s" が３回しか実行されていません。
これは、ルール上 "b(0)" が実行されないことに起因します。
それらをふまえると、"b(X-7+1)" とすれば正しく動くことが分かります。
b(B):sb(B-7) a(A):b(A-6)ra(A+10) a(10)
初項を変えると 1B(byteの略) 縮みます。
b(B):sb(B-7) a(A):b(A)ra(A+10) a(4)
このように割り算が出来ました。
参考問題
剰余
先ほどは「7で割った商」でしたが、今回は「7で割った余り」つまり「Mod 7」を求めてみましょう。
つまり、
3 6 2 5 1 4 0 3 6....
こんな感じです。
先ほどのコードを半分流用して書いてみます。
f(F,G):F c(C):sc(C-1) b(B):f(c(B),7-B)b(B-7) a(A):b(A)ra(A+10) a(10)
まず１行目の "f(F,G):F" ですがこれは、
引数が正でなければ実行しないことを利用した条件判断です。
例えば、Xが１の時だけ "s" を実行したいならば
f(s,2-X)
と書けば良いのです。
よって３行目は「引数を７ずつ減らしていき、７未満になればその数だけ"s"を実行する」となります。
実行してみると、一周する前に "Numeric Limit Exceeded." が出ています。
Modの性質を利用すると、この問題を簡単に解消することができるので考えてみて下さい。
実はもう少しうまい書き方が出来ます。
b(B):sb(B-1) a(A):a(A-7)b(A-1)ra(A+10) a(11)
かなり縮みました。
分かりにくいと思うので少し解説をしてみます。
まず、展開をしてみましょう。
a(10) = a(3)b(9)ra(20) = a(-4)b(2)ra(13)b(9)ra(13)b(19)ra(30) = .....
複雑すぎてわけが分かりませんね・・・
意味を考えていきましょう。
まず、Aが 0以下になるまで "a(A-7)" を実行します。
するとそれ以降のものは、Aが 1~7 であるときのみ実行されます。
つまり、この部分でModが実現できます！
しかし、実際のModの値は 1~7 ではなく 0~6 なので、b(A-1)としています。
それに合わせて、初期値に１を足して a(11) としておきます。
と、こんな感じです。
参考問題
双曲線
双曲線の問題HOJ1026を解いてみましょう。
y = 24 / x (小数点以下切り上げ)
という式なので、
y(A,X):sy(A-X,X) a(X):ry(24,X)rry(24,X)rsa(X+1) a(1)
Byte数制限はクリアしていませんが、こう書けます。
ry(24,X)rry(24,X)rs
では、「右に 24/X 歩、左に 24/X 歩、上に 1歩」という動きをさせているのですが、このあたりを改善することが出来て、
y(A,X):rsly(A-X,X)lsr a(X):y(24,X)sa(X+1) a(1)
"y(A-X,X)" の両サイドに "s" を書けば縮みます。
すると、例えば "y(24,13)" なら、
y(24,13) = rsly(11,13)lsr = rslrsly(-2,13)lsrlsr = rslrsllsrlsr ≒ rssllssr
となり「右に 24/X 歩、左に 24/X 歩」を実現できます。
書き方を工夫することでコードを縮めることが出来ました。
他にも細かいテクニックはありますが、だいたいはこんなところです。
以下に数学ゲーの問題をリストアップしておきます。
是非トライしてみて下さい！
7：7の倍数でポコってやって、22の倍数で左を向く。
Fizz Buzz：かの有名なFizz Buzzです。
1 divided by 23：分数の計算。
NO TITLE：HOJ初の数学ゲー、解けた時は感動しました。
59 shou tasu amari...：HOJコンテストの問題
primes mod 11：素数判定です。
True Parabola：放物線です。式に少し工夫が必要です。
Collatz 18.9.28.14.7.22.11.34...：偶数なら２で割り、奇数なら３倍して１を足します。
300 mod n：300を1.2.3...で割った余り。「300」というのが曲者
X! mod 23：階乗 mod 23
hyperbola：綺麗な双曲線です。
soukyokusen：ちょっと変わった双曲線。
Bit Counts：例えば「19」は、２進数で「10011」なので「３」となります。
Bit Counts 2：より綺麗な規則で解けます。
GCD：210とのGCDです。
rectangles：ユークリッドの互除法の過程を描きます。美しい。
Circle：半径12の円です。
Farey sequence：ファレイ数列です。こんなものまで書けてしまいます。
sequence：ところどころ不規則のように見えるところがどうなっているのかがポイント。
59：規則が分かるでしょうか？
mod 5：フィボナッチ数列 mod 5
minimum primitive root of 23：最小原始根
Shuriken 4：「13」がヒント。
フラクタル
数の数学を離れて、幾何学っぽいことをやりましょう。
H言語では、簡単にフラクタルな図形がかけてしまいます。
例えば、
a(A,B):Ala(BlAAABl,BB) a(r,s)
こう書いて成長させると、
こんなフラクタルな図形が出来上がりました。
引数の変化をシミュレーションしてみます。
a(r,s) ↓ a(slrrrsl,ss) ≒ a(srrsl,ss) ↓ a(sslsrrslsrrslsrrslssl,ssss)
"sslsrrslsrrslsrrslssl" を実行すると
こうなります。このパーツを "P" とします。
すると次のステップでは、
「上に４歩 → "P" を左・上・右にくっつける → 下に４歩」
となります。
方向転換の調整がなかなか難しいですが、その辺りは慣れです。
「これらを実行し終わった時にどちらの方向を向いているか」を考えるのが有効です。
フラクタルな形の問題をリストアップします。
Fractal arrow：上の例。
Recurring Hs：フィボナッチ数列とフラクタル
Recursion1：綺麗な規則です。
Pascal 2：パスカルの三角形の奇数部分
Five Storied Pagoda：HOJerの中でも満場一致の名作。
two dimension：Hilbelt曲線。これが綺麗に書けた時は感動しました。
252525：ペアノ曲線。
chikaramochi：C曲線。こんなものを10Bで書けてしまうH言語、恐ろしい子。
King seahorse：ドラゴン曲線。これもなかなか綺麗に書けて感動しました。
どうでしたか？
「H言語スゲェ！」
と思っていただけていれば嬉しいです^^
ここまで僕の駄文に付き合っていただいた皆さま、ありがとうございました！
