Bestimmen Sie anhand einer Liste von 2d (x, y) -Koordinaten, wie viele Einheitsquadrate (Kantenlänge 1 Einheit) unter Verwendung der Koordinaten gebildet werden können.
- Die Eingabe erfolgt über ein Array von 0 oder mehr Koordinatenpaaren:
z. B. in JavaScript:numofsq([[0,0], [1,0], [1,1], [0,1]]) - Keine doppelten Koordinaten in der Eingabe
- Die Eingabereihenfolge ist zufällig (zufällige 2D-Koordinaten).
- Koordinatenform: [x-Koordinate, y-Koordinate] (duh)
- Reihenfolge der Koordinaten: [0,0], [1,0], [1,1], [0,1] und [0,0], [0,1], [1,1], [1,0 ] bezeichnen das gleiche Einheitsquadrat (nur einmal zu zählen)
- Koordinaten können negative oder positive ganze Zahlen sein (duh)
- Die Funktion gibt nur die Anzahl der möglichen Einheitsquadrate zurück, 0 oder mehr.
Testfälle:
Input Coordinates Pairs Expected Output
[0,0], [0,1], [1,1], [1,0], [0,2], [1,2] 2
[0,0], [0,1], [1,1], [1,0], [0,2], [1,2], [2,2], [2,1] 3
[0,0], [0,1], [1,1], [1,0], [0,2], [1,2], [2,2], [2,1], [2,0] 4
[0,0], [0,1], [1,1], [1,0], [0,2], [1,2], [2,2], [2,1], [2,0], [9,9] 4
Spoiler Alert: Lösungsmaterial ab hier [JS]
Nicht-Golf, schnell und schmutzig, Brute-Force-Ansatz (enthalten, um einige Anweisungen zu geben).
//cartesian distance function
function dist(a, b) {
if (b === undefined) {
b = [0, 0];
}
return Math.sqrt((b[0] - a[0]) * (b[0] - a[0]) + (b[1] - a[1]) * (b[1] - a[1]));
}
//accepts 4 coordinate pairs and checks if they form a unit square
//this could be optimized by matching x,y coordinates of the 4 coordinates
function isUnitSquare(a) {
var r = a.slice(),
d = [],
c = [],
i,
j = 0,
counter = 0;
for (i = 1; i < 4; i++) {
if (dist(a[0], a[i]) === 1) {
d.push(a[i]);
r[i] = undefined;
counter++;
}
}
r[0] = undefined;
c = d.concat(r.filter(function(a) {return undefined !== a}));
if (dist(c[0], c[1]) === 1) {j++};
if (dist(c[1], c[2]) === 1) {j++};
if (dist(c[2], c[0]) === 1) {j++};
return counter === 2 && j === 2;
}
//a powerset function (from rosetta code)
//however, we will need only "sets of 4 coordinates"
//and not all possible length combinations (sets of 3 coords or
//sets of 5 coords not required). Also, order doesn't matter.
function powerset(ary) {
var ps = [[]];
for (var i=0; i < ary.length; i++) {
for (var j = 0, len = ps.length; j < len; j++) {
ps.push(ps[j].concat(ary[i]));
}
}
return ps;
}
//so to capture only sets of 4 coordinates, we do
var res = powerset([[0,0], [0,1], [1,1], [1,0], [0,2], [1,2], [2,2], [2,1], [2,0]])
.filter(function (a) {return a.length === 8;});
//and a little bit of hoopla to have a nice set of sets of 4 coordinates.
//(Dizzy yet? Wait for the generalized, 3D, cube of any edge length version ;))
var squareQuads = res.map(function(ary) {
return ary.join().match(/\d\,\d/g)
.map(function(e) {
return [+e.split(',')[0], +e.split(',')[1]];
});
});
//Finally, the last bit
var howManyUnitSquares = 0;
squareQuads.map(function(quad) {
if (isUnitSquare(quad)) {
howManyUnitSquares++;
}
});
console.log(howManyUnitSquares);
//Cleaning up and putting those in-line stuff into a function
function howManySquares(r) { //r = [[x,y], [x,y], [x,y], [x,y], ......];
var res = powerset(r)
.filter(function (a) {return a.length === 8;});
var squareQuads = res.map(function(ary) {
return ary.join().match(/\d\,\d/g)
.map(function(e) {
return [+e.split(',')[0], +e.split(',')[1]];
});
});
var answer = 0;
squareQuads.map(function(quad) {
if (isUnitSquare(quad)) {
answer++;
}
});
return answer;
}
[-1,0],[0,-1],[1,0],[0,1]ein Quadrat?[-2,0],[0,-2],[2,0],[0,2]aber eine Kantenlänge von2. Quadrat?Antworten:
APL (Dyalog), 30
In den meisten Fällen sind Lesbarkeit und Zeichenanzahl proportional.
Beispielausgabe
Erklärung
4 Punkte bilden also genau dann ein Einheitsquadrat, wenn ihre relativen Positionen (1,1), (1,2), (2,1), (2,2)
{(2-/⍵)≡2-/,⍳2 2}sind. Dies ist eine Funktion, die 1 oder 0 zurückgibt (true / false) bei einer Menge von 4 Punkten als Eingabe, basierend darauf, ob sie sich in relativen Positionen befinden und in der Reihenfolge (1,1), (1,2), (2,1), (2,2) sortiert sind:⍳2 2Generiere eine 2 × 2 Matrix der Punkte (1,1), (1,2), (2,1), (2,2),Entwirre diese Matrix zu einem Array von Punkten.2-/Paarweise Subtraktion reduzieren: (1,1) - ( 1,2); (1,2) - (2,1); (2,1) - (2,2), was das Array [(0, -1), (- 1,1), (0, -1)] ergibt.(2-/⍵)Paarweise Subtraktion am Eingang reduzieren≡Überprüfen Sie, ob die beiden Arrays gleichDas Hauptprogramm
⎕nimmt Eingaben entgegen und wertet sie aus. Dinge wie(0 0)(0 1)(1 0)(1 1)Auswertungen zu einem verschachtelten Array (Entspricht[[0,0],[0,1],[1,0],[1,1]]in JS) Schließen Sie es⊂¨für jeden Punkt (¨) in einen Skalar ein (⊂) ([[[0,0]],[[0,1]],[[1,0]],[[1,1]]])∘.,⍨⍣2Verketten Sie sie für jedes Elementpaar des Arrays, um ein neues Array zu bilden. ([ [[0,0],[0,0]],[[0,0],[0,1]]...) Einmal wiederholen. Dies ergibt alle Sätze von 4 Punkten, die mit den angegebenen Punkten erstellt werden können. In einigen dieser Sätze würde derselbe Punkt mehrmals verwendet, dies wären jedoch keine Einheitsquadrate, sodass keine Tastenanschläge verschwendet werden müssen, um sie zu entfernen. (,Verkettet 2 Arrays,∘.bedeutet "mache das für jedes Elementpaar",⍨bedeutet "benutze den rechten Operanden sowohl als linken als auch als rechten Operanden" und⍣2bedeutet "mache das zweimal"),Da die vorherige Operation ein 4-dimensionales Array ergeben würde (beachten Sie, dass verschachtelte Arrays und mehrdimensionale Arrays in APL unterschiedliche Dinge sind), müssen wir es entwirren, um ein Array von Mengen (mit 4 Punkten) zu erhalten.¨Führen Sie für jeden Satz{...}die oben genannte Funktion aus. Das Ergebnis wäre ein Array von Nullen und Einsen, das angibt, ob die Menge ein Einheitsquadrat ist. Beachten Sie, dass Duplikate eliminiert werden, da die Funktion auch die Reihenfolge überprüft.+/Summieren Sie schließlich das resultierende Array, um die Anzahl zu erhalten.quelle
Mathematica 65 Zeichen
Tests
Erläuterung
Erzeugt alle Teilmengen von 4 Punkten und überprüft alle Zwischenpunktabstände. Die sortierten Zwischenpunktabstände für ein Einheitsquadrat sind: `{1, 1, 1, 1, √2, √2}.
Lengthzählt dann die Anzahl der Einheitsquadrate.quelle
g?f=Count[#-#[[1]]&/@(Sort/@#~Subsets~{4}.{1,I}),{0,I,1,1+I}]&Ruby,
164161153147 ZeichenEs ist tatsächlich sehr gut lesbar, mit Ausnahme des Teils, der testet, ob es sich um ein Einheitsquadrat handelt oder nicht.
Wahrscheinlich sind viele Verbesserungen möglich, um sie jetzt zu finden.
Proben (alle funktionieren):
Ich kann vielleicht einen Trick finden
transpose, aber ich habe es eine Weile versucht und kann es nicht. Folgendes macht es:quelle
Python, 61 Zeichen
Stichprobe:
quelle
Mathematica, 56 Zeichen
quelle