Zaintrygował mnie projekt tej grafiki z „New York Timesa”, w którym każdy stan USA jest reprezentowany przez kwadrat w siatce. Zastanawiałem się, czy umieścili kwadraty ręcznie, czy rzeczywiście znaleźli optymalne rozmieszczenie kwadratów (pod pewną definicją), aby przedstawić pozycje sąsiednich stanów.

Twój kod podejmie niewielką część zadania polegającego na optymalnym umieszczeniu kwadratów do reprezentowania stanów (lub innych dowolnych dwuwymiarowych kształtów). W szczególności zakłada, że ​​mamy już wszystkie geograficzne centra lub centroidy kształtów w wygodny format i że optymalna reprezentacja danych na takim schemacie to ta, w której całkowita odległość od centrów kształtów do środków kwadratów, które je reprezentują, jest minimalna, z co najwyżej jednym kwadratem na każdym możliwa pozycja.

Twój kod pobierze listę unikalnych par współrzędnych zmiennoprzecinkowych X i Y od 0,0 do 100,0 (włącznie) w dowolnym dogodnym formacie i wyświetli nieujemne liczby całkowite współrzędnych kwadratowych w siatce optymalnie umieszczonej do reprezentacji danych , zachowując porządek. W przypadkach, w których wielokrotne ułożenie kwadratów jest optymalne, możesz wyprowadzić dowolne z optymalnych ułożenia. Podanych zostanie od 1 do 100 par współrzędnych.

To jest kod golfowy, wygrywa najkrótszy kod.

Przykłady:

Wejście: [(0.0, 0.0), (1.0, 1.0), (0.0, 1.0), (1.0, 0.0)]

To jest proste. Środki kwadratów w naszej siatce wynoszą 0,0, 1,0, 2,0 itd., Więc te kształty są już idealnie umieszczone w środkach kwadratów w tym wzorze:

21
03

Zatem dane wyjściowe powinny mieć dokładnie te współrzędne, ale jako liczby całkowite, w wybranym formacie:

[(0, 0), (1, 1), (0, 1), (1, 0)]

Wejście: [(2.0, 2.1), (2.0, 2.2), (2.1, 2.0), (2.0, 1.9), (1.9, 2.0)]

W tym przypadku wszystkie kształty znajdują się blisko środka kwadratu w (2, 2), ale musimy je odepchnąć, ponieważ dwa kwadraty nie mogą znajdować się w tej samej pozycji. Minimalizacja odległości od środka ciężkości kształtu do reprezentującego go kwadratu daje nam następujący wzór:

 1
402
 3

Tak powinien wyglądać twój wynik [(2, 2), (2, 3), (3, 2), (2, 1), (1, 2)].

Przypadki testowe:

