Derive Your Dreams

Twitter: @kinaba

12:20 07/11/29

シドニー

着いた~。 → いまここ

とりあえずManeth先生のVPNアカウントを借りて日記を更新。 時差1時間だと思ってたらサマータイムで2時間だったのを忘れてた、というか時間に関しては サマーだったのをすっかり忘れてた。という感じの現状です。

00:37 07/11/27

iroiro

@_tad_ Rubyを最新のに svn up したら全然バグらなくなりました!お騒がせしてスミマセン。

あなたが一番好きなアルゴリズムを教えてください」 という楽しい質問。自分のこれに対する答えは昔っから決まっていて、0.001秒で即答できます。 ヒープソート です。(ヒープソートと言っても色々バリエーションあると思いますけど、 特に、リンク先のWikipediaのページで解説されているような、配列をinplaceでソートするもの)

だって、入力データだった領域が滑らかに中間の作業用データ構造に切り替わっていって、 それがまた滑らかに出力データへと塗り替えられていくの、めっちゃ格好いいじゃないですか。 芸術的ですらある。 エッシャーの絵 を思い浮かべてもいい。

私がヒープソート好きな理由の95%を占めているのはこの見事な遷移ですが、それでなくても、 データ間の関係を明示せずに配列上の位置によってひっそりと表現するという 巧い方法を自分が初めて知ったのも多分ヒープソートですし、もう配列表現に限りませんが 「二分探索木と違って兄弟間の大小はどーでもいいよー」という一見なんともルーズに 思えてしまう半順序木というデータ構造が見事に活躍するのも面白い。こう、なんだか隅から隅まで ちょっと不思議な感覚で埋め尽くされているアルゴリズムだと思うのです。

23:48 07/11/25

PEG

PEG意見交換会 に行ってきました。

発表したネタ→ [ppt] [pdf] [ソースコード (Ruby 1.9)]。 半年くらい前に書いた 正規表現にマッチする例の生成 がわりと面白かったので、これを PEG でやるとどうなるだろうと思ってやってみました。 パーザジェネレータはみんな書いてそうだから一歩外そうと思ってこうしたはずなのに、 結局そっちも書くはめに。↓こんな感じの代物です。

require 'peg'

e = Pegexp.new <<PEG
  A <- a B / a
  B <- b A / b
PEG

e.example.take(5)        # == ["a", "ab", "aba", "abab", "ababa"]

e.example("A").take(5)   # == ["a", "ab", "aba", "abab", "ababa"]
e.example("B").take(5)   # == ["b", "ba", "bab", "baba", "babab"]

アルゴリズムはもっとずっとマシなのがあると思うので誰か考えて下さい。

ちょい補足。先読みPredicateの除去は基本的には

&e  => !!e
!e  => (e .* / ε)

こういう変形です。!e は、「eにマッチしたら入力全部食い尽くして後ろがマッチできなくさせちゃう意地悪君」 パターンに変換。ただし、!e の後ろに空文字列にマッチできるパターンが続いてると「マッチできなくさせちゃう」 ことにならないので、その場合は適宜何とかしてごまかします。

16:43 07/11/18

最大フロー

配列にした。あとDFSって毎回Srcからやり直さなくてもいいね → dinic_arr.cpp。トップの 15ms って凄いなあ。

22:18 07/11/17

マックス流

桜庭氏に資料を教えてもらったり。 とりあえず [PDF] A New Approach to the Maximum-Flow Problem を読んで理解したつもりになって実装してみたもの → goldberg.cpp。 何の変哲もない、と思います。まだ何の賢いヒューリスティックスも積んでません。 計算量の証明全然追ってないので細かいところが怪しい気がします。RELABEL の時ってキューにpushし直さないと いけないんだっけ。

imbue( locale("C") ) してるのは、しないとVC++で 整数の直後に','が来るとヤバいというのに引っかかったからです。このバグ一昨日初めて知った…。

