next »

[JConk007]

Hey All,
I got this test from the Parade Magazine Section in my local paper. When I see the word Pizza It grabs my attention.

The problem is this.

What is the maximum number of pieces can you produce from a pizza (circle)  with 7 straight cuts all the way across pizza?

Size does Not Matter. Just amount of pieces that can be produced.

Hopefully I can post the link with the results Later today Good luck

There is a formula right November?
John

[November]

It's actually rather easy.  I can post the equation if you really want, but the solution is an iterative summation.  You just add the number of pieces from the previous cut to the index of the present cut.  So,

Cuts = Pieces
0 = 1
1 = 1+1 = 2
2 = 2+2 = 4
3 = 3+4 = 7
4 = 4+7 = 11
5 = 5+11 = 16
6 = 6+16 = 22
7 = 7+22 = 29

- red.november

EDIT: I modified the font size so that one has to work a little to see my answer.  Copy and paste my post in a text editor to see the solution.

[JConk007]

November,
 You are very, very sharp as evidenced by your posts. I knew you would get it. Wanna hold off a bit on solution? What percentage of pizza makers/members do you think could really solve this beside yourself? You think 15% is a fair # ?
 I was hoping to tickle the minds of other members. And at least let them wager a guess. I worked for a bit on it then went to the web page for the solution. Oh well
JOhn

[November]

Wanna hold off a bit on solution?

The thing is, the solution is already out there, so I'm not sure if I held off giving the solution it would be enough to keep everyone honest.  Update your initial post to tell others to overlook my posts if they want to try to figure it out on their own.  The solution can be easily found by simply drawing the problem out on paper too.  Draw a circle, then with each cut look to intersect as many lines as possible.  After just a few cuts the pattern becomes obvious.  Attached is what the equation would look like.  n is the number of cuts.

- red.november

EDIT: I reduced the font size of my solution above.
EDIT2: Added an algebraic expression.

[JConk007]

Thanks November!  Looks as though our pizza crowd would rather cook than slice.
As I mentioned  I did mess with it for a short time criss crossing the lines but did come up short. Thought it was interesting. I would assume the answer is out there as you mention. But the fun is just trying it and see how many pieces the average person comes up with without as you say cheating. I got the second equation you list to work fine but the other I have no clue. or (n^2+n+2)/2 regions=
I have the picture to put up later . I feel bad for the guy who got the middle pieces.

John
 

[parallei]

I drew 4 lines and concluded that RedN's equation is correct.  Maybe I'll draw them all later, but I'll need to make a larger circle!

[November]

I got the second equation you list to work fine but the other I have no clue.

The first equation is just a mathematical expression for what I demonstrated in my first post in this thread.  The Greek letter Sigma, symbolizes summation.  The number bellow the Sigma is the lower bound or starting index, and the number above the Sigma is the upper bound or limit.

[pizzapro]

Great puzzle - OK I'm a pizza freak and I love this one. November's solution is absolutely right, but I prefer to think of it this way as a computer programmer and pizza lover:

The resulting  pieces where the number of cuts is C, is the sum from N=1 to N=C of the output of max(N,2) for all C > 0 - see attached image

Why does this make more sense than the formula given previously? For any number of cuts greater than zero - each cut by definition makes at least 2 pieces, since even at the smallest value for cuts (1) you are creating 2 pieces. In fact for each value greater than 1, the cut can make a maximum number of additional pieces equal to the number of the cut; e.g. the Nth cut can produce N extra pieces (proving this is tough) In pseudo-code:

function get_number_pieces( cuts )
{
   if cuts < 1 return 0
   pieces = 0
   for (n=1; n<= cuts; n++) {
      pieces += n > 2 ? n : 2
   }
   return pieces
}

[abatardi]

Great puzzle - OK I'm a pizza freak and I love this one. November's solution is absolutely right, but I prefer to think of it this way as a computer programmer and pizza lover:

The resulting  pieces where the number of cuts is C, is the sum from N=1 to N=C of the output of max(N,2) for all C > 0 - see attached image

Why does this make more sense than the formula given previously? For any number of cuts greater than zero - each cut by definition makes at least 2 pieces, since even at the smallest value for cuts (1) you are creating 2 pieces. In fact for each value greater than 1, the cut can make a maximum number of additional pieces equal to the number of the cut; e.g. the Nth cut can produce N extra pieces (proving this is tough) In pseudo-code:

function get_number_pieces( cuts )
{
   if cuts < 1 return 0
   pieces = 0
   for (n=1; n<= cuts; n++) {
      pieces += n > 2 ? n : 2
   }
   return pieces
}

-bash-3.2$ php cuts.php
29

woot!  ;-)

[November]

