Ich war fasziniert vom Design dieser Grafik der New York Times, in der jeder US-Bundesstaat durch ein Quadrat in einem Raster dargestellt wird. Ich fragte mich, ob sie die Quadrate von Hand platzierten oder tatsächlich eine optimale Platzierung der Quadrate (unter einer bestimmten Definition) fanden, um die Positionen der angrenzenden Zustände darzustellen.

Ihr Code wird einen kleinen Teil der Herausforderung annehmen, Quadrate optimal zu platzieren, um Zustände (oder andere beliebige zweidimensionale Formen) darzustellen. Insbesondere wird davon ausgegangen, dass wir bereits alle geografischen Zentren oder Schwerpunkte der Formen in haben ein praktisches Format, und dass die optimale Darstellung der Daten in einem Diagramm wie diesem derjenige ist, in dem der Gesamtabstand von den Schwerpunkten der Formen zu den Mittelpunkten der Quadrate, die sie darstellen, minimal ist, mit höchstens einem Quadrat in jedem mögliche Position.

Ihr Code erstellt eine Liste eindeutiger Gleitkomma-X- und -Y-Koordinatenpaare von 0,0 bis 100,0 (einschließlich) in einem beliebigen geeigneten Format und gibt die nicht negativen Ganzzahlkoordinaten der Einheitsquadrate in einem Raster aus, das für die Darstellung der Daten optimal platziert ist Ordnung bewahren. In Fällen, in denen mehrere Anordnungen von Quadraten optimal sind, können Sie eine der optimalen Anordnungen ausgeben. Es werden zwischen 1 und 100 Koordinatenpaare angegeben.

Dies ist Code Golf, der kürzeste Code gewinnt.

Beispiele:

Eingang: [(0.0, 0.0), (1.0, 1.0), (0.0, 1.0), (1.0, 0.0)]

Das ist einfach. Die Zentren der Quadrate in unserem Raster liegen bei 0,0, 1,0, 2,0 usw., sodass diese Formen in diesem Muster bereits perfekt an den Zentren der Quadrate platziert sind:

21
03

Ihre Ausgabe sollte also genau diese Koordinaten haben, aber als ganze Zahlen in einem Format Ihrer Wahl:

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

Eingang: [(2.0, 2.1), (2.0, 2.2), (2.1, 2.0), (2.0, 1.9), (1.9, 2.0)]

In diesem Fall befinden sich alle Formen in der Nähe der Mitte des Quadrats bei (2, 2), aber wir müssen sie wegschieben, da sich nicht zwei Quadrate an derselben Position befinden können. Durch Minimieren des Abstands vom Schwerpunkt einer Form zur Mitte des Quadrats, das sie darstellt, erhalten wir folgendes Muster:

 1
402
 3

So sollte Ihre Ausgabe sein [(2, 2), (2, 3), (3, 2), (2, 1), (1, 2)].

Testfälle:

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

Gesamtabstand von den Schwerpunkten der Formen zu den Mittelpunkten der Quadrate, die sie jeweils darstellen (bitte geben Sie mir Bescheid, wenn Sie Fehler entdecken!):

0.0
3.6
4.087011
13.243299
2.724791
1.144123

Nur zum Spaß:

Hier ist eine Darstellung der geografischen Zentren der angrenzenden Vereinigten Staaten in unserem Eingabeformat in etwa der von der Times verwendeten Größenordnung:

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

Um diese zu erhalten, habe ich die Koordinaten aus der zweiten Liste auf dieser Seite genommen und 0.4 * (125.0 - longitude)für unsere X-Koordinate und 0.4 * (latitude - 25.0)für unsere Y-Koordinate verwendet. So sieht das geplottet aus:

Die erste Person, die die Ausgabe ihres Codes mit den obigen Koordinaten als Eingabe verwendet, um ein Diagramm mit tatsächlichen Quadraten zu erstellen, bekommt einen Klaps auf die Rückseite!

Mathematica, 473 Bytes

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)

Vor dem Golfen:

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)

Erklärung :

Dieses Optimierungsproblem ist in Mathematica nicht schwer zu beschreiben. Eine Liste pvon Längenpunkten gegeben n,