[(0.0, 0.0), (1.0, 1.0), (0.0, 1.0), (1.0, 0.0)] -> [(0, 0), (1, 1), (0, 1), (1, 0)]
[(2.0, 2.1), (2.0, 2.2), (2.1, 2.0), (2.0, 1.9), (1.9, 2.0)] -> [(2, 2), (2, 3), (3, 2), (2, 1), (1, 2)]
[(94.838, 63.634), (97.533, 1.047), (71.954, 18.17), (74.493, 30.886), (19.453, 20.396), (54.752, 56.791), (79.753, 68.383), (15.794, 25.801), (81.689, 95.885), (27.528, 71.253)] -> [(95, 64), (98, 1), (72, 18), (74, 31), (19, 20), (55, 57), (80, 68), (16, 26), (82, 96), (28, 71)]
[(0.0, 0.0), (0.1, 0.0), (0.2, 0.0), (0.0, 0.1), (0.1, 0.1), (0.2, 0.1), (0.0, 0.2), (0.1, 0.2), (0.2, 0.2)] -> [(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
[(1.0, 0.0), (1.0, 0.1), (1.0, 0.2), (1.0, 0.3)] -> [(1, 0), (0, 0), (2, 0), (1, 1)] or [(1, 0), (2, 0), (0, 0), (1, 1)]
[(3.75, 3.75), (4.25, 4.25)] -> [(3, 4), (4, 4)] or [(4, 3), (4, 4)] or [(4, 4), (4, 5)] or [(4, 4), (5, 4)]

Całkowita odległość od środkowych kształtów do środków kwadratów, które je reprezentują w każdym przypadku (daj mi znać, jeśli zauważysz jakieś błędy!):

0.0
3.6
4.087011
13.243299
2.724791
1.144123

Dla żartu:

Oto reprezentacja centrów geograficznych przyległych Stanów Zjednoczonych w naszym formacie wejściowym, w przybliżeniu w skali stosowanej przez Times:

[(15.2284, 3.1114), (5.3367, 3.7096), (13.0228, 3.9575), (2.2198, 4.8797), (7.7802, 5.5992), (20.9091, 6.6488), (19.798, 5.5958), (19.1941, 5.564), (17.023, 1.4513), (16.6233, 3.0576), (4.1566, 7.7415), (14.3214, 6.0164), (15.4873, 5.9575), (12.6016, 6.8301), (10.648, 5.398), (15.8792, 5.0144), (13.2019, 2.4276), (22.3025, 8.1481), (19.2836, 5.622), (21.2767, 6.9038), (15.8354, 7.7384), (12.2782, 8.5124), (14.1328, 3.094), (13.0172, 5.3427), (6.142, 8.8211), (10.0813, 6.6157), (3.3493, 5.7322), (21.3673, 7.4722), (20.1307, 6.0763), (7.5549, 3.7626), (19.7895, 7.1817), (18.2458, 4.2232), (9.813, 8.98), (16.8825, 6.1145), (11.0023, 4.2364), (1.7753, 7.5734), (18.8806, 6.3514), (21.3775, 6.6705), (17.6417, 3.5668), (9.9087, 7.7778), (15.4598, 4.3442), (10.2685, 2.5916), (5.3326, 5.7223), (20.9335, 7.6275), (18.4588, 5.0092), (1.8198, 8.9529), (17.7508, 5.4564), (14.0024, 7.8497), (6.9789, 7.1984)]

Aby je uzyskać, wziąłem współrzędne z drugiej listy na tej stronie i użyłem 0.4 * (125.0 - longitude)dla naszej współrzędnej X i 0.4 * (latitude - 25.0)naszej współrzędnej Y. Oto, jak to wygląda na wykresie:

Pierwsza osoba, która użyje danych wyjściowych ze swojego kodu z powyższymi współrzędnymi jako danych wejściowych do stworzenia diagramu z rzeczywistymi kwadratami, zostanie poklepana po plecach!

Mathematica, 473 bajty

f@p_:=(s=Flatten@Round@p;v=Array[{x@#,y@#}&,n=Length@p];
  Do[w=Flatten[{g@#,h@#}&/@(b=Flatten@Position[p,x_/;Norm[x-p[[i]]]<=2,{1}])];f=Total[Norm/@(p-v)]+Total[If[#1==#2,1*^4,0]&@@@v~Subsets~{2}]/.Flatten[{x@#->g@#,y@#->h@#}&@@@w]/.Thread[Flatten@v->s];
    c=w∈Integers&&And@@MapThread[Max[#-2,0]<=#2<=Min[#+2,100]&,{Flatten@p[[b]],w}];s=Flatten@ReplacePart[s~Partition~2,Thread[b->Partition[w/.Last@Quiet@NMinimize[{f,c},w,MaxIterations->300],2]]]
    ,{i,n}]~Do~{2};s~Partition~2)

Przed golfem:

f[p_]:=(n=Length@p;s=Flatten@Round@p;v=Array[{x[#],y[#]}&,n];
  Do[
    v2=Flatten[{x2[#],y2[#]}&/@(b=Flatten@Position[p,x_/;Norm[x-p[[i]]]<=2,{1}])];
    f2=Total[Norm/@(p-v)]+Total[If[#1==#2,1*^4,0]&@@@Subsets[v,{2}]]/.Flatten[{x[#]->x2[#],y[#]->y2[#]}&@@@v2]/.Thread[Flatten@v->s];
    c2=v2∈Integers&&And@@MapThread[Max[#-2,0]<=#2<=Min[#+2,100]&,{Flatten@p[[b]],v2}];
    s=Flatten@ReplacePart[s~Partition~2,Thread[b->Partition[v2/.Last@Quiet@NMinimize[{f2,c2},v2,MaxIterations->300],2]]];
    ,{i,n}]~Do~{2};
  s~Partition~2)

Objaśnienie :

Ten problem optymalizacji nie jest trudny do opisania w Mathematica. Biorąc pod uwagę listę punktów pdługości n,

• są zmienne x[i]i y[i]: v=Array[{x[#],y[#]}&,n],
• Funkcja celu zminimalizowania jest całkowitą przemieszczeń: f=Total[Norm/@(p-v)],
• ograniczenia są: c=Flatten[v]∈Integers&&And@@(Or@@Thread[#1!=#2]&@@@Subsets[v,{2}]).

I NMinimize[{f,cons},v,MaxIterations->Infinity]da wynik. Niestety taki prosty schemat wydaje się zbyt skomplikowany, aby można go było zjednoczyć.

Aby obejść problem złożoności, przyjmuje się dwie techniki:

• duża „interakcja” If[#1==#2,1*^4,0]&służy do uniknięcia kolizji między punktami.
• zamiast optymalizować wszystkie zmienne w tym samym czasie, optymalizujemy w każdym punkcie ich sąsiadów z kolei.

Zaczynamy od wstępnego odgadnięcia, zaokrąglając punkty. Gdy optymalizacje są wykonywane jeden po drugim, oczekuje się, że kolizje zostaną rozwiązane, a zoptymalizowane ustawienie zostanie ustanowione.

Ostateczne rozwiązanie jest co najmniej dobre, jeśli nie optymalne. (Wierzę :P)

Wynik :

Wynik Just for fun pokazano poniżej. Ciemnozielone punkty to dane wejściowe, szare kwadraty to dane wyjściowe, a czarne linie pokazują przemieszczenia.

Suma przesunięć wynosi 19,4595 . I rozwiązaniem jest

{{15,3},{5,4},{13,4},{2,5},{8,6},{21,6},{20,5},{19,5},{17,1},{17,3},{4,8},{14,6},{15,6},{13,7},{11,5},{16,5},{13,2},{22,8},{19,6},{21,7},{16,8},{12,9},{14,3},{13,5},{6,9},{10,7},{3,6},{22,7},{20,6},{8,4},{20,7},{18,4},{10,9},{17,6},{11,4},{2,8},{19,7},{22,6},{18,3},{10,8},{15,4},{10,3},{5,6},{21,8},{18,5},{2,9},{18,6},{14,8},{7,7}}

Python 3, 877 bajtów

To nie jest poprawna implementacja. Nie udaje się to w drugim z „dalszych przypadków testowych”, tworząc rozwiązanie o całkowitej odległości 13,5325, gdzie dostarczone rozwiązanie potrzebuje tylko 13,2433. Dalszą komplikacją jest fakt, że moja implementacja gry w golfa nie pasuje do tego, który napisałem pierwszy ...

Jednak nikt inny nie odpowiedział, a jest to zbyt interesujące wyzwanie, aby przejść obok niego. Mam też zdjęcie wygenerowane na podstawie danych z USA, więc o to chodzi.

Algorytm jest mniej więcej taki:

1. Popchnij wszystkie punkty do najbliższych współrzędnych całkowitych (zwanych dalej „kwadratem”).
2. Znajdź kwadrat z największą liczbą punktów.
3. Znajdź najtańszą redystrybucję tych punktów w sąsiedztwie dziewięciu kwadratów, z wyłączeniem kwadratów, które zostały już przetworzone w kroku 2.
   • Redystrybucja jest ograniczona do jednego punktu na kwadrat, chyba że nie zapewniłoby to wystarczającej liczby kwadratów (chociaż nawet wtedy na tym kwadracie pozostanie tylko jeden punkt ).
4. Powtarzaj od kroku 2, aż żaden kwadrat nie będzie miał więcej niż jednego punktu.
5. Zlokalizuj kolejno każdy z oryginalnych punktów i wyślij kolejno kwadraty.

Nie mam absolutnie żadnego dowodu optymalności dla jakiejkolwiek części tego algorytmu, tylko silne podejrzenie, że zapewni on „całkiem dobre” wyniki. Myślę, że to właśnie nazywaliśmy „algorytmem heurystycznym” w moich czasach uniwersyteckich ...!

l=len
I,G,M=-1,101,150
d=lambda x,y,X,Y:abs(x-X+1j*(y-Y))
N=(0,0),(I,0),(0,I),(1,0),(0,1),(I,I),(1,I),(1,1),(I,I)
n=lambda p,e:[(x,y)for(x,y)in(map(sum,zip(*i))for i in zip([p]*9,N))if(x,y)not in e and I<x<G and I<y<G]
def f(p):
 g={};F=[];O=[I]*l(p)
 for P in p:
  z=*map(round,P),
  if z in g:g[z]+=[P]
  else:g[z]=[P]
 while l(g)<l(p):
  L,*P=0,
  for G in g:
   if l(g[G])>l(P):L,P=G,g[G]
  o=n(L,F);h=l(o)<l(P);c=[[d(*q,*r)for r in o]for q in P];r={}
  while l(r)<l(c):
   A=B=C=M;R=S=0
   while R<l(c):
    if R not in r:
     z=min(c[R])
     if z<A:B,A=R,z;C=c[R].index(A)
    R+=1
   while S<l(c):
    if S==B:
     v=0
     while v<l(c[S]):
      if v!=C:c[S][v]=M
      v+=1
    elif C<1or not h:c[S][C]=M
    S+=1
   r[B]=C
  for q in r:
   x,y=P[q],o[r[q]]
   if y==L or y not in g:g[y]=[x]
   else:g[y]+=[x]
  F+=[L]
 for G in g:
  O[p.index(g[G][0])]=G
 return O

I wynik uruchomienia go na danych USA (dzięki funkcji narzędzia, która zamienia wyniki w SVG):

Jest to nieco gorsze niż ten, który stworzył nieoznakowany kod; jedyną widoczną różnicą jest to, że kwadrat w prawym górnym rogu znajduje się jeden dalej w lewo w lepszym.

MATLAB, 316 343 326 bajtów

Ten jest w toku - nie jest szybki, ale jest krótki. Wydaje się, że zdaje większość testów. Obecnie działa mapa dla zabawy, ale nadal działa po 10 minutach, więc ...

function p=s(a)
c=ceil(a');a=a(:,1)+j*a(:,2);[~,p]=r(a,c,[],Inf);p=[real(p),imag(p)];end
function [o,p]=r(a,c,p,o)
if ~numel(c)
o=sum(abs(p-a));else
x=c(1)+(-1:1);y=c(2)+(-1:1);P=p;
for X=1:3
for Y=1:3
Q=x(X)+j*y(Y);if(x(X)>=0)&(y(Y)>=0)&all(Q~=P)
[O,Q]=r(a,c(:,2:end),[P;Q],o);
if(O<o) o=O;p=Q;disp(o);end
end;end;end;end;end

I w nieco bardziej czytelnym formacie:

function p=squaremap(a)
%Input format: [2.0, 2.1;2.0, 2.2;2.1, 2.0;2.0, 1.9;1.9, 2.0]

    c=ceil(a'); %Convert each point to the next highest integer centre
    a=a(:,1)+j*a(:,2); %Convert each 2D point into a complex number
    [~,p]=r(a,c,[],Inf); %Recurse!
    p=[real(p),imag(p)];
end

function [o,p]=r(a,c,p,o)
    if ~numel(c) %If we are as deep as we can go
        o=sum(abs(p-a)); %See what our overall distance is
    else
        x=c(1)+(-1:1);y=c(2)+(-1:1); %For each point we try 9 points, essentially a 3x3 square
        P=p;
        for X=1:3;
            for Y=1:3
                %For each point
                Q=x(X)+j*y(Y); %Covert to a complex number
                if(x(X)>=0)&(y(Y)>=0)&all(Q~=P) %If the point is not negative and has not already been used this iteration
                    [O,Q]=r(a,c(:,2:end),[P;Q],o); %Otherwise iterate further
                    if(O<o) o=O;p=Q;end %Keep updating the smallest path and list of points we have found
                end
            end
        end
    end
end

Format wejściowy ma być tablicą MATLAB, taką jak:

[2.0, 2.1;2.0, 2.2;2.1, 2.0;2.0, 1.9;1.9, 2.0]

Który jest dość zbliżony do formatu w pytaniu, co pozwala na pewną swobodę.

Dane wyjściowe są w tym samym formacie co dane wejściowe, tablica, w której dowolny dany indeks odpowiada temu samemu punktowi zarówno na wejściu, jak i na wyjściu.

Hmm, 8 godzin i nadal działa na mapie jedna ... to rozwiązanie gwarantuje znalezienie najbardziej optymalnej, ale robi to z użyciem brutalnej siły, więc zajmuje to bardzo dużo czasu.

Wymyśliłem inne rozwiązanie, które jest znacznie szybsze, ale podobnie jak druga odpowiedź nie znajduje najbardziej optymalnego w jednym z przypadków testowych. Co ciekawe mapa, którą otrzymuję dla mojego innego rozwiązania (niepublikowana), jest pokazana poniżej. Osiąga łączny dystans 20,72.