12
\$\begingroup\$

Given a regular N-gon with all diagonals drawn, how many regions do the diagonals form?

For example, a regular triangle has exactly 1, a square has exactly 4, pentagon has exactly 11, and a hexagon has 24.

  • score is inversely proportional to number of bytes in solution
  • small fudge factors may be added to scores based on their runtime
  • the region surrounding the polygon does not count
\$\endgroup\$
1
  • 1
    \$\begingroup\$ So ... write a program that returns this \$\endgroup\$
    – mob
    Oct 12, 2012 at 22:45

3 Answers 3

14
\$\begingroup\$

Mathematica 118

Although there are well-defined routines for computing the number of regions in a regular n-gon with all the diagonals drawn, they are quite cumbersome. I thought it might be fun to take an image processing approach: if we draw the n-gon with it's diagonals, would it be possible to count the regions from the drawn image (more precisely, from the rasterized and binarized representation of the image as an array)?

The following produces and processes an actual image of a polygon and determines the number of regions from the rasterized image.

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}

This is what might be referred to as an engineer's solution. It gets the job done, but only within some limited conditions. (And it's slow: the above code took 4.24 s to run.) The above routine works correctly up to and including a 14-Complete graph, shown below. I found this surprising, given that some of 952 regions are very difficult to see, even when the image is displayed at 1200 by 1200 pixels.

The picture below is the image before being rasterized and binarized.

14-complete graph

\$\endgroup\$
1
  • \$\begingroup\$ +1 because lol "Just count the regions!" \$\endgroup\$ Nov 23, 2021 at 13:25
3
\$\begingroup\$

Excel, 341 bytes

Implements the formula given on the Woflram Mathworld link in @mob's comment.

=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 for some clarity:

=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 
\$\endgroup\$
2
+400
\$\begingroup\$

Haskell, 232 bytes

f n|t<-(.(0^).mod n).(*)=div(t(1176*n)12-t(3744*n)120+t(1536*n)18+t(42*n^2-5*n^3-40*n-48)2-t(2394*n)210+t(912*n)25-t(1728*n)30-t(36*n)4-t(2400*n)42+t(1240*n-212*n^2)6-t(9120*n)60-t(3744*n)84-t(2304*n)90+2*n^4-12*n^3+46*n^2-84*n)48+1

Try it online!

Uses the formula from OEIS user Chai Wah Wu.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.