Cuenta los polígonos cerrados

8

Entrada:

Una NxMcuadrícula o cadena de varias líneas (u otro formato de entrada razonable), que contiene solo ASCII imprimible (rango unicode [32,126]).

Salida:

La cantidad de polígonos cerrados del mismo carácter que se pueden encontrar, con dos reglas especiales:

  • Los espacios son comodines y se pueden usar (varias veces) para cualquier personaje
  • o, Oy 0se cuentan como polígonos cerrados

Reglas de desafío:

  • (Anti-) Las conexiones diagonales entre los mismos caracteres (o espacios) se incluyen para formar polígonos cerrados.
  • No puede repasar otros personajes (excepto los espacios comodín). (Es decir, en el primer caso de prueba / ejemplo a continuación, no se pueden formar dos triángulos con la A's' sobre el x.) Por lo tanto, todos los caracteres utilizados para un polígono cerrado deben estar conectados (horizontalmente, verticalmente y / o (anti)) diagonalmente )
  • Los polígonos son al menos tres caracteres (sin incluir los caracteres individuales o, O, 0).
  • Las líneas de caracteres adyacentes no son polígonos cerrados.
  • No se pueden usar los mismos caracteres para múltiples polígonos, excluyendo espacios comodín.
  • Espacios comodín no pueden ser contados como o, Oo 0.
  • Tres o más espacios por sí solos no pueden formar un polígono cerrado. Siempre debe tener al menos un carácter no espacial (y no o/ O/ 0).
  • La entrada puede estar en cualquier formato razonable. Puede ser una matriz de caracteres, una cadena de delimitador de nueva línea, una matriz de cadenas, una matriz de caracteres con ancho entero agregado, etc.
  • Las entradas siempre serán un rectángulo N o M (o un cuadrado), por lo que no hay formas de entrada extrañas
  • Dado que los mismos caracteres no se pueden usar más de una vez y queremos tener tantos polígonos cerrados, usar múltiples caracteres para formar dos (o más) polígonos cerrados en lugar de un polígono más grande es, por supuesto, el objetivo previsto en el conteo (que también es por qué los polígonos cerrados formados por o, Oo 0nunca serán contados, ya que ya son polígonos cerrados individualmente).
  • Las letras mayúsculas y minúsculas, por supuesto, se cuentan como caracteres individuales.

Reglas generales:

  • Este es el , por lo que la respuesta más corta en bytes gana.
    No permita que los lenguajes de code-golf lo desanimen a publicar respuestas con lenguajes que no sean codegolf. Trate de encontrar una respuesta lo más breve posible para 'cualquier' lenguaje de programación.
  • Las reglas estándar se aplican a su respuesta con las reglas de E / S predeterminadas , por lo que puede usar STDIN / STDOUT, funciones / método con los parámetros adecuados y programas completos de tipo retorno. Tu llamada.
  • Las lagunas predeterminadas están prohibidas.
  • Si es posible, agregue un enlace con una prueba para su código (es decir, TIO ).
  • Además, se recomienda agregar una explicación para su respuesta.

Ejemplos / Casos de prueba:

Entrada:

AAAw
AxA4
'AoQ

Salida: 2porque estos polígonos se pueden formar:
ingrese la descripción de la imagen aquí


Entrada:

1822uaslkoo
12*2sl ljoo
a* 0a91)j$*
()*#J9dddj*
*Q#ID dJj!"
*UJD SO&*93

Salida: 12porque estos polígonos se pueden formar:
ingrese la descripción de la imagen aquí

Tenga en cuenta que:
- El amarillo de abajo no es un polígono, porque los o's ya se cuentan como polígonos separados
- Los morados y marrones no están cerrados
- Los rojos, grises, verdes y azules claros usan uno o más -caracteres de espacio que ya se usaron para otros polígonos cerrados
ingrese la descripción de la imagen aquí


Entrada (las dimensiones son 2x4):

3  3
  2 

Salida: 3porque estos polígonos se pueden formar:
ingrese la descripción de la imagen aquí


Entrada:

AAAA
AAAA
AAxA

Salida: 3porque estos polígonos se pueden formar:
ingrese la descripción de la imagen aquí

