Haskell- 115 130 131 135 136

저는 영감을받은 에라토스테네스의 체, 특히 에라토스테네스 의 진짜 체 , 하비 머드 칼리지의 Melissa E. O’Neill의 논문입니다. 내 원래 버전 (인덱스 순서로 포인트를 고려한)은 매우 빨리 포인트를 체질 했습니다. 어떤 이유로 나는이 버전에서 포인트를 “체질”하기 전에 포인트를 셔플하기로 결정했습니다 (단지 사용하여 다른 답변을 쉽게 생성 할 수 있다고 생각합니다) 무작위 생성기의 새로운 시드). 포인트는 더 이상 어떤 종류의 순서도 없기 때문에 더 이상 체질이 더 이상 진행되지 않으므로 결과적으로 단일 115 포인트 응답을 생성하는 데 몇 분이 걸립니다. 녹아웃 Vector이 아마도 더 나은 선택 일 것입니다.

따라서이 버전을 검사 점으로 사용하면 “Genuine Sieve”알고리즘으로 돌아가서 List 모나드를 활용하거나에 Set대한 해당 작업을 교체하는 두 가지 분기 가 Vector있습니다.

편집 : 따라서 작업 버전 2의 경우 체 알고리즘으로 되돌아 가서 “복수”생성을 개선했습니다 (소수점 생성과 유사하게 두 점 사이의 거리와 같은 반경을 가진 원의 정수 좌표에서 점을 찾아서 인덱스를 두드립니다) ) 및 불필요한 재 계산을 피함으로써 일정한 시간 개선 효과를 제공합니다.

어떤 이유로 프로파일 링을 켠 상태에서 다시 컴파일 할 수 없지만 현재 주요 병목 현상은 역 추적이라고 생각합니다. 약간의 병렬 처리와 동시성을 탐색하면 선형 속도가 향상되지만 메모리 소진으로 인해 2 배 향상 될 수 있습니다.

편집 : 버전 3은 약간의 구불 구불 한 것으로, 먼저 다음 ? 지수 (이전 선택에서 체질 한 후)를 가져 와서 다음 최소 녹아웃 세트를 생성 한 지수를 선택하는 휴리스틱을 실험했습니다. 이것은 너무 느리게 끝나서 전체 검색 공간 무차별 대입법으로 돌아갔습니다. 원점에서 거리를 기준으로 점을 정렬하는 아이디어가 나에게 왔으며 (내 인내심이 지속되는 시점에) 하나의 점으로 개선되었습니다. 이 버전은 인덱스 0을 원점으로 선택하므로 평면의 중심점을 시도해 볼 가치가 있습니다.

편집 : 검색 공간을 재정렬하여 중심에서 가장 먼 지점을 우선 순위로 지정하여 4 점을 선택했습니다. 당신이 내 코드를 테스트하는 경우, (135) (136)는 실제로 두 번째 세 번째 솔루션은 발견했다. 빠른 편집 : 이 버전은 계속 실행하면 생산성을 유지할 가능성이 가장 높습니다. 나는 137에 묶은 다음 138을 기다리는 인내심이 부족한 것 같습니다.

나는 (그 사람에게 도움이 될 수 있음)주의 한가지는 당신이 (즉, 제거 평면의 중심에서 포인트 순서를 설정 한 경우 (d*d -)에서 originDistance) 이미지 형성 외모 스파 스 프라임 나선형 같은 비트.

