DouKaku?beta

challenge 格子点の列挙

二次元平面上の格子点(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 がなかったので。力技。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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 - Objective-C

あらかじめ点の配列を作っておいてソートするという力業。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#import <Foundation/Foundation.h>

@interface MyPoint : NSObject
{
  int x;
  int y;
  long distance;
}

+ (MyPoint*)pointWithX:(int)x y:(int)y;
- (int)x;
- (int)y;
- (long)distance;
- (NSComparisonResult)compareWithPoint:(MyPoint*)rhs;

@end

@implementation MyPoint

- (int)x { return x; }
- (int)y { return y; }
- (long)distance { return distance; }

- (void)setX:(int)px y:(int)py
{
  x = px;
  y = py;
  distance = x*x + y*y;
}

+ (MyPoint*)pointWithX:(int)x y:(int)y
{
  MyPoint* obj = [[[MyPoint alloc] init] autorelease];
  [obj setX:x y:y];
  return obj;
}

- (NSComparisonResult)compareWithPoint:(MyPoint*)rhs
{
  long d = [rhs distance];
  if (distance < d) return NSOrderedAscending;
  if (distance > d) return NSOrderedDescending;
  
  int rx = [rhs x];
  int ry = [rhs y];
  if (y >= 0) {
    if (ry >= 0) {
      return x < rx ? NSOrderedDescending : NSOrderedAscending;
    } else {
      return NSOrderedAscending;
    }
  } else {
    if (ry >= 0) {
      return NSOrderedDescending;
    } else {
      return x < rx ? NSOrderedAscending : NSOrderedDescending;
    }
  }
}

@end

int main(int argc, char** argv)
{
  NSAutoreleasePool* pool = [NSAutoreleasePool new];
  
  NSMutableArray* input = [NSMutableArray array];
  int r = 25;
  int i, j;
  for (i=-r; i<=r; i++)
    for (j=-r; j<r; j++)
      [input addObject:[MyPoint pointWithX:i y:j]];

  NSArray* result = [input sortedArrayUsingSelector:@selector(compareWithPoint:)];
  
  printf("count: %d\n", [result count]);
  i = 0;
  for (id p in result) {
    printf("%3d, %3d\n", [p x], [p y]);
    i++;
  }
  
  [pool release];
  return 0;
}


デバッグ用のコードが残っていたので削除しました。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#import <Foundation/Foundation.h>

@interface MyPoint : NSObject
{
  int x;
  int y;
  long distance;
}

+ (MyPoint*)pointWithX:(int)x y:(int)y;
- (int)x;
- (int)y;
- (long)distance;
- (NSComparisonResult)compareWithPoint:(MyPoint*)rhs;

@end

@implementation MyPoint

- (int)x { return x; }
- (int)y { return y; }
- (long)distance { return distance; }

- (void)setX:(int)px y:(int)py
{
  x = px;
  y = py;
  distance = x*x + y*y;
}

+ (MyPoint*)pointWithX:(int)x y:(int)y
{
  MyPoint* obj = [[[MyPoint alloc] init] autorelease];
  [obj setX:x y:y];
  return obj;
}

- (NSComparisonResult)compareWithPoint:(MyPoint*)rhs
{
  long d = [rhs distance];
  if (distance < d) return NSOrderedAscending;
  if (distance > d) return NSOrderedDescending;
  
  int rx = [rhs x];
  int ry = [rhs y];
  if (y >= 0) {
    if (ry >= 0) {
      return x < rx ? NSOrderedDescending : NSOrderedAscending;
    } else {
      return NSOrderedAscending;
    }
  } else {
    if (ry >= 0) {
      return NSOrderedDescending;
    } else {
      return x < rx ? NSOrderedAscending : NSOrderedDescending;
    }
  }
}

@end

int main(int argc, char** argv)
{
  NSAutoreleasePool* pool = [NSAutoreleasePool new];
  
  NSMutableArray* input = [NSMutableArray array];
  int r = 25;
  int i, j;
  for (i=-r; i<=r; i++) {
    for (j=-r; j<r; j++) {
      [input addObject:[MyPoint pointWithX:i y:j]];
    }
  }

  NSArray* result = [input sortedArrayUsingSelector:@selector(compareWithPoint:)];
  
  printf("count: %d\n", [result count]);
  for (id p in result) {
    printf("%3d, %3d\n", [p x], [p y]);
  }
  
  [pool release];
  return 0;
}

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]