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 - VB.net

少しメモリ消費量とか速度を考えて。
1000番目は(-8,16)、
1000000番目は(497,-267)、
100000000番目は(5554,-992)。
計算時間は200秒くらい。

もっと頭いい方法がありそうな。
  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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
Module Module1

    Sub Main()
        Dim e As IEnumerator(Of LatticePoint) = New LatticePointEnumerator()
        Dim i As Integer
        For i = 1 To 999
            e.MoveNext()
        Next
        e.MoveNext()
        Console.WriteLine(i.ToString() & ":" & e.Current.ToString())

        For i = 1001 To 999999
            e.MoveNext()
        Next
        e.MoveNext()
        Console.WriteLine(i.ToString() & ":" & e.Current.ToString())

        For i = 1000001 To 99999999
            e.MoveNext()
        Next
        e.MoveNext()
        Console.WriteLine(i.ToString() & ":" & e.Current.ToString())

        Console.ReadKey()
    End Sub

End Module

Public Class LatticePointEnumerator
    Implements IEnumerator(Of LatticePoint)

    Private _list As LinkedList(Of LatticePoint)
    Private _r As Integer
    Private _pointlist As List(Of LatticePoint)
    Private _enumerator As IEnumerator(Of LatticePoint)

    Public Sub New()
        _list = New LinkedList(Of LatticePoint)
        _pointlist = New List(Of LatticePoint)
        Reset()
    End Sub

    Public Sub Reset() Implements System.Collections.IEnumerator.Reset
        _list.Clear()
        _list.AddLast(New LatticePoint(0, 0))
        _list.AddLast(New LatticePoint(1, 0))
        _list.AddLast(New LatticePoint(1, 1))
        _list.AddLast(New LatticePoint(2, 0))
        _list.AddLast(New LatticePoint(2, 1))
        _list.AddLast(New LatticePoint(2, 2))
        _list.AddLast(New LatticePoint(3, 0))
        _list.AddLast(New LatticePoint(3, 1))
        _list.AddLast(New LatticePoint(3, 2))
        _list.AddLast(New LatticePoint(3, 3))
        _r = 4
        _pointlist.Clear()
        _enumerator = _pointlist.GetEnumerator()
    End Sub

    Public ReadOnly Property Current() As LatticePoint Implements System.Collections.Generic.IEnumerator(Of LatticePoint).Current
        Get
            Return _enumerator.Current
        End Get
    End Property

    Public ReadOnly Property Current1() As Object Implements System.Collections.IEnumerator.Current
        Get
            Return DirectCast(_enumerator, IEnumerator).Current
        End Get
    End Property

    Public Function MoveNext() As Boolean Implements System.Collections.IEnumerator.MoveNext
        If _enumerator.MoveNext() Then Return True

        If _list.First.Value._r2 >= _r * _r Then
            Dim node As LinkedListNode(Of LatticePoint)
            Dim p As LatticePoint
            node = _list.First
            For y As Integer = 0 To _r
                p = New LatticePoint(_r, y)
                While node IsNot Nothing AndAlso p._r2 > node.Value._r2
                    node = node.Next
                End While
                If node Is Nothing Then _list.AddLast(p) Else _list.AddBefore(node, p)
            Next
            _r += 1
        End If

        _pointlist.Clear()
        _pointlist.Add(_list.First.Value)
        _list.RemoveFirst()
        While _list.First.Value._r2 = _pointlist(0)._r2
            _pointlist.Add(_list.First.Value)
            _list.RemoveFirst()
        End While

        Dim j As Integer
        j = _pointlist.Count - 1
        If _pointlist(j).X = _pointlist(j).Y Then j -= 1
        For i As Integer = j To 0 Step -1
            _pointlist.Add(New LatticePoint(_pointlist(i).Y, _pointlist(i).X))
        Next
        j = _pointlist.Count - 1
        If _pointlist(j).X = 0 Then j -= 1
        For i As Integer = j To 0 Step -1
            _pointlist.Add(New LatticePoint(-_pointlist(i).X, _pointlist(i).Y))
        Next
        j = _pointlist.Count - 1
        If _pointlist(j).Y = 0 Then j -= 1
        For i As Integer = j To 1 Step -1
            _pointlist.Add(New LatticePoint(_pointlist(i).X, -_pointlist(i).Y))
        Next
        If _pointlist(0).Y <> 0 Then _pointlist.Add(New LatticePoint(_pointlist(0).X, -_pointlist(0).Y))

        _enumerator = _pointlist.GetEnumerator()
        _enumerator.MoveNext()

        Return True
    End Function

    Public Sub Dispose() Implements IDisposable.Dispose
    End Sub

End Class

Public Class LatticePoint
    Friend _x As Integer
    Friend _y As Integer
    Friend _r2 As Long

    Friend Sub New(ByVal x As Integer, ByVal y As Integer)
        _x = x
        _y = y
        _r2 = x * x + y * y
    End Sub

    Public ReadOnly Property X() As Integer
        Get
            Return _x
        End Get
    End Property

    Public ReadOnly Property Y() As Integer
        Get
            Return _y
        End Get
    End Property

    Public ReadOnly Property SquaredRadius() As Long
        Get
            Return _r2
        End Get
    End Property

    Public Overrides Function ToString() As String
        Return String.Format("({0}, {1}) [{2}]", _x.ToString(), _y.ToString(), _r2.ToString())
    End Function

End Class

Index

Feed

Other

Link

Pathtraq

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