Pixels séparés de manière unique

30

Pour une image N par N , recherchez un ensemble de pixels tel qu'aucune distance de séparation ne soit présente plus d'une fois. Autrement dit, si deux pixels sont séparés par une distance d , alors ce sont les deux seuls pixels qui sont séparés par exactement d (en utilisant la distance euclidienne ). Notez que d n'a pas besoin d'être entier.

Le défi est de trouver un tel ensemble plus grand que quiconque.

spécification

Aucune contribution n'est requise - pour ce concours, N sera fixé à 619.

(Puisque les gens continuent de demander - le nombre 619 n'a rien de spécial. Il a été choisi pour être suffisamment grand pour rendre improbable une solution optimale, et assez petit pour permettre à une image N par N d'être affichée sans que Stack Exchange la rétrécisse automatiquement. Les images peuvent être affiché en taille réelle jusqu'à 630 par 630, et j'ai décidé d'aller avec le plus grand nombre premier qui ne dépasse pas cela.)

Le résultat est une liste d'entiers séparés par des espaces.

Chaque entier dans la sortie représente l'un des pixels, numéroté dans l'ordre de lecture anglais à partir de 0. Par exemple pour N = 3, les emplacements seraient numérotés dans cet ordre:

0 1 2
3 4 5
6 7 8

Vous pouvez générer des informations de progression pendant l'exécution si vous le souhaitez, tant que la sortie de notation finale est facilement disponible. Vous pouvez exporter vers STDOUT ou vers un fichier ou tout ce qui est plus facile à coller dans le juge d'extrait de pile ci-dessous.

Exemple

N = 3

Coordonnées choisies:

(0,0)
(1,0)
(2,1)

Sortie:

0 1 5

Gagnant

Le score est le nombre d'emplacements dans la sortie. Parmi les réponses valides qui ont le score le plus élevé, la première à publier la sortie avec ce score l'emporte.

Votre code n'a pas besoin d'être déterministe. Vous pouvez publier votre meilleure sortie.

Domaines de recherche connexes

(Merci à Abulafia pour les liens Golomb)

Bien qu'aucun de ces éléments ne soit identique à ce problème, ils sont tous deux de concept similaire et peuvent vous donner des idées sur la façon d'aborder ce problème:

Notez que les points requis pour cette question ne sont pas soumis aux mêmes exigences qu'un rectangle de Golomb. Un rectangle de Golomb s'étend du cas unidimensionnel en exigeant que le vecteur de chaque point à l'autre soit unique. Cela signifie qu'il peut y avoir deux points séparés par une distance de 2 horizontalement, et également deux points séparés par une distance de 2 verticalement.

Pour cette question, c'est la distance scalaire qui doit être unique, donc il ne peut pas y avoir une séparation horizontale et verticale de 2. Chaque solution à cette question sera un rectangle de Golomb, mais tous les rectangles de Golomb ne seront pas une solution valide pour cette question.

Limites supérieures

Dennis a utilement souligné dans le chat que 487 est une limite supérieure sur le score, et a donné une preuve:

Selon mon code CJam ( 619,2m*{2f#:+}%_&,), il y a 118800 nombres uniques qui peuvent être écrits comme la somme des carrés de deux entiers compris entre 0 et 618 (les deux inclus). n pixels nécessitent n (n-1) / 2 distances uniques entre eux. Pour n = 488, cela donne 118828.

Il y a donc 118 800 longueurs différentes possibles entre tous les pixels potentiels de l'image, et placer 488 pixels noirs entraînerait 118 828 longueurs, ce qui rend impossible leur caractère unique.

Je serais très intéressé d'entendre si quelqu'un a une preuve d'une limite supérieure inférieure à celle-ci.

Classement

(Meilleure réponse de chaque utilisateur)

image de classement

Juge d'extrait de pile

Afficher l'extrait de code

code-challenge grid optimization trichoplax
la source
J'aurais adoré voir une réponse Piet ici
C5H8NNaO4
@ C5H8NNaO4 la compétition est ouverte - personne n'est près d'une solution optimale donc il y a beaucoup de place pour de nouvelles réponses ...
trichoplax
Puisque vous offrez des primes pour la liste supérieure prouvée et expérimentale de pixels, je suppose qu'il existe une sorte d'application à ce problème?
Fatalize
@Fatalize pas que je sache, mais je serais fasciné d'en entendre parler. Le problème similaire du tableau Costas a des applications pratiques répertoriées, mais je n'ai rien trouvé sur ce problème particulier.
trichoplax
1
J'ai regardé cela, et je pense que n = 487 est la limite supérieure minimale des pixels. Par curiosité, accepterez-vous une preuve qu'il n'y a pas de limite supérieure moindre pour la prime?
Mego

Réponses:

13

Python 3, 135 136 137

10 6830 20470 47750 370770 148190 306910 373250 267230 354030 30390 361470 118430 58910 197790 348450 381336 21710 183530 305050 2430 1810 365832 99038 381324 39598 262270 365886 341662 15478 9822 365950 44526 58862 24142 381150 31662 237614 118830 380846 7182 113598 306750 11950 373774 111326 272358 64310 43990 200278 381014 165310 254454 12394 382534 87894 6142 750 382478 15982 298326 70142 186478 152126 367166 1162 23426 341074 7306 76210 140770 163410 211106 207962 35282 165266 300178 120106 336110 30958 158 362758 382894 308754 88434 336918 244502 43502 54990 279910 175966 234054 196910 287284 288468 119040 275084 321268 17968 2332 86064 340044 244604 262436 111188 291868 367695 362739 370781 375723 360261 377565 383109 328689 347879 2415 319421 55707 352897 313831 302079 19051 346775 361293 328481 35445 113997 108547 309243 19439 199037 216463 62273 174471 207197 167695 296927

Trouvé à l'aide d'un algorithme gourmand qui, à chaque étape, choisit le pixel valide dont l'ensemble des distances aux pixels choisis chevauche le moins celui des autres pixels.

Plus précisément, la notation est

score(P) = sum(number of pixels with D in its distance set
               for each D in P's distance set)

et le pixel avec le score le plus bas est choisi.

La recherche est lancée avec le point 10(ie (0, 10)). Cette partie est réglable, donc commencer avec des pixels différents peut conduire à des résultats meilleurs ou pires.

C'est un algorithme assez lent, donc j'essaie d'ajouter des optimisations / heuristiques, et peut-être un peu de retour en arrière. PyPy est recommandé pour la vitesse.

Quiconque essaie de trouver un algorithme devrait tester N = 10, pour lequel j'ai 9 (mais cela a pris beaucoup de réglages et d'essais différents points initiaux):

entrez la description de l'image ici

Code

from collections import Counter, defaultdict
import sys
import time

N = 619

start_time = time.time()

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

selected = [10]
selected_dists = {norm(p1, p2) for p1 in selected for p2 in selected if p1 != p2}
pix2dist = {} # {candidate pixel: {distances to chosen}}
dist2pix = defaultdict(set)

for pixel in range(N*N):
    if pixel in selected:
        continue

    dist_list = [norm(pixel, p) for p in selected]
    dist_set = set(dist_list)

    if len(dist_set) != len(dist_list) or dist_set & selected_dists:
        continue

    pix2dist[pixel] = dist_set

    for dist in dist_set:
        dist2pix[dist].add(pixel)

while pix2dist:
    best_score = None
    best_pixel = None

    for pixel in sorted(pix2dist): # Sorting for determinism
        score = sum(len(dist2pix[d]) for d in pix2dist[pixel])

        if best_score is None or score < best_score:
            best_score = score
            best_pixel = pixel

    added_dists = pix2dist[best_pixel]
    selected_dists |= added_dists
    del pix2dist[best_pixel]
    selected.append(best_pixel)

    for d in added_dists:
        dist2pix[d].remove(best_pixel)

    to_remove = set()
    for pixel in pix2dist:
        new_dist = norm(pixel, best_pixel)

        if (new_dist in selected_dists or new_dist in pix2dist[pixel]
                or added_dists & pix2dist[pixel]):
            to_remove.add(pixel)
            continue

        pix2dist[pixel].add(new_dist)
        dist2pix[new_dist].add(pixel)

    for pixel in to_remove:
        for d in pix2dist[pixel]:
            dist2pix[d].remove(pixel)

        del pix2dist[pixel]

    print("Selected: {}, Remaining: {}, Chosen: ({}, {})".format(len(selected), len(pix2dist),
                                                                 best_pixel//N, best_pixel%N))
    sys.stdout.flush()

print(*selected)
print("Time taken:", time.time() - start_time)
Sp3000
la source
3
J'ai rapidement forcé brutalement N=10et il existe de nombreuses dispositions distinctes avec 9 points, mais c'est le mieux que vous puissiez faire.
Will
5

SWI-Prolog, score de 131

À peine mieux que la réponse initiale, mais je suppose que cela fera démarrer les choses un peu plus. L'algorithme est le même que la réponse Python, à l'exception du fait qu'il essaie les pixels d'une manière alternative, en commençant par le pixel supérieur gauche (pixel 0), puis le pixel inférieur droit (pixel 383160), puis le pixel 1, puis le pixel 383159 , etc.

a(Z) :-
    N = 619,
    build_list(N,Z).

build_list(N,R) :-
    M is N*N,
    get_list([M,-1],[],L),
    reverse(L,O),
    build_list(N,O,[],[],R).

get_list([A,B|C],R,Z) :-
    X is A - 1,
    Y is B + 1,
    (X =< Y,
    Z = R
    ;
    get_list([X,Y,A,B|C],[X,Y|R],Z)).

build_list(_,[],R,_,R) :- !.
build_list(N,[A|T],R,W,Z) :-
    separated_pixel(N,A,R,W,S),
    is_set(S),
    flatten([W|S],V),!,
    build_list(N,T,[A|R],V,Z)
    ;build_list(N,T,R,W,Z).


separated_pixel(N,A,L,W,R) :-
    separated_pixel(N,A,L,[],W,R).

separated_pixel(N,A,[A|T],R,W,S) :-
        separated_pixel(N,A,T,R,W,S).

separated_pixel(N,A,[B|T],R,W,S) :-
    X is (A mod N - B mod N)*(A mod N - B mod N),
    Y is (A//N - B//N)*(A//N - B//N),
    Z is X + Y,
    \+member(Z,W),
    separated_pixel(N,A,T,[Z|R],W,S).

separated_pixel(_,_,[],R,_,R).

Contribution:

a(A).

Sortie:

Z = [202089, 180052, 170398, 166825, 235399, 138306, 126354, 261759, 119490, 117393, 281623, 95521, 290446, 299681, 304310, 78491, 314776, 63618, 321423, 60433, 323679, 52092, 331836, 335753, 46989, 40402, 343753, 345805, 36352, 350309, 32701, 32470, 352329, 30256, 28089, 357859, 23290, 360097, 22534, 362132, 20985, 364217, 365098, 17311, 365995, 15965, 15156, 368487, 370980, 371251, 11713, 372078, 372337, 10316, 373699, 8893, 374417, 8313, 7849, 7586, 7289, 6922, 376588, 6121, 5831, 377399, 377639, 4941, 378494, 4490, 379179, 3848, 379453, 3521, 3420, 379963, 380033, 3017, 380409, 2579, 380636, 2450, 2221, 2006, 381235, 1875, 381369, 381442, 381682, 1422, 381784, 1268, 381918, 1087, 382144, 382260, 833, 382399, 697, 382520, 622, 382584, 382647, 382772, 384, 382806, 319, 286, 382915, 382939, 190, 172, 383005, 128, 383050, 93, 383076, 68, 383099, 52, 40, 383131, 21, 383145, 10, 383153, 4, 383158, 1, 383160, 0]

Image de l'extrait de pile

131 points

Fatalize
la source
Puisqu'il y a un maximum théorique de 487, même une augmentation incrémentielle est significative ...
trichoplax
Votre sortie, comme illustré, a-t-elle fonctionné avec l'extrait de pile? J'avais spécifié l'espace séparé (comme dans mon exemple de réponse) mais la raison principale en était que l'extrait de pile fonctionnerait.
trichoplax le
@trichoplax Ouais c'est une faute de frappe, je commence par le pixel 0, je vais le corriger. Pour obtenir l'image, j'ai sélectionné la partie de la sortie entre les deux crochets et supprimé toutes les virgules. L'extrait de pile semble cependant fonctionner avec des pixels séparés par des virgules.
Fatalize
4

Haskell— 115 130 131 135 136

Mon inspiration était le tamis d'Ératosthène et en particulier le tamis authentique d'Ératosthène , un article de Melissa E. O'Neill du Harvey Mudd College. Ma version originale (qui considérait les points dans l'ordre des index) a criblé les points extrêmement rapidement, pour une raison que je ne me souviens pas, j'ai décidé de mélanger les points avant de les "tamiser" dans cette version (je pense uniquement pour faciliter la génération de réponses différentes en utilisant une nouvelle graine dans le générateur aléatoire). Parce que les points ne sont plus dans aucun ordre, il n'y a plus vraiment de tamisage, et en conséquence, cela prend quelques minutes juste pour produire cette réponse unique de 115 points. Un KO Vectorserait probablement un meilleur choix maintenant.

Donc, avec cette version comme point de contrôle, je vois deux branches, revenir à l'algorithme «Genuine Sieve» et tirer parti de la monade List pour le choix, ou échanger les Setopérations contre des équivalents Vector.

Edit: Donc, pour la version de travail deux, je suis retourné vers l'algorithme de tamisage, amélioré la génération de «multiples» (assommant les indices en trouvant des points aux coordonnées entières sur des cercles de rayon égal à la distance entre deux points quelconques, semblable à la génération de multiples premiers ) et en apportant quelques améliorations de temps constant en évitant un recalcul inutile.

Pour une raison quelconque, je ne peux pas recompiler avec le profilage activé, mais je pense que le principal goulot d'étranglement est maintenant le retour en arrière. Je pense qu'explorer un peu de parallélisme et de simultanéité produira des accélérations linéaires, mais l'épuisement de la mémoire me limitera probablement à une amélioration de 2x.

Edit: la version 3 serpentait un peu, j'ai d'abord expérimenté une heuristique en prenant les index next suivants (après avoir tamisé à partir des choix précédents) et en choisissant celui qui a produit le prochain ensemble de knock-out minimum. Cela a fini par être beaucoup trop lent, alors je suis retourné à une méthode de force brute sur tout l'espace de recherche. Une idée de commander les points par distance à partir d'une certaine origine m'est venue et a conduit à une amélioration d'un seul point (dans le temps ma patience a duré). Cette version prend l'index 0 comme origine, cela peut valoir la peine d'essayer le point central de l'avion.

Edit: J'ai ramassé 4 points en réorganisant l'espace de recherche pour prioriser les points les plus éloignés du centre. Si vous testez mon code, 135 136 est en fait la deuxième troisième solution trouvée. Édition rapide: cette version semble la plus susceptible de rester productive si elle est exécutée. Je soupçonne que je peux égaliser à 137, puis manquer de patience en attendant 138.

Une chose que je remarque (qui peut être utile à quelqu'un) est que si vous définissez la commande de point au centre du plan (c. -à- remove (d*d -)de originDistance) l'image semble formé un peu comme une spirale premier clairsemée.

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

Sortie

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
RB
la source
Améliorations impressionnantes. Il vous reste 2 heures pour atteindre 138 avant l'attribution de la prime. Beau travail de toute façon ...
trichoplax
Il semble peu probable que j'atteigne cet objectif, je n'ai toujours pas réussi à générer un ensemble de 137 éléments. Je pense que cette méthode est probablement exploitée ...
RB
Il est intéressant de noter que deux réponses différentes avec des approches différentes atteignent un maximum autour de la même taille.
trichoplax
Je pense que la limite supérieure est probablement assez proche. Considérons un plan infini et deux points quelconques. Le placement optimal de ces points à n'importe quelle distance dminimise le nombre d'autres points exclus de la prise en compte en traçant des cercles de rayon davec les centres des deux points choisis, où le périmètre ne touche que trois autres coordonnées entières (à 90, 180 et 270 degrés). le cercle), et la ligne bissectrice perpendiculaire ne croisant aucune coordonnée entière. Ainsi, chaque nouveau point n+1exclura d' 6nautres points de la considération (avec un choix optimal).
RB
3

Python 3, score 129

Ceci est un exemple de réponse pour commencer.

Juste une approche naïve en passant par les pixels dans l'ordre et en choisissant le premier pixel qui ne provoque pas de distance de séparation en double, jusqu'à ce que les pixels soient épuisés.

Code

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()

Sortie

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

Image de l'extrait de pile

image de 129 pixels séparés de façon unique

trichoplax
la source
3

Python 3, 130

À titre de comparaison, voici une implémentation de backtracker récursif:

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)

Il trouve rapidement la solution de 130 pixels suivante avant de commencer à s'étouffer:

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

Plus important encore, je l'utilise pour vérifier les solutions pour les petits cas. Pour N <= 8, les optimales sont:

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)

Entre parenthèses figurent les premiers optimaux lexicographiques.

Non confirmé:

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

Scala, 132

Numérise de gauche à droite et de haut en bas comme la solution naïve, mais essaie de commencer à différents emplacements de pixels. 

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)

Sortie

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
Dave Swartz
la source
3
Juste faire bouger les choses ...
Dave Swartz
3

Python, 134 132

Voici un simple qui élimine au hasard une partie de l'espace de recherche pour couvrir une plus grande zone. Il itère les points à distance d'un ordre d'origine. Il saute les points qui sont à la même distance de l'origine et les départs anticipés s'il ne peut pas s'améliorer au mieux. Il fonctionne indéfiniment.

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

Il trouve rapidement des solutions avec 134 points:

3097 3098 2477 4333 3101 5576 1247 9 8666 8058 12381 1257 6209 15488 6837 21674 19212 26000 24783 1281 29728 33436 6863 37767 26665 14297 4402 43363 50144 52624 18651 9996 58840 42792 6295 69950 48985 347367477 7197 7197487 7197 7197 7197 7197 7997 9197 7997 7997 947 7607 247 7367477 247 7367 347 437 7367 7367 7367 7327 dans la vente de la vente des produits de la vente de la vente en France 113.313 88.637 122.569 11.956 36.098 79.401 61.471 135.610 31.796 4.570 150.418 57.797 4.581 125.201 151.128 115.936 165.898 127.697 162.290 33.091 20.098 189.414 187.620 186.440 91.290 206.766 35.619 69.033 351 186.511 129.058 228.458 69.065 226.046 210.035 235.925 164.324 18.967 254.416 130.970 17.753 248.978 57.376 276.798 456 283.541 293.423 257.747 204.626 298.427 249115 21544 95185 231226 54354 104483 280665 518 147181 318363 1793 248609 82260 52568 365227 361603 346849 331462 69310 90988 341446 229599 277828 382837 339014 323612 365040 269883 307597 374347 3162821 354698

Pour les curieux, voici quelques petits N brutaux:

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
Volonté
la source
Avez-vous essayé d'exécuter ceci via PyPy ?
trichoplax du
1
@trichoplax J'exécute toujours ces passe-temps sur pypy et cpython, et si cpython est plus rapide, je dépose des tickets sur pypy. Dans ce cas particulier, pypy est un peu plus rapide que cpython et c'est comme ça que j'ai obtenu ces chiffres :)
Will
Je suis intéressé, qu'est-ce que cela implique "rapidement"?
Cain
@Cain 'rapidement' était d'environ 5 minutes iirc
Will
2

Fantom 96

J'ai utilisé un algorithme d'évolution, essentiellement ajouter k points aléatoires à la fois, faire cela pour j différents ensembles aléatoires, puis choisir le meilleur et répéter. Réponse assez terrible en ce moment, mais c'est la faire fonctionner avec seulement 2 enfants par génération pour des raisons de vitesse, ce qui est presque juste aléatoire. Je vais jouer un peu avec les paramètres pour voir comment ça se passe, et j'ai probablement besoin d'une meilleure fonction de notation que le nombre de places libres restantes.

class Pixel
{
  static const Int n := 619
  static const Int stepSize := 20
  static const Int generationSize := 5
  static const |Int, Int -> Int| d := |Int x, Int y -> Int| {
      d1 := x%n - y%n
      d2 := x/n - y/n
      return d1.pow(2) + d2.pow(2)
    }


  public static Void main(){

    //Initialize

    [Int: Int[][]] disMap := [:]
    Int[] freeSpots := (0..<n*n).toList
    Int[] pixels := [,]
    Int[] distances := [,]





    genNum := 0
    children := [,]
    while(freeSpots.size > 0){
      echo("Generation: ${genNum++} \t Spots Left: ${freeSpots.size} \t Pixels added: $pixels.size \t Distances used: $distances.size uniqueDistances: $distances.unique.size" )
      echo(distances)
      echo("Pixels: " + pixels.join(" "))
      //echo("Distances: $distances")
      //Generate children
      children = [,]
      generationSize.times{
        //echo("\tStarting child $it")
        i := Int.random(0..<freeSpots.size)
        childFreeSpots := freeSpots.dup
        childPixels := pixels.dup
        childDistances := distances.dup

        for(Int step := 0; step < stepSize; step++){

          if( i < childFreeSpots.size){
            //Choose a pixel
            pixel := childFreeSpots.removeAt(i)
            //echo("\t\tAdding pixel $pixel")

            //Remove neighbors that are the new distances away
            ///Find distances
            newDis := [,]
            childPixels.each { 
              newDis.add(d(pixel, it))
            }

            //Check that there are no equal distances
            if(newDis.size != newDis.unique.size) continue



            //Remove neighbors
            childPixels.each | Int childPixel|{
              newDis.each |Int dis|{
                neighbors := getNeighbors(childPixel, dis, disMap)
                neighbors.each| Int n |{
                  index := childFreeSpots.binarySearch(n)
                  if(index >= 0) childFreeSpots.removeAt(index)
                }
              }
            }
            //echo("Removed neighbors: $test")
            //Remove all the neighbors of new pixel
            childDistances.addAll(newDis)
            childDistances.each|Int dis| {   
              neighbors := getNeighbors(pixel, dis, disMap)
              childFreeSpots.removeAll(neighbors)
            }

            //Add new pixel
            childPixels.add(pixel)  
          }
        }
        children.add([childPixels.dup, childDistances.dup, childFreeSpots.dup])
        echo("\tChild $it: pixels: $childPixels.size \t distances: $childDistances.size \t freeSpots: $childFreeSpots.size")
      }

      //Score children and keep best one as new parent
      Obj?[][] parent := children.max |Int[][] a, Int[][] b -> Int| { return (a.last.size  + a.first.size*10000) <=> (b.last.size + b.first.size*10000)  }
      pixels = parent.first
      distances = parent[1]
      freeSpots = parent.last

    }//End while


    //Return result
    echo("Size: " + pixels.size)
    echo(pixels.join(" "))





  }

  private static Bool checkValid(Int[] pixels){
    distances := [,]
    pixels[0..-2].each|Int p, Int i|{
      for(Int j := i + 1; j < pixels.size; j++){
        distances.add(d(p, pixels[j]))
      }
    }
    if(distances.size > distances.unique.size){
      echo("Duplicate distance found!!!!")
      echo("Pixel $pixels.last is not valid")
      return false
    }
    return true
  }

  public static Int[] getNeighbors(Int spot, Int distance, [Int : Int[][]] disMap ){
    result := [,]
    //Check hash map
    pairs := disMap.get(distance, null)

    //Find possible int pairs if not already in the map
    if(pairs == null){
      for(Int i := 0; i*i <= distance; i++ ){
        for(Int j := i; j*j + i*i <= distance; j++){
          if(i.pow(2) + j.pow(2) == distance){
            pairs.add([i, j])
          }
        }
      }
      disMap.add(distance, pairs)
    }

    pairs.each|Int[] pair|{
      //Find neighbors with pair
      x := pair.first
      y := pair.last
      2.times{ 
        //Positive x
        result.add(spot + x + y*n)
        result.add(spot + x - y*n)

        //negative x
        result.add(spot - x + y*n)
        result.add(spot - x - y*n)

        //Swap x and y and repeat
        temp := x
        x = y
        y = temp
      }
    }

    return result.findAll |Int i -> Bool| { i >= 0 }.unique
  }

}

Sortie

17595 17596 17601 17627 17670 17726 17778 17861 17956 18117 18324 18733 19145 19597 20244 21139 21857 22742 24078 25343 28577 30152 32027 34406 37008 39864 42313 44820 48049 52193 55496 59707 64551 69976 74152 79758 84392 91782 98996 104625 150212 158877 169579 178660 189201 201343 213643 225998 238177 251012 263553 276797 290790 304915 319247 332702 347266 359665 373683 125899 144678 170677 195503 220092 244336 269861 289473 308633 326736 343756 358781 374280 131880 172485 212011 245015 277131 302055 321747 347911 363717 379166 249798 284200 313870 331913 360712 378024 9704 141872 249686 293656 357038 357596 370392 381963
Caïn
la source
1
Oh wow, tu as raison, je suis désolé. Hmm, je n'ai pas dû tout copier au début quand j'ai testé. Je vais corriger tout ce qui se passe et répondre avec une mise à jour
Cain
Ahh, je l'ai compris, lors de l'ajout d'un nouveau pixel, je ne vérifiais pas qu'il n'était pas à égale distance de deux autres pixels
Cain
Corrigé, mais ça craint vraiment maintenant, je pense que je pourrais accidentellement trouver la pire solution au lieu de la meilleure
Cain
Au moins, cela fonctionne maintenant, vous pouvez donc modifier les paramètres et voir si vous pouvez améliorer le résultat. Super de voir une autre nouvelle approche. +1
trichoplax
1

Python 3, 119

Je ne me souviens plus pourquoi j'ai nommé cette fonction mc_usp , même si je soupçonne qu'elle a quelque chose à voir avec les chaînes de Markov. Ici, je publie mon code que j'ai exécuté avec PyPy pendant environ 7 heures. Le programme essaie de créer 100 ensembles de pixels différents en choisissant aléatoirement des pixels jusqu'à ce qu'il ait vérifié chaque pixel de l'image et en renvoyant l'un des meilleurs ensembles.

Sur une autre note, à un moment donné, nous devrions vraiment essayer de trouver une limite supérieure pour N=619mieux que 488, car à en juger par les réponses ici, ce nombre est beaucoup trop élevé. Le commentaire de Rowan Blush sur la façon dont chaque nouveau point n+1peut potentiellement supprimer des 6*npoints avec un choix optimal semblait être une bonne idée. Malheureusement, lors de l'inspection de la formule a(1) = 1; a(n+1) = a(n) + 6*n + 1, où se a(n)trouve le nombre de points supprimés après avoir ajouté des npoints à notre ensemble, cette idée peut ne pas être la meilleure. Vérifier quand a(n)est supérieur à N**2, a(200)étant plus grand que ce qui 619**2semble prometteur, mais a(n)plus grand que cela 10**2est a(7)et nous avons prouvé que 9 est la limite supérieure réelle deN=10. Je vous tiendrai au courant pendant que j'essaierai de chercher une meilleure limite supérieure, mais toutes les suggestions sont les bienvenues.

Sur ma réponse. Tout d'abord, mon ensemble de 119 pixels.

15092 27213 294010 340676 353925 187345 127347 21039 28187 4607 23476 324112 375223 174798 246025 185935 186668 138651 273347 318338 175447 316166 158342 97442 361309 251283 29986 98029 339602 292202 304041 353401 236737 324696 42096 102574 357602 66845 40159 57866 3291 24583 254208 357748 304592 86863 19270 228963 87315 355845 55101 282039 83682 55643 292167 268632 118162 48494 378303 128634 117583 841 178939 20941 161231 247142 110205 211040 90946 170124 362592 327093 336321 291050 29880 279825 212675 138043 344012 187576 168354 28193 331713 329875 321927 129452 163450 1949 186448 50734 14422 3761 322400 318075 77824 36391 31016 33491 360713 352240 45316 79905 376004 310778 382640 383077 359178 14245 275451 362125 268047 23437 239772 299047 294065 46335 112345 382617 79986

Deuxièmement, mon code, qui choisit au hasard un point de départ à partir d'un octant du carré 619x619 (puisque le point de départ est par ailleurs égal en rotation et en réflexion), puis tous les autres points du reste du carré.

import random
import time

start_time = time.time()
print(start_time)

def mc_usp_v3(N, z, k=100, m=1.0):
    """
    At m=1.0, it keeps randomly picking points until we've checked every point. Oh dear.
    """
    ceil = -(-N//2)
    a=random.randint(0,ceil)
    b=random.randint(a,ceil)
    r=[a*N+b]

    best_overall = r[:]
    all_best = []
    best_in_shuffle = r[:]
    num_shuffles = 0
    num_missteps = 0
    len_best = 1

    while num_shuffles < k and len(best_overall) < z:
        dist = []
        missteps = []
        points_left = list(range(N*N))
        points_left.remove(r[0])

        while len_best + num_missteps < m*N*N and len(points_left):
            index = random.randint(0, len(points_left)-1)
            point = points_left[index]
            points_left.pop(index)
            dist, better = euclid(r, point, dist, N)

            if better and len(r) + 1 > len_best:
                r.append(point)
                best_in_shuffle = r[:]
                len_best += 1
            else:
                missteps.append(point)
                num_missteps += 1

        else:
            print(num_shuffles, len(best_overall), len_best, num_missteps, time.time() - start_time)

            num_shuffles += 1
            num_missteps = 0
            missteps = []

            if len(best_in_shuffle) == len(best_overall):
                all_best.append(best_in_shuffle)
                print(best_in_shuffle)

            if len(best_in_shuffle) > len(best_overall):
                best_overall = best_in_shuffle[:]
                all_best = [best_overall]
                print(best_overall)
            a=random.randint(0,ceil)
            b=random.randint(a,ceil)
            r=[a*N+b]
            best_in_shuffle = r[:]
            len_best = 1
    return len(best_overall), all_best

def euclid(point_set, new_point, dist, N):
    new_dist = []
    unique = True
    a,b=divmod(new_point, N)
    for point in point_set:
        c,d=divmod(point, N)
        current_dist = (a-c)**2+(b-d)**2
        if current_dist in dist or current_dist in new_dist:
            unique = False
            break
        new_dist.append(current_dist)
    if unique:
        dist += new_dist
    return dist, unique

def mcusp_format(mcusp_results):
    length, all_best = mcusp_results
    return " ".join(str(i) for i in all_best[0])

print(mcusp_format(mc_usp_v3(10, 20, 100, 1.0)))
print(mcusp_format(mc_usp_v3(619, 488, 100, 1.0)))
print(time.time()-start_time)
Sherlock9
la source