カメヲラボ

主にプログラミングとお勉強全般について書いてます

ショートコーディング完結編

ショートコーディング

はじめに

ショートコーディングという本を書いてから、16年近く経ちました。当時のスキルを思えば120%の力で書ききったものではありましたが、ずっと心残りだったことがあります。

それはCのマクロについてです。マクロを使ってより短いコードを書くことができるのではないかと思いつつも適当な問題が見つからず、また自分で作ることもできず、「今のところできないけどできるかもしれない。」という結論にせざるを得なかったわけです。

しばらくはそのことも記憶の隅に追いやっていたのですが、年に1回くらいは思い出してしまい、Anarchy Golf(あなごる)のCの記録を覗いてみるということを繰り返していました。そして2016年、すばらしい作品に出合いました。

…とまあ、感想文を書いていても仕方ないので、そういうのは最後に書くこととして、ショートコーディング本の最後のピースとして、マクロを利用した超記録とその解説をしたいと思います。紹介する問題は「Fractal X」というフラクタルのAAを出力する問題と「Big Fibonacci Number」という大きなフィボナッチ数を計算する問題の2つです。

この2つの解は、いずれもゴルフ神のtailsさんによるもので、ここでの紹介・解説することにも快く応じてくださいました。心より感謝いたします。 なお、本ブログは私Ozyが勝手に書いたものですので、内容に誤りがあったとしても私が間違えたものであり100%私の責任です。ご了承ください(もし誤りがあった場合はご指摘いただけるとありがたいです)。

では始めましょう！

Fractal X

問題概要

このFractal Xという問題は、入力なしで次のようなAAを出力するコードを書くというものです。

Fractal X
いたってシンプルな問題ですね(見た目の都合で画像にしています)。

基本的な考え方

まずは小さなX

X X
 X 
X X

を作ってみたいと思います。

#include<stdio.h>

void f(int x) {
    if(x >= 4) {
        printf("%d ", x);
    } else {
        f(x * 2);     // X_X
        f(x * 2 + 1); // _X_
        f(x * 2);     // X_X
    }
    if(x / 2 == 1) puts(""); 
}

int main(int x) {
    f(1);
    return 0;
}

これを実行すると、次のような出力が得られます。

4 5 4
6 7 6
4 5 4

フラクタルの問題なので、再帰的な関数呼び出しがよくマッチしていますね。再帰関数内で3回再帰することで、AAの縦横サイズを3n倍にすることができます。

上記の4と7の部分をXにしたいので、出力部分を次のように書きます。

        printf(x % 3 == 1 ? "X" : " ");

これで小さなXを作ることができました。次はこれを拡大していきます。

void f(int x) {
    if(x >= 16) { // ←ココ！
        printf(x % 5 == 1 ? "X" : " "); // ←ココ！
    } else {
        f(x * 2);
        f(x * 2 + 1);
        f(x * 2);
    }
    if(x / 4 == 1) puts(""); // ←ココ！
}

こんな感じでひと回り大きなXができました。

X X   X X
 X     X
X X   X X
   X X
    X
   X X
X X   X X
 X     X
X X   X X

こんな感じで必要な大きさまにまで育ててやったものが次のコードです。

void f(int x) {
    if(x >= 256) {
        printf(x % 17 == 1 ? "X" : " ");
    } else {
        f(x * 2);
        f(x * 2 + 1);
        f(x * 2);
    }
    if(x / 16 == 1) puts(""); 
}

main再帰と基本短縮

この問題では入力の心配をする必要がありませんので、main関数自体を再帰することも難しくありません。

int main(int x) {

    if(x >> 8 != 0) { // x >= 256
        if(x % 17 == 1) putchar('X');
        else putchar(' ');
    } else {
        x *= 2;
        main(x);
        main(x + 1);
        main(x);
    }

    if(x / 32 == 1) puts("");
}

引数なしの実行ではmain関数の第1引数が1になることも利用すれば、非常にスッキリとしたコードになります。これを基本通りに短縮してやると、次のようになります。空白文字や改行を取り除くと82バイトと、かなり短いコードになりました。

main(x){
    x>>8?putchar(x%17-1?32:88):main(x*=2)+main(x+1)+main(x);x/32-1||puts("");
}