November's solution is absolutely right, but I prefer to think of it this way as a computer programmer and pizza lover:

The resulting  pieces where the number of cuts is C, is the sum from N=1 to N=C of the output of max(N,2) for all C > 0 - see attached image

Why does this make more sense than the formula given previously? For any number of cuts greater than zero - each cut by definition makes at least 2 pieces, since even at the smallest value for cuts (1) you are creating 2 pieces. In fact for each value greater than 1, the cut can make a maximum number of additional pieces equal to the number of the cut; e.g. the Nth cut can produce N extra pieces (proving this is tough) In pseudo-code:

function get_number_pieces( cuts )
{
   if cuts < 1 return 0
   pieces = 0
   for (n=1; n<= cuts; n++) {
      pieces += n > 2 ? n : 2
   }
   return pieces
}

As a computer programmer, your interest should be in keeping your algorithm as efficient as possible.  Computer Science is a field that evolved from Mathematics, so I'm not sure what the excessive code and rejection of an algebraic solution is supposed to prove about a "programming" paradigm.  Supposing that you wanted to implement a for-next-loop, the following would be more straightforward:

function get_number_pieces2(cuts)
{
   pieces = 1;
   for (n=0; n<cuts; n++, pieces+=n);
   return pieces;
}

[abatardi]

As a computer programmer, your interest should be in keeping your algorithm as efficient as possible.  Computer Science is a field that evolved from Mathematics, so I'm not sure what the excessive code and rejection of an algebraic solution is supposed to prove about a "programming" paradigm.  Supposing that you wanted to implement a for-next-loop, the following would be more straightforward:

function get_number_pieces2(cuts)
{
   pieces = 1;
   for (n=0; n<cuts; n++, pieces+=n);
   return pieces;
}

Well let's go even faster then:

function get_number_pieces($cuts, &$pieces) {
        for($n = 0, $pieces = 1; $n < $cuts; $n++, $pieces += $n);
}

avg 36.4ms faster over 100k executions.

- aba

[November]

function get_number_pieces($cuts)
{
   if ($cuts < 1) return 0;
   $pieces = 0;
   for ($n=1; $n<= $cuts; $n++) {
      $pieces += $n > 2 ? $n : 2;
   }
   return $pieces;
}

function get_number_pieces2($cuts)
{
   $pieces = 1;
   for ($n=0; $n<$cuts; $n++, $pieces+=$n);
   return $pieces;
}

function get_number_pieces3($cuts)
{
   return ($cuts==0) ? 1 : get_number_pieces3($cuts-1) + $cuts;
}

(PHP 5.2.4)
Function 1: 65536 cuts in 0.019865989685059 s
Function 2: 65536 cuts in 0.011153936386108 s
Function 3: 16384 cuts in 0.039979934692383 s

I threw in recursion (F3) for academic kicks, but obviously it isn't going to be nearly as fast.

- red.november

EDIT: Changed micro to s.

[November]

function get_number_pieces($cuts, &$pieces) {
        for($n = 0, $pieces = 1; $n < $cuts; $n++, $pieces += $n);
}

That particular type of optimization has negligible effects in PHP because memory handling is quite inferior to C.  It looks better though.

Function abatardi: 65536 cuts in 0.011177778244019 s

EDIT: Changed micro to s.

[abatardi]

Yeah..  here is what i got.  Baseline = your function, current = mine

-bash-3.2$ php cuts.php
baseline = 3140.0470733643 ms
current = 2275.4240036011 ms

-bash-3.2$ php cuts.php
baseline = 2780.3201675415 ms
current = 2341.7859077454 ms

-bash-3.2$ php cuts.php
baseline = 3011.7900371552 ms
current = 2272.696018219 ms

-bash-3.2$ php cuts.php
baseline = 3044.4490909576 ms
current = 2274.7750282288 ms

each execution called it 1M times (php 5.2.9 on 4x2 core opteron, 8 proc total)

Edit: approx 25% faster in this test... so it is not a negligible performance increase... where I work this would save us 8 figures in hardware costs... if only all we were doing was running cuts.php, LOL :-)

- aba

[November]

abatardi,

You haven't mentioned how many cuts you are passing to the functions.

[abatardi]

abatardi,

You haven't mentioned how many cuts you are passing to the functions.

7!  That's what we are trying to figure out in this thread, right?  :-)

Edit: Tried with 30 cuts:

-bash-3.2$ php cuts.php
baseline = 7178.2610416412 ms
current = 6529.0699005127 ms

-bash-3.2$ php cuts.php
baseline = 7006.8099498749 ms
current = 6720.4880714417 ms

-bash-3.2$ php cuts.php
baseline = 7167.9768562317 ms
current = 6568.1581497192 ms

