20
\$\begingroup\$

Most people would cut circular pizzas into circular sectors to divide them up evenly, but it's also possible to divide them evenly by cutting them vertically like so, where each piece has the same area (assume the pizza has no crust):

Challenge

Your task is to make a program or function that takes a positive integer \$n\$ where \$2 \le n \le 100\$ that represents how many vertical slices a circular pizza with a radius of \$100\$ will be cut into as input and outputs the horizontal distance from the center of each cut (which will make each slice have the same area) from left to right (or right to left, since the cuts are symmetrical), rounded to the nearest integer.

Note that this will probably require more than just a simple formula.

Rules

  • Input and output can be in any convenient format.
  • This is , so the shortest code in bytes in each language wins.

Test cases

Input Output
2 [0]
3 [26, 26]
4 [40, 0, 40]
5 [49, 16, 16, 49]
6 [55, 26, 0, 26, 55]
7 [60, 34, 11, 11, 34, 60]
8 [63, 40, 20, 0, 20, 40, 63]
9 [66, 45, 26, 9, 9, 26, 45, 66]
10 [69, 49, 32, 16, 0, 16, 32, 49, 69]
50 [90, 83, 78, 73, 69, 64, 60, 57, 53, 49, 46, 42, 39, 35, 32, 29, 25, 22, 19, 16, 13, 9, 6, 3, 0, 3, 6, 9, 13, 16, 19, 22, 25, 29, 32, 35, 39, 42, 46, 49, 53, 57, 60, 64, 69, 73, 78, 83, 90]
82 [92, 88, 84, 81, 78, 75, 72, 69, 67, 64, 62, 59, 57, 55, 52, 50, 48, 46, 44, 41, 39, 37, 35, 33, 31, 29, 27, 25, 23, 21, 19, 17, 15, 13, 12, 10, 8, 6, 4, 2, 0, 2, 4, 6, 8, 10, 12, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 44, 46, 48, 50, 52, 55, 57, 59, 62, 64, 67, 69, 72, 75, 78, 81, 84, 88, 92]
97 [93, 89, 86, 83, 80, 77, 75, 73, 70, 68, 66, 64, 62, 60, 58, 56, 54, 52, 50, 48, 46, 44, 43, 41, 39, 37, 36, 34, 32, 30, 29, 27, 25, 24, 22, 20, 19, 17, 15, 14, 12, 11, 9, 7, 6, 4, 2, 1, 1, 2, 4, 6, 7, 9, 11, 12, 14, 15, 17, 19, 20, 22, 24, 25, 27, 29, 30, 32, 34, 36, 37, 39, 41, 43, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 73, 75, 77, 80, 83, 86, 89, 93]
100 [93, 90, 86, 83, 81, 78, 76, 73, 71, 69, 67, 64, 62, 60, 59, 57, 55, 53, 51, 49, 47, 46, 44, 42, 40, 39, 37, 35, 34, 32, 30, 29, 27, 25, 24, 22, 21, 19, 17, 16, 14, 13, 11, 9, 8, 6, 5, 3, 2, 0, 2, 3, 5, 6, 8, 9, 11, 13, 14, 16, 17, 19, 21, 22, 24, 25, 27, 29, 30, 32, 34, 35, 37, 39, 40, 42, 44, 46, 47, 49, 51, 53, 55, 57, 59, 60, 62, 64, 67, 69, 71, 73, 76, 78, 81, 83, 86, 90, 93]
\$\endgroup\$
12
  • 3
    \$\begingroup\$ There is no direct formula for these. The values for an input of 4 are known from the Quarter-Tank Problem which can be looked up on e.g. Wolfram MathWorld. \$\endgroup\$ Commented Aug 11, 2023 at 23:31
  • 5
    \$\begingroup\$ It seems though that the integer making a slice area closest to the desired area isn't necessary the same as the true real value rounded to the nearest integer. If there's any inputs where this distinction matters, it would be good to have test cases for them. \$\endgroup\$ Commented Aug 12, 2023 at 7:35
  • 1
    \$\begingroup\$ Never mind, it looks like there are a few cases where that happens. I'll add those as test cases. \$\endgroup\$ Commented Aug 12, 2023 at 12:08
  • 3
    \$\begingroup\$ Another issue is that rounding to the nearest integer is not a consistent measure of precision, since it requires much more precise estimates for values that are close to n + 0.5 for an integer n. Allowing for off-by-one errors is much closer to the more intuitive "estimate must be within 1 of the true value" \$\endgroup\$ Commented Aug 14, 2023 at 7:06
  • 1
    \$\begingroup\$ Just solve for (0-indexed) array \$a\$ with length \$n\$ where $$\int_{0}^{a_0}\sqrt{10000-x^2}dx = \int_{a_0}^{a_1}\sqrt{10000-x^2}dx = ... = \int_{a_{n-1}}^{100}\sqrt{10000-x^2}dx$$ and the solution shall follow. Oh, and in case it helps, the indefinite integral of \$\sqrt{10000-x^2}\$ is $$\dfrac{x\sqrt{10000-x^2}}{2}+5000\arcsin\left(\dfrac{x}{100}\right)$$ \$\endgroup\$ Commented Aug 15, 2023 at 16:03

