Antecedentes

Quiero construir una cerca. Para eso, he recogido un montón de postes y los he pegado al suelo. También he reunido muchas tablas que clavaré a los postes para hacer la cerca real. Tiendo a dejarme llevar cuando construyo cosas, y lo más probable es que siga clavando las tablas en los postes hasta que no haya más lugar para colocarlas. Quiero que enumeres las posibles vallas con las que puedo terminar.

Entrada

Su entrada es una lista de coordenadas enteras bidimensionales que representan las posiciones de los polos, en cualquier formato conveniente. Puede suponer que no contiene duplicados, pero no puede suponer nada sobre su orden.

Los tableros están representados por líneas rectas entre los polos, y por simplicidad, solo consideramos tableros horizontales y verticales. Una tabla puede unir dos postes si no hay otros postes o tablas entre ellos, lo que significa que las tablas no pueden cruzarse entre sí. Una disposición de postes y tableros es máxima si no se le pueden agregar nuevos tableros (de manera equivalente, hay un poste o un tablero entre dos postes alineados horizontal o verticalmente).

Salida

Su salida es el número de arreglos máximos que se pueden construir utilizando los polos.

Ejemplo

Considere la lista de entrada

[(3,0),(1,1),(0,2),(-1,1),(-2,0),(-1,-1),(0,-2),(1,-1)]

Visto desde arriba, la disposición correspondiente de los postes se ve así:

  o
 o o
o    o
 o o
  o

Hay exactamente tres arreglos máximos que se pueden construir utilizando estos polos:

  o        o        o
 o-o      o|o      o-o
o----o   o||| o   o| | o
 o-o      o|o      o-o
  o        o        o

Por lo tanto, la salida correcta es 3.

Reglas

Puede escribir una función o un programa completo. El conteo de bytes más bajo gana, y las lagunas estándar no se permiten.

Casos de prueba

[] -> 1
[(0,0),(1,1),(2,2)] -> 1
[(0,0),(1,0),(2,0)] -> 1
[(0,0),(0,1),(1,0),(1,1)] -> 1
[(1,0),(0,1),(-1,0),(0,-1)] -> 2
[(3,0),(1,1),(0,2),(-1,1),(-2,0),(-1,-1),(0,-2),(1,-1)] -> 3
[(0,0),(4,0),(1,1),(1,-2),(3,1),(3,-2),(2,-1),(4,-1)] -> 3
[(0,0),(4,0),(1,1),(1,-2),(3,1),(3,-2),(2,-1),(4,-1),(0,-1)] -> 4
[(0,0),(4,0),(1,1),(1,-2),(3,1),(3,-2),(2,-1),(0,-1),(2,2)] -> 5
[(0,0),(4,0),(1,1),(1,-2),(3,1),(3,-2),(2,-1),(4,-1),(0,-1),(2,2)] -> 8

Mathematica, 301 bytes

