13
\$\begingroup\$

I have a piece of paper whose shape is a regular n-gon with side length 1. Then I fold it through some of its diagonals. What is the area of the shape formed by the (former) edges of the regular polygon?

Illustration

Suppose n = 8, i.e. an octagon-shaped paper. Let's name the vertices from A to H (left picture). Then I fold the paper along the two diagonals BE and FH (right picture). Mathematically, folding BE means to reflect the vertices C and D with respect to the line BE to obtain C' and D'. Your task is to calculate the area of the shaded octagon on the right picture.

Input

The number of sides n and a list representation of the folds l. Each element of l represents either a fold or an intact side of the polygon. If it is a fold, its value is the number of sides moved by the fold (e.g. 3 for the BE fold above, 2 for FH). Otherwise, the value is 1 (e.g. for the sides AB, EF, AH).

For the example above, the input will be 8, [1, 3, 1, 2, 1] if we count from the vertex A, counter-clockwise. If we count clockwise from E instead, the input will be 8, [3, 1, 1, 2, 1]; the expected answer is the same.

Note that sum(l) == n. Also, l == [1] * n (1 repeated n times) case is just the regular polygon untouched, which is a valid input.

The resulting polygon is guaranteed to be simple (it does not intersect or touch itself). For n=3 or n=4, this means that the only valid input is the polygon folded zero times. For n=6, l=[1, 2, 2, 1] or l=[1, 2, 1, 2] is invalid because the two folds will cause two folded vertices to meet at the center of the hexagon.

Output

The area of the n-sided polygon created by the given folds. The result must be within 1e-6 absolute/relative error from the expected result.

Scoring & winning criterion

Standard rules apply. Shortest code in bytes wins.

Test cases

n l => answer
---------------
4 [1, 1, 1, 1]    => 1.000000
5 [1, 1, 1, 1, 1] => 1.720477
5 [2, 1, 1, 1]    => 0.769421
6 [1, 2, 1, 1, 1] => 1.732051
7 [1, 2, 1, 2, 1] => 2.070249
8 [1, 3, 1, 2, 1] => 1.707107

The picture below shows the first five test cases.

A reference implementation in Python.

\$\endgroup\$

10 Answers 10

8
\$\begingroup\$

Ruby, 79 .. 66 65 bytes

->n,f{(f*2+[w=-1]*n).sum{|z|(w**z*=b=2r/n).imag/(1-w**b).real}/4}

Try it online!

Loosely based on the reference implementation: Original image

  • The area of the original polygon (ABCDEFGH) is a
  • If we cut instead of folding, we get a new convex polygon (ABEFH), we call the area of this polygon b
  • The difference between a and b is the area of the polygons we cut away (BCDE and FGH), let's call it c
  • The area of the folded polygon is b-c or a-2c (we have to remove BCDE and FGH twice from the original polygon). This equals to 2b-a
  • Both a and b can be represented as the sum of triangles (formed by 2 radiuses of the enclosing circle and one side of the polygon). Yes, we have a formula for calculating a, but if we define an intermediate function g it's easier to use it for both a and b
  • The area of a triangle is r*r*sin(2lπ/n) where l is the number of vertices in a fold and n is the total number of vertices, and r is the radius (which is 1/sin(π/n))
  • a is the sum of n triangles with l=1
  • since g(-x)=-g(x), we don't need to split the sum in 2 parts, we can sum over a larger array (that is twice f plus [-1] repeated n times), the intermediate function can become a block.
  • sin(x)^2 becomes (1-cos(2x))/2
  • sin(2π/x) and cos(2π/x) are imaginary and real part of the xth root of -1.
\$\endgroup\$
8
\$\begingroup\$

Wolfram Language (Mathematica), 37 36 bytes