9 Answers 9

6
\$\begingroup\$

R, 74 bytes (partial, probabilistic solution)

A bit of a silly Monte Carlo solution based on the fact that the histogram of eigenvalues of an \$N \times N\$ symmetric matrix with Gaussian entries converges to a semicircle with base \$[-2\sqrt{N}, 2\sqrt{N}]\$ as \$N \rightarrow \infty\$.

Taking \$N = 50^2\$, this is the semicircle with base \$[-100, 100]\$. By a result known as eigenvalue rigidity, the eigenvalue quantiles are all within \$\sim 50/N\$ of the corresponding quantiles of the semicircle.

Hence, we solve this problem by computing the eigenvalues of a \$50^2 \times 50^2\$ matrix with Gaussian entries and finding the quantiles from \$1/n\$ to \$(n-1)/n\$ of the sample:

\(n)round(abs(quantile(eigen(matrix(rnorm(50^4),50^2),T)[[1]],1:(n-1)/n)))

This is obviously not an exact solution, and when a true value is close to the form \$k + 0.5\$ for integer \$k\$, the estimate can be off the true rounded value by \$\pm 1\$.

It also takes a long time to find the eigenvalues of a \$ 50^2 \times 50^2\$ matrix, so in the demonstration I can only run two test cases before timing out.

Attempt This Online!

\$\endgroup\$
2
  • \$\begingroup\$ You have a wrong link for the R in the header :P \$\endgroup\$ Commented Aug 14, 2023 at 16:00
  • \$\begingroup\$ you can use eigen(...)$va instead of eigen(...)[[1]] for -2 bytes. For testing purposes you can use eigen(...,T,T) to only calculate the eigenvalues, which should speed things up considerably. \$\endgroup\$ Commented Aug 15, 2023 at 0:35
5
\$\begingroup\$

JavaScript (V8), 87 bytes

Prints the results.

n=>{for(t=0,x=w=1e6;x--+w;t*n>15708e8&&print((x*x)**.5/1e4+.49|(t=0)))t+=(w*w-x*x)**.5}

Try it online!

NB: This gives the same results as the OP for all test cases. We may disagree for some other inputs, but I've no way of knowing.

Commented

n => {                // n = input
  for(                // loop:
    t = 0,            //   start with t = 0
    x = w = 1e6;      //   and x = w = 1000000
    x-- + w;          //   stop when x = -w (decrement x afterwards)
    t * n > 15708e8   //   if t * n > round(pi / 2 * w² / 10^8) * 10^8 ...
    &&                //
    print(            //   ... print floor(abs(x) * 100 / w + 0.49)
      (x * x) ** .5   //
      / 1e4 + .49     //
      | (t = 0)       //   and reset t to 0
    )                 //
  )                   //
    t +=              //   at each iteration, add to t:
      (w * w - x * x) //     sqrt(w² - x²)
      ** .5           //
}                     //
\$\endgroup\$
3
\$\begingroup\$

Python, 225 202 152 bytes

-23 bytes thanks to @solid.py

