Dada una lista de coordenadas 2d (x, y), determine cuántas unidades cuadradas (longitud del borde 1 unidad) pueden formarse utilizando las coordenadas.
- La entrada será una matriz de 0 o más pares de coordenadas:
por ejemplo, en JavaScript:numofsq([[0,0], [1,0], [1,1], [0,1]]) - No hay coordenadas duplicadas en la entrada
- El orden de entrada será aleatorio (coordenadas aleatorias 2d).
- Forma de coordenadas: [coordenada x, coordenada y] (duh)
- Orden de coordenadas: [0,0], [1,0], [1,1], [0,1] y [0,0], [0,1], [1,1], [1,0 ] denota la misma unidad cuadrada (se contará solo una vez)
- Las coordenadas pueden ser enteros negativos o positivos (duh)
- La función devolverá solo el número de cuadrados unitarios posibles, 0 o más.
Casos de prueba:
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
Alerta de spoiler: solución de aquí en adelante [JS]
Enfoque de fuerza bruta no golfizado, rápido y sucio (incluido para proporcionar algunas instrucciones).
//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]un cuadrado?[-2,0],[0,-2],[2,0],[0,2]tiene una longitud de borde de2. ¿Cuadrado?Respuestas:
APL (Dyalog), 30
Bueno, en la mayoría de los casos, la legibilidad y el recuento de caracteres es proporcional.
Salida de muestra
Explicación
Entonces, 4 puntos forman un cuadrado unitario si y solo si sus posiciones relativas son (1,1), (1,2), (2,1), (2,2)
{(2-/⍵)≡2-/,⍳2 2}es una función que devuelve 1 o 0 (verdadero / falso) dado un conjunto de 4 puntos como entrada en función de si están en posiciones relativas y ordenados en el orden (1,1), (1,2), (2,1), (2,2):⍳2 2generar un 2 × 2 matriz de los puntos (1,1), (1,2), (2,1), (2,2),Desentrañar esa matriz en una matriz de puntos2-/La resta por pares se reduce: (1,1) - ( 1,2); (1,2) - (2,1); (2,1) - (2,2), que proporciona la matriz [(0, -1), (- 1,1), (0, -1)](2-/⍵)La resta por pares se reduce en la entrada≡Compruebe si los dos matrices igualesEl programa principal
⎕toma datos y los evalúa. Cosas como se(0 0)(0 1)(1 0)(1 1)evalúa en una matriz anidada (Equivalente de[[0,0],[0,1],[1,0],[1,1]]en JS)⊂¨Para cada punto (¨), encerrarlo en un escalar (⊂) ([[[0,0]],[[0,1]],[[1,0]],[[1,1]]])∘.,⍨⍣2Para cada par de elementos de la matriz, concatenarlos para formar una nueva matriz. ([ [[0,0],[0,0]],[[0,0],[0,1]]...) Repita una vez. Esto proporciona todos los conjuntos de 4 puntos que se pueden hacer usando los puntos dados. En algunos de estos conjuntos, el mismo punto se usaría varias veces, pero no serían cuadrados unitarios, por lo que no es necesario desperdiciar pulsaciones de teclas para eliminarlos. (,concatena 2 matrices,∘.significa "hacer eso por cada par de elementos",⍨significa "usar el operando derecho como operandos izquierdo y derecho", y⍣2significa "hacer esto dos veces"),Como la operación anterior daría una matriz de 4 dimensiones (tenga en cuenta que las matrices anidadas y las matrices multidimensionales son cosas diferentes en APL), tenemos que desentrañarlo para obtener una matriz de conjuntos (de 4 puntos).¨Para cada uno de los conjuntos,{...}ejecute la función mencionada anteriormente. El resultado sería una matriz de 0s y 1s que indica si el conjunto es una unidad cuadrada. Tenga en cuenta que debido a que la función también verifica el orden, se eliminan los duplicados.+/Finalmente, suma la matriz resultante para obtener el recuento.fuente
Mathematica 65 caracteres
Pruebas
Explicación
Genera todos los subconjuntos de 4 puntos y verifica todas las distancias entre puntos. Las distancias entre puntos ordenadas para un cuadrado unitario son: `{1, 1, 1, 1, √2, √2}.
Lengthluego cuenta el número de cuadrados unitarios.fuente
g?f=Count[#-#[[1]]&/@(Sort/@#~Subsets~{4}.{1,I}),{0,I,1,1+I}]&Rubí,
164161153147 caracteresEn realidad, es muy legible, excepto por la parte que prueba si es una unidad cuadrada o no.
Probablemente muchas mejoras posibles, intentando encontrarlas ahora.
Muestras (todas ellas funcionan):
Es posible que pueda encontrar un truco
transpose, pero lo he estado intentando durante un tiempo y no puedo. Esto es lo que hace:fuente
Python, 61 caracteres
Muestra:
fuente
Mathematica, 56 caracteres
fuente