リング状の数列を辿る

Java どう書く

第19回どう書くの解答に関連して、リング状の数列を辿るイディオムが知りたいと言っていたところ、finalfusionさんから教えていただいたのでメモします。ありがとうございます!

リングを辿るコード

Before

リングの最小値と最大値を行き来できず、ハードコーディングしていました。

int getNext(int n) {
	if (n == 107) {
		return 100;
	}
	if (n == 215) {
		return 200;
	}
	if (n == 323) {
		return 300;
	}
	if (n == 431) {
		return 400;
	}
	return n + 1;
}

int getPrev(int n) {
	if (n == 100) {
		return 107;
	}
	if (n == 200) {
		return 215;
	}
	if (n == 300) {
		return 323;
	}
	if (n == 400) {
		return 431;
	}
	return n - 1;
}
After

リテラルは、リング内の数値の公約数公差である8だけになりました（リングの基本単位の100は大目に見るとして）。

int getNext(int n) {
	int unit = n / 100;
	int tmp = n - 100 * unit;
	return 100 * unit + (tmp + 1) % (8 * unit);
}

int getPrev(int n) {
	int unit = n / 100;
	int tmp = n - 100 * unit;
	return 100 * unit + (tmp + (8 * unit - 1)) % (8 * unit);
}

考え方

ターゲットの1つ次の値を得る（getNextメソッド）

まず、100の位の数を保存します。

int unit = n / 100;

次に、ターゲットの下2桁を保存します。

int tmp = n - 100 * unit;

そして、ターゲットの次の数の下2桁を求めます。これを100の位の数に足せば、ターゲットの次の数が得られるためです。

例として、図でマーキングした200台の数に注目します。

200〜215の下2桁と16（200台の最大値）の剰余は、次のようになっています。

(x - 100 * 2) % (8 * 2) = 0, 1, 2, ..., 13, 14, 15

というわけで、ターゲットの次の数の下2桁は、ターゲットの下2桁 + 1と16の剰余で求められることが分かります。

たとえば、214から215を求める場合は、こうなります。

(14 + 1) % (16) = 15
200 + 15 = 215

まとめると、次のようになります。

return 100 * unit + (tmp + 1) % (8 * unit);
ターゲットの1つ前の値を得る（getPrevメソッド）

途中まで一緒ですが、最後だけ違います。

たとえば、200台の数だと、1つ前の値を得るには、下2桁を次のように遡らなければなりません。

... 2 → 1 → 0 → 15 → 14 ...

上の数列は、ターゲットの下2桁 + (16 - 1)と16の剰余で求められます。

というわけで、次のようになります。

return 100 * unit + (tmp + (8 * unit - 1)) % (8 * unit);

参考

ありがとうございました。