{-# LANGUAGE RecordWildCards #-}
{-# LANGUAGE BangPatterns #-}

module Main where

import Data.Function (on)
import Data.List     (tails, sortBy)
import Data.Maybe    (fromJust)
import Data.Ratio
import Data.Set      (fromList, toList, union, difference, member)

import System.IO

sideLength :: Int
sideLength = 619

data Point = Point {  x :: !Int,  y :: !Int } deriving (Ord, Eq)
data Delta = Delta { da :: !Int, db :: !Int }

euclidean :: Delta -> Int
euclidean Delta{..} = da*da + db*db

instance Eq Delta where
  (==) = (==) `on` euclidean

instance Ord Delta where
  compare = compare `on` euclidean

delta :: Point -> Point -> Delta
delta a b = Delta (min dx dy) (max dx dy)
  where
    dx = abs (x a - x b)
    dy = abs (y a - y b)

equidistant :: Dimension -> Point -> Point -> [Point]
equidistant d a b =
  let
    (dx, dy) = (x a - x b, y a - y b)
    m = if dx == 0 then Nothing else Just (dy % dx)                    -- Slope
    w = if dy == 0 then Nothing else Just $ maybe 0 (negate . recip) m -- Negative reciprocal
    justW = fromJust w -- Moral bankruptcy
    (px, py) = ((x a + x b) % 2, (y a + y b) % 2)                      -- Midpoint
    b0 = py - (justW * px)                                             -- Y-intercept
    f q = justW * q + b0                                               -- Perpendicular bisector
  in
   maybe (if denominator px == 1 then map (Point (numerator px)) [0..d - 1] else [])
         ( map (\q -> Point q (numerator . f . fromIntegral $ q))
         . filter ((== 1) . denominator . f . fromIntegral)
         )
         (w >> return [0..d - 1])

circle :: Dimension -> Point -> Delta -> [Point]
circle d p delta' =
  let
    square = (^(2 :: Int))
    hypoteneuse = euclidean delta'
    candidates = takeWhile ((<= hypoteneuse) . square) [0..d - 1]
    candidatesSet = fromList $ map square [0..d - 1]
    legs = filter ((`member` candidatesSet) . (hypoteneuse -) . square) candidates
    pythagoreans = zipWith Delta legs
                 $ map (\l -> floor . sqrt . (fromIntegral :: Int -> Double) $ hypoteneuse - square l) legs
  in
    toList . fromList $ concatMap (knight p) pythagoreans

knight :: Point -> Delta -> [Point]
knight Point{..} Delta{..} =
    [ Point (x + da) (y - db), Point (x + da) (y + db)
    , Point (x + db) (y - da), Point (x + db) (y + da)
    , Point (x - da) (y - db), Point (x - da) (y + db)
    , Point (x - db) (y - da), Point (x - db) (y + da)
    ]

type Dimension = Int
type Index = Int

index :: Dimension -> Point -> Index
index d Point{..} = y * d + x

point :: Dimension -> Index -> Point
point d i = Point (i `rem` d) (i `div` d)

valid :: Dimension -> Point -> Bool
valid d Point{..} = 0 <= x && x < d
                 && 0 <= y && y < d

isLT :: Ordering -> Bool
isLT LT = True
isLT _  = False

sieve :: Dimension -> [[Point]]
sieve d = [i0 : sieve' is0 [i0] [] | (i0:is0) <- tails . sortBy originDistance . map (point d) $ [0..d*d - 1]]
  where
    originDistance :: Point -> Point -> Ordering
    originDistance = compare `on` ((d*d -) . euclidean . delta (point d (d*d `div` 2)))

    sieve' :: [Point] -> [Point] -> [Delta] -> [Point]
    sieve' []     _  _ = []
    sieve' (i:is) ps ds = i : sieve' is' (i:ps) ds'
      where
        ds' = map (delta i) ps ++ ds
        knockouts = fromList [k | d' <- ds
                                , k  <- circle d i d'
                                , valid d k
                                , not . isLT $ k `originDistance` i
                                ]
            `union` fromList [k | q  <- i : ps
                                , d' <- map (delta i) ps
                                , k  <- circle d q d'
                                , valid d k
                                , not . isLT $ k `originDistance` i
                                ]
            `union` fromList [e | q <- ps
                                , e <- equidistant d i q
                                , valid d e
                                , not . isLT $ e `originDistance` i
                                ]
        is' = sortBy originDistance . toList $ fromList is `difference` knockouts

main :: IO ()
main = do let answers = strictlyIncreasingLength . map (map (index sideLength)) $ sieve sideLength
          hSetBuffering stdout LineBuffering
          mapM_ (putStrLn . unwords . map show) $ answers
  where
    strictlyIncreasingLength :: [[a]] -> [[a]]
    strictlyIncreasingLength = go 0
      where
        go _ []     = []
        go n (x:xs) = if n < length x then x : go (length x) xs else go n xs

산출

1237 381923 382543 382541 1238 1857 380066 5 380687 378828 611 5571 382553 377587 375113 3705 8664 376356 602 1253 381942 370161 12376 15475 7413 383131 367691 380092 376373 362114 36 4921 368291 19180 382503 26617 3052 359029 353451 29716 382596 372674 352203 8091 25395 12959 382479 381987 35894 346031 1166 371346 336118 48276 2555 332400 46433 29675 380597 13066 382019 1138 339859 368230 29142 58174 315070 326847 56345 337940 2590 382663 320627 70553 19278 7309 82942 84804 64399 5707 461 286598 363864 292161 89126 371267 377122 270502 109556 263694 43864 382957 824 303886 248218 18417 347372 282290 144227 354820 382909 380301 382808 334361 375341 2197 260623 222212 196214 231526 177637 29884 251280 366739 39442 143568 132420 334718 160894 353132 78125 306866 140600 297272 54150 240054 98840 219257 189278 94968 226987 265881 180959 142006 218763 214475

답변

width = 619
height = 619
area = width * height
currentAttempt = 0

temporaryLengths = []
lengths = []
points = []
pixels = []
for i in range(area):
    pixels.append(0)


def generate_points():
    global lengths
    while True:
        candidate = vacantPixel()
        if isUnique(candidate):
            lengths += temporaryLengths
            pixels[candidate] = 1
            points.append(candidate)
            print(candidate)
        if currentAttempt == area:
            break
    filename = 'uniquely-separated-points.txt'
    with open(filename, 'w') as file:
        file.write(' '.join(points))


def isUnique(n):
    x = n % width
    y = int(n / width)
    temporaryLengths[:] = []
    for i in range(len(points)):
        point = points[i]
        a = point % width
        b = int(point / width)
        d = distance(x, y, a, b)
        if d in lengths or d in temporaryLengths:
            return False
        temporaryLengths.append(d)
    return True


def distance(x1, y1, x2, y2):
    xd = x2 - x1
    yd = y2 - y1
    return (xd*xd + yd*yd) ** 0.5


def vacantPixel():
    global currentAttempt
    while True:
        n = currentAttempt
        currentAttempt += 1
        if pixels[n] == 0:
            break
    return n


generate_points()

0 1 3 7 12 20 30 44 65 80 96 122 147 181 203 251 289 360 400 474 564 592 627 660 747 890 1002 1155 1289 1417 1701 1789 1895 2101 2162 2560 2609 3085 3121 3331 3607 4009 4084 4242 4495 5374 5695 6424 6762 6808 7250 8026 8356 9001 9694 10098 11625 12881 13730 14778 15321 16091 16498 18507 19744 20163 20895 23179 25336 27397 31366 32512 33415 33949 39242 41075 46730 47394 48377 59911 61256 66285 69786 73684 79197 89530 95447 102317 107717 111751 116167 123198 126807 130541 149163 149885 154285 159655 163397 173667 173872 176305 189079 195987 206740 209329 214653 220911 230561 240814 249310 269071 274262 276855 285295 305962 306385 306515 312310 314505 324368 328071 348061 350671 351971 354092 361387 369933 376153

N = 619

def norm(p1, p2):
    return (p1//N - p2//N)**2 + (p1%N - p2%N)**2

def solve(selected, dists):
    global best

    if len(selected) > best:
        print(len(selected), "|", *selected)
        best = len(selected)

    for pixel in (range(selected[-1]+1, N*N) if selected else range((N+1)//2+1)):
        # By symmetry, place first pixel in first half of top row
        added_dists = [norm(pixel, p) for p in selected]
        added_set = set(added_dists)

        if len(added_set) != len(added_dists) or added_set & dists:
            continue

        selected.append(pixel)
        dists |= added_set

        solve(selected, dists)

        selected.pop()
        dists -= added_set

print("N =", N)
best = 0
selected = []
dists = set()
solve(selected, dists)

0 1 3 7 12 20 30 44 65 80 96 122 147 181 203 251 289 360 400 474 564 592 627 660 747 890 1002 1155 1289 1417 1701 1789 1895 2101 2162 2560 2609 3085 3121 3331 3607 4009 4084 4242 4495 5374 5695 6424 6762 6808 7250 8026 8356 9001 9694 10098 11625 12881 13730 14778 15321 16091 16498 18507 19744 20163 20895 23179 25336 27397 31366 32512 33415 33949 39242 41075 46730 47394 48377 59911 61256 66285 69786 73684 79197 89530 95447 102317 107717 111751 116167 123198 126807 130541 149163 149885 154285 159655 163397 173667 173872 176305 189079 195987 206740 209329 214653 220911 230561 240814 249310 269071 274262 276855 285295 305962 306385 306515 312310 314505 324368 328071 348061 350671 351971 354092 361387 371800 376153 378169

1: 1 (0)
2: 2 (0 1)
3: 3 (0 1 5)
4: 4 (0 1 6 12)
5: 5 (0 1 4 11 23)
6: 6 (0 1 9 23 32 35)
7: 7 (0 2 9 20 21 40 48)
8: 7 (0 1 3 12 22 56 61)
9: 8 (0 1 3 8 15 37 62 77)
10: 9 (0 1 7 12 30 53 69 80 89)

11: 10 (0 2 3 7 21 59 66 95 107 120)
12: 10 (0 1 3 7 33 44 78 121 130 140)

import math.pow
import math.sqrt

val height, width = 619
val area = height * width

case class Point(x: Int, y: Int)

def generate(n: Int): Set[Point] = {

  def distance(p: Point, q: Point) = {
    def square(x: Int) = x * x
    sqrt(square(q.x - p.x) + square(q.y - p.y))
  }

  def hasDuplicates(s: Seq[_]) = s.toSet.size != s.size

  def rotate(s: Vector[Point]): Vector[Point] = s.drop(n) ++ s.take(n)

  val remaining: Vector[Point] =
    rotate((for (y <- 0 until height; x <- 0 until width) yield { Point(x, y) }).toVector)
  var unique = Set.empty[Point]
  var distances = Set.empty[Double]
  for (candidate <- remaining) {
    if (!unique.exists(p => distances.contains(distance(candidate, p)))) {
      val candidateDistances = unique.toSeq.map(p => distance(candidate, p))
      if (!hasDuplicates(candidateDistances)) {
        unique = unique + candidate
        distances = distances ++ candidateDistances
      }
    }
  }
  unique
}

def print(s: Set[Point]) = {
  def toRowMajor(p: Point) = p.y*height + p.x
  println(bestPixels.map(toRowMajor).toSeq.sorted.mkString(" "))
}

var bestPixels = Set.empty[Point]
for (n <- 0 until area) {
  val pixels = generate(n)
  if (pixels.size > bestPixels.size) bestPixels = pixels
}
print(bestPixels)

302 303 305 309 314 322 332 346 367 382 398 424 449 483 505 553 591 619 647 680 719 813 862 945 1014 1247 1459 1700 1740 1811 1861 1979 2301 2511 2681 2913 3114 3262 3368 4253 4483 4608 4753 5202 5522 5760 6246 6474 6579 6795 7498 8062 8573 8664 9903 10023 10567 10790 11136 12000 14153 15908 17314 17507 19331 20563 20941 22339 25131 26454 28475 31656 38328 39226 40214 50838 53240 56316 60690 61745 62374 68522 71208 78598 80204 86005 89218 93388 101623 112924 115702 118324 123874 132852 136186 139775 144948 154274 159730 182200 193642 203150 203616 213145 214149 218519 219744 226729 240795 243327 261196 262036 271094 278680 282306 289651 303297 311298 315371 318124 321962 330614 336472 343091 346698 354881 359476 361983 366972 369552 380486 382491

from random import *
from bisect import *

W = H = 619
pts = []
deepest = 0
lengths = set()

def place(x, y):
    global lengths
    pos = (x, y)
    for px, py in pts:
        dist = (x-px)*(x-px) + (y-py)*(y-py)
        if dist in lengths:
            return False
    dists = set((x-px)*(x-px) + (y-py)*(y-py) for px, py in pts)
    if len(dists) != len(pts):
        return False
    lengths |= dists
    pts.append(pos)
    return True

def unplace():
    x, y = pos = pts.pop()
    for px, py in pts:
        dist = (x-px)*(x-px) + (y-py)*(y-py)
        lengths.remove(dist)

def walk(i):
    global deepest, backtrack
    depth = len(pts)
    while i < W*H:
        d, x, y, rem = order[i]
        if rem+depth <= deepest: # early out if remaining unique distances mean we can't improve
            return
        i += 1
        if place(x, y):
            j = i
            while j < W*H and order[j][0] == d: # skip those the same distance from origin
                j += 1
            walk(j)
            unplace()
            if backtrack <= depth:
                break
            if not randint(0, 5): # time to give up and explore elsewhere?
                backtrack = randint(0, len(pts))
                break
            backtrack = W*H # remove restriction
    if depth >= deepest:
        deepest = depth
        print (ox, oy), depth, "=", " ".join(str(y*W+x) for x, y in pts)

try:
    primes = (0,1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97)
    while True:
        backtrack = W*H
        ox, oy = choice(primes), choice(primes) # random origin coordinates
        order = sorted((float((ox-x)**2+(oy-y)**2)+random(), x, y) for x in xrange(W) for y in xrange(H))
        rem = sorted(set(int(o[0]) for o in order)) # ordered list of unique distances
        rem = {r: len(rem)-bisect_right(rem, r) for r in rem} # for each unique distance, how many remain?
        order = tuple((int(d), x, y, rem[int(d)]) for i, (d, x, y) in enumerate(order))
        walk(0)
except KeyboardInterrupt:
    print

3  =  0  2  3
4  =  0  2  4  7
5  =  0  2  5 17 23
6  =  0 12 21 28 29 30
7  =  4  6 11 14 27 36 42
8  =  0  2  8 11 42 55 56
9  =  0  2  9 12 26 50 63 71
10 =  0  2  7 10 35 75 86 89  93
11 =  0 23 31 65 66 75 77 95 114 117