13
\$\begingroup\$

The difficulty with sharing pizza with friends is that it is hard to make sure that everyone gets the same amount of pepperoni on their slice. So, your task is to decide how to fairly slice a pizza so that everyone is happy.

Directions

Write a program that, given a list of the positions of pepperonis on a circular pizza and the number of slices to be made, outputs a list of the angles that the pizza should be cut at so that each slice has the same amount of pepperoni on it.

  • The pizza has only one topping: pepperoni.
  • Your friends don't care about the size of their slice, just that they are not cheated out of any pepperoni.
  • The pizza is a circle centered on the origin (0, 0) and with a radius of 1.
  • The pepperonis are circles that are centered wherever the input says they are centered and have a radius of 0.1
  • Take input as an integer that represents the number of slices to be made and a list of ordered-pairs that represent the positions of the pepperonis on a cartesian coordinate system. (In any reasonable format)
  • Output should be a list of angles given in radians that represents the positions of the "cuts" to the pizza (in the range 0 <= a < 2pi). (In any reasonable format) (Precision should be to at least +/- 1e-5.)
  • You can have partial pieces of a pepperoni on a slice (eg. If a pizza has one pepperoni on it and it needs to be shared by 10 people, cut the pizza ten times, all cuts slicing through the pepperoni. But make sure it's fair!)
  • A cut can (may have to) slice through multiple pepperonis.
  • Pepperonis may overlap.

Examples

Input:

8 people, pepperonis: (0.4, 0.2), (-0.3, 0.1), (-0.022, -0.5), (0.3, -0.32)

Possible valid output:

slices at:
0, 0.46365, 0.68916, 2.81984, 3.14159, 4.66842, 4.86957, 5.46554

Here is a visualisation of this example (everyone gets half a pepperoni):

enter image description here

More examples:

Input: 9 people, 1 pepperoni at: (0.03, 0.01)
Output: 0, 0.4065, 0.8222, 1.29988, 1.94749, 3.03869, 4.42503, 5.28428, 5.83985

enter image description here

Input: 5, (0.4, 0.3), (0.45, 0.43), (-0.5, -0.04)
Output: 0, 0.64751, 0.73928, 0.84206, 3.18997

enter image description here

Scoring

This is , so least number of bytes wins.

\$\endgroup\$
  • \$\begingroup\$ To what precision must submissions adhere to be considered valid? \$\endgroup\$ – Rainbolt Dec 19 '14 at 1:27
  • \$\begingroup\$ @Rainbolt I would say that 4 or 5 decimal places should be enough. What do you suggest? I should add it to the question. \$\endgroup\$ – kukac67 Dec 19 '14 at 1:28
  • \$\begingroup\$ I'm not sure that every problem is solvable. What if there are 7 slices and 3 pepperoni evenly spaced out? \$\endgroup\$ – Nathan Merrill Dec 19 '14 at 1:28
  • 1
    \$\begingroup\$ @NathanMerrill Then everyone would get 3/7 of a pepperoni. :) (Size of the slices doesn't matter.) \$\endgroup\$ – kukac67 Dec 19 '14 at 1:30
  • 1
    \$\begingroup\$ Pizza hat attempt failed. Ask an easier one next time. ;) \$\endgroup\$ – Ilmari Karonen Dec 19 '14 at 11:05
7
\$\begingroup\$

Mathematica, 221 bytes

f=(A=Pi.01Length@#2/#;l=m/.Solve[Norm[{a,b}-m{Cos@t,Sin@t}]==.1,m];k=(l/.{a->#,b->#2})&@@@#2;d=1.*^-5;For[Print[h=B=0];n=1,n<#,h+=d,(B+=If[Im@#<0,0,d(Max[#2,0]^2-Max[#,0]^2)/2])&@@@(k/.{t->h});If[B>A,n+=1;Print@h;B-=A]])&

Ungolfed:

f = (
   A = Pi .01 Length@#2/#;
   l = m /. Solve[Norm[{a, b} - m {Cos@t, Sin@t}] == .1, m];
   k = (l /. {a -> #, b -> #2}) & @@@ #2;
   d = 1.*^-5;
   For[Print[h = B = 0]; n = 1, n < #, h += d,
    (
      B += If[Im@# < 0, 0, d (Max[#2, 0]^2 - Max[#, 0]^2)/2]
    ) & @@@ (k /. {t -> h});
    If[B > A, n += 1; Print@h; B -= A]
   ]
) &

This defines a function which takes as parameters the number of slices and a list of pairs for the peperoni coordinates, like

f[8, {{0.4, 0.2}, {-0.3, 0.1}, {-0.022, -0.5}, {0.3, -0.32}}]

It will print the slices to the console as it traverses the pizza.

On most pizzas, this is fairly slow, because (to achieve the required precision) I'm integrating the peperoni area from 0 to 2π in steps of 1e-5. To get a slightly less precise result in a reasonable amount of time, you can change the 1.*^-5 at the end to 1.*^-3.

How it works

The idea is to sweep out the slices of pizza while integrating over the area of the peperoni pieces covered. Whenever that area hits the required amount of peperoni per person, we report the current angle and reset the area counter.

To obtain the peperoni area swept out, we intersect the line with the peperoni to give use the two distances from the origin, where the line intersects with the peperoni. Since a line extends to infinity in both directions, we need to clamp these distances to non-negative values. This solves two problems:

  • Counting intersections with each peperoni twice, once positive and once negative (which would actually yield to an overall area of 0).
  • Counting only wedges of peperoni pieces which include in the origin.

I'll include some diagrams later.

\$\endgroup\$
  • \$\begingroup\$ Yep. This was my plan of attack. At least I can more easily make examples now! :D \$\endgroup\$ – kukac67 Dec 19 '14 at 12:11
  • \$\begingroup\$ I noticed that your implementation sometimes outputs one extra angle that would create an extra slice with no pepperoni on it. (for example with input: [8, {{0.4, 0.2}, {-0.3, 0.1}, {-0.022, -0.5}, {0.3, -0.32}}]) \$\endgroup\$ – kukac67 Dec 21 '14 at 22:31
  • \$\begingroup\$ @kukac67 fixed. \$\endgroup\$ – Martin Ender Dec 23 '14 at 10:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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