• die Variablen x[i]und y[i]: v=Array[{x[#],y[#]}&,n],
• die Funktion zu minimieren , ist die Summe der Verschiebungen: f=Total[Norm/@(p-v)],
• die Einschränkungen sind: c=Flatten[v]∈Integers&&And@@(Or@@Thread[#1!=#2]&@@@Subsets[v,{2}]).

Und NMinimize[{f,cons},v,MaxIterations->Infinity]wird das Ergebnis geben. Leider scheint ein solches direktes Schema zu kompliziert, um konvergieren zu können.

Um das Problem der Komplexität zu umgehen, werden zwei Techniken angewendet:

• Eine große "Wechselwirkung" If[#1==#2,1*^4,0]&wird verwendet, um eine Kollision zwischen Punkten zu vermeiden.
• Anstatt alle Variablen gleichzeitig zu optimieren, optimieren wir nacheinander an jedem Punkt mit ihren Nachbarn.

Wir beginnen mit einer ersten Vermutung, indem wir die Punkte abrunden. Wenn die Optimierungen einzeln durchgeführt werden, wird erwartet, dass Kollisionen aufgelöst werden, und es wird eine optimierte Anordnung hergestellt.

Die endgültige Lösung ist zumindest gut, wenn nicht optimal. (Ich glaube :P)

Ergebnis :

Das Ergebnis von Just for fun ist unten dargestellt. Dunkelgrüne Punkte sind die Eingaben, graue Quadrate sind die Ausgaben und schwarze Linien zeigen die Verschiebungen.

Die Summe der Verschiebungen beträgt 19,4595 . Und die Lösung ist

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

Dies ist keine korrekte Implementierung. Es schlägt im zweiten der "weiteren Testfälle" fehl und erzeugt eine Lösung mit einer Gesamtentfernung von 13,5325, wobei die bereitgestellte Lösung nur 13,2433 benötigt. Eine weitere Komplikation ist die Tatsache, dass meine Golf-Implementierung nicht mit der ungolften übereinstimmt, die ich zuerst geschrieben habe ...

Es hat jedoch noch niemand geantwortet, und dies ist eine zu interessante Herausforderung, als dass man sie hätte überspringen lassen können. Außerdem habe ich ein Bild aus den USA-Daten erstellt, also gibt es das.

Der Algorithmus sieht ungefähr so ​​aus:

1. Schieben Sie alle Punkte auf die nächsten Ganzzahlkoordinaten (im Folgenden als "Quadrat" bezeichnet).
2. Finden Sie das Quadrat mit der größten Punktzahl.
3. Ermitteln Sie die kostengünstigste Umverteilung dieser Punkte auf die Nachbarschaft mit neun Feldern in diesem Bereich, wobei alle Quadrate ausgeschlossen sind, die bereits in Schritt 2 verarbeitet wurden.
   • Die Umverteilung ist auf einen Punkt pro Quadrat begrenzt, es sei denn, dies würde nicht genügend Quadrate ergeben (obwohl selbst dann nur ein Punkt auf diesem Quadrat verbleibt ).
4. Wiederholen Sie den Vorgang ab Schritt 2, bis kein Quadrat mehr als einen Punkt hat.
5. Suchen Sie die ursprünglichen Punkte nacheinander und geben Sie die Quadrate nacheinander aus.

Ich habe absolut keinen Beweis für die Optimalität für irgendeinen Teil dieses Algorithmus, nur den starken Verdacht, dass er "ziemlich gute" Ergebnisse liefert. Ich denke, das haben wir in meinen Uni-Tagen einen "heuristischen Algorithmus" genannt ...!

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

Und das Ergebnis der Ausführung auf den USA-Daten (dank einer Dienstprogrammfunktion, die die Ergebnisse in SVG umwandelt):

Dies ist etwas schlimmer als der, den der ungolfed Code erzeugt hat; Der einzige sichtbare Unterschied besteht darin, dass das Quadrat ganz oben rechts im besseren weiter links liegt.

MATLAB, 316 343 326 Bytes

Dieser ist in Arbeit - er ist nicht schnell, aber er ist kurz. Es scheint die meisten Testfälle zu bestehen. Momentan läuft die nur zum Spaß eingegebene Karte, aber sie läuft noch nach 10 Minuten, also ...

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

Und in einem etwas besser lesbaren Format:

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

Es wird erwartet, dass das Eingabeformat ein MATLAB-Array ist, beispielsweise:

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

Welches ist ziemlich nah an dem Format in der Frage, die etwas Spielraum ermöglicht.

Die Ausgabe hat dasselbe Format wie die Eingabe. Dabei handelt es sich um ein Array, bei dem jeder angegebene Index sowohl in der Eingabe als auch in der Ausgabe demselben Punkt entspricht.

Hmm, 8 Stunden und noch läuft auf der Karte eine ... diese Lösung ist garantiert am optimalsten zu finden, aber es macht es mit brachialer Gewalt, also dauert es sehr lange.

Ich habe eine andere Lösung gefunden, die viel schneller ist, aber wie die andere Antwort nicht das Optimum in einem der Testfälle findet. Interessanterweise wird unten die Karte angezeigt, die ich für meine andere (nicht veröffentlichte) Lösung bekomme. Es erreicht eine Gesamtstrecke von 20,72.