Por supuesto, otros polígonos son posibles aquí, pero no más de 3. Aquí otro ejemplo válido con 3polígonos:
ingrese la descripción de la imagen aquí


Entrada:

0QoO

Salida: 3porque estos polígonos se pueden formar:
ingrese la descripción de la imagen aquí


Entrada:

W w
 Ww

Salida: 3porque estos polígonos se pueden formar:
ingrese la descripción de la imagen aquí

Tenga en cuenta que el espacio de la capa superior se usa para los tres polígonos. Aquí están los tres polígonos resaltados individualmente:
ingrese la descripción de la imagen aquí ingrese la descripción de la imagen aquí ingrese la descripción de la imagen aquí


Entrada:

W W
 WW

Salida: 3porque se pueden formar los mismos tres polígonos que en la prueba anterior. Entonces no, no es 2con estos dos polígonos:
ingrese la descripción de la imagen aquí


Entrada:

abcdQefg
hQiQjQQk
QlQmnopQ
QqrstQQu
QvQQQwxy
QQz0QQQQ

Salida: 3porque estos polígonos se pueden formar:
ingrese la descripción de la imagen aquí

Kevin Cruijssen
fuente
2
Yo quiero a +1esto, pero yo realmente no veo lo especial de la carcasa de los os, OS & 0s se suma al reto.
Shaggy
Parece que todos los polígonos de ejemplo son convexos. A menos que se excluyan los polígonos cóncavos, sugeriría agregar un caso de prueba que incluya uno.
Arnauld
1
@Arnauld Agregó un caso de prueba en la parte inferior. No estoy seguro de si es suficiente para lo que querías decir, ya que solo va hacia adentro una vez. La cuadrícula tiene que ser bastante grande para hacer un polígono cóncavo. Si tiene algún caso de prueba sugerido que debería agregar además, avíseme.
Kevin Cruijssen
@ Shaggy Tienes razón. Cuando hice el reto vi la forma de la o, O, 0siendo círculos como polígonos individuales, sino en una solución que no aporta mucho, excepto que el o, O, 0se debe evitar cuando se forman los polígonos más grandes, y la adición de un recuento para ellos. Sin embargo, es demasiado tarde para cambiarlo ahora.
Kevin Cruijssen

Respuestas:

4

Python 2 , 714 737 821 bytes

  • -23 bytes gracias a Kevin Cruijssen
M=input()
m=''.join(M)
def P(L):
 if len(L)<2:yield[L];return
 for p in P(L[1:]):
	for n,s in enumerate(p):yield p[:n]+[[L[0]]+s]+p[n+1:]
	yield[[L[0]]]+p
h,w,R,C=len(M),len(M[0]),0,[-1,0,1]
K=[(i,j)for i in range(h)for j in range(w)]
Z=[(i,j)for i,j in K if' '==M[i][j]]
from networkx import*
for l in set(m):
 G,S=[],[]
 if l in'oO0':R+=m.count(l);continue
 for I in K:
  i,j=I
  for p in C:
	for q in C:
	 X=x,y=i+p,j+q
	 if X in K and X!=I and set(M[i][j]+M[x][y])<=set(' '+l):G+=[(I,X)];S+=[I,X]
 B=0
 for L in P(list(set(S))):
  b=0
  for p in L:
	for i,j in p:
	 if' '!=M[i][j]: 
		try:find_cycle(from_edgelist([(I,X)for I,X in G if I in p+Z and X in p+Z]));b+=1
		except:1
		break
	if b>B:B=b
 R+=B
print R

Pruébalo en línea!

  1. Para cada letra A(excepto o, Oy 0) el código construye un gráfico que representa la adyacencia de las diferentes ocurrencias de letra Ay espacio en la matriz inicial dada. Luego, calcula el conjunto de ciclos semiseparados que cubren el gráfico al maximizar el número de ciclos (la separación se basa solo en la letra A, el mismo espacio se puede usar durante varios ciclos).

  2. El código pasa todas las pruebas.

  3. Entrada: la lista de líneas de la matriz.

  4. Más explicaciones y golf próximamente.
mdahmoune
fuente
1
714 bytes mediante el uso de una combinación de pestañas y espacios como sangrías, en lugar de solo espacios.
Kevin Cruijssen