19:14 07/11/16

最大流

昨日のコード、nyaasanのでいうfinishedみたいなチェックを入れないとO(|V|^2|E|)に なってない気がしてきた…

ニコグラマー

ニコニ考 - オープンソースプログラマーとニコ厨の違い を読んで。

弾さんのいうオープンソースプログラマーニコ厨も、 それを動かす力学は根本的には同じで、「何か作ってみたときに他の人の反応を聞きたい」 という思いに尽きるのではないかな、と思いました。いや、他の方がどうかは わかりませんが、自分の中のプログラマー的な部分とニコ厨的な部分は そう言っています。

多くの人の反応を得たいと思ったらどうすればよいか。方法は大別して2つあります。

前者がつまり「名前を売る」ということで (※)、 名前やURIを明らかにして活動を続けることで、 次に自分が作った作品をチェックしてくれるであろう人数を増やす。私の場合 k.inaba / kMonos.NET は明確にこの目的のためにあって、なにか猛烈に人に見て欲しいプログラムや文章ができたときに 何百人かには確実に見てもらえるであろう場を作るために、ここでこうしています。

逆にもし既に、そこに行って発表すれば反応を得られる場がすでにあるのなら、 わざわざ名前で人を集めたりしないで、ついつい 匿名 or 1作品1名前 で しがらみなく気楽にやりたくなってしまう。というか、やってしまう。 その そこに行って発表すれば反応を得られる場 が、 この場合ニコニコ動画なんじゃないかなーと。つまり、 人気投稿者になったりしなくても、最初から反応くれる人たちがたくさんいる場所。

って、私ニコニコに投稿したことはないですが、 プログラムの世界でも「作り手知らず」で発表するというのは珍しいものではないと 思うのですよね。例えば有名なところでは "47氏" みたいな。どこかのuploaderにzip置いたり、 Geocitiesに捨てアカ取って、名無しさんで「こんなん作ったがどうよ」と、 2chのスレにアドレス張ってみるスタイル。こういうのは既にそういう話題でにぎわっているスレや板があって、 名無しさんでもそこで反応もらえるわけです。もちろん「コテハンかっこわるい」みたいな 文化もあって仕方なく名無しにしてる人もいるのかもしれないですけど、 大抵の場合わざわざそこでコテハン名乗る必要すら感じていないんじゃないかという勝手な予想。

※: 弾さんは、記事では「名前を売る」メリットを特に 「他人からコンタクトされる機会を増やす」メリットとして評価されているようなので、 それとはこの考えは違いますよね。ここが違いなのかなあ。

仕切り直し

だんだん自分で何書いているのかわからなくなってきた。 えーとなんだろう、違いは作り手側を動かす原動力の方にあるのではなくて、 動画に関してはニコニコ動画みたいな場があるのに対して、プログラムに関してはそういう場が一般的にはない、 ということなのではないのかなーと思いました。

記事で引き合いに出されている blog、あれも、そういう "場" があればまた違うんではないかと思う。 はてなのキーワードについて漠然と思ってるんですが、 この仕組みってうまく使えば blog に関してそういう "場" にならんかなーとか。 例えば 「Haskell」を含む日記 をとりあえず全部読んでるという人は結構いると思う。なので、はてなにアカウント取って 1個だけHaskellに関する記事を書いてそれで終わり、という blog を作っても、 結構それなりな回数読まれるはず。この考えを進めると、著者単位で記事をまとめるのをやめて、 「blog の URI」という「名前」を無くしても反応もらえる場としての性質を保つことが 可能なのではないか等々。あー、それが増田なのか。 なんか違う気もするな。

19:51 07/11/15

最大流

ブームブーム らしいので Dinic(Dinitz? Dinits?) の最大流アルゴリズムを書いてみました→ dinic.cpp。 PKU 1459 を解くのに 1500ms くらいかかってますがこれは配列で書き直せば3倍程度は速くなるのではなかろうか。 あと、桜庭氏にならって他の人のコードは見ずに書いてみたのですが、自分のだいぶ冗長だなあ。

