『デスコロC #1』の感想
はじめに
『デスコロC #1』で優勝しました!
前回が最終回だった tbpgr さんの『デスマコロシアム』シリーズを引き継いで、新たに ciel さんの『デスコロC』シリーズが始まりました。企画の内容は前シリーズとほとんど変わっていないはずですが、出題者が交代した影響は想像以上に大きいようで、全く違った雰囲気になっています。一言で言うと、超ガチです。スーパーガチです。その理由は、主に次の2点です。
- 『デスマコロシアム』シリーズ最大の特徴であった、役によるバトルが、バッサリとカットされ、一切の運要素が排除されています。
- 前シリーズでは、コード長と言語ペナルティがトップに届いていなくても、僅差ならバトルでの逆転に期待することができましたし、大差でも「デスマーチ」による一発逆転が用意されていました。これにより、誰もが優勝の可能性を持って参加できました。
- 今シリーズでは、純粋にコード長と言語ペナルティだけで競うため、トップに1ポイントでも負けていれば、絶対に優勝できず、絶望するしかありません。逆に言うと、トップの人はトーナメントの組み合わせにかかわらず優勝が約束されています。
- 出力文字列が、かなり複雑なものになっています。もはや、コーディングの工夫だけではどうにもならず、知識、考察、閃きなどの総合力が試されます。
また、途中経過が毎日ではなく数日おきだったり、ツイートのまとめが行われなかったりしたことも、ストイックさを醸し出す要因になっていたと思います。
私は、初日に2桁バイトのコードを提出し、そのまま最後までアベベのごとく独走状態でした。初日に提出した時点では、暫定トップに立ってみたもののすぐに追いつかれて後はガチゴルフ勝負、といういつもの展開を予想していたのですが、意外な展開となってしまいました。
私の解答
print/.$/gfor sort map/.{999}/?$_=$'.$&:y/9Zz0-z/Aa0-z/<s/s$/sNtUUVb/,(A^eUVb)x3822
Perl (83) です。3822回ループを回していますが、このうち先の2822回で1000文字のデータを生成し、後の1000回で1文字ずつローテートさせながら、ソートして出力しています。
問題の解説
この問題の出力文字列は、ある文字列をブロックソート(BWT)した結果になっています。短いコードを書くためには、このことに気付かなければなりません。
どうすればこれがブロックソートだと気付くのでしょうか? 出力文字列を見てまず気付くのは、同じ文字が連続して現れるなど、ある程度の規則性があることです。もちろん、今までのデスマコロシアムの出力文字列にも規則性がありました。今回違うのは、規則性がありながらも、具体的に調べていくと、細かい部分が不規則になっていて、これをそのままコードに落とすのは困難だということです。
次に気付くべきは、文字列の先頭付近にある、あからさまに怪しい $ の文字です。いかにも何かの終端を表していそうです。ところで、上記の Wikipedia の記事によると、ブロックソートの変換後のデータは「ccoaa, 3」のように、変換後の文字列と開始位置の組で表されています。しかし、変換前の文字列に終端文字を付加しておけば、開始位置の情報を別途持たなくても、変換後の文字列に埋め込まれた終端文字の位置から特定することができ、実際にそのような実装も存在します。
したがって、
- ブロックソートの結果は同じ文字が連続する傾向がある
- ブロックソートをするときには終端文字を付加することがある
この2つを知っていれば、もしかしてブロックソートかな? と気付くことができます。
推測ができたところで、実際にブロックソートであることを確認してみます。まず、出力文字列に現れる文字の出現頻度を、ASCIIコード順に調べると、次のようになります。
文字 | 頻度 |
---|---|
$ | 1 |
0 | 16 |
1 | 16 |
2 | 16 |
3 | 16 |
4 | 17 |
5 | 17 |
6 | 15 |
… | … |
次に、出力文字列を、先頭から、この頻度に従って切り分けてみます。
文字 | 頻度 | 文字列 |
---|---|---|
$ | 1 | b |
0 | 16 | PP00$zzzuuuVVUUU |
1 | 16 | QQ11000vvvWWWVVV |
2 | 16 | RRR22211wwXXXWWW |
3 | 16 | SSS333222xxYYYXX |
4 | 17 | TTT444333yyyZZZYY |
5 | 17 | UUU555444zzzaaZZZ |
6 | 15 | VV66555000bbaaa |
ちょうどいい位置で切れていますね。ブロックソートで間違いなさそうです。
次に、ブロックソートする前の文字列の生成ですが、結果記事によると、「線形合同法っぽい方法で生成」できるようです。これは全く気付きませんでした(○○○○○=「ROT13」かな?とか思っていました)。もし気付いていたら、もっと違ったコードになっていたかもしれませんね。私のコードでは、この文字列を6文字単位のローテートと解釈して、 y と s を使ってなんとか生成しています。
(2015/11/7追記)「線形合同法っぽい方法」の部分について、 angel さん(アイコンが急にかわいくなった!)が詳しく考察されています。
ところで、ブロックソートは、データを縮めるための前処理として行われるものですが、今回はコードを縮めるためにわざわざ圧縮元のデータに遡るところが面白いと思いました。下手をしたら、圧縮データを埋め込んで逆符号化したほうが短くなるなんてことにもなりかねないわけで、うまくバランス調整されていると感じました。
まとめ
今回の問題はかなり難易度が高かったようで、題意通りに解けた人がわずかしかいなかったとのことですが、私としては、今までの問題よりパズル的な要素が強くて、とても楽しめました。
ciel さん、出題及び集計お疲れ様でした。次回も楽しみにしています。
「無限整数」について考えたこと
はじめに
…111111 のように、無限桁の数字が並ぶ整数、「無限整数」の性質について、以前より興味がありました。なお、ここでの「無限整数」というのは私の造語であり、数学的には別の用語を用いてもっと精緻な議論がされているのだろうと思います(私は数学の素人です)。
「無限整数」のイメージ(右端が一の位)
実数の表記法に、無限小数というものがあります。例えば 1/3 = 0.333333… というやつです。また、円周率 π = 3.141592… も無限小数ですね。これらは、桁が細かくなるほうに無限に続いているので、値の大きさがイメージできます。先の円周率なら、大体 3.14 くらい、ということです。 3.14 より大きくて 3.15 より小さい、ともいえます。
では、「無限整数」の場合はどうでしょうか。万の位、億の位、兆の位、…と桁が大きくなるほうに無限に続いているため、値の大きさをイメージすることはできません。でも、先の …111111 の場合は、例えば、 10 で割ったら 1 余りそうだ、といった性質が見て取れます。単に無限大とするよりは、もっと考察の対象となる性質がありそうです。
そこで、以下では、「無限整数」というものが意味を成すと仮定して、その性質について考えてみます。
循環無限整数
無限小数には循環無限小数と非循環無限小数があって、循環無限小数のほうが考えやすいですね。必ず有理数であるなど、良い性質があります。
そこで、「無限整数」についても、まずは「循環無限整数」を考えてみることにします。例として、冒頭に挙げた …111111 という数を考えてみます。少し考えてみると、この数は -1/9 であると解釈すると、いろいろ都合がいいことがわかります。その理由をいくつか挙げてみます。
理由1.10倍して1を加えると元に戻る
…111111111111 ↓10倍する …1111111111110 ↓1を加える …1111111111111 ↑元に戻った!
つまり、 x = …111111 とすると、 10x+1 = x が成り立ちます。よって x = -1/9 です。え、桁が増えてるって? まあ、無限桁が1桁増えたところで変わらないでしょう。
理由2.9倍して1を加えると0になる
…111111111111 ↓9倍する …999999999999 ↓1を加える …000000000000 ↑全桁が0になった、ということは0だ!
つまり 9x+1=0 です。よって x = -1/9 ですね。え、無限の彼方に、繰り上がった0でない値があるだろうって? まあ、無限の彼方なら無視してもいいでしょう。
理由3.1/9を加えた値が、10倍(100倍、1000倍)しても不変
大胆にも、無限小数 0.111111… を加えてしまいます。
…111111 + 0.111111… = …111111.111111… ↑10倍しても、100倍しても、変わらない。ってことは0だね!
つまり、 x+1/9=10(x+1/9) よって x = -1/9 です。少々乱暴ですが。
このように、 …111111 という値にいろいろと変形を試みてみると、一貫して -1/9 の性質が出てくるのです。正の整数だったはずなのに、負の小数になってしまうのですから、不思議ですね
特に理由3は乱暴ながら面白くて、例えば …123123123 というような、複数桁が循環するような循環無限整数についても、同様に 0.123123123… = 123/999 を加えれば 0 になるので、 …123123123 = -123/999 ということがすぐにわかります。このことから、純粋な(循環節のみからなる)循環無限整数は、 -1 より大きく 0 以下の有理数に対応しているということがわかります。循環無限整数の性質が、すっかりわかってしまいました。
補足1.
では正の有理数は無限整数でどう表現できるのかというと、単純に普通の整数を加えればいいのです。例えば 8/9 = 1 + (-1/9) = 1 + …111111 = …111112 です。
補足2.
全ての有理数が循環無限整数で表現できるわけではないようです。例えば 1/2 は、どう頑張っても表現できません(非循環無限整数でも表せません)。
非循環無限整数
循環無限整数の性質はわかりましたから、あとは数字が循環しない「非循環無限整数」について考えたいと思います。
無限小数の場合、数字を適当に無限に並べたものであっても、値の大きさがイメージできるので、何らかの一つの値として認識できる気がします。しかし、無限整数の場合、数字を適当に無限に並べても、大きさはイメージできませんし、上述の循環無限整数に対する考察も無力っぽいので、果たしてその数の並びが何らかの値を表すものなのかどうかさえ、よくわかりません。数字を循環しないように規則的に並べたもの(例えば …100001000100101)についても同様です。
そこで、アプローチを変えて、「無限整数で表現できるとすれば非循環になるはずの数」を考えてみることにします。ここで、循環無限整数は必ず有理数になることが上記の考察でわかっていますから、もし無理数が無限整数で表現できれば、それは非循環になるはずです。対偶というやつですね(「叱られなければ勉強しない 」←→「勉強すれば叱られる」)。
2の平方根は無限整数では表現できない
まず、最も簡単な無理数と考えられる √2 (2の平方根)を考えてみることにします。2乗して2になるような無限整数を、一の位から上位に向かって1桁ずつ決定していけば良さそうです。しかし、この試みは、一の位でいきなり失敗します。2乗して10で割った余りが2になるような1桁の数は、存在しないのです。図らずも、「無限整数は2の平方根を表現することができない」ことが示されてしまいました。
1の平方根は?
ふと、では 1 の平方根ならどうだろうか? と思って確かめてみたところ、4つの無限整数が出てきました。
2乗して 1 になる無限整数のを探すプログラム(Perl スクリプト)は、次の通りです。このプログラムでは、一の位から上位に向かって51桁求めて、それらの下50桁をユニークに出力しています。
use bigint;
@a=('');
for $n (1..51) {
for $a (@a) {
for $d (0..9) {
$t = $d.$a;
if ($t**2%10**$n == 1) {
push @b, $t;
}
}
}
@a=@b, @b=();
}
/./,++$a{$'} for @a;
print $_,"\n" for keys %a;
結果は次の通りです。
00000000000000000000000000000000000000000000000001 99999999999999999999999999999999999999999999999999 85153153538207781991786760045215487480163574218751 14846846461792218008213239954784512519836425781249
循環無限整数が2つと、非循環無限整数が2つ、出てきました。意味のありそうな非循環無限整数が発見された、記念すべき初めての例です!
これら4つの数のうち、最初の …000001 は普通の整数の 1 なので2乗して 1 になるのは当然、次の …999999 も -1 なのでまあ当然です。問題は、2つの非循環無限整数の意味というか正体です。どうやら互いに正負の関係にあるようですが、それ以外の素性がさっぱりわかりません。どういう数なのでしょう。ともあれ貴重な手掛かりなので、もう少し探ってみることにします。
p進数
ところで、数学の世界には、p進数というものがあるらしいです。
どうやら、p進数と「無限整数」はかなり似たもののようですが、p進数は p を素数に限定しているようです。一方、「無限整数」は暗黙に10進数を仮定しているため、p進数ではないということになります。このウィキペディアの記事によると、 p が素数でない場合には「2つの 0 でない p-進数の積が 0 になってしまうことや、逆数が存在しないことがある。」とのことなので、2乗して 1 になる無限整数が …001 と …999 以外に見つかったのも、10が素数でないことと関係しているのかもしれません。
もう一つ、手掛かりとなりそうな論文を見つけました。
- p-進世界へようこそ [PDF](山崎隆雄、筑波大学)
おおお! 3進数では、なんと -2 の平方根が表現できるようです。p進数と実数とでは表現できる数の範囲が異なっていて、有理数はそれらの共通部分に含まれる、ということのようです。
1の平方根とpq進数
いろいろなn進数で 1 の平方根を探してみたところ、どうやら、 n が素数の場合(つまりp進数)や n が素数の冪乗の場合には ±1 しか出てこないのに対して、 n が異なる素数 p, q の積で表される場合には、10進数で確かめたときのように、 ±1 以外にもう1組出てくるようです。さらに、30進数のように n が3つの異なる素数の場合には、4組8個出てきます。どうやら、10進数のあの …751 という数は、2と5の狭間に紡ぎ出された数のようです。でも、どのように紡ぎ出されているのか、相変わらずわからないままです。
7進数での1の立方根
さらに実験を続けていくと、7進数では1の立方根(3乗すると 1 になる数のこと)が3つ出てくることに気付きました。
00000000000000000000000000000000000000000000000001 43214516604202226653431432053116412125443426203642 23452150062464440013235234613550254541223240463024
…001 は当然として、後の2つは何でしょうか? 10進数の 1 の平方根のときと似ているようですが、これらは微妙に正負の関係にはなっていないようで、和が 0 でなく -1 になっています。一方を x とすると、他方は -x-1 です。
ところで、立方根ですから x3 = 1 です。これを式変形すると、
x3 - 1 = 0
(x - 1)(x2 + x + 1) = 0
となります。もしかしたら、 x2 + x + 1 = 0 の解ではないでしょうか? 和が -1 になることは確かめられているので、あとは積を確かめます。サクッと dc でやってみます。
$ dc -e '7o7i??*p' 43214516604202226653431432053116412125443426203642 23452150062464440013235234613550254541223240463024 1420511032411144133256606146615413653451402652230000000000000000000000000000000000000000000000000001
やはり、 1 になりました! 和が -1 で積が 1 ですから、 x2 + x + 1 = 0 の解と係数の関係を満たします。7進数の 3 つの立方根の正体が判りました。
何やら重要な手掛かりを得た気がします。ということは、10進数の4つの平方根も、これと同じように x2 - 1 = 0 の何らかの別解になっているのでしょうか? しかし、これ以上考えが進みません。
Trimorphic numbers
そんな折、 angel さんから、 trimorphic numbers というものを教えていただきました。
@saito_ta 面白そうなお話のところネタばれぽいですが…。検索すると https://t.co/h685AVeg5K ( trimorphic num ) が出てきますね。10進 x^2=1 は x^2≡1 mod 10^n にあたり、x^3≡x でもあるのですね。
— angel-p57 (@angel_p_57) 2015, 8月 26
ほほう… って、私が「1の平方根」と呼んでいるもの(を数列化したもの)の一般項が示されているではありませんか! 「2と5の狭間に紡ぎだされた」というのは、どうやらある程度当を得ていたようです。
ちなみに、 trimorphic number というのは、3乗した数の下位の桁が元の数(の全桁)と同じになるもののようで、例えば 25 なんかもそうです。
Trimorphic number - Wikipedia, the free encyclopedia
なので、 angel さんのご教示のとおり「1の平方根」は trimorphic number ですが、逆は必ずしも成り立ちません。どちらかというと、より特定性の高い「1の平方根」のほうが、この数(数列)を良く表していると思うのですが…。
ゴルフへの出題
1. 出題しました
ここまでに考えたことのまとめのつもりで、いつもお世話になっている Anarchy Golf に、 1 の平方根を求める問題を出題しました。
- Square root of 1 in mod 1e300 (現在は post mortem です。)
問題の内容は、「所定の300桁の値を出力せよ。その値は、2乗すると 10300 での剰余が 1 になる。その値の下3桁が入力で与えられる。」というものです。出力すべき「所定の値」は、解答者からは見えますが、解答者が提出するコードからは見えません。入力は3種類あります(751, 249, 999)。要するに、無限整数での 1 の平方根について、それぞれ、下300桁を求めてください、ということです。
出題時の想定解法としては、下4桁目(千の位)から上位に向かって1桁ずつ探索していく、というものでした。N桁目を求めるときには、N-1桁目まで求めた値の先頭に 0 ~ 9 の数字をそれぞれ付加してみて、2乗して下N桁が1になるものを選ぶ、という方法です。この想定のもと、300桁もあれば埋め込むよりも真面目に実装した方が短くなるかな、くらいに(ろくに検証もせずに)思って出題しました。
ざっと見たところ、 rolf さんの Python(135) がこの想定解法通りのようです。
なお、問題文には蛇足的に「これらの条件だけではその値が一意に決定しないかもしれない。」とも書いてあります。どいういうことかというと、上記の条件では最上位の桁に2通りの自由度があって、例えば 49999…999999 も条件を満たしてしまいます。これに対しては、 上記の rolf さんのコードのように最上位の桁の数字で正解を判別してもいいですし、1桁多く求めてから下300桁だけを出力するようにしてもいいのですが、じつは、剰余を 10300 ではなくて 2×10300 で求めることでも題意の通りに一意に定まります。さらに、上述の想定解法において、1桁ずつ探索する際に、「下N桁が1」の代わりに「2×10Nでの剰余が1」という条件を採用すれば、候補を常に1つに絞ることができて探索の必要がなくなり、実装を大幅に簡略化できます。
2. 想定解法で解けない!
というわけで、自分の問題に Perl で提出してみました。上述の想定解法です。もちろん、 2×10N での剰余を利用した、探索不要バージョンです。
#!perl -p
use bigint;
for$n(4..300){
for$d(0..9){
$_=$t,last if($t=$d.$_)**2%(2*10**$n)<2
}
}
ところが、なんと、3回の実行の合計で8秒ほどかかってしまいます。文字数を犠牲にして 2*10**$n
の部分をループの外に出したりしてみましたが、ほとんど効果がありませんし、 bmodpow も試しましたが、却って遅くなる始末です。また、最後のテストケース(999)では 9 が明らかに最頻出なので 9 を先に試したほうが速いのは確かですが、そもそも最初のケースで timeout してしまっています。
Perl の bigint が遅いことはわかっていたのですが、これほどとは。自分出題の問題の解き方がわからないのですから、困りました。
#anagol http://t.co/wyB3kPBe0v 出題者が言うのもナニだけど、これPerlでまともに解けるのかな。ていうか、Perlの多倍長なんでこんなにオッソイの?
— 齊藤 (tails) (@saito_ta) 2015, 9月 14
ところが、しばらくして問題ページを見てみたら、 mitchs さんと llhuii さんが見事 Perl で解いているではありませんか! なにかうまいやり方があるようです。
3. Trimorphic numbers の一般項
ここで思い出したのが、 angel さんに教えていただいた、あの trimorphic numbers の一般項の式です。
とりあえず1番のケース(751)だけであれば、この一般項の式を使って次のように書けます。
use bigint;
print+(2*16->bmodpow(5**299,1e300)-1)%1e300
少し考えると、次のように短縮できることがわかります(若干遅くなります)。
use bigint;
print 2*2->bmodpow($x=5e299,$x)-1
45文字です。いい感じです。
と思ったのですが、やはりこれも激烈に遅いのです。3秒ほどかかってしまいます。文字数を犠牲にして高速化するにしても、到底及びません。
4. 桁の数字を直接求める
最初に提出しようとした想定解法のコードでは、各桁に 0 ~ 9 の数字をそれぞれ当てはめて試してみましたが、そうではなくて、この数字を直接求められないでしょうか?
1番目のテストケース(751)について、想定解法のコードの挙動を観察してみると、次のようなことがわかりました。すなわち、N-1桁目までの数の2乗のN桁目以上の部分を20で割った余り(なぜか必ず偶数なので10通り)が、N桁目の数字の 0 ~ 9 に直接対応している、ということです。具体的には、下表のように対応しています。
余り | 0 | 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 |
---|---|---|---|---|---|---|---|---|---|---|
N桁目 | 0 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
具体例として、「751」の次の桁を求めてみます。751を2乗して564001。4桁目以上の部分は564で、これを20で割った余りは4。4に対応する数字は8なので、「8751」となります。
冷静に考えてみれば、この事実は2乗の二項展開から導くことができます。「なぜか必ず偶数」なのは、出題の節で説明した「2通りの自由度」と同じ話であり、要するに奇数になるほうは探索で行き詰まるのです。
また、2番目と3番目のテストケース(249, 999)は、20で割った余りとN番目の数字との対応関係が1番目のテストケースの場合と異なりますが(下表)、それ以外は同じです。
余り | 0 | 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 |
---|---|---|---|---|---|---|---|---|---|---|
N桁目 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
なぜ対応関係が異なるのかは、やはり2乗の二項展開を考えればわかります。一の位の数字がそのまま乗率となって影響しているのです。
さて、これをそのまま(テストケースの場合分けを含んだまま)コードに落としてみます。次のようになります。
#!perl -p
use bigint;
for$n(3..299){
$_=$_**2/10**$n/(/9$/?2:-2)%10 .$_
}
ところで、この場合分け(/9$/?2:-2
のところ)は、一の位が乗率になって生じているのですから、だったら $_
を掛けてやるだけでよさそうです。つまり、2乗ではなく、3乗にします。
#!perl -p
use bigint;
for$n(3..299){
$_=$_**3/-2/10**$n%10 .$_
}
だいぶスッキリした形になりました。実行時間を計ってみると 2.5s と、間に合っています。やった、とうとう Perl で解けました!
@saito_ta なるほどできた… てゆかこれ良問じゃね!?
— 齊藤 (tails) (@saito_ta) 2015, 9月 16
5. 桁の制限を外したら二次収束!
ところで、上記のコードは下位から1桁ずつ数字を決定していっていますが、この一度に決定できるのが1桁だけという制限はどこから来ているのでしょうか? どうも考え当たりません。
そこで、試しに、1桁ずつの制限を外してみることにしました。具体的には、結果を %10 して先頭に付加する代わりに、 %10 せずに全桁をそのまま $_ に足し込んでやります。ちょっと試行錯誤してみたところ、「3倍から3乗を引いて2で割る」と辻褄が合うようです。
use bigint;
$n=<>;
$n=($n*3-$n**3)/2%1e300 for 1..8;
print $n;
(これは最終提出した50文字のコードを多少読みやすく書き直したものです。)
驚くべきことに、先程まで300回回していたループが、たったの8回で済んでしまっています。どういうことでしょうか。
0: 751 (3桁) 1: 99999999999999999999999999999999999999999788218751 (6桁) 2: 4749331894286163574218751 (12桁) 3: 24281580101871438384291806045215487480163574218751 (24桁) 4: 11153153538207781991786760045215487480163574218751 (48桁) 5: 85153153538207781991786760045215487480163574218751 (96桁)
これは、ループごとの値の変化を表したものです(下50桁のみ)。赤の部分が、数字が合っている桁です。1回回るごとに、合っている桁数が2倍になっています。そう、二次収束しているのです! まるでニュートン法のようです。
先程の漸化式を調べてみましょう。「3倍から3乗を引いて2で割る」、つまり $n=($n*3-$n**3)/2
の部分です。これは、真の値を a 、現在の n の真の値からの誤差を e すなわち n = a + e とすると、
(3n - n3) / 2
= (3(a + e) - (a + e)3) / 2
= (3a + 3e - (a3 + 3a2e + 3ae2 + e3)) / 2
= (a(3 - a2) + 3(1-a2)e - 3ae2 - e3) / 2
ここで a2 = 1 (mod 10300) ですから、
= (2a + 3ae2 - e3) / 2
= a + (3ae2 - e3) / 2
となり、確かに2次以上の誤差しかなくなることがわかります。
ところで、ニュートン法では x ← x - f(x)/f'(x) のように微分を用いて収束させていきます。本問は「1の平方根」、つまり2乗して1になる数を求めているので、 f(x) = x2 - 1 です。あの3次式は x - f(x)/f'(x) の形になっていないのは明らかであり、従って、ニュートン法ではありません。では何なのでしょうか。
試しに、 f(x) を積分してみると、 F(x) = x3/3 - x + C となります。なんと、あの3次式は (F(n) - F(0)) × (-3/2) に一致します。これは単なる偶然なのか、それとも何か理由があるのか? もう少し考えてみたいところですが、私の数学力ではちょっと持て余しそうです…。
まとめ
勝手に思いついた「無限整数」というものについて、素人なりにいろいろと考えてみました。その過程において、いろいろ得るものがあったように思います。多分、群論とかその辺りを勉強すればもっと体系的な理解ができるのでしょうけれど、遊びとしてはひとまずこれで満足です。
追記1
GOTO M. さんが、ゴルフ問題の考察を書いてくださいました。ありがとうございます!
「ちょっと試行錯誤」ではここに至れないというご指摘がありますが、1桁ずつ求めていたロジックからの変形で、特に苦労した記憶がないんですよね… 当然できると思ってやったらできた、という感じで。二次収束するとは思っていませんでしたが。
追記2
angel さんが、数学的側面の解説を書いてくださいました。ありがとうございます!
いやー、さすがです。10進無限整数における1の平方根については、これで丸裸ですね。開平算の図もとてもわかりやすい。はてなブログで MathJax 使えるんですね。こうかな? \[x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}\] おおできた。
追記3
漸化式 \((3x-x^3) / 2\) の正体がわかりました。これは、(実数の)平方根の逆数を求めるときのニュートン法の漸化式です。
\[f(x) = \frac{1}{x^2} - a \Longrightarrow x - \frac{f(x)}{f'(x)} = \frac{3x-ax^3}{2}\]
上式において \(a=1\) です。
ちなみに、この方法では除算が不要なため、 \(\sqrt a\) を求める際、まずこの方法で \(1/\sqrt a\) を求めておいてから、その結果に \(a\) を乗算するようにして利用されます。
『第10回デスマコロシアム』に参加しました
デスマコロシアムとは(テンプレート)
大雑把に説明すると、
- 問題文で与えられたある文字列を出力するコード(プログラム)を提出する。
- 言語は ideone で利用可能なものから選ぶ。
- コードのサイズが短いほどよい。(1文字につき1点減点)
- 同じ言語を選択した人が少ないほどよい。(1人につき10点減点)
- その他、コーディングとは無関係な運の要素も加えて、トーナメントで競う。
といった感じです。要するに、コードゴルフに運の要素を加えたトーナメントです。
第10回の問題
treetreetreefiregoldtreetreetreetreegoldtreegoldtreegoldtreegoldtreegoldtreetreegoldtreegoldtreetreetreegoldtreetreetreewaterwatertreetreewatergoldgoldtreegoldtreegoldtreegoldtreegoldtreetreegoldtreegoldtreetreetreegoldtreetreefiregoldgoldwatermoontreemoontreegoldgoldtreewatergoldgoldtreetreegoldgoldtreetreemoonwatergoldgoldwatergoldtreetreemoongoldgoldmoon
という文字列を出力するという問題でした。この文字列は、 { moon, fire, water, tree, gold } の中から要素を88回選んで連結したものになっています。 /^(moon|fire|water|tree|gold){88}$/
にマッチする、と言ったほうがわかりやすいでしょうか。具体的にどのように作られた文字列なのかは、出題者の tbprg さんによる結果記事で説明されています。
「第10回デスマコロシアム」問題のトーナメント結果発表です!~優勝者は…!|CodeIQ MAGAZINE
さて、Perl (78) が気になると思いますが、まずは初日に提出した比較的わかりやすい Perl (81) について、仕組みと作り方を説明します。その後で Perl (78) を説明します。
Perl (81)
use v5.10;
say+((moon,fire,water,tree,gold)x60)[unpack C88,'伊畏伊!一!逸一逸伊袷仮!一!逸一逸鞍}援違仮/`依}/泳A']
(Ideone で開く → http://ideone.com/9yGZzt)
初日に提出した Perl (81) です。最初の use v5.10;
の行は文字数カウント外です。
デスマコロシアムはコードの長さをバイト数ではなく文字数で数えますが、 Ideone はコード中の文字を UTF-8 で扱うため、日本語文字を使えば1文字で3バイトを表現できます。これは第4回デスマコロシアムでも使用したテクニックですが、今回もこれを利用しない手はありません。
『第4回デスマコロシアム』私の Perl (57) - Tails の(仮)
上記のコードの文字列
伊畏伊!一!逸一逸伊袷仮!一!逸一逸鞍}援違仮/`依}/泳A
は、日本語 29 文字+ASCII 1 文字で88バイトです。これを unpack C88
でバイト値のリストに分解しています。このバイト値それぞれの mod 5 を取り、その結果を moon, fire, water, tree, gold に対応付ければ結果の文字列が得られるのですが、 mod 5 を取る代わりに moon, fire, water, tree, gold のリストを60回繰り返したものと対応付けることで文字数を少し稼いでいます(60は適当な値です)。
Perl (81) コードの作り方
アイデアは上記の通りなのですが、ではどのようにしてこのコードの文字列を作ればいいのでしょうか。 Unicode の文字コード表を眺めながら条件に合う文字を1つずつ拾っていってもいいのですが、数が多いですし、あの CodeIQ の解答欄の悪名高い「機種依存文字」判定のせいで、使いたいコードの文字が自由に使えないため、イラつくこと間違いありません。なんとかして自動化したいものです。
そこで今回私が取った方法は、一言でいうと「JIS文字コード表を UTF-8 で保存し、そこから文字を拾う」というものです。JIS第何水準とかよくわかりませんが、まあ普通のJIS文字コード表に載っている字は問題なく使えるだろうという判断です。以下、少し具体的に説明します。
まず、JIS文字コード表を用意します。これは Google で「JIS文字コード表」で検索すればいくらでも出てきます。そこから良さそうなものを1つ選んで、表の部分をテキストファイルにコピペすれば、UTF-8 でエンコードされたJIS文字コード表がすぐに作れます。
この文字コード表を利用して、出力文字列を日本語文字列に変換します。具体的には、次のようなスクリプトになります。
# 文字コード表(ファイル名 "kanji" )から1文字ずつ連想配列 %k に格納していく。
# 改行とかコードの値とかの余分な文字が混ざっていても読み飛ばすので気にしなくてよい。
# 入力を reverse することによって、コード表で先に登場する文字が優先的に使用される。
{
my $h;
open($h,"kanji");
for(reverse<$h>){
while(/([\xe0-\xff])(.)(.)/g){
$k{ord($1)%5 .ord($2)%5 .ord($3)%5}=$&;
++$count;
}
}
}
# 何文字読めたか確認。インデックス重複分を含む。
print($count,$/);
# お題の文字列。
$_='treetreetreefiregoldtreetreetreetreegoldtreegoldtreegoldtreegoldtreegoldtreetreegoldtreegoldtreetreetreegoldtreetreetreewaterwatertreetreewatergoldgoldtreegoldtreegoldtreegoldtreegoldtreetreegoldtreegoldtreetreetreegoldtreetreefiregoldgoldwatermoontreemoontreegoldgoldtreewatergoldgoldtreetreegoldgoldtreetreemoonwatergoldgoldwatergoldtreetreemoongoldgoldmoon';
# お題の文字列を 0 ~ 4 に変換。
s/moon/0/g;
s/fire/1/g;
s/water/2/g;
s/tree/3/g;
s/gold/4/g;
# 変換済みのお題から3文字ずつ拾ってエンコード。
while($_ ne ""){
if(/.../ && $k{$&}){
print($k{$&});
}elsif(/./){
print(chr(65+$&));
}
s///;
}
これであの
伊畏伊!一!逸一逸伊袷仮!一!逸一逸鞍}援違仮/`依}/泳A
という文字列が得られました。めでたし、めでたし。
ところで、この結果の文字列には記号がいくつか含まれていますが、これは、スクリプトのコメントにも書いたように、文字コード表の上のほうの文字を優先的に使うようにしたためです。しかし、単純に文字コード表の下のほうの文字を優先させると、「齊」とかの難しい漢字(第2水準?)ばかりが使われることになって微妙です。そこで、文字コード表を加工して、記号を下のほうに移動しておけば、簡単な漢字が優先的に使われて、文字列部分のみが異なる次のようなコードが得られます。
use v5.10;
say+((moon,fire,water,tree,gold)x60)[unpack C88,'伊畏伊威一威逸一逸伊袷仮威一威逸一逸鞍偉援違仮壊夷依偉壊泳A']
(Ideone で開く → http://ideone.com/dz67QP)
うわ、俺、初日 Perl (81) で言語内暫定ビリか! #デスマコロシアム
— 齊藤 (tails) (@saito_ta) 2015, 2月 7
Perl (78)
上記の (81) のコードでは3ワードを1文字でエンコードしていますが、このまま頑張ってもこれより縮みそうもありません。もっと縮めるためには1文字でエンコードするワード数を増やさなければならないようです。
そこで、1文字で5ワードをエンコードするようにして作ったのが、次の Perl (78) のコードです。
use v5.10;
say+((gold,tree,water,moon,fire)x35)[map{ord,7&ord}'桐案閑卦卦斡牒呑刈鍍桑鐇ネ咥或鏥疫尻'=~/./g]
(Ideone で開く → http://ideone.com/i5FW0b)
1つのバイト値を、そのまま(ord
)と、8で割った余り(7&ord
)とで2回使っています。ただし、UTF-8の各文字の先頭バイトは日本語文字に割り当てられているレンジが狭く(0xe3~0xe9の間くらい?)、2回使うのは現実的ではありません。そこで、このレンジの「そのまま」の値は無視されるようにリストの繰り返し回数を制限してあります。2バイト目と3バイト目は 0x80~0xbf の間くらいなので、「そのまま」の値もどれかのワードに対応します。
ところで、ワード数の88は5で割り切れません。そこで、リストの繰り返し回数をさらに制限し(35回繰り返しで要素数 0xaf )、2バイト目と3バイト目の「そのまま」の値も無視される場合があるようにしました。具体的には、最後の「尻」という文字は、2バイト目(0xb0)と3バイト目(0xbb)の「そのまま」の値が無視されて、3ワードをエンコードするようになっています。
アイデアは以上ですが、実際には1文字で5ワードをエンコードするのは難しく、ワードの順序(gold, tree, water, moon, fire)を工夫する必要がありました。前述の Perl (81) を作ったときのスクリプトを改造して、1文字を5ワードに対応させるとともに、ワードの順序も固定ではなく120通り全て試して、うまくいったものを出力するようにしました。
なおさんの Perl (78)
use v5.10;
say map{(fire,gold,water,moon,tree)[vec('驛乾ddd鑑鑞"休斑派乙`!蝶α仔#ab丁',$_,4)%5]}0..87
結果記事で紹介されている、なお(naoki_kp)さんのコードです。なんと驚くことに、1文字で6ワードをエンコードしています。これは思い至らなかったので、このコードの長さに並ぶことができたのはラッキーでした。 "α" は2バイト文字(0xce, 0xb1)のようです。
同じPerl(81), Perl(78)でも色々違う…。#デスマコロシアム
— angel-p57 (@angel_p_57) 2015, 3月 6
『そろばんのダンジョン』私の解答
テンプレ
この問題(に限らずダンジョンシリーズ)の面白いところは、定められた文字数制限と使用禁止文字列を満たす JavaScript のコードを提出すれば正解となってバッジが付与されるのですが、実際には場外(Twitter とか CodeIQ MAGAZINE とか)で出題者様主導で解答コードの短さが競われているのです! いわゆるコードゴルフです。このことは問題文には一切書かれていなくて、バッジほしさに適当に解答を送ると、知らずにコードゴルフに引きずり込まれるという、恐ろしい罠が仕掛けられているのです!
はじめに
今回は『そろばんのダンジョン』というお題でした。 0 ~ 999 の整数 i が与えられたときに、その整数を表すそろばんの珠の並び r を求めるというものです。例えば i が 7 の場合は、 5 の珠 1 個と 1 の珠 2 個なので、 r は "12" となります。 i が 12 の場合は r は "0102" 、 i が 999 の場合は r は "141414" です。 i が 0 の場合は r は "00" です。より正確なルールは、 CodeIQ MAGAZINE の公式解説記事をご覧ください。
大人気ダンジョンシリーズ!そろばんのダンジョンLV1~LV2の解説+最短コード発表 #javascript|CodeIQ MAGAZINE
以下では、私が提出したコードについて、どのようにそのコードに至ったのかなどの説明をしたいと思います。
LV1
LV1 は、 eval や Function などいくつかの禁止文字列が設定されているものの、ほぼ無制限です。
37文字(4位)のコード
for(x=i;r=[x/5&1]+x%5+[r],x=x/10|0;);
解説記事で、 for 文を使った方法で最短として紹介されたコードです。このコード自体はどうということはないのですが、頂いたフィードバックで事件は起きました。
「for of」文と非常に短い計算で、上手く処理を組み立てていました。
上記コードで用いられているのは for of 文ではなく for 文であり、フィードバックは単なる書き間違いだろうと思います。ところで、 for of 文の存在自体はググって知っていましたが、一度試してみたときにうまく動かなかったので、このフィードバックを頂くまで、 for of 文は使えないものと思い込んでいました。しかし、本当に使えないのなら、例え間違いであってもこのようなフィードバックを頂くはずがありません。 for of 文は使えるのです!
30文字(1位)のコード
for(d of''+i)r=[r]+[d/5&1]+d%5
そんなわけで for of 文が使えることに気付いて書いたのがこのコードです。ちょっとずるい気もしますが、ともあれ無事に最短コードに並ぶことができました。
LV2
LV2 は、 LV1 の禁止文字列に加えて新たに (
)
{
}
が禁止されています。私のコードの動作については、大変ありがたいことに、解説記事の中で出題者様が確認コードを書いて下さっています。私自身もはっきりわかって書いていたわけではないので、なるほどこうなっていたのか!というのが正直な感想ですw
「無双」と評された64~59文字(5~1位)のコードは、考え方は一切変えずに書き方を工夫していった(そして縮むたびに提出した)だけですので、順を追って見ていくことにします。
64~62文字(5~3位)のコード
r=i*200-i%500*100-i%100*80-i%50*10-i%10*8-i%5;r='.'+i<.5?"0"+r:r
r='.'+i<.5?'0':0;r+=i*200-i%500*100-i%100*80-i%50*10-i%10*8-i%5
r='.'+i<.5&&'0';r+=i*200-i%500*100-i%100*80-i%50*10-i%10*8-i%5
書き方が少しずつ違っているだけで、やっていることはどれも一緒です。 r の値を十進数の数値計算で求めて、必要に応じて先頭に "0" を付加しています。少し具体的に説明します。
(1)先頭の "0" の判定
答えを数値計算で求める関係上、 r の先頭が "0" になる場合には、その "0" を明示的に付加しなければなりません。 r の先頭が "0" になるのは、 i の最上位の桁の値が 0~4 の場合です。これを、
'.'+i<.5
という式で判定しています。つまり、 i の先頭に小数点を付けて、その結果が数値的に 0.5 より小さければ r の先頭に "0" が必要と判断しています。
(2)数値計算
胆となる計算の部分です。どのコードも共通で
i*200-i%500*100-i%100*80-i%50*10-i%10*8-i%5
となっています。これをどのように導出したのでしょうか?
基本的な方針は、「先に大雑把な値を求めて、細かい部分はあとで微調整する」です。つまり、 r の上位の桁から下位の桁に向かって辻褄を合わせていくことにします。
r の最上位は、500の珠の数です。 r の最上位だけが異なる2つの i を考えてみます。例えば
- i == 499 → r = "041414"
- i == 999 → r = "141414"
なので、大雑把に「 i が 500 増えると r が 100000 増える」と言えます。言い替えると「 i が 1 増えると r が 200 増える」となります。これが、上記の式の先頭の項 i*200
というわけです。
次に、 r の上から2桁目、100の珠の数を考えます。これも先程と同様に
- i == 899 → r = "131414"
- i == 999 → r = "141414"
ですから、大雑把に「 i が 100 増えると r が 10000 増える」すなわち「 i が 1 増えると r が 100 増える」となります。ところで、 r の最上位考えたときに i*200
としてしまいましたから、 r の最上位が変化しない場合には i*200 - i*100 = i*100 分が多すぎることになります。これを調整するのが、2番目の項 -i%500*100
というわけです。
このような調整を r の最下位の桁まで繰り返すことによって、最終的な式を得ることができます。確かめてみてください。
ここで、またも事件が起きます。じつは、これらのコードを提出したときまでは、 {
}
ではなく [
]
が禁止文字列だと勘違いしていたのでした!
61文字(2位)のコード
r=[i]<'5'&&'0';r+=i*200-i%500*100-i%100*80-i%50*10-i%10*8-i%5
コードを縮めようといろいろ試行錯誤しているときに、うっかり、禁止文字であるはずの [
]
を使ってしまい、提出してしまいました。テストページの判定がバグっているだとか、提出を無かったことにしてくれだとか、 Twitter でひとしきり大騒ぎした後、ただ自分が禁止文字を勘違いしていただけだと判明してかなり恥ずかしかったですし、今まで勝手に一人縛りプレイをやっていたと知って愕然としました。 [ ] は使えるのです!
59文字(1位)のコード
r=[[i]<[5]?0:r]+[[[i*2-i%500]+0-i%100*8-i%50]+0-i%10*8-i%5]
これまで禁止文字だと思っていた [
]
を、思う存分使って縮めてみました。なんと 6 組も使っています。前述の(2)の計算式
i*200-i%500*100-i%100*80-i%50*10-i%10*8-i%5
は、自明に
[[i*2-i%500]*10-i%100*8-i%50]*10-i%10*8-i%5
と書き換えることができます。これだけだと短くも長くもなっていませんが、 […]*10 は要するに数値の右に "0" を付けるということなので、 […]+0 とも書くことができます。これを利用して
[[i*2-i%500]+0-i%100*8-i%50]+0-i%10*8-i%5
と書き換えることができ、2文字も縮めることができました。
おわりに
楽しかったです。
『正規表現でどう書くの?』ひねくれた別解
(※ジョーク記事です。)
問題及び模範解答
増井雄一郎(@masuidrive)さんの「正規表現でどう書くの?」問題解説記事 #正規表現|CodeIQ MAGAZINE より:
(引用ここから)
問題
Perl、Rubyの最新版でサポートしている正規表現を利用して、下記の条件にマッチするようにア、イ、ウを埋めて下さい。
正規表現: “123456″ =~ /([0-9]+ア
)/
条件: $1 == “1″
正規表現: “123456″ =~ /(イ
[0-9]+ア
)([0-9]+)/
条件: $1 == “23456″
正規表現: “123456″ =~ /123(ウ
45)4/
条件: マッチする
正規表現: “123456″ =~ /123(ウ
45)6/
条件: マッチしない
解答
ア:?
イ:?:
ウ:?= (もしくは、?<!)
(引用ここまで)
(まともな)別解現る
(イ)「?>」が不正解な理由は? http://t.co/VY9vNKfIcz /増井雄一郎(@masuidrive)さんの「正規表現でどう書くの?」問題解説記事 #正規表現|CodeIQ MAGAZINE https://t.co/RUbszlfLOw @codeiqさんから
— カニ戯(ry (@bananawani_mc) 2014, 10月 6
ひねくれた別解
私も別解を考えてみました。方針としては、模範解答がいずれも「?」を含んでいるので、「?」を使わない方向で。
ア:A|1*
イ:23456)( もしくは \B.*)(
ウ:|A
Ideone で実行:
http://ideone.com/nZojmy
どうだエヘン!
ちなみに、動作確認は Perl でのみ行っています。 Ruby のことは知りません。
以下、一応説明です。
1つ目の式:
“123456″ =~ /([0-9]+A|1*)/
説明:「A」は、文字列に現れない文字なら何でもいいのですが、ともかくこれで | の左側はマッチしないのでキャンセルできます。結局 $1 は 1* にマッチする "1" になります。
2つ目の式:
“123456″ =~ /(23456)([0-9]+A|1*)([0-9]*)/
説明:$1 == "23456" になるようにするのですから、先頭に (23456) と書いてしまうのが素直な書き方というものです(多分ね!)。ちなみに $2 と $3 には空文字列がマッチします。
3つ目・4つ目の式:
"123456" =~ /123(|A45)4/
"123456" =~ /123(|A45)6/
説明:これも「A」はほぼ何でもよく、 | の右側をキャンセルしています。これで、上側の式は "1234" の部分がマッチしますが、下側の式はマッチしません。
『第6回デスマコロシアム』に参加しました
デスマコロシアムとは(テンプレート)
大雑把に説明すると、
- 問題文で与えられたある文字列を出力するコード(プログラム)を提出する。
- 言語は ideone で利用可能なものから選ぶ。
- コードのサイズが短いほどよい。(1文字につき1点減点)
- 同じ言語を選択した人が少ないほどよい。(1人につき10点減点)
- その他、コーディングとは無関係な運の要素も加えて、トーナメントで競う。
といった感じです。要するに、コードゴルフに運の要素を加えたトーナメントです。
第6回の問題
今回の出力は
2:3:5:7:11:13:17:19:23:29:31:37:41:43:47:53:59:61:67:71:73:79:83:89:97:101:103:107:109:113:127:131:137:139:149:151:157:163:167:173:179:181:191:193:197:199:211:223:227:229:233:239:241:251:257:263:269:271:277:281:283:293:307:311:313:317:331:337:347:349:353:359:367:373:379:383:389:397:401:409:419:421:431:433:439:443:449:457:461:463:467:479:487:491:499:503:509:521:523:541:547:557:563:569:571:577:587:593:599:601:607:613:617:619:631:641:643:647:653:659:661:673:677:683:691:701:709:719:727:733:739:743:751:757:761:769:773:787:797:809:811:821:823:827:829:839:853:857:859:863:877:881:883:887:907:911:919:929:937:941:947:953:967:971:977:983:991:997
という文字列です。997以下の素数を ":" で区切ったものになっています。ちなみに、私の出題予想はフィボナッチ数列でした。
今回は算術系な気がする… フィボナッチ数列とか “@tbpgr: 第6回デスマコロシアムは明日の朝受付開始です #デスマコロシアム #CodeIQ”
— 齊藤 (tails) (@saito_ta) 2014, 8月 25
素数列も一瞬頭をよぎったのですが、言語によっては素数が組み込みで用意されていて単に出力するだけになってしまうので、まあ無いだろうと思って脳内却下したのですが…
ちなみに期待していた言語はPARI/GPでした。
— tbpgr | peco | cat (@tbpgr) 2014, 8月 26
というか、むしろ Perl を除け者にするための問題としか思えないのですが!
私が提出した解答
1. Perl (45)
今回もPERLerの本気が見られるのを期待+(0゚・∀・) + #コードな情報戦 #デスマコロシアム
— カニ戯(ry (@bananawani_mc) 2014, 8月 26
期待されては、本気を見せざるを得ません。本気の Perl (45) を提出しました。
$,=":";print grep+(1x$_)!~/^(11+)\1+$/,2..999
正規表現で素数判定するコードです。具体的には、2~999の範囲の整数 $_
が素数かどうかを判定するために、 1x$_
で 1 を n 個並べた文字列を作り、その文字列が 2 文字以上の文字列の 2 回以上の繰り返しになっているかどうかを判定しています。ちなみに、私が最初にこの方法を知ったのは、 tybalt89 さんのこのコードです。感動したのを覚えています。
http://golf.shinh.org/reveal.rb?Gaussian+Prime/tybalt89_1323996492&pl
第6回デスマコロシアム(http://t.co/52r9L6nNd1)。やはりPerlが強い。「持たざるもの」の中では圧倒的 #デスマコロシアム #CodeIQ
— tbpgr | peco | cat (@tbpgr) 2014, 8月 27
2. Perl (44)
Perl (45) は本気のコードのはずだったのですが、翌日になって見直してみたらあっさり縮んでしまい、 Perl (44) を提出しなおしました。素数判定の方法は同じです。
print 2,map":$_"x(1x$_)!~/^(11+)\1+$/,3..999
なお、同日に Octave (26) を提出したため、この Perl (44) は集計に反映されませんでした。
3. Octave (26)
この時点での集計では Octave (27) が最短でした。最短賞狙いの私としては、早速試してみたのですが、リファレンスとにらめっこしつつどう書いても (34) より短くなりません。
printf("%d:",primes(991));disp 997
ヒントを求めていろいろやっている中、 Google で「octave delimiter」で検索してみたところ、このようなページが見つかりました。
GNU Octave: Simple File I/O
これぞ求めていた情報です!
dlmwrite(1,primes(999),58)
dlmwrite という関数は、指定した区切り文字を用いて出力するという、まさにこの問題のために存在するような関数です。短くならないわけがありません。ていうか、このコードは (26) なので、最短更新です。喜び勇んで提出しました。
この後しばらく、最短は Octave (26) で動きがなく、今回の最短コードはこれで決まりかと思われたのですが…
4. Perl (5)
とある言語で、デスマコロシアムのQAページに記述されている細則を利用して文字数を稼いでいる賢い解答者の方がおられますが、これ活用するとトップが変わるような・・・ #デスマコロシアム
— tbpgr | peco | cat (@tbpgr) 2014, 9月 7
と、トップが変わるですと!?
第6回デスマコロシアム(http://t.co/52r9L6nNd1)。全言語中最小文字数はRub(22)が1名になりました。 #デスマコロシアム #CodeIQ
— tbpgr | peco | cat (@tbpgr) 2014, 9月 10
本当だ! しかも、よりによって Ruby ですか! Ruby は触ったことがないので、さっぱりわからりません(ゴルフで Ruby が Perl より有利になることなんて滅多にないのでスルーし続けてきました)。困った…。
ところで、細則を利用して賢く文字数を稼ぐって、どういうことでしょうね? 短縮に使えそうな細則といえば、モジュールのインポートくらいでしょうか。モジュールを賢くインポート… って、もしかして、 Perl で書けば、こういうこと!?
use 5.01;
use constant a,"2:3:5:7:11:13:17:……中略……:991:997";
say a
1行目はひとまず置いておくとして、2行目は constant.pm というモジュールをインポートしていますが、(当時の)細則によればこれは文字数にカウントされません。結局、このコードの長さは、3行目だけがカウント対象なので (5) になってしまいます。
まあ、当然のごとく、この解答は却下され、モジュールのインポートの際にパラメータを渡した場合には文字数にカウントするというルールが整備されることとなりました。
5. Ruby (22)
どうやら最短を目指すためには Ruby を書かなければならないようです。 Ruby には手を出さないというアイデンティティと、デスマコロシアムは最短賞・最小賞を獲りに行くというアイデンティティとが、激しくコンフリクトしています。まあ、少しやってみて駄目だったら諦めるということで…
Ruby での短縮ということで、まず思ったのが goruby です(こんなことだけは知っている)。 goruby 自体はコマンドですが、モジュールとしては golf_prelude.rb というものになるようです。しかし、このモジュールは Ideone にはインストールされていないようです。
ということは、別のモジュールでしょうか。とりあえず Ruby の標準モジュールを片っ端から見て回ることにします。何せ Ruby を触るのはほぼ初めてなので、どのようなモジュールがあるのかさっぱり知らないのです。 CSV モジュールとかは Octave の dlmwrite に似ていて怪しい気もしますが、どうもコンマ区切り専用のようで、使えそうもありません。むむ…
まあ、とりあえずモジュールのことは置いておいて、普通に書いてみましょうか。ええとなに、 Prime は Enumerable で Object なのか。さっぱりわからんが、こんな感じ?
require 'prime'
$><<Prime.take(168)*?:
おや!? 普通に (22) で書けてしまいました! うわ、モジュールのドキュメントをひたすら読みまくったあれは一体何だったんだ…
生まれて初めて Ruby ゴルフやった。 #デスマコロシアム
— 齊藤 (tails) (@saito_ta) 2014, 9月 14
結果
Ruby (22) でなんとか無事に最短賞を獲得できました。デスマコロシアムでの最短賞・最小賞は、これで5回連続5回目です。おめでとうございます。ありがとうございます。せっかくなので、これからもトーナメントそっちのけで最短賞・最小賞を狙っていきたいと思います。
『ワンライナーでクールに解く!』所感(ネガティブ注意)
はじめに
CodeIQ で『ワンライナーでクールに解く!』と題した2問の出題に解答してみました。どちらも、与えられた問題の答えを解くためのワンライナーを書けという問題です。「解答評価のポイント」は「冗長さをそぎ落とし、どれだけ簡潔に問題を解決できているかが評価のポイントとなります。」とのことです。(この「解答評価のポイント」は、次のリンクから読むことができます。)
挑戦者求む!【プログラミング】ワンライナーでクールに解く!その1 by 無形ソフトウェアLLC 代表社員:村山 男也│CodeIQ
挑戦者求む!【プログラミング】ワンライナーでクールに解く!その2 by 無形ソフトウェアLLC 代表社員:村山 男也│CodeIQ
その1
問題
「一番大きいマトリョーシカの中に、6つの少しずつ小さなマトリョーシカが入って10500円で売っています。(マトリョーシカは全部で7つです。) マトリョーシカはひとつ大きくなるにつれて、150円ずつ値上がりします。一番小さなマトリョーシカの値段はいくらですか?」
要するに、等差数列の総和が与えられたときの初項を求める問題です。
私の解法
真ん中の大きさ(小さいほうから4番目)のマトリョーシカが 10500 / 7 円なので、それより3つ小さい一番小さなマトリョーシカは 10500 / 7 - 150 * 3 円です。これを Perl ワンライナーで素直に書くと、
perl -e 'print 10500/7-150*3'
となります。これが私の解答です。これ以上、複雑になりようがありませんね。逆に、これ以上簡単にしようとすると単に答えを表示するだけになってしまうので、まあこんなもんでしょう。
評価結果
評価は「4」でした。
今回はプログラム言語のワンライナーというカテゴリーですので、 ループ処理や組み込みのリスト演算などをクールに使用している 回答者様に高得点を差し上げております。ご了承いただければ幸いです。
とのことで、「高評価を獲得した解答例」として示されていたのが、次のコードです。
perl -e 'for($n=10500,$i=0;$i<7;$n-=150*$i++){}print $n/7'
…へ?
まあ確かにワンライナーですが、なんというか、普通のスクリプトから改行を機械的に取り除いただけですよね。
ていうか、「冗長さをそぎ落とし、どれだけ簡潔に問題を解決できているかが評価のポイント」じゃないんですか? 上記の「高評価を獲得した解答例」は、むしろ可能な限り複雑に書いてあるようにしか見えないんですが。
まあ、どのようなコードを「クール」と感じるかは人それぞれなのでそれはいいのですが、評価基準を示した以上、それに従って評価してもらわないと困ります。これではただの価値観の押し付けです。ともあれ、この問題や評価からは、出題意図がさっぱり見えてきません。
その2
問題
「1個の値段が40円、50円、77円の品物を合わせて11個買ったところ、代金が601円になりました。それぞれ何個ずつ買いましたか?」
私の解法
これは非常に困りました。ワンライナーで書くのに適したような簡単な解法を思いつかなかったからです。
ところで、「解答評価のポイント」には、「変数名などにキラリと光るネーミングセンスを感じるものなどは、高評価につながります。」とも書いてあります。そこで、変数名(の扱い)に趣向を凝らして、こんなコードにしてみました。
perl -e '@a=(50,40,77);$n50=11;do{$total=0;$total+=$_*${n.$_}for@a;++${n.$a[$cond=$total<=>601]};--$n50}while$cond;print"$_=>${n.$_}\n"for@a'
到底ワンライナーと呼べるような代物ではありませんが(それこそ改行を機械的に取り除いただけ)、簡単な解法を思いつかないので、仕方ありません。しかも、趣向を凝らしたせいで、可読性もさっぱりです。
評価結果
Perlの特徴を思う存分に発揮されており、文句なしの「5」評価です。
なんと、気に入られてしまいました。どうも、こういうコードが「クール」なようです。どうも私とは価値観が正反対です。
まとめ
結局、この出題者は、どのような意図でこれらの問題を出し、解答者に何を求めたかったのか、さっぱりわかりません。
CodeIQ では、以前にもひどい問題が出されたことがありますが(ボゴソートの計算量のやつとか)、 CodeIQ の中の人は、もっと問題や評価の質に気を配るべきだと思います。出題の質が低下したときに、最初に離れていくのは、スキルの高いユーザです。自分よりレベルが低い(と感じる)出題者から評価を受けようなどと思う人はいませんから。つまり、 CodeIQ の存在価値を維持し高めていくためには、出題の質は非常に重要だということです。