Partition Function
今日は大晦日。また新しい年が来る。来年は、個人的には大変良い年となる。
さて、ゴルフ。
Partition Function
なかなか面白い問題だったと思う。wikipedia 等より、Partition Function p(n) は以下のように表されることがわかる。
P(k,n)=0 if k>n -- (1) P(k,n)=1 if k==n -- (2) P(k,n)=P(k+1,n)+P(k,n-k) otherwise -- (3) p(n)=P(1,n) -- (4)
これより、横軸を k 、縦軸を n に対応させて N x N の行列を考えると、第 1 列が Partition Function となる。(1) より、行列の右上半分は 0 となり、(2) より対角線要素は 1 である。行列の左下半分を (3) の式により対角線要素から左に向かって、つまり、k が小さくなる方向へ計算して行き、k==1 (左端)となったところが求める、Partition Function p(n) の値となる。C で書くと、
p[99][100];n;
main(k,a){
for(;a=n++<100;printf("p(%d)=%d\n",n,a))
for(k=n;k;)p[k][n]=a+=p[k][n-k--];
}100 x 100 の行列を配列として確保し、1 行目から順に値を求めていく(外側の for 文)。各行においては、対角要素から左に向かって計算して行く(内側の for 文)。対角要素は常に 1 なので、変数 a を 1 で初期化し、その a に、上記 (3) 式の右辺の第 2 項を足すことで、1 つ左の項を求めている。このまま、左端の列まで計算すると、a の値が Partition Function の値となるので、それを出力している。
〜〜〜
さて、新たに、endless 問題として、Paths in matrix と Paths in matrix 2 を出題した。どちらも、最近、地下鉄の日能研の広告(http://www.nichinoken.co.jp/column/shikakumaru/2012/1212_sa.html)に出ていた問題からヒントを得たものである。この日能研の問題は、中学の入試問題だそうだ。すごいな。小学生がこんな問題解けるのか。特に問 2 の合計が 70 になる道順が何通りあるかなんて、結構難しいと思う。でも、小学生に解けるのだから、golfer なら簡単だろう。
問題はちょっとアレンジしてある。Paths in matrix は、単純に正方行列の左上から右下への道順の個数を求めるというもの。ヒントになってしまうが、この問題を考えていた時、以下に気が付いた。行列のある位置、(i, j) に関して考えると、この位置に来る道順の個数は、上 (i, j-1) から来るものと、左 (i-1, j) から来るものの和であるということが言える。これって、行列を 45 度右に回転して頂点から見ていくと、パスカルの三角形じゃん！っということになる。漸化式で書くと、
p(n)=P(n,n)=P(n-1,n)+P(n,n-1)
Partition Function ともちょっと似てたな。
Paths in matrix 2 は、もろ、日能研の問 2 の汎化。合計が 70 だけではなく、golfer なら、すべての合計値に対して道順の数くらい数えられるだろう、という問題である。頑張ってください。
〜〜〜
では、よいお年を。
2013/1/1追記
Paths in matrix は、411. PATHS と同じだった。記憶から消えてた。まぁ、でも、今回のは、output が 32bit int のレンジに入っているので、より多くの言語で解きやすいだろう。
2013/1/3追記
Paths in matrix 2 について。
はじめの数項をみると、Partition function と同じだ。前述日能研のページの解説にもあるが、すべての道順は、1〜10 の数を最低 1 回は使う。なので、その分を差し引くと、道順の全 19 ポジション(通過する行列要素)の内、残り 9 ポジションに、1〜10 の数をどう配置するかで道順は決まることになる。たとえば、9 ポジションすべて 1 とすると、合計が 64 の道順になる。8 個の 1 と 1 個の 3 とすると、合計が 66 の道順として＊確定＊する。以下のよう。
1 1 1 1 1 1 1 1 1 1 2 3 4 5 6 7 8 9 10 # 9 個の 1。合計：64 1 1 1 1 1 1 1 1 1 2 2 3 4 5 6 7 8 9 10 # 8 個の 1 と 1 個の 2。合計：65 1 1 1 1 1 1 1 1 1 2 3 3 4 5 6 7 8 9 10 # 8 個の 1 と 1 個の 3。合計：66
これは、つまり、64 との差を 1〜10 の数字 9 個の和として表す表し方である。また、その表し方の個数が求めるものとなる。この 9 個という制限は、9 個の 1 との差分で考えると、2 〜 10 の数字の 9 個以下の和で表す表し方、と言い換えることができ、さらに、この使う数も 1 との差分で考えると、結局、以下のように問題を再定義することができる。
これは、N が 9 より小さいときは、おのずと「1 〜 9 の自然数」、「最大 9 個」という制限は成立するので、この範囲では、自然数 N に対する Partition Function と一致するということになる。なので、本問のはじめの数項は、Partition Function と一致したということだ。
なんだか、新しい問題を作ったつもりだったのだが、結局 Partition Function のバリエーションにすぎなかったということか。とはいえ、N > 9 の時の制限をどう解決するかは、それはそれで難しそうだな。
2013/1/4追記
Partition Function の補助関数 P(k,n) は、自然数 n を k 以上の自然数の和に分割する方法の個数だった。wikipedia にもそう書いてあった。P(n,n) が 1 なのは、n は n としてしか表せないからであり、また、P(1,n) が Partition Function となるのは、1 以上の自然数の和で表す個数なので、定義そのものである。この点を考慮すると、昨日の追記で書いた制限「1 〜 9 の自然数」という点は、
P(k,n)=0 if k>9
という条件を足してやればよいのではないか？(k,n) の行列で言うと、k 列より右はすべて 0 ということ。これなら簡単に計算できそうだ。
残すは、「最大 9 個」という制限だ。こちらは、P(k,n) の再帰の深さに対応しそうな気がする。ちょっとやってみるか。
2013/1/4追記2
できたことはできたが、120B と短くならなかった。
p(k,n,d){return n?d>9|k>9|k>n?0:k<n?p(k+1,n,d)+p(k,n-k,d+1):1:1;}
n;main(){for(;n<82;)printf("%d:%d\n",++n+63,p(1,n,1));}もう少しチューニング可能かな？
Fill in the blanks
Fill in the blanks 終了。
awkの戦いは結構しんどかった。
始め 34B で並んでから、33B、32B と後追いになってしまったし、追いつくのが大変だった。
34B は
RS="_"{ORS=substr(S=S$0FS,i,1)}i++これでも、結構難しかったし、これ以上縮まるとは思いもよらなかった。この解は、考え方は割と面白い。awk の行区切り文字(RS: Record Separator)として、'_' をを指定し、出力行区切り文字(ORS)を入力の先頭行の文字を順に割り当てることで、問題の 'fill in' を実現するというもの。$0 の後ろに１文字 FS にて空白文字を入れているのは、最終レコードの後ろにつく ORS を空白にするため。
33B は、
RS="_"{ORS=substr(S=S$NR,i,1)}i++$0 の代わりに $NR とすることで、$2、$3、、、と参照することになるが、それらは、空なので、最終レコードの後ろにつく ORS を空白にすることができる。
32Bは、
ORS=substr(S=S$0FS,i++,0<RS="_")
ちょっとした式変形。でもなかなか思いつけなかった。$NR を $0FS に戻したのは、$NR だと ORS が空になってしまい、式の値は、false と判断され、最終レコードが出力されないため。
★☆★☆★☆★☆
fill dots@awk
◇◆◇ 以下 Spoiler注意 ◇◆◇
少し前の endless 問題。
ちょっと考えてたら、awk で、26B と短い解ができた。この問題、'*' に囲まれた空白をドット '.' で置き換えるという問題。当初は、
{for(;sub(/\* /,"*.")+sub(/\. /,"..");)}1こんな解で、41B。わりとすなおな解だ。この問題、mawk 独特の behavior を使うと短くなる。150. duplicate certain lines _C_で使った方法だ。つまり、gsub に正規表現として、/^ で始まる行の先頭からの指定を指定したものを使うもの。gsub と '/^' と少し矛盾した組み合わせのようだが、mawk では、この組み合わせは面白い動きをする。たとえば、行の先頭から続く 'A' を 'B' に置換するという問題を考えると、
AAAAAAAAxxAAxx
↓
BBBBBBBBxxAAxxつまり、このような置換を考えた場合、通常の awk では、やりにくいが、mawk では、
gsub(/^A/,"B")
でできてしまう。もし、awk の正規表現に back reference があれば、
{for(;sub(/(^|B)A/,"\1B");)}とでもするところだが、back reference が無いため、上のようなやり方が有用だ。因みに、行末から逆方向にやることはできないようだ。
gsub(/A$/,"B")
これは、期待通りには動かない。
さて、fill dots に戻ると、まず、全空白を一気に "." に置き換えてやる。その後、先頭から始まる "."* を上記の方法で、空白に戻すということをやると、以下、26B になる。
gsub(FS,".")gsub(/^\./,FS)
Line counter
Line counter が公開になった。この問題、出力が 7 と 1 と 8 だけなので、「また、くだらない embed/random 問題かぁ」っと思ったが、行数を数える、ということ自体は、ゴルフとしては割と面白いと思ったので、“真面目に”やってみた。
vi
vi はいろいろな解法があり面白かった。
:%s/.*/+1
V{JS^R=^R"^H
^[ZZこれで23B 。この解は、まず、各行を "+1" に置換したあと、全行を連結して結果の式（"+1+1+1+1+1+1+1"といった式）を評価して行数を求めるというもの。
s^R=line("$")
^[lvG$dZZ次は、行番号を line() 関数で取得するというもの。最終行は、移動して line(".") ではなく、line("$") で直接取れる。これで、21B 。この解では、行数を得たあとに、残りのデータを削除するのが若干 B を食う。で、考えたのが、以下。
VGr s^R=line("$")
^[ZZこの解のアイデアは、まず、全行を "VGr " で、スペースに置き換えてしまう。そのあとで行数を数えて先頭行に書いている。これは、anarchy golf では、trailing space は無視されるという性質を使っているもの。これで、20B 。
r19@='J0^A' lDZZ
最終的にたどり着いたのがこの 15B 。これは、マクロ実行により行の結合("J")が何回できるかを数えるという方法。マクロは "J" コマンドに失敗すると exit するので正しくカウントできる。カウンターは初めに "r1" で作っておき、マクロの実行ごとに "^A" でカウントアップしている。この解はコンパクトだが、行数が一桁であることを仮定している、ちょっと cheat 気味な解。
他の人の解は、もっと短くなっているが、それらは、"wc -l" を "!" で実行している cheat 解。やってて面白いのかな。くだらね。
C
C にとってはそんなに難しくはないが、43B と 42B の間にはちょっとした工夫がいる。42B トップは ush さんだが、私も同じ解にたどり着けた。inaniwa さんも同じだ。
n=48;main(b){for(;gets(&b);)n++;puts(&n);} // 42B
main(n,b){for(;gets(b);)n++;putchar(n+47);} // 43Bn を 48 で初期化しておいて、puts() に持っていくのが面白いところ。
bash
bash にとって、本問の問題は、最終行に改行がついていないところ。問題作者はたぶん意識していなかったのではないかと思うが、むしろその点が bash golf での工夫する点となり面白かった。
当初単に sed を用いて
sed -n $=
という 9B 解を作った。しかしながら、sed を使わない 9B を思いつき、bash の代わりに、zsh で投稿した。
rev|wc -l
rev コマンドが最終行に改行文字を補ってくれる。
このあと何か同様のコマンドがないかと探していたら、nl コマンドを見つけた。このコマンドは、各行に行番号を付けてくれるというもの。ただし、本問では、その行番号は使わず、単に、最終行に改行を補う目的で使っている。
nl|wc -l
これで、8B 。
最近読んだ本
孤島パズル/双頭の悪魔：有栖川 有栖さん
江上二郎シリーズ。長編推理小説。このシリーズは面白いと思う。
「読者への挑戦」は相変わらず分からず。
谷崎潤一郎マゾヒズム小説集：谷崎潤一郎さん
谷崎潤一郎さんは（『さん』付けがしっくりこないな）、大学のとき結構読んだ。代表作の『細雪』や『痴人の愛』は面白かったな。また、台所太平記には、親戚が登場しているというのを母から聞いたことがある。
この本は短編集。タイトルから想像されるかもしれない性的描写はあまりない。もう少しやわらかい(?)曖昧なＭだ(ったと思う)。
十角館の殺人：綾辻 行人さん
長編推理小説。大学生が主人公なところもあり、有栖川 有栖さんの江上二郎シリーズと雰囲気は似てるな。事件が起こっていく前半から中盤は面白いが、終盤の種明かしはあまり好きな展開ではなかった。
共食い：田中 慎弥さん
芥川賞受賞作。ちょっと前に話題になっていた本。あまり好きじゃないな。ちょっと狂気な世界だと思う。
話虫干：小路 幸也さん
新聞の書評に出ていて、面白そうだと思ってすぐに買って読んだ。漱石の『こころ』の本に話虫という虫が入り込み、話の内容を変えてしまう。それを元に戻すために図書館員が本の世界に入り込むという話し。コンセプトが凄く面白そうと思って期待して買ったが、ちょっといまいちだったかな。文学に詳しい人なら面白いのかもしれない。私には夏目漱石さんとラフカディオハーンさんと石川啄木さんの関係なんてわからないよ。
ビブリア古書堂の事件手帳１〜３：三上 延さん
最近の私にとっての一番のヒット作。結構話題になっている本。めちゃくちゃ面白く３巻を一気に読んだ。短編のミステリー。短編だけど『謎解きはディナーの後で』より深い感じがして面白かった。舞台が鎌倉周辺なのも市民として好感が持てた。年内に４巻がでるとか。期待している。
Hello broken keyboard
Hello broken keyboard が終了した。近年まれに見る盛り上がりだった。
C
トップ shinh さん@12.336B。
a;m;t;main(){
a++;a++;a++;m++;t++;
n(++t+a+t*a*t*a);i(t);i(a*a);i(a*a);i(a*t*t);n(t*t+a*a);n(m);
i(t+a*t*a);i(a*t*t);i(a*(t+a));i(a*a);i(m);n(t);
}
n(i){
((int(*)())(
(
t*t*(t*t+a*a)*t*t*(t*t+a*a)*(m+a*a*a*t*t)+ // A
**(int**)( // B
((t+t*(t+a)*a*t*t)*(t*t+a*a*(t+a*a))+a)* // C
((t+t*a*t*t*t)*(t+t*t*t*a+a*a*a*a)+m)* // D
t // E
) // F
)
)
)(i+t*t+a*a*a);
}
i(i){n(t+t*a*(t+a*a)+i);}少しはみやすくなるように適当に改行を入れた。
まず、ぱっと見、変数 t は mm など二文字変数にすればいいような。それはいいとして、main() 本体は、i() や n() で "Hello, world!" を一文字ずつ出力しているということだな。i(a*a) が "l"(エル) だ。
i() は、n() を呼んでいるが、ここは、単に文字数を減らすための計算だけのよう。
中心は、n() 。ここも、括弧の対が余分なような。まぁ、それはいいとして、問題は A 〜 Fの 6 行だ。関数へのポインターにキャストしてその関数を呼んでいるので、計算しているものは、なんかの関数のアドレスだ。
t=2, a=3, m=1 か。A と C, D, E は単に数値計算だ。B は、int へのポインターへのポインターにキャストして、その int の内容を dereference している。この間接参照はなんなんだ？そして、その int の内容に、A を足したものがなんかの(出力)関数のアドレスなのか。あとで、もう少し詳しく見てみよう。ただ、今の勘だと、関数のアドレスが呼出しごとに変ってしまうので、どこかの固定値からの相対値として参照しているということなんだろうと思う。でも、** をするのはなぜなんだ？直接値を計算するのや、* 一個ではだめなのか？ちょっと不明。
まぁ、でもだいたい構造は分かった。
あぁ、変数 t は、(int(*)()) で使っていたからいいのか。これ、int は省けないのかな？グローバル変数にするとか。だめか、アドレスがリテラルにならないな。
＃また後で考えよう。
２位 nai さん@13.486B。
mm;ma;mi;mn;mp;am;aa;n;an;m;a;ap;im;ia;
(*pp)();*p;
na(){}
main(i){
p=na();
mm--;ma=mm-i;mi=ma-i;mn=mi-i;mp=mn-i;am=mp-i;aa=am-i;n=aa-i;an=n-i;
p-=am*n;
*p--=pp;
p--;
*p--=m=mp*aa-i;
*p--=-aa;
*p=na;
pp=p=mmap();
p-=aa;
*p--=-ma*mp*(a=m*ma-aa)*(a*mn-aa)*(a*(a-mm)-i);
im=a-ma;
*p--=m*am*an*(m*(-m-aa)-mp-am)*(ap=m*(i-m)-i);
*p--=(ia=-am-aa)*(a*a-ma*mi*mi)*(m*(-ap-n)-mp);
*p--=im*im*n*n*mn*mi*mp*aa*ia;
*p--=m*ia-mm;
*p--=-mn;
*p--=-n*n*n*n*n*n*n*n*n*an;
*p=(((m-a-mn)*a-aa)*ap-a-aa-aa)*m-mi;
pp(pp-(am-ia));
}こちらは難解だな。p=na() は、スタックのアドレスが得られるようだ。そのアドレスからいくつか(am*n)引いたところに、pp を入れている。これは、ゼロで初期化か？そこから、*p-- にいくつか値を入れて言っている。これは、文字列 "Hello, world!" を作っていることなのかな？
と考えていたら、nai さん自身がブログ(id:nai_62:20120913)に書いていた。機械語を生成しているのだとか。
はじめの方にある、(*pp)(); の宣言。関数へのポインターの入れ物だ。ここに、main() の中で値をセットして、呼び出している。これを、先の、shinh さん解に応用すれば、1B 減るんじゃないかな？
awk
他の(私の理解できる)言語では、teebee さん@16.199 がユニークだと思う。
END{
printf"%c%c%c%c%c,%c%c%cr%c%c%c",
1111111E111%111,
11E11%111,
1111E111%1111%111,
1111E111%1111%111,
111,
1111E111%11E11%111,
1E111%1111111111111%1111,
111,
1111E111%1111%111,
1E11%111,
1111E111%111E111%111
}awk は、入力が無い場合、END{} で処理することになる。この解は、END の E と printf の % と 1 を使って、うまいこと文字コードを作っている。
9/13追記
shinh さん、nai さんの解をベースに "int" の "t" を取り除くことをやってみたが、大失敗。代わりに "=" が入って文字数減らなかった。かっこわる。
しばらく、ゴルフ自粛しよ。
あまりにかっこ悪いので、とりあえず、縮めておいた。これは、この方針でまだまだ縮むな。
9/14追記
kik さんが 1B 縮めた。
(*mm)();...ii(i){(mm+n*n...)(...);}...あぁ、確かに。mm はゼロだし、関数型は持っているから足し算でいいんだ。かっこいいな。
9/14追記
clock さんの vi@7.227 もおもしろいな。
:h h
y :x
p:h p
y :x
p:h hp
(以下省略)":h h" は、":help h" のことで、つまり、"h" コマンドのヘルプを開いているということ。その後、空白と改行でカーソルを動かし、ヘルプテキスト中の "H" の文字を "y" コマンドでコピーして、":x" でヘルプを終了して、"p" でペーストしている、ということだ。つまり、"Hello, world!" の文字をヘルプから一文字ずつコピーしてきているということ。
String Halving
昨晩、String Halving が終了した。面白い問題だった。
sed
sedは結構コンパクトにできたな(83B)と思っていたら、tails さん@70B にあっさり抜かれた。
この問題は、文字列を２分割して、それぞれを中かっこで囲えばいいのだが、２分割するところが工夫のいるところ。考えたのは、２つマーカーを設けて、１ポジションずつ文字列の内側へ向けて寄せていく方法。例示すると以下のよう。
B----------E -B--------E- --B------E-- ---B----E--- ----B--E---- -----BE-----
マーカーとして、中かっこを使えば最も効率がいいのだが、分割をしていくと中かっこが文字列中に現れるので、ほかの文字を使う必要があると思っていた。ところが、tails さんの解を見たら、中かっこを使っていた。確かに、右に動ける右中かっこは一つしか存在しないし、左に動けるものも同様なんだ。
B E
{{--}-----{--}{----------}}この例のように、B と E は簡単に特定できる。
s/}\([^{}]\)/\1}/
s/\([^{}]\){/{\1/中かっこはマーカーに使えないという思い込みがあったためか、気付けなかった。tails さんさすがです。
JavaScript(と C)
JavaScript は、youz さん@83B に 1B 差で負けた。以下は youz さんの解。
s=readline(i=0)
function r(n)"{"+(n<2?s[i++]:r(n/2+.5|0)+r(n>>1))+"}"
print(r(919))特徴的なのは、i を使って、分割しきった長さ 1 の文字列の取り出しを、s[i++] で行っているところだ。入力文字列の先頭から順にアクセスされるということなんだ。試しに、私の解に以下のようにprint()を突っ込んでみたら、
s=readline(f=function(b,e)'{'+(e+~b?f(b,b=b-~e>>1)+f(b,e):(print(b),s[b]))+'}')
print(f(0,s.length))確かに、
0 1 2 3 :
と順に表示された。これは、気づかなかった。
ということは、C では、getchar() で順に読み込んでやればいいんだと思い、自分の解を以下のように変更してみたら 88B ができた。
p(x){putchar(x);}f(l){p('{')+(l>1?f(l+1>>1)+f(l/2):p(getchar()))+p('}');}main(){f(919);}これは面白いな。もう少し短くなるかも。
追記：
アクセスが文字列の先頭から順に行なわれるというのは、２分木の Depth-First サーチ（日本語ではなんていうんだろう？）だから、ツリーの左から順にアクセスされるということか。