lambda n:[h(pi*abs(a/n-.5))//2for a in range(1,n)]
def h(a,p=0):
 while(d:=a-p*(r:=sqrt(1-p*p))-asin(p))>1E-9:p+=d/r/2
 return 200*p+1
from math import*

Attempt This Online!

Uses Newton's method to find the inverse of the formula \$ \int_0^h 2 \sqrt{1-h²} dh = h \sqrt{1-h²} + \sin^{-1}(h)\$ for the area of a slice of height h from the center in a circle of radius 1.

\$\endgroup\$
1
  • \$\begingroup\$ Python, 202 bytes \$\endgroup\$ Commented Aug 12, 2023 at 9:47
3
\$\begingroup\$

R, 84 83 bytes

\(n,r=2e8)for(x in -r:r)if((F=F+(r^2-x^2)^.5)>pi*2e16/n)F=!print(abs(round(x/2e6)))

Attempt This Online! (but it will time-out before completing), or Attempt a less-accurate version with only 4 million x-axis steps.

Straightforward loop-over-x-values approach, not as elegant as Damian Pavlyshyn's probabilistic approach in R, but produces a single defined output for any input n.

Calculates the area-so-far in 400 million x-axis steps across the pizza, outputting the rounded x-axis value each time it hits the intended slice-area, and resetting the area-so-far back to zero.
Setting the area-so-far back to zero, instead of subtracting the slice-area and keeping the remainder for the next slice, is rather inaccurate, and so necessitates the huge number of x-axis steps to match all the test-cases.
Subtracting the slice-area at each step would require ≈10,000x less steps to achieve the required accuracy, but costs 5 bytes more.

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

JavaScript (V8), 93 bytes

n=>{q=2;for(S=x=1;S;x-=1e-6)q<(S+=(1-x*x)**.5/Math.PI*2e-6*n)&&q++*print((x*x)**.5*100+.5|0)}

Try it online!

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

Charcoal, 69 bytes

Nθ≔XE⊗φ⁻⊕⊗ι⊗φ²ηUMηΣ⁻¹÷⁺ιηX⊗φ²≔ΣηζUMη↨…ηκ¹I↔÷⁻⁺⁴φ⌕AEΦηκ⁻÷×θιζ÷×θ§ηκζ¹χ

Try it online! Link is to verbose version of code. Explanation:

Nθ

Input the desired number of slices.

XE⊗φ⁻⊕⊗ι⊗φ²η

Generate a list of odd numbers from -1999 to 1999 and square them.

UMηΣ⁻¹÷⁺ιηX⊗φ²

For each square odd number, add all of the square odd numbers to it, and count how many are less than 4 million.

≔Σηζ

Get the total "area".

UMη↨…ηκ¹

Get the cumulative area at each potential slice point. Note that there are still 2000 points at this stage, with coordinates from -99.95 to 99.95 in steps of 0.1.

I↔÷⁻⁺⁴φ⌕AEΦηκ⁻÷×θιζ÷×θ§ηκζ¹χ

Find the slice points where the area increases to the next fraction of the total area and calculate the nearest integer slice points.

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

Perl 5, 95 bytes

sub{($n,$c,$s)=@_;map$-=.49+abs$_/100,grep$c<($s+=$n/15708*sqrt 1-$_**2/1e8)-1&&++$c,-1e4..1e4}

Try it online!

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

Python, 146 bytes

lambda n:[round(min(range(900),key=lambda d:abs(tau/n*k+sin(a:=2*acos(d/900))-a))/9)for k in[[i,n-i][i>n/2]for i in range(1,n)]]
from math import*

Attempt This Online!

\$\endgroup\$
1
  • \$\begingroup\$ [i,n-i][i>n/2] can be min(i,n-i). And it looks like you can save bytes by doing the transformation from i to k in the main comprehension: lambda n:[round(min(range(900),key=lambda d:abs(tau/n*min(i,n-i)+sin(a:=2*acos(d/900))-a))/9)for i in range(1,n)]. \$\endgroup\$ Commented Aug 14, 2023 at 7:52
0
\$\begingroup\$

Python, 126 125 bytes

from math import*
def f(q,m=0):
 for i in range(1,q):exec('m=sin(pi/q*i-pi/2-m*sqrt(1-m*m));'*99999);print(abs(round(m*100)))

Attempt This Online!

Uses an iterative approach to converge to the true answer. This version is extremely slow and will time out.


Python, 134 133 bytes

from math import*
def f(q,m=0):
 for i in range(1,q):
  for j in[0]*99999:m=sin(pi/q*i-pi/2-m*sqrt(1-m*m))
  print(abs(round(m*100)))

Attempt This Online!

This version will not time out.

\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.