Euclids orchard とか

anarchy golf js Groovy sed vi

Euclids orchard が終了した。あなごるやっていると、数学のちょっとした話題に触れることができて面白い。
この問題で見つけたちょっとしたテク。

Groovy：
    't '[1%it.gcd(1)]
    it.gcd(1)>1?' ':'t'
JavaScript：
    o+='t '[1%k]
    o+=k>1?' ':'t'

つまり、n > 0 である n に関して、

0 if n==1
1 if n>0

を得る方法として、1%n が使える。Euclids orchard もそうだが、あなごるでしばしばでる、共通因数を探す問題では有効かも。
さて、C は、もともと、３重だった for 文を１重までもっていって、94B まで縮めたのだが、inaniwa さんに 93B で抜かれた。こちらは、２重 for 文だが、orchard を一次元(j

121321

こちらは、まだ、アクティブな問題。ちょっと前に終わった 122333 のバリエーション的な問題だが、解答方針は異なるので面白い。

JavaScript

JavaScript はコンパクトにまとまり 67B。わりと美しい解答。122333 より短い。

sed

sed は、よく縮まり 43B までいった。なかなか面白い。sed に関しては、ちょっとフライングな話題だが、微妙な挙動に気がついた。

echo 12341552 | sed 's/\([0-9]\)\+\1/\1/'

この結果はどうなるか？答えは、

52

どこが微妙かというと、RE のマッチ対象は、1234155 で、\1 による参照は、5 となっているところ。JavaScript も同じだった。

print(readline().replace(/(\d)+\1/,'$1'))  // 12341552 -> 52
print(/(\d)+\1/.exec(readline()))          // 12341552 -> 1234155,5

てっきり、12341 にマッチして、\1 は、1 になるかと思っていた。ところが、

echo 12341 | sed 's/\([0-9]\)\+\1/\1/'

は、12341 で、RE はマッチしない。

vi

vi は、122333 と同じ方針。以下は、122333 の解答。

O:%s/9//ge^[hh9i&^[qzYp^XeXq8@zdH@"ZZ

わかりにくいと思うが、実は、vi は結構面白いことをやっている。いわゆるメタプログラミングだ。つまり、解答を直接作成するのではなく、解答を作成するプログラムを作成して実行する、という方法だ。プログラムといっても、:substitute の集合のことだが。つまり、上記は、まず、以下を作成している。

:%s/9/&&&&&&&&&/ge
:%s/8/&&&&&&&&/ge
:%s/7/&&&&&&&/ge
:%s/6/&&&&&&/ge
:%s/5/&&&&&/ge
:%s/4/&&&&/ge
:%s/3/&&&/ge
:%s/2/&&/ge
:%s/1/&/ge
:%s/0//ge

あとは、これを実行すれば結果が得られるというもの。なお、この :s の集合は単純な規則性を持っているので、vi で、先頭の O から、@z までの短い手数で得られる。こういった方法は、vi では、しばしば用いられる。

Polynomial Sequences part 2

ちょっとトライしたが、JavaScript では、timeout してしまった。まぁ、あまりきれいなやり方ではなく、Brute Force 攻撃だからしょうがない。もっと、いいやり方があるのかな？7 元 1 次連立方程式を解くのも試みたが、長くなるので、途中でやめた。