格子点の列挙 in Smalltalk DouKaku?

格子点の列挙

二次元平面上の格子点(X,Y座標がともに整数の点)を、原点から近い順に列挙してください。

同じ距離の点はどういう順番でも構いませんが、可能であればX軸に一番近い第一象限の点から原点を中心として反時計回りの順に列挙してください。列挙の方法は、1行に一つの点の、X,Y座標を出力することとします。

サンプル出力

0, 0
1, 0
0, 1
-1, 0
0, -1
1, 1
-1, 1
1, -1
-1, -1
2, 0

最低でも1000件まで列挙できることを確認してください。また「反時計回り」の条件も満たしている場合は、1000番目の頂点が何かも併せて答えてください。

このお題はかもさんの投稿を元にしています。ご協力ありがとうございました。

Perl がなかったので。力技。

use strict;

my $PI = atan2(1, 1) * 4;
my $MAXR = int(sqrt(1000 / $PI) + sqrt(2) + 0.5);
my @res = ();

for (my $i = 0; $i <= $MAXR; $i++) {
    for (my $j = 0; $j <= $MAXR; $j++) {
        my $r = sqrt($i * $i + $j * $j);
        push(@res, [$i, $j, $r, atan2($j, $i)]);
        ($i != 0) && push(@res, [-$i, $j, $r, atan2($j, -$i)]);
        ($j != 0) && push(@res, [$i, -$j, $r, atan2(-$j, $i) + 2 * $PI]);
        ($i * $j != 0) && push(@res, [-$i, -$j, $r, atan2(-$j, -$i) + 2 * $PI]);
    }
}

foreach my $p (sort {($a->[2] <=> $b->[2]) || ($a->[3] <=> $b->[3])} @res) {
    printf("%3d, %3d\n", splice(@{$p}, 0, 2));
}

post comment

Posted feedbacks - Smalltalk

Squeak Smalltalk で。

1. 円形のブラシを描く機能（#dotOfSize:）があるので、これで描いた円形のドット数を数え（primCountBits）て、同心円内に列挙すべき格子点をすべて含む最少の矩形格子を探し、その x （もしくは y）の最大値（max）を求めます。

2. -max から max まで整数で、重複を許す二項の順列組み合わせを生成（asDigitsToPower: 2 do: [...]）し、それぞれの項目を x、y に持つ、ポイントオブジェクト（x@y）としてコレクション（points）に収めます。

3. pointsを、各要素の原点からの距離（r）、距離が同じなら x 軸となす角度（theta）の小さい順に並べ変えます。

4. 前から n 個をとり（first: n）、各ポイントの x、y を出力。終了後、ファイルを開いて表示（edit）し、最後の出力を結果として返して（^last）います。

| n count max out points last |
n := 1000.
count := [:m | (Form dotOfSize: (m + 1 * 2)) primCountBits - (m + 1 * 4) + 1].
max := (1 to: Float infinity) detect: [:r | (count value: r) >= n].
out := FileStream forceNewFileNamed: 'doukaku65.out.txt'.
points := OrderedCollection new: max * max.
(max negated to: max) asDigitsToPower: 2 do: [:xy | points add: xy first @ xy second].
points := points asArray sort: [:a :b | a r < b r or: [a r = b r and: [a theta < b theta]]].
points := points first: n. 
points do: [:pt | out nextPutAll: (last := '{1}, {2}' format: {pt x. pt y}); cr].
out edit.
^last   "=> '-8, 16' "

DouKaku?

格子点の列挙

Posted feedbacks - Smalltalk

Index

Feed

Other

Link

Pathtraq