格子点の列挙 in Bash 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 - Bash

1000番目は (-8, 16) だと思います。配列 x, y のダミーはかなり変ですが、もう直す気がしないのでそのままにしておきます。

#!/bin/bash

set -ue

FMT="%d, %d\n"

print_lattice () {
  # distance^2
  local -i d
  # cache of square of integers
  local -ia scache=(0)
  # #scache
  local -i n_scache="${#scache[@]}"

  local -i i j
  local -ia x
  local -ia y

  for ((d = 0;; d++)); do
    # set dummy data(due to "set -u")
    x=(-1)
    y=(-1)

    if [ $d -gt ${scache[n_scache-1]} ]; then
      scache[n_scache++]=$(( n_scache * n_scache ))
    fi

    for ((i = n_scache-1; i >= 0; i--)); do
      for ((j = 0; j < n_scache; j++)); do
        if let "scache[i]+scache[j]-d"; then
          continue
        fi

        x=("${x[@]}" $i)
        y=("${y[@]}" $j)
      done
    done

    if [ ${#x[@]} -gt 1 ]; then
      # origin
      if ! let "x[1] + y[1]"; then
        printf "$FMT" 0 0
      fi
      # quadrant 1
      for ((i = 1; i < ${#x[@]}; i++)); do
        if [ ${x[i]} -ne 0 ]; then
          printf "$FMT" ${x[i]} ${y[i]}
        fi
      done
      # quadrant 2
      for ((i = ${#x[@]} -1 ; i > 0; i--)); do
        if [ ${y[i]} -ne 0 ]; then
          printf "$FMT" -${x[i]} ${y[i]}
        fi
      done
      # quadrant 3
      for ((i = 1; i < ${#x[@]}; i++)); do
        if [ ${x[i]} -ne 0 ]; then
          printf "$FMT" -${x[i]} -${y[i]}
        fi
      done
      # quadrant 4
      for ((i = ${#x[@]} -1 ; i > 0; i--)); do
        if [ ${y[i]} -ne 0 ]; then
          printf "$FMT" ${x[i]} -${y[i]}
        fi
      done
    fi
  done
}

print_lattice

DouKaku?

格子点の列挙

Posted feedbacks - Bash

Index

Feed

Other

Link

Pathtraq