…と悲しくなってきたので、気分転換を試みました。 ぐぐって読んだ Dinic 法の解説してるページいくつかによると [PDF] Sleator-Tarjan による改良なるものがあるらしい。よしこれを実装してやるぜ!!っと思って論文読んで把握はした つもりなんですがこれ100行前後に納めるの無理ですね。基本アイデア(DinicでDFSで増加路構成を 繰り返すときに、前作った増加路片の情報を再活用)をちょっとでも取り込めないかと 少し弄ってたんですが、なかなか複雑なコードにしかならない…。

あとそういえば自分 Goldberg-Tarjan のアルゴリズムを全く理解してないので一度ちゃんと勉強しないとなーと 思って早幾年なのですが、ううむ、ソース読むか。 oxyさんの前原さんの。 誰か、「10分でわかる Goldberg-Tarjan」とか解説記事書くといいと思うんだ。

20:05 07/11/14

moving

やっとこさオーストラリア行きのチケット買ったよー。11/28に出ます。

ヘッドドロップ

Array#tail のスレッドを読んだり、そこで最近のRubyは takeやdrop があるのかーと知ったりして、なんか面白かったので自分ならどういうメソッド名にするか考えてました。 自転車置場のバイク小屋がどうこうというあれですが、現時点での結論はこう。 Rubyとの互換性とかそういったものはこれっぽちも考えてないです注意。

# My妄想                     # 結果      == Rubyで
[1,2,3,4,5].head             # 1         == first
[1,2,3,4,5].head(1)          # [1]       == first(1), take(1)
[1,2,3,4,5].head(2)          # [1,2]     == first(2), take(2)
[1,2,3,4,5].head{|x|x<3}     # [1,2]     == take_while{|x|x<3}
[1,2,3,4,5].drophead         # [2,3,4,5] == drop(1)
[1,2,3,4,5].drophead(1)      # [2,3,4,5] == drop(1)
[1,2,3,4,5].drophead(2)      # [3,4,5]   == drop(2)
[1,2,3,4,5].drophead{|x|x<3} # [3,4,5]   == drop_while{|x|x<3}
alias drop drophead

[1,2,3,4,5].tail             # 5         == last
[1,2,3,4,5].tail(1)          # [5]       == last(1)
[1,2,3,4,5].tail(2)          # [4,5]     == last(2)
[1,2,3,4,5].tail{|x|x>3}     # [4,5]     == (rtake?)
[1,2,3,4,5].droptail         # [1,2,3,4] == (rdrop?)
[1,2,3,4,5].droptail(1)      # [1,2,3,4] == (rdrop?)
[1,2,3,4,5].droptail(2)      # [1,2,3]   == (rdrop?)
[1,2,3,4,5].droptail{|x|x>3} # [1,2,3]   == (rdrop_while?)

[1,2,3,4,5].pop              # 5      == pop      破壊的
[1,2,3,4,5].pop(1)           # [5]    == pop(1)   破壊的
[1,2,3,4,5].pop(2)           # [4,5]  == pop(2)   破壊的
[1,2,3,4,5].pop{|x|x>3}      # [4,5]  == (なし?)  破壊的

head はともかく、tail が Haskell や ML その他の tail と意味が違っているというのが かなり大きな問題点に思えます。自分でもかなり迷いそうかなと思いました。 ただ、Unix の tail コマンドを使うときに一切迷わないことを思い返せば、 別に実際には混乱することもないかなーと思い直しました。 J の {: / Tail"select the last item" みたいなので、今週は J に合わせよう週間です。 ちなみに drophead は }. / Behead、 droptail は }: / Curtail だそうな。

