Golf: ¿Cuántos cuadrados de unidades de longitud en una lista de coordenadas 2d?

8

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;
}

fuente
1
es [-1,0],[0,-1],[1,0],[0,1]un cuadrado?
Johannes Kuhn
@JohannesKuhn No, sus longitudes de borde no son la unidad, sino sqrt (2), por lo que no son cuadrados unitarios.
Pero [-2,0],[0,-2],[2,0],[0,2]tiene una longitud de borde de 2. ¿Cuadrado?
Johannes Kuhn
2
@JohannesKuhn Square? Si. UNIDAD Square? No.

Respuestas:

5

APL (Dyalog), 30

+/{(2-/⍵)≡2-/,⍳2 2}¨,∘.,⍨⍣2⊂¨⎕

Bueno, en la mayoría de los casos, la legibilidad y el recuento de caracteres es proporcional.


Salida de muestra

⎕:
      (0 0)(0 1)(1 0)(1 1)(0 2)(1 2)(2 2)(2 1)(2 0)
4

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 puntos
2-/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 iguales

El 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.

TwiNight
fuente
3

Mathematica 65 caracteres

f@d_ := Length@Select[Subsets[d, {4}], Sort[g@#] == {1, 1, 1, 1, √2, √2} &]

Pruebas

f[{{0, 0}, {0, 1}, {1, 1}, {1, 0}, {0, 2}, {1, 2}}]

2

f[{{0, 0}, {0, 1}, {1, 1}, {1, 0}, {0, 2}, {1, 2}, {2, 2}, {2, 1}}]

3

f[{{0, 0}, {0, 1}, {1, 1}, {1, 0}, {0, 2}, {1, 2}, {2, 2}, {2, 1}, {2,0}}]

4 4

f[{{0, 0}, {0, 1}, {1, 1}, {1, 0}, {0, 2}, {1, 2}, {2, 2}, {2, 1}, {2,0}, {9, 9}}]

4 4

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}.

Length luego cuenta el número de cuadrados unitarios.

DavidC
fuente
¿Cuál es la definición de g?
alephalpha
1
Aquí está mi solución más corta:f=Count[#-#[[1]]&/@(Sort/@#~Subsets~{4}.{1,I}),{0,I,1,1+I}]&
alephalpha
1

Rubí, 164 161 153 147 caracteres

f=->a{a.combination(4).map(&:sort).uniq.count{|x|[x[1][0]==l=x[0][0],x[3][0]==m=x[2][0],x[2][1]==n=x[0][1],x[3][1]==o=x[1][1],m-l==1,o-n==1].all?}}

En 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):

puts f[[[0,0], [0,1], [1,1], [1,0], [0,2], [1,2]]]                             #--> 2
puts f[[[0,0], [0,1], [1,1], [1,0], [0,2], [1,2], [2,2], [2,1]]]               #--> 3
puts f[[[0,0], [0,1], [1,1], [1,0], [0,2], [1,2], [2,2], [2,1], [2,0]]]        #--> 4
puts f[[[0,0], [0,1], [1,1], [1,0], [0,2], [1,2], [2,2], [2,1], [2,0], [9,9]]] #--> 4

Es posible que pueda encontrar un truco transpose, pero lo he estado intentando durante un tiempo y no puedo. Esto es lo que hace:

irb(main):001:0> a = [[5, 10], [5, 11], [6, 10], [6, 11]]
=> [[5, 10], [5, 11], [6, 10], [6, 11]]
irb(main):002:0> a.transpose
=> [[5, 5, 6, 6], [10, 11, 10, 11]]
Pomo de la puerta
fuente
De acuerdo con la parte legible: como alguien que nunca ha programado en Ruby, todavía puedo entender claramente los pasos. Lástima que JS no tenga combinatoria incorporada.
0

Python, 61 caracteres

f=lambda l:sum(1for x,y in l if{(x+1,y),(x,y+1),(x+1,y+1)}<l)

Muestra:

>>> f({(0,0), (0,1), (1,1), (1,0), (0,2), (1,2)})
2
>>> f({(0,0), (0,1), (1,1), (1,0), (0,2), (1,2), (2,2), (2,1)})
3
>>> f({(0,0), (0,1), (1,1), (1,0), (0,2), (1,2), (2,2), (2,1), (2,0)})
4
>>> f({(0,0), (0,1), (1,1), (1,0), (0,2), (1,2), (2,2), (2,1), (2,0), (9,9)})
4
Daniel Lubarov
fuente
0

Mathematica, 56 caracteres

f=Count[#-#[[1]]&/@Subsets[{}⋃#.{1,I},{4}],{0,I,1,1+I}]&
alephalpha
fuente