マクロの出番が来た！

「main(x」という記述が4回も現れました。文字数にして24文字です。これをマクロで置換すると、以下のようになります。

#define m main(x
m){x>>8?putchar(x%17-1?32:88):m*=2)+m+1)+m);x/32-1||puts("");}

一見コンパイルすら通らなさそうな見た目ですが、ちゃんとコンパイルできます。そして先のコードより3バイト短い79バイトのコードになりました。

マクロを使うと、#define ...の部分がそれなりの文字数になるため利用できるケースが少ないですが、このように数多く繰り返すケースであれば利用できることが確認されました。

では次に、大きなフィボナッチ数の問題について解説していきます。

Big Fibonacci Number

問題概要

Big Fibonacci Numberでは、大きなフィボナッチ数を出力します。

フィボナッチ数列を、

f(0) = f(1) = 1

n > 2のとき

f(n) = f(n - 1) + f(n - 2)

と定義します。

このときnが入力として与えられるので、f(n) mod 1000000000(1e9)を出力するという問題です。 なお、入力の最大値は1000000000(1e9)となっています。

Cにはきつい問題

Cにおけるゴルフの基本的なテクニックとして、 型名を省略→(32bit)int型として扱う というものがあります。しかしこの問題では扱う値が大きいので、少なくとも(long longのような)64bit整数が欲しいところです。また、入力も大きめですので愚直に計算すると制限時間内に解答することができません。

つまり、ポイントとして次の3点を考慮する必要があります。

  • 大きな整数値を扱う
  • 計算速度も必要
  • 最短コードを狙う

基本的なアイデア

変数について

long longのような記述は基本的に避けたいので、64bit整数型の変数は使いません。幸い出力はmod 1e9で構わないので、うまくやれば32bit整数型の変数だけで何とかできるはずです。

計算方法について

フィボナッチ数を高速に計算する方法で一般的なものとして、

\begin{pmatrix}F_{n+1} &F_n\\F_n &F_{n-1}\end{pmatrix}=\begin{pmatrix}1 &1\\1 &0\end{pmatrix}^n

のように行列を使う方法があります。

しかしこれをCでそのまま実装すると、次のように結構なコード量になります。

#include<stdio.h>
#include<string.h>

#define ll long long
#define M 1000000000

ll p[30][4] = {{1, 1, 1, 0}};

void mul(ll *a,ll *x,ll *y)
{
  ll t[4];
  t[0] = (x[0] * y[0] + x[1] * y[2]) % M;
  t[1] = (x[0] * y[1] + x[1] * y[3]) % M;
  t[2] = (x[2] * y[0] + x[3] * y[2]) % M;
  t[3] = (x[2] * y[1] + x[3] * y[3]) % M;

  memcpy(a,t,sizeof(t));
}

int main() {
    int n;

    for(int i = 1; i < 30; ++i) {
        mul(p[i], p[i - 1], p[i - 1]);
    }

    for(;~scanf("%d",&n);) {
        ll k[4] = {1, 0, 0, 1};

        for(int i = 0; i < 30; ++i) {
            if((n + 1) & (1 << i)) mul(k, k, p[i]);
        }
        printf("%lld\n", k[1]);
    }
    return 0;
}

他に高速化する方法としてよく使われる方法は配列を使ったDPやメモ化再帰で、実用上は問題ないことが多いのですが、この問題の場合は入力の最大値が1000000000です。4バイト整数の配列を用意するとなると、4GB近く必要になりますので、ちょっとしんどいですね。

周期性を利用できるか

フィボナッチ数列の周期性を利用できるかもしれませんので、調べてみました。

桁数 周期
下1桁 60
下2桁 300
下3桁 1500
下4桁 15000
下5桁 150000
下6桁 1500000
下7桁 15000000
下8桁 150000000
下9桁 1500000000

桁数が増えると周期はかなり長くなるため、出力サイズが9桁の場合は必要な配列サイズを超えてしまっていて利用するのは難しそうです。

この時点で行列を使った方法をベースに気合で短縮していきたい気分になるところですが、本物は違いました。

最短コードに向けて

まず計算量を落とす

フィボナッチ数列には、

f(m + n) = f(m - 1) \times f(n) + f(m) \times f(n + 1)