あと、Rubyとの互換性とか考えていないとかいいながら考えてるんですけども、 Enumerator でしたっけ、その辺の仕様全く把握してないんですが、 .head 引数無しと .head{ブロック} に違う意味を持たせるのはよろしくないということになってるのかな。

それはさておき

マイ妄想は脇に置いておくとして、Rubyにどうなって欲しいかと考えると…。 a[1..-1] は a.drop(1) って書ければ十分満足ではあるかなあ。rdrop_while もしくは pop_while はちょびっと欲しい。

17:52 07/11/13

moved

やっとこさ kmonos.net のサーバ移りました。あとはDNSの浸透待ち。

PATH_INFO使ってるPHPでハマったり、 あと .htaccess で Options 使えない のかーとか。Files と FilesMatch も使えない気が。自分が別のとこミスってるだけかも。 あと、独自ドメイン使うとauto_indexが参照してる/icons がちゃんとエイリアスされてなくて困った。RedirectPermanent でごまかしたけど正しくはどうすればいいんだ。 他になんかおかしくなってるところ見つけたら突っ込んでやって下さい。

移転ついでに diki 0.07

21:31 07/11/12

PTAPG 2nd

Parsing Techniques - Second Edition』 のページにとうとう

The new edition is finished and has been sent off to the publisher, Springer Verlag!

の一文が加わっていることに気づきました。うひょー。 SpringerのページにはDecember 2007って書いてある。 Amazon.comはまだ特に何も。 定期的に延期のお知らせが更新される様を眺めていた甲斐がありました。 構文解析好きの諸氏は要チェックです。

前に紹介した時の記事。3年半前か…。

11:11 07/11/11

J (続き)

もう少し J っぽいコードを書いてみます。 e を計算しよう。 この式を使います。

e = Σ_{n=0}^∞ 1/n! = 1/0! + 1/1! + 1/2! + 1/3! + ...

無限に足し算するわけにもいかないので、とりあえず 1/9! 辺りまで足し算。

> jconsole
   +/ % ! i. 10
2.71828

できました。1ステップずつ見ていくことにすると

> jconsole
   i. 10
0 1 2 3 4 5 6 7 8 9                  NB.  i. は 0 1 2 ... N-1 というリストの生成
   ! (i. 10)
1 1 2 6 24 120 720 5040 40320 362880 NB.  !  は単項演算子として使うと階乗の計算
   % (! (i. 10))
1 1 0.5 0.166667 0.0416667 0.00833333 0.00138889 0.000198413 2.48016e_5 2.75573e_6
                                     NB.  %  は単項演算子として使うと逆数の計算
   + / (% (! (i. 10)))
2.71828                              NB.  +  は二項演算子として使うと普通の足し算
                                     NB.  /  はadverb(副詞)で、二項verbを修飾して、
                                     NB.  リスト全体に適用する op / (a b c ... z) = a op b op ... op z 働き

こんな感じです。括弧を省略したのが最初の形です。 普通に書くと浮動小数点数として計算されますが、数値10の代わりに 多倍長整数リテラル10xを使うと、多倍長整数 + 有理数 での計算になります。

   +/ % ! i. 10x
98641r36288
   +/ % ! i. 30x
2403440095914245030058787948979r884176199373970195454361600000
   +/ % ! i. 99x
25624945006073464385380883657806082873247230158211933558866180402772651909938024
900903079335873944423562364417406869039758536717156534765324218635386178181r9426
89044888324774562618574305724247380969376407895166349423877729470707002322379888
2976159207729119...

上位100桁 を知りたくなりました。 10^100 倍して、小数点以下を切り捨てれば良さそうです。

   <. ((10x^100) * (+/ % ! i. 99x))
27182818284590452353602874713526624977572470936999595749669676277240766303535475
945713821785251664274

できました。^ が累乗の演算子です。xorじゃないです。<. が切り捨てです。 全部優先順位は同じで右結合なので、括弧をいくつか外して

   <. (10x^100) * +/ % ! i. 99x