Tr[Csc[i=Pi/#2]^2Sin[2i#]-Cot@i#]/4&

Try it online!

Takes input in the order l, n.

Uses the same approach as in the reference and many other implementations.

Mathematica's trigonometric and arithmetic functions will automatically vectorize, and Tr returns the sum of the elements of a one-dimensional list.

\$\csc\$ and \$\cot\$ are relatively uncommon; \$\csc x=\frac1{\sin x}\$, and \$\cot x=\frac1{\tan x}\$.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Nice solution. Do you mind adding an explanation? \$\endgroup\$
    – Jonah
    Nov 13, 2019 at 13:47
  • \$\begingroup\$ @Jonah it turned out to be the same as the reference implementation, but I'll add a little in. \$\endgroup\$
    – att
    Nov 14, 2019 at 5:18
6
\$\begingroup\$

JavaScript (ES7),  87 83 82 79  72 bytes

Saved 2 bytes thanks to @Shaggy
Saved 7 bytes thanks to @GB's insight

Takes input as (n)(list). Derived from the reference implementation.

with(Math)f=n=>a=>a.map(v=>n+=sin(2*v*T)/sin(T)**2,n/=-tan(T=PI/n))&&n/4

Try it online!

Given the number of sides \$n\$ and the folding values \$F_1\$ to \$F_m\$, this computes:

$$A=\frac{1}{4}\left(-\frac{n}{\tan(\theta)}+\sum_{i=1}^{m}\frac{\sin(2\theta F_i)}{\sin(\theta)^2}\right)$$

with \$\theta=\dfrac{\pi}{n}\$

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 80 bytes \$\endgroup\$
    – Shaggy
    Nov 13, 2019 at 11:33
  • 2
    \$\begingroup\$ You can take the 2Fi/t out of the sum. t is a constant and the sum of Fi is n. \$\endgroup\$
    – G B
    Nov 13, 2019 at 17:26
2
\$\begingroup\$

Java 8, 123 114 112 103 bytes

a->n->{double t=Math.PI/n,T=Math.sin(t);n/=-Math.tan(t);for(int v:a)n+=Math.sin(2*v*t)/T/T;return n/4;}

Port of the Python reference implementation.
-11 bytes by porting @Arnauld's JavaScript answer.
-9 bytes thanks to @G.B's insight.

Try it online.

\$\endgroup\$
0
2
+150
\$\begingroup\$

APL (Dyalog Unicode), 41 35 bytes

{4÷⍨(+/(1○2×⍵×t)÷2*⍨1○t)-⍺÷3○t←○÷⍺}

Try it online!

Uses Arnauld's expression for calculating the area.

-6 bytes from ovs. (removing inner dfn)

Explanation

{4÷⍨(+/(1○2×⍵×t)÷2*⍨1○t)-⍺÷3○t←○÷⍺} ⍺ → n, ⍵ → l
                             t←○÷⍺  assign t to Π/n (○÷n = (○1)÷n)
    (                  )            apply the following to each element of l:
       (1○2×⍵×t)                       sin(2×element×t)
                ÷                      divided by
                 2*⍨1○t                sin(t)²
    (+/                             sum the results
                        -           minus:
                         ⍺          n
                          ÷         divided by
                           3○t      tan(t)
 4÷⍨                                divide that whole expression by 4  
\$\endgroup\$
0
1
\$\begingroup\$

Python 3, 81 79 bytes

lambda n,f,a=-1:sum([(a**(2/n*r)).imag/(1-a**(2/n)).real for r in f*2+[a]*n])/4

Try it online!

A Python port of my Ruby solution.

\$\endgroup\$
1
\$\begingroup\$

R, 60 57 bytes

-2 and -1 thanks to Nick Kennedy and CriminallyVulgar!

function(n,l,t=pi/n)(sum(sin(2*t*l)/sin(t)^2)-n/tan(t))/4

Try it online!

\$\endgroup\$
2
1
\$\begingroup\$

05AB1E, 36 31 30 25 23 bytes

·žqI/©*®šÅ½ćn/OI®Å¼/-4/

Folds-list as first input, sides-integer as second input.

Port of my Java answer.
-5 bytes by porting @Arnauld's JavaScript answer.
-1 byte thanks to @Grimy.
-5 bytes thanks to @G.B's insight.

Try it online or verify all test cases.

Explanation:

·               # Double each value in the (implicit) input-list
 žq             # Push PI
   I/           # Divide it by the input-integer
     ©          # Store this PI/input in variable `®` (without popping)
      *         # Multiply this to each doubled value in the list
       ®š       # Prepend `®` (PI/input) to this list
         Ž     # Take the sine of each value in the list
           ć    # Pop and push remainder-list and first item separated to the stack
            n   # Square this first item: sin(PI/input)²
             /  # Divide each value in the list by this
              O # And then sum all values together 
  ®Å¼           # Get the tangent of `®`: tan(PI/input)
 I   /          # And divide the input-integer by this
      -         # Subtract it from the sum
       4/       # And divide it by 4
                # (after which the result is output implicitly)
\$\endgroup\$
3
  • \$\begingroup\$ -1 by sharing the · \$\endgroup\$
    – Grimmy
    Nov 13, 2019 at 13:43
  • \$\begingroup\$ As noticed by GB, my formula was overcomplicated. You should be able to save a couple of bytes in your ports as well. \$\endgroup\$
    – Arnauld
    Nov 13, 2019 at 17:43
  • \$\begingroup\$ @Arnauld Thanks for letting me know. -9 in my Java port and -5 in 05AB1E :) \$\endgroup\$ Nov 13, 2019 at 21:21
0
\$\begingroup\$

Icon, 108 bytes

procedure g(s,f)
r:=.5/sin(t:=&pi/s)
p:=s*(c:=.25/tan(t))
p-:=(c*(i:=!f)-r*r*sin(2*i*t)/2)*2&\z
return p
end

Try it online!

An Icon port of the Python reference implementation.

\$\endgroup\$
0
\$\begingroup\$

Jelly, 23 bytes

×ḤÆS÷ÆS²¥_ÆTİ×ɗS
ØP÷ç÷4

Try it online!

A full program that takes the number of sides as its first argument and the list of folds as its right. Returns/prints the area of the folded polygon.

Loosely based on the formula in @Arnauld’s answer.

\$\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.