Regiones de polígonos regulares

10

Dado un N-gon regular con todas las diagonales dibujadas, ¿cuántas regiones forman las diagonales?

Por ejemplo, un triángulo regular tiene exactamente 1, un cuadrado tiene exactamente 4, el pentágono tiene exactamente 11 y un hexágono tiene 24.

  • la puntuación es inversamente proporcional al número de bytes en la solución
  • Se pueden agregar pequeños factores de fudge a las puntuaciones en función de su tiempo de ejecución
  • la región que rodea el polígono no cuenta
Wug
fuente
1
Entonces ... escriba un programa que devuelva esto
mafia

Respuestas:

11

Mathematica 118

Aunque existen rutinas bien definidas para calcular el número de regiones en un n-gon regular con todas las diagonales dibujadas , son bastante engorrosas. Pensé que sería divertido adoptar un enfoque de procesamiento de imágenes : si dibujamos el n-gon con sus diagonales, ¿sería posible contar las regiones de la imagen dibujada (más precisamente, de la representación rasterizada y binarizada de la imagen como una matriz)?

Lo siguiente produce y procesa una imagen real de un polígono y determina el número de regiones de la imagen rasterizada.

Table[MorphologicalEulerNumber@Binarize@Rasterize@CompleteGraph[k, ImageSize->1200,EdgeStyle->Thickness[Large]],{k,3,14}]

{1, 3, 11, 24, 50, 80, 154, 220, 375, 444, 781, 952}

Esto es lo que podría denominarse la solución de un ingeniero. Hace el trabajo, pero solo dentro de algunas condiciones limitadas. (Y es lento: el código anterior tardó 4,24 s en ejecutarse). La rutina anterior funciona correctamente hasta e incluye un gráfico 14-Complete , que se muestra a continuación. Esto me pareció sorprendente, dado que algunas de las 952 regiones son muy difíciles de ver, incluso cuando la imagen se muestra a 1200 por 1200 píxeles.

La siguiente imagen es la imagen antes de ser rasterizada y binarizada.

Gráfico 14 completo

DavidC
fuente
3

Excel, 341 bytes

Implementa la fórmula dada en el enlace Woflram Mathworld en el comentario de @ mob.

=A1*(A1^3-6*A1^2+23*A1-42)/24+1+(MOD(A1,2)=0)*(A1*(42*A1-5*A1^2-40)/48-1)-(MOD(A1,4)=0)*3*A1/4+(MOD(A1,6)=0)*A1*(310-53*A1)/12+(MOD(A1,12)=0)*49/2*A1+(MOD(A1,18)=0)*32*A1+(MOD(A1,24)=0)*19*A1-(MOD(A1,30)=0)*36*A1-(MOD(A1,42)=0)*50*A1-(MOD(A1,60)=0)*190*A1-(MOD(A1,84)=0)*78*A1-(MOD(A1,90)=0)*48*A1-(MOD(A1,120)=0)*78*A1-(MOD(A1,210)=0)*48*A1

Ungolfed para algo de claridad:

=A1*(A1^3-6*A1^2+23*A1-42)/24+1
+(MOD(A1,2)=0)  *(A1*(42*A1-5*A1^2-40)/48-1)
-(MOD(A1,4)=0)  *3*A1/4
+(MOD(A1,6)=0)  *A1*(310-53*A1)/12
+(MOD(A1,12)=0) *49/2*A1
+(MOD(A1,18)=0) *32*A1
+(MOD(A1,24)=0) *19*A1
-(MOD(A1,30)=0) *36*A1
-(MOD(A1,42)=0) *50*A1
-(MOD(A1,60)=0) *190*A1
-(MOD(A1,84)=0) *78*A1
-(MOD(A1,90)=0) *48*A1
-(MOD(A1,120)=0)*78*A1
-(MOD(A1,210)=0)*48*A1 
Wernisch
fuente