27182818284590452353602874713526624977572470936999595749669676277240766303535475
945713821785251664274

これでも同じ意味ですね。ただし 10x^100 の周りの括弧を外すと

   <. 10x^(100 * +/ % ! i. 99x)

こう解釈されちゃいますので注意。

さて、ちょっと別の書き方も考えてみました。「10^100 を掛ける」代わりに「10 を 100回 掛ける」コードです。

   <. (10 * ^: 100) (+/ % ! i. 99x)

^: も adverb で、(f ^: n) と書くと「f を n 回適用」する処理になります。 (a f ^: n) なら 「a f を n 回」。なので、この場合だと上のコードは

   <. 10 * 10 * ... 10 * (+/ % ! i. 99x)

と同じ働きというわけです。元々多倍長の数に1個ずつ 10 * していくので、 10x にしなくても平気です。 さらに、 A 1.4.2 Operators Before Verbs に adverb の方が verb より先に適用されると書いてあったので全部括弧を外していいらしく

   <.10*^:100+/%!i.99x
27182818284590452353602874713526624977572470936999595749669676277240766303535475
945713821785251664274

全部ぎっしり詰めちゃったりできます。

J (続きの続き)

昨日のコレを One Liner にしよう編。

perms =: verb : 0
  len =. #y
  num =. !len
  idx =. i. num
  idx A. y
)
wd perms stdin ''  NB. 入力の並び替えを全通り出力

とりあえず余計な変数を全部とりのぞくと、perms関数はこうなります。

perms =: verb : 0
  (i.!#y) A. y
)
wd perms stdin ''  NB. 入力の並び替えを全通り出力

関数合成を駆使して perms を i. と ! と # と A. の合成で書くことができれば完璧で、

