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 - C#

1000個目は(-8. 20)で合ってる？
  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
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication1
{
  class Program
  {
    static void Main(string[] args)
    {
      SortedList<LatticePoint, LatticePoint> list = new SortedList<LatticePoint, LatticePoint>();
      LatticePoint origin = new LatticePoint(0, 0);
      list.Add(origin, origin);
      int count = 0;
      while (count < 1000)
      {
        LatticePoint point = list.Keys[0];
        list.RemoveAt(0);
        foreach (LatticePoint p in point.GetRotatedPoints())
        {
          Console.WriteLine("{0}: {1}", ++count, p);
        }
        foreach (LatticePoint p in point.GetNeighborhood())
        {
          if (!(list.ContainsKey(p)))
          {
            list.Add(p, p);
          }
        }
      }
      Console.ReadKey();
    }
  }
  struct LatticePoint : IEquatable<LatticePoint>, IComparable<LatticePoint>
  {
    public int X;
    public int Y;
    public LatticePoint(int x, int y)
    {
      this.X = x;
      this.Y = y;
    }
    public override string ToString()
    {
      return string.Format("{0}, {1}", X, Y);
    }
    public override bool Equals(object obj)
    {
      if (!(obj is LatticePoint))
      {
        return false;
      }
      return Equals((LatticePoint)obj);
    }
    public bool Equals(LatticePoint p)
    {
      return (p.X == X) && (p.Y == Y);
    }
    public override int GetHashCode()
    {
      return X.GetHashCode() * 31 + Y.GetHashCode();
    }
    public static bool operator ==(LatticePoint p1, LatticePoint p2)
    {
      return p1.Equals(p2);
    }
    public static bool operator !=(LatticePoint p1, LatticePoint p2)
    {
      return !p1.Equals(p2);
    }
    public long SquaredSum
    {
      get
      {
        long x2 = (long)X * (long)X;
        long y2 = (long)Y * (long)Y;
        return x2 + y2;
      }
    }
    public int CompareTo(LatticePoint other)
    {
      return (int)(this.SquaredSum - other.SquaredSum);
    }
    public IEnumerable<LatticePoint> GetNeighborhood()
    {
      yield return new LatticePoint(X + 1, Y);
      if (X > Y)
      {
        yield return new LatticePoint(X, Y + 1);
      }
    }
    public LatticePoint RotateSquare()
    {
      return new LatticePoint(-Y, X);
    }
    public IEnumerable<LatticePoint> GetRotatedPoints()
    {
      if ((X == 0) && (Y == 0))
      {
        yield return this;
        yield break;
      }
      LatticePoint p = this;
      LatticePoint f = new LatticePoint(Y, X);
      LatticePoint r = this.RotateSquare();
      bool withFlip = ((p != f) && (f != r));
      for (int i = 0; i < 4; i++)
      {
        yield return p;
        p = p.RotateSquare();
        if (withFlip)
        {
          yield return f;
          f = f.RotateSquare();
        }
      }
    }
  }
}


CompareTo()を修正したので、1000番目は(-8, 16)になりました。

  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
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication1
{
  class Program
  {
    static void Main(string[] args)
    {
      SortedList<LatticePoint, LatticePoint> list = new SortedList<LatticePoint, LatticePoint>();
      LatticePoint origin = new LatticePoint(0, 0);
      list.Add(origin, origin);
      int count = 0;
      while (count < 1000)
      {
        LatticePoint point = list.Keys[0];
        list.RemoveAt(0);
        foreach (LatticePoint p in point.GetRotatedPoints())
        {
          Console.WriteLine("{0}: {1}", ++count, p);
        }
        foreach (LatticePoint p in point.GetNeighborhood())
        {
          if (!(list.ContainsKey(p)))
          {
            list.Add(p, p);
          }
        }
      }
      Console.ReadKey();
    }
  }
  struct LatticePoint : IEquatable<LatticePoint>, IComparable<LatticePoint>
  {
    public int X;
    public int Y;
    public LatticePoint(int x, int y)
    {
      this.X = x;
      this.Y = y;
    }
    public override string ToString()
    {
      return string.Format("{0}, {1}", X, Y);
    }
    public override bool Equals(object obj)
    {
      if (!(obj is LatticePoint))
      {
        return false;
      }
      return Equals((LatticePoint)obj);
    }
    public bool Equals(LatticePoint p)
    {
      return (p.X == X) && (p.Y == Y);
    }
    public override int GetHashCode()
    {
      return X.GetHashCode() * 31 + Y.GetHashCode();
    }
    public static bool operator ==(LatticePoint p1, LatticePoint p2)
    {
      return p1.Equals(p2);
    }
    public static bool operator !=(LatticePoint p1, LatticePoint p2)
    {
      return !p1.Equals(p2);
    }
    public long SquaredSum
    {
      get
      {
        long x2 = (long)X * (long)X;
        long y2 = (long)Y * (long)Y;
        return x2 + y2;
      }
    }
    public int CompareTo(LatticePoint other)
    {
      long r2 = this.SquaredSum - other.SquaredSum;
      if (r2 != 0)
        return (int)r2;
      bool f1 = (other.Y >= 0);
      bool f2 = !((this.Y >= 0) ^ f1);
      return (f1 ? 1 : -1) * (f2 ? this.X - other.X : 1);
    }
    public IEnumerable<LatticePoint> GetNeighborhood()
    {
      yield return new LatticePoint(X + 1, Y);
      if (X > Y)
      {
        yield return new LatticePoint(X, Y + 1);
      }
    }
    public LatticePoint RotateSquare()
    {
      return new LatticePoint(-Y, X);
    }
    public IEnumerable<LatticePoint> GetRotatedPoints()
    {
      if ((X == 0) && (Y == 0))
      {
        yield return this;
        yield break;
      }
      LatticePoint p = this;
      LatticePoint f = new LatticePoint(Y, X);
      LatticePoint r = this.RotateSquare();
      bool withFlip = ((p != f) && (f != r));
      for (int i = 0; i < 4; i++)
      {
        yield return p;
        p = p.RotateSquare();
        if (withFlip)
        {
          yield return f;
          f = f.RotateSquare();
        }
      }
    }
  }
}

以下のソースコードの場合には、1000番目の点は（-10,16）でした。 格子点生成時に、ｘとｙの範囲を「-17<=x<=17、-17<=y<=17」に変更すると(-8,16)になってしまいました。 この辺りを誰か検証してくださると面白そうですね。

 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
class MyPoint
{
    public int x { get; set; }
    public int y{ get; set; }
    public int dist { get; set; }
    public double theta { get; set; }
}

class Program
{
    static void Main(string[] args)
    {
        ArrayList list = new ArrayList();
        double theta = 0;
        for (int x = -16; x <= 16; x++)
        {
            for (int y = -16; y <= 16; y++)
            {
                theta = Math.Atan2(y, x);
                if (theta < 0) theta += Math.PI * 2;
                list.Add(new MyPoint { x = x, y = y, dist = x * x + y * y, theta = theta });
            }
        }

        var query = (from MyPoint point in list
                    orderby point.dist ascending, point.theta ascending
                    select point.x + "," + point.y).Take(1000);
        foreach(string str in query)
            Console.WriteLine(str);
    }
}

Index

Feed

Other

Link

Pathtraq

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