が成立するという面白い性質があります。証明・解説は省略しますので、参考として高校数学の美しい物語 > フィボナッチ数列の7つの性質（一般項・黄金比・互いに素）をご覧ください。

この式において、m = nとすると

f(2n) = f(n - 1) \times f(n) + f(n) \times f(n + 1)

となり、m = n + 1とすると

f(2n + 1) = f(n) \times f(n) + f(n + 1) \times f(n + 1)

となります。

つまり、入力が偶数の場合と奇数の場合で計算方法が少し異なりますが、同じような式の形で計算できそうです。 またこの方法を使うとfの呼び出し毎に引数の値が約1/2倍になり、定義通りの漸化式と比べて計算量が格段に少なくなります。メモ化なしのコードは次のようになります。

#include<stdio.h>

#define ll long long
#define M 1000000000

ll fib(ll n) {
    if(n <= 2) return 1;
    int m =  n / 2; // nが奇数の場合は小数点以下を切り捨てる
    if(n & 1) {
        return (fib(m) * fib(m) + fib(m + 1) * fib(m + 1)) % M;
    } else {
        return (fib(m - 1) * fib(m) + fib(m) * fib(m + 1)) % M;
    }
}

int main() {
    int n;

    for(;~scanf("%d",&n);) {
        ll ans = fib(n + 1);
        printf("%lld\n", ans);
    }
}

これで入力が5桁くらいまで動くようになります(定義通りだと2桁程度が限度です)。かなり高速になりましたが、より大きな入力にはメモ化せざるを得ません。

消費メモリを少なくする

先のアルゴリズムでは、関数の呼び出し回数を大幅に少なくする効果がありましたがそれはメモ化回数も少なくしているということになります。入力が最大(1000000000)の場合でも、実際に配列に書き込まれる値は100個程度しかありません。C++であればmapを使ってかなりコンパクトに書くことができます。Cではmapが使えないため、小さめの配列にマッピングすることで実現可能です。

#include<stdio.h>

#define ll long long
#define M 1000000000
#define W 99999
ll memo[W];

ll fib(ll n) {
    if(n <= 2) return 1;
    int w = n % W;
    if(memo[w] > 0) return memo[w];
    int m =  n / 2; // nが奇数の場合は小数点以下を切り捨てる
    if(n & 1) {
        memo[w] = (fib(m) * fib(m) + fib(m + 1) * fib(m + 1)) % M;
        return memo[w];
    } else {
        memo[w] = (fib(m - 1) * fib(m) + fib(m) * fib(m + 1)) % M;
        return memo[w];
    }
}

int main() {
    int i, n;

    for(;~scanf("%d",&n);) {
        for(i = 0; i < W; ++i) memo[i] = 0;        
        ll ans = fib(n + 1);
        printf("%lld\n",ans);
    }
}

ハッシュ計算が雑過ぎるので競プロ的にはアウトだと思いますが、すべての入力がわかっているあなごるでは衝突の心配をあまりする必要はありません。もし衝突したら配列サイズや計算方法を変えれば良いですからね。

これで基本的な準備は終わりました。

偶奇の分岐を無くす

小数点以下の切り捨てを上手く利用すれば、偶奇による分岐を無くして1行で書くことができます。

ll fib(ll n) {
    if(n <= 2) return 1;
    int w = n % W;
    if(memo[w] > 0) return memo[w];
    memo[w] = (fib((n - 1) / 2) * fib(n / 2) + fib((n + 1) / 2) * fib((n + 2) / 2)) % M;
    return memo[w];
}

計算結果は32ビット整数に収まることがわかっていますので、そろそろint型のみの変数を使ったものに書き替えて、コード全体を手直しします。

#include<stdio.h>

#define M 1000000000
#define W 99999

int z[W],i;
int f(int n) {
    if(n < 5) return 1;
    int w = n % W;
    z[w] = z[w] ? z[w] : (1LL * f((n + 1) / 2) * f((n + 2) / 2) + 1LL * f((n + 3) / 2) * f((n + 4) / 2)) % M;
    return z[w];
}

int main(int a) {
    for(;~scanf("%d",&a);) printf("%d\n",f(a + 3));
}