wd (i. と ! と # と A. の合成で書いた式) stdin ''

こんな風に1行にできるはずです。 さてさて、J の大きな特徴として、 Hook と Fork という 合成があります。(bu) のように二項verb (b) と単項verb (u) をくっつけて書くと

(bu) y  ==  y b (u y)

こういう意味の合成になるのだそうな。例として

tax =: verb : '0.05 * y'  NB. y円の物にかかる消費税

(+tax) 100                NB. 100 + tax 100 == 105

こんなのがよくあるみたい。さっきの perms 関数をよく見てみると、 A. の左と右さえ交換できれば この Hook が適用できそうな形です。 当然左右を交換する adverb が用意されていまして、ずばり ~ です。

x A.~ y  ==  y A. x

というわけで Hook と ~ を使って書き直すと

u =: verb : 'i.!#y'
wd (A.~u) stdin ''

こうなりました。u は i. と ! と # を普通に合成した形なので 普通に合成する演算 & で書けます(…というのは不正確でこの辺りも色々あるんですが略)。 無事一行になりました。

wd (A.~i.&!&#) stdin ''

さらに

ここで wd のかわりに stdout

stdout (A.~i.&!&#) stdin ''

とすると、改行が入ってくれないので問題の解答としては不適切になってしまうのですが、 仮にこのパターンだったとすると、さらに面白い関数合成 &. が使えます。

(A.~i.&!&#)&.stdin ''

f &. g という合成は、g を適用してから f を適用してから g の逆演算を適用

(f &. g) y  ==  (g^:_1) f g y

                NB. +: 2倍する
                NB. >: 1を足す。逆演算は1を引く <:
(+: &. >:) 5    NB. ((5+1)*2)-1 == 11

という物。stdinの逆はstdoutと定義されているので、 &.stdin と合成することで結果が自動的に出力に回るわけです。

00:28 07/11/10

J

最近 J言語 で遊んでます。 遊んでますといいますか、遊ばれてます。

をいったり来たりしながらお勉強中です。簡単にご紹介。

インストール

Stable から適当にダウンロードして入れるとよいです。

Windows版だと J.exe が GUI っぽいの開発環境っぽいもので、jconsole.exe が コマンドラインから叩く対話型シェルでした。以下のコード例は jconsole でしか動かしてません。 ちなみに Java にも jconsole というコマンドがあるのでそっちを起動しないように注意しましょう。

標準入出力

マニュアルの読み方がさっぱりわからなくてechoのやり方がわかるまでに5回くらい挫折しかけました。 まあわかると簡単で

s =. stdin ''
stdout s

stdin 関数(そういえば関数に当たるものはJではverbと言うらしい)で、標準入力全体を1個の文字列に読み込みます。 0引数のverbというものが存在しないのでstdinは仕方なく1引数になってるぽい。引数は 0 でも 123 でも '' でも なんでもいいです。で、stdout で標準出力。=. はローカル変数への代入です。なのでもちろん変数使わないで 書いても同じです。

stdout stdin ''

さてゴルフします。

wd(1!:1)3

stdout の代わりに wd というのを使います。この wd、実行環境によっては色々豪華な機能があるっぽいんですけど、 とりあえずコンソール環境では wd =: echo という定義でした。で、echo というのはだいたい おおむね stdout です。ただしなんか大きめのデータを出力しようとすると後ろの方が勝手に ... で省略されるので、 対話環境での表示用ということなんじゃないかと思います。 この程度なら ... にならなかったのでOK。

(1 !: 1) 3 が、要するに stdin '' です。 二項verb !: は整数で番号を与えると、foreign procedure を色々返してくれます。 1!:1Read らしい。 3 は標準入力を表すIDです。ちなみに同じ要領で、stdout s の代わりに s (1!:2) 4 とも書けます。

この辺りの定義は system/main/conlib.ijs に書いてありました。

verbs

入出力ができたので色々計算してみることにしました。 J の verb (≒関数, 演算子) は単項(Monad)か二項(Dyad)のどちらかです。 大抵のverbは単項でも二項でも使えます。どっちで使うかで意味ががらっと変わるものもあります。 例えば * は、二項で使うと掛け算で、単項で使うと 正なら1,零なら0,負なら-1を返す、いわゆるsign関数です。

2 * 3    ==> 6
* 3      ==> 1

これは普通にベクトル演算ができて、

2 * 3 4 5      ==> 6 8 10
2 3 4 * 5 6 7  ==> 10 18 27
3 4 5 * 2      ==> 6 8 10

* 2 1 0 _1 _2  ==> 1 1 0 _1 _1

値を並べて書くとベクトルになって、長さが等しいベクトル同士か、スカラ対ベクトルにならverbがそのまま 適用できます。負のリテラルは - ではなく _ で始めるらしい。ひとつだけ注意点として、全部右結合です。

2 * 3 + 4 ==> 14

あとはもう組み込みのverbを 関数合成その1 関数合成その2 で組み合わせまくると色々できちゃいます。

実践編

実践編 : parmutater

perms =: verb : 0
  len =. #y      NB. yの長さ
  num =. !len    NB. yの長さの階乗
  idx =. i. num  NB. 0, 1, 2, ..., num-1

  idx A. y
)
wd perms stdin ''

こんな感じで。verb : 0 ~ ) がverb定義です。引数はMonadなら y、Dyad なら x と y で参照します。 ここでは、与えられたリスト y の全permutationを返す処理を実装しています。 とりあえず # と ! と i. という verb を使って、0 からpermutationの個数-1 までのリストを作りました。 次が流石 J といったところで、以下のような素晴らしい verb A.

0 A. 'abc'   ==> abc
1 A. 'abc'   ==> acb
2 A. 'abc'   ==> bac
...
5 A. 'abc'   ==> cba

が用意されているので、これを使うだけです。あとは頑張って縮めると20Bになりました。 とりあえず数論ぽい計算をする問題はひととおりJで解いてみようかなーと思っています。

06:33 07/11/03

くさび数

Sphenic Numbers の挑戦ログ。 基本アイデア「約数の数を使う」については ょゎさんのメモ が詳しいです。私はひたすら約数8個の余計なパターン(ab^3, a^7)をはじく方法を考えてました。

最初に思いついた案が、「約数が 8 個で、v^3 の形の約数を (1以外に) 含まないもの」を数える 66B。 ちなみにここで (1以外に) という条件が混入してたので、最後まで約数数えループが 1..n ではなく 2..n になってました。

763.times{|n|z=0;2.upto(n){|v|z+=n%v>0?0:n%v**3>0?1:9};z==7&&p(n)}

んで、よく考えたら「約数が 8 個で、v^2 の形の約数を (1以外に) 含まないもの」で十分じゃんと気づいて、 あとマジメにコード縮めたら62B。

763.times{|n|z=9;2.upto(n){|v|n%v<1&&z-=n/v%v>0?1:9}==z&&p(n)}

ここでしばらく停滞してたのですが ksk さんに抜かれたので考える。どうもzというカウンタを使って 数数えてる部分が一番無駄っぽく見えるので、Enumerable#select一発で判定できる方法があるはずだと考えて、 条件を「v^3 型の約数が1個でもでたらアウト」じゃなくて「約数を v^3 型のものを除いて数えたら7個」と 変えてしまっても動くことに気づく。なぜ動くかはょゎさんの解説の通り。で、61B。

763.times{|n|(2..n).select{|v|n%v<1&&n/v**3>0}.size==7&&p(n)}

&& を後置ifに変えたらStatisticsまでkskさんと完全一致するので、同じ解であろうと推察。 後追いで同じ解では悔しいのでしばらく考えてサイズ判定部を縮めた 59B

そして、なんとなくこのアルゴリズムをPerlで書き直してみるテスト。 直訳すると "763.times" == "for 1..762" で "select.size" == "grep" なのですけど、 forもgrepも暗黙のループ変数として$_を使うため二重ループにするとコンフリクトしてしまう。仕方がないので for 1..762 を諦めて手でループカウンタをインクリメントしたバージョンで 54B。 Rubyと違って、0が偽になったり比較演算が1 or 0を返す言語はこういう問題では色々と楽です。 (flagitiousさんyowaさんの解にある Integer#[] を使う手は全然考えなかった…不覚。)

7-grep$^%$_?0:$^%$_**3,2..$^or print$^,$/while$^++<763

この時点でySasさんとバイト数で並んでいたのですが、Statisticsを見ると、ySasさんは $^ に当たる変数を 4 回しか使っていないことが見て取れる。対して私のは 5 回、 小手先の変更では 4 回にならない。きっとその 4 回で済む方法を見つけられれば さらに縮むはず…と考えたけど思いつかずタイムアップ。 外側for 1..762でもそこで$_を使わなければ 問題ないのですねなるほど…。

さらにJavaScriptに持って行ってみた。特に短いループ方法が用意されている言語でもないので、 地道にfor(;;)でループしてカウントアップ…してたらコード残ってないのですけど確か63Bで、 トップのmurky-satyrさんに負けている。むむむ、と考えて、ループ最内周の約数数え上げ をいじってたらこんなのでました 61B。 これはわりとお気に入り。

for(n=0;v=++n<763;i||print(n))for(i=7;v++<n;)i-=n/v/v%v>0>n%v

さらに調子にのって C で書いてみたら 82B か何かから縮まなかったので挫折。 ちょっと自分は C ゴルフ力が足りなすぎるのではないか。

reveal

±5Bくらいの範囲の人のアルゴリズムは皆同じだろう…と思っていたら、 revealで、v^2 型の約数が出たらループを打ち切るという があることがわかりなるほどなぁ…と感心しているところ←今ここ

presented by k.inaba (kiki .a.t. kmonos.net) under CC0