(t~SetAttributes~Orderless;u=Subsets;c=Complement;l=Select;f=FreeQ;Count[s=List@@@l[t@@@u[Sort@l[Sort/@#~u~{2},!f[#-#2&@@#,0]&]//.{a___,{x_,y_},{x_,z_},b___,{y_,z_},c___}:>{a,{x,y},b,{y,z},c}],f[#,t[{{a_,b_},{a_,c_}},{{d_,e_},{f_,e_}},___]/;d<a<f&&b<e<c]&],l_/;f[s,k_List/;k~c~l!={}&&l~c~k=={},{1}]])&

Esta es una función sin nombre que toma las coordenadas como anidadas Listy devuelve un entero. Es decir, puede darle un nombre y llamarlo, o simplemente agregar

@ {{3, 0}, {1, 1}, {0, 2}, {-1, 1}, {-2, 0}, {-1, -1}, {0, -2}, {1, -1}}

Con sangría:

(
  t~SetAttributes~Orderless;
  u = Subsets;
  c = Complement;
  l = Select;
  f = FreeQ;
  Count[
    s = List @@@ l[
      t @@@ u[
        Sort @ l[
          Sort /@ #~u~{2}, 
          !f[# - #2 & @@ #, 0] &
        ] //. {a___, {x_, y_}, {x_, z_}, b___, {y_, z_}, c___} :> 
              {a, {x, y}, b, {y, z}, c}
      ],
      f[
        #,
        t[{{a_, b_}, {a_, c_}}, {{d_, e_}, {f_, e_}}, ___] 
          /; d < a < f && b < e < c
      ] &
    ], 
    l_ /; f[
      s, 
      k_List /; k~c~l != {} && l~c~k == {}, 
      {1}
    ]
  ]
) &

Ni siquiera puedo comenzar a expresar lo ingenua que es esta implementación ... definitivamente no podría ser más fuerza bruta ...

• Obtenga todos los pares de polos (sin ordenar).
• Ordena cada par y todos los pares en un orden canónico.
• Deseche los pares que no comparten una coordenada (es decir, que no son conectables por una línea ortogonal).
• Los pares de descarte se pueden formar a partir de dos pares más cortos (de modo que o--o--osolo se obtienen dos cercas en lugar de tres).
• Obtenga todos los subconjuntos de esos pares, es decir, todas las combinaciones posibles de cercas.
• Filtra las combinaciones que tienen cercas que se cruzan entre sí.
• Cuente el número de conjuntos de cercas resultantes para los que no se puede encontrar un superconjunto estricto en la lista.

Sorprendentemente, resuelve todos los casos de prueba prácticamente de inmediato.

Un buen truco que descubrí para esto es el uso de Orderlessreducir el número de patrones que tengo que hacer coincidir. Esencialmente, cuando quiero deshacerme de conjuntos de cercas con cercas cruzadas, necesito encontrar un par de cercas vertical y horizontal y verificar la condición en ellas. Pero no sé en qué orden aparecerán. Dado que los patrones de lista normalmente dependen del orden, esto generaría dos patrones realmente largos. Entonces, en su lugar, reemplazo con la lista circundante con una función tcon t @@@, que no está definida, por lo que se mantiene como está. Pero esa función es Orderless, así que puedo verificar un solo orden en el patrón, y Mathematica lo verificará contra todas las permutaciones. Después, puse las listas de nuevo en su lugar con List @@@.

Desearía que hubiera un incorporado que sea a) Orderless, b) no Listable yc) no definido para 0 argumentos o argumentos de lista. Entonces podría reemplazar tpor eso. Pero no parece haber tal operador.

Haskell, 318 bytes

import Data.List
s=subsequences
k[(_,a,b),(_,c,d)]|a==c=f(\w->(1,a,w))b d|1<2=f(\w->(2,w,b))a c
f t u v=[t x|x<-[min u v+1..max u v-1]]
q l=nub[x|x<-map(k=<<)$s[a|a@[(_,n,m),(_,o,p)]<-s l,n==o||m==p],x++l==nubBy(\(_,a,b)(_,c,d)->a==c&&b==d)(x++l)]
m=q.map(\(a,b)->(0,a,b))
p l=sum[1|x<-m l,all(\y->y==x||x\\y/=[])$m l]

Uso: p [(1,0),(0,1),(-1,0),(0,-1)]. Salida:2

Cómo funciona:

• cree todas las sublistas de la lista de entrada y mantenga aquellas con dos elementos y con coordenadas iguales x o iguales y. Esta es una lista de todos los pares de postes donde se puede construir una cerca.
• crear todas las sublistas de ella
• agregar tableros para cada lista
• eliminar listas donde una coordenada xy aparece dos veces (tableros y polos)
• eliminar listas duplicadas (solo tableros) para manejar múltiples listas vacías, debido a polos directamente adyacentes (p. ej. (1,0) y (1,1))
• mantener aquellos que no son una sublista estricta de otra lista
• contar las listas restantes