Performance gap is closing! 

[November]

Performance gap is closing! 

Precisely as it should.  You don't write functions with arguments and then only pass them the same values.  Optimization for low range inputs does not make for a very good function.  That's why I was testing in a larger range.  To make matters worse, in my configuration and using 7 cuts in a 100k loop, I get a 10.5x performance decrease with yours.  But my box is probably configured for different things than yours.  We probably ought to take this to personal messages though since this is beyond what the average pizza maker wants to see.

[pizzapro]

Thanks for the speedup, but I have to disagree respectfully. My intention was definitely not to give efficient code. Despite the great importance of algorithms in computer science, efficiency is rarely the principal concern, since most programming problems are not difficult - thus the pervasiveness of high-level interpreted languages. Efficiency and PHP - do these really belong together?

The point was that my formula made more sense logically to me than yours did. That's not a criticism, really. And I'll give you that by adding a one to your summation, yours handles the edge case with zero cuts, returning a one, as in one large piece. It just didn't seem like the crowd was interested in the formulas, thus the pdeudo code.

Wanna calculate this for a giant pie and 256k cuts by a laser in a big hurry? Write it in C.

I think it's more interesting to prove that for the nth cut the number of additional pieces created is always between 1 and n inclusive. The half of that proof that shows n as the upper bound for number of new pieces would prove the correctness of BOTH of our formulas.

By the way I ate an awesome coal-fired thin-crust marguerita pizza tonight for dinner, with an appetite whet by this cool puzzle. Kudos to JConk007 for posting this in the first place!   

As a computer programmer, your interest should be in keeping your algorithm as efficient as possible.  Computer Science is a field that evolved from Mathematics, so I'm not sure what the excessive code and rejection of an algebraic solution is supposed to prove about a "programming" paradigm.  Supposing that you wanted to implement a for-next-loop, the following would be more straightforward:
[snip....]

[JConk007]

Wow great stuff here. Thanks for all the replies Yes its 29 pieces. Glad we all are so logical. Like I said I could not get it so I am sticking with pizza 
Heres the pie sliced up

http://www.parade.com/news/2009/05/test-your-logic.html
John

[November]

Despite the great importance of algorithms in computer science, efficiency is rarely the principal concern, since most programming problems are not difficult - thus the pervasiveness of high-level interpreted languages.

Rarely?!  Maybe most of your programming problems are not difficult, but the application of Computer Science (CS) thrives on finding the most efficient solution.  I don't know at what level you are at with your CS education, but it doesn't sound like you've taken all the courses.  There isn't a discipline within the field of CS that isn't concerned with algorithmic efficiency or computational complexity.  Efficiency in this case is about both speed of execution and memory overhead.  If you were to argue this from the point of code readability, which is a legitimate concern in team development environments, you still have less readable code because you unnecessarily obfuscate the problem domain.

Efficiency and PHP - do these really belong together?

Algorithmic efficiency is independent of the computer language.  It's the interpreter that sometimes makes mistakes.  You started with pseudocode and we decided to use PHP as a proof-of-concept.  Again, the language has nothing to do with how efficient an algorithm is.

The point was that my formula made more sense logically to me than yours did. That's not a criticism, really. And I'll give you that by adding a one to your summation, yours handles the edge case with zero cuts, returning a one, as in one large piece. It just didn't seem like the crowd was interested in the formulas, thus the pdeudo code.

Wanna calculate this for a giant pie and 256k cuts by a laser in a big hurry? Write it in C.

I think it's more interesting to prove that for the nth cut the number of additional pieces created is always between 1 and n inclusive. The half of that proof that shows n as the upper bound for number of new pieces would prove the correctness of BOTH of our formulas.

Zero cuts is not an edge case.  It's a starting condition.  If you are approaching this algorithmically through summation, rather than algebraically, your algorithm creates a division of zero condition (and I don't mean divide by zero).  How can you divide zero by another number and get anything but zero?  If you start out with a pizza that hasn't been cut, which most people do, that's a pizza with zero cuts.  Zero cuts means you start out with one piece.  If it were not so, your first cut would either be 0+1=1 or 0/2=0; neither of which are correct.

If I were in a hurry I would write it in a functional language, not a procedural language like C.  This is just mathematics implemented in computer code.

You should examine what you call a proof again.  Besides not being a rigorous proof of any kind, you didn't prove anything beyond the fact that a number multiplied by two is always greater than or equal to two.  Proving that is not only trivial, it's also pointless in the context of the problem.  To make your so-called proof meaningful, you would have to compare the number of pieces added after the cut.  This is still a fool's errand, because in the end the question still remains if the algorithm solved the problem, which is what a real proof is supposed to be for.