計算途中で32ビットを超えてしまいますので、関数fの戻り値に1LLをかけてlong long型に変換しておきます。あとはここから基本的なテクニックや基本的じゃないテクニックを駆使してコードを短縮していくのですが、かなり複雑になりますので詳細は省いておきます。興味のある方は手元でやってみて、動くかな？と思ったらあなごるのCheckerで動作確認してみてください。

マクロを活用する

関数呼び出しの部分と、64ビット型にキャストする部分がどうしても冗長になってしまいますが、ここでマクロを利用します。

#include<stdio.h>

#define M 1000000000
#define W 99999
#define F 1LL * f(++n / 2)

int z[W],i;
int f(int n) {
    if(n < 5) return 1;
    int w = n % W;
    z[w] = z[w] ? z[w] : (F * F + F * F) % M;
    return z[w];
}

int main(int a) {
    for(;~scanf("%d",&a);) printf("%d\n",f(a + 3));
}

す、すばらしい…。

至高の129B

#define F 1ll*f(++n/2)
m=1e9;h[5686];i;f(n){h[i=n%5686]=h[i]|n<5?:(F*F+F*F)%m;}main(){for(;gets(&i);printf("%d\n",f(atoi()+3)));}

getsの部分はhに読み込むことで1B減らすことができるみたいですが、あえてtailsさんのコードをそのまま掲載します。

全てが調和した上で仕上げのマクロという、私が夢見ていたコードにやっと出会ったと思いました。本当にすばらしいです。

ショートコーディング完結編

ここから感想文です。

コードゴルフの認知度って結構上がりましたよね。いろんなところで目にするようになりました。ショートコーディング本に書かれていない変態的テクニックもいろいろと存在しています。私はというと、あなごるは定期的に観察しているものの提出まで至っておらず、年に一回程度POJで遊ぶくらいです。ご存じの方もいらっしゃるかもしれませんが、最近はマラソンマッチにお熱です。

そんな私でも、今回紹介した大きなフィボナッチ数の問題だけはいつも頭の中にありました。もしショートコーディング本を書いている頃にこの問題に出会っていたとしても、マクロを使ったコードはまったく思いつかなかったと思います。いつ見ても、何度見ても素晴らしい。今日もこのコードを観ながらご飯食べてます。

無知が原動力

アルゴリズム・データ構造・処理系等々、知らないことが多すぎて、何を見ても何を聞いても何をやっても、すべてが新鮮で本当に面白い。そんな状況でショートコーディング本を書いていました。そもそもショートコーディングなんてワードはコードゴルフというものを良く知らないが故に産まれたようなものですからね。

さて、今はと言いますと、当時と比べてそれなりに知識も技術もある程度レベルアップしました。もちろんまだまだ知らないことはあるのですが、新しいモノを生み出すモチベーションになるのかというとそれは少し微妙です。むしろコードゴルフを最近知って「面白い！」と感じた若い人がたくさん発信した方が、絶対良いと感じています。

記事も本も書かないのか

書かないということはたぶんなくて「Cゴルフ」みたいなもうちょっとコンパクトでお気持ち少なめの何かとか、シェル系のゴルフには興味があります。何よりPOJで遊ぶのは私の楽しみのひとつですので、ときどき何かやりたいなーと思っています。

本当に完結なのか

完結しない可能性が1つあります。今回紹介した2つのコード以外でもhttp://golf.shinh.org/reveal.rb?Fire+Emblem+4+RNG/tails_1551928236&cのようにマクロで最短を取っているものがあるのですが、これらの記録がすべてマクロを使わないコードに破られてしまった場合、「やっぱマクロ意味ないじゃん！」と言われてしまう可能性があります。その時はまたマクロの可能性について考える旅が始まるかもしれません(お願いだから始まらないで欲しい)。

というわけで

ここまで読んでくださった方はありがとうございました。どうしても今日投稿したい、今日しなかったら一生しないと思い、超特急で書きあげました。記述に雑な部分はいろいろとありますので、後日修正したいと思います。何か問題点等あればご指摘いただけると嬉しいです。ではまた！

おまけ

毎年2月11日は、ゆるっとPOJで遊んでいます。今年は3970番をやっていました。そしてまたushiodaさんに負けました…くやちいぃ！

POJ 3970 ランキング