Hatena::ブログ(Diary)

あなたは嘘つきですかと聞かれたら「YES」と答えるブログ このページをアンテナに追加 RSSフィード Twitter

2011-12-06

Herbertと数学

数学が好き?

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 のルール等は、

no title

Rule - Herbert Online Judge

snukeのHOJ動画講座

などのページをご覧下さい。

いまいち分かりにくいところがあれば、Edit上でいろいろ試してみたり、講座を読んだり(見たり)、質問したりして下さい^^


等差数列

ではまず、

0 1 2 3 4 5 6 ....

という等差数列を作ってみましょう。

a(A):Ara(sA)
a()

こうなります。(各項の数だけ進んで右を向くようにしています。)

これを実行してみると、

f:id:snuke:20111129232248p:image

このように渦を書いてくれます。

長さを測ってみると、ちゃんとさっきの数列になっています!

簡単に解説しますと、

a(A):Ara(sA)

というものを宣言し、

a()

を呼び出しているので、これを展開すると、

a() = ra(s)

となり、続いて

a(s) = sra(ss)
a(ss) = ssra(sss)
a(sss) = sssra(ssss)
....

となるので、実行部分をつなげると

rsrssrsssrssssr...

先ほどの数列が実現できるわけです。


2の冪乗

1 2 4 8 16...

というような2の冪乗も、簡単に表現することができます。

a(A):Ara(AA)
a(s)

f:id:snuke:20111130000517p:image

イメージが出来なければ、さきほどと同様に展開してみて下さい。

参考問題


フィボナッチ数列

1 1 2 3 5 8 13....

前の2項を足し合わせる数列なので、「今の項」「1つ前の項」の2つを引数に記録します。

a(A,B):Ara(AB,A)
a(s,)

f:id:snuke:20111201230421p:image

ちょっとややこしいので展開してみます。

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)

一見正しそうな雰囲気ですが、実はこのコードだとダメです。

解析してみましょう。

まず1行目です。

これは、「7で割った商」を「ある数から何回7を引くことが出来るか」と言い換えて、それを実現しています。

例えば、"b(10)" を実行したとします。

ルール上、引数が正でなくなると実行されないので、

b(10) = sb(10-7) = sb(3)
b(3) = sb(3-7) = sb(-4) = s
↓
b(10) = ss

となります。

10÷7 の商は 1 なのに、"s" が2回も実行されてしまいました。

"b(30)" でも試してみると、

b(30) = sb(23) = ssb(16) = sssb(9) = ssssb(2) = sssssb(-5) = sssss

30÷7 の商は 4 なのに、"s" が5回も実行されてしまいました。

どうやら1個余分に実行してしまっているようです。

ということは、呼び出す前に "b(X-7)" のように7を引いておけば良さそうに見えます。

しかし、これも失敗します。

どういう時かというと、Xが7の倍数の時です。

例えば、X = 28 のとき "b(21)" が実行され、

b(21) = sb(14) = ssb(7) = sssb(0) = sss

28÷7 の商は 4 なのに、"s" が3回しか実行されていません。

これは、ルール上 "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)

f:id:snuke:20111201230422p:image

このように割り算が出来ました。

参考問題


剰余

先ほどは「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)

まず1行目の "f(F,G):F" ですがこれは、

引数が正でなければ実行しないことを利用した条件判断です。

例えば、Xが1の時だけ "s" を実行したいならば

f(s,2-X)

と書けば良いのです。

よって3行目は「引数を7ずつ減らしていき、7未満になればその数だけ"s"を実行する」となります。

f:id:snuke:20111201230423p:image

実行してみると、一周する前に "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)としています。

それに合わせて、初期値に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 歩」を実現できます。

書き方を工夫することでコードを縮めることが出来ました。

f:id:snuke:20111203175724p:image

他にも細かいテクニックはありますが、だいたいはこんなところです。


以下に数学ゲーの問題をリストアップしておきます。

是非トライしてみて下さい!

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...偶数なら2で割り、奇数なら3倍して1を足します。

300 mod n:300を1.2.3...で割った余り。「300」というのが曲者

X! mod 23階乗 mod 23

hyperbola:綺麗な双曲線です。

soukyokusen:ちょっと変わった双曲線。

Bit Counts:例えば「19」は、2進数で「10011」なので「3」となります。

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)

こう書いて成長させると、

f:id:snuke:20111203230131p:image

こんなフラクタルな図形が出来上がりました。

引数の変化をシミュレーションしてみます。

a(r,s)
↓
a(slrrrsl,ss) ≒ a(srrsl,ss)
↓
a(sslsrrslsrrslsrrslssl,ssss)

"sslsrrslsrrslsrrslssl" を実行すると

f:id:snuke:20111204002326p:image

こうなります。このパーツを "P" とします。

すると次のステップでは、

「上に4歩 → "P" を左・上・右にくっつける → 下に4歩」

となります。

方向転換の調整がなかなか難しいですが、その辺りは慣れです。

「これらを実行し終わった時にどちらの方向を向いているか」を考えるのが有効です。


フラクタルな形の問題をリストアップします。

Fractal arrow:上の例。

Recurring Hsフィボナッチ数列フラクタル

Recursion1:綺麗な規則です。

Pascal 2パスカルの三角形の奇数部分

Five Storied Pagoda:HOJerの中でも満場一致の名作。

two dimension:Hilbelt曲線。これが綺麗に書けた時は感動しました。

252525:ペアノ曲線。

chikaramochi:C曲線。こんなものを10Bで書けてしまうH言語、恐ろしい子。

King seahorse:ドラゴン曲線。これもなかなか綺麗に書けて感動しました。


どうでしたか?

「H言語スゲェ!」

と思っていただけていれば嬉しいです^^

ここまで僕の駄文に付き合っていただいた皆さま、ありがとうございました!