Positive Analogue

Pascal's Pizza

May 13, 2019

Skip to counting pizza in Clojure or the maths part

A game about pizza! I was instantly a fan. It’s called ‘New York Slice’, 2-6 players, a quick 30min game. The idea is: each player attempts to collect pizza slices. Slices are worth between 3 to 12 points. Each turn a new 11 slice pizza is laid out at random. One person must partition the pizza, a group of slices per player, changing the order of the slices is not allowed. Then, in turn, each player takes the group they most like the look of, with the person who sliced choosing last.

dividing up a pizza

My friends will tell you that playing a game with me can be quite frustrating. Like a chess player I think deeply about each move, trying to weigh up all the possibilities. Though in this particular case I wasn’t weighing up the possibilities, I was trying to calculate how many possibilities there were. Seeing the look on my friends’ faces I snapped back into the room and split up the pizza by going with my gut. Pretty sure I lost that game.

For the next few days I was still wondering about the game. Instead of jumping in and using code (or the internet) to solve this I fancied trying the old fashioned way. Pen and paper. I wrote f(1, 1) = 1 in a little book, to represent that a pizza made up of 1 slice divided between 1 person has 1 possibility. The plan is to try and spot a pattern before manually counting all the way up to the number I was actually trying to calculate: f(11, 6) = ?. Tea in hand I got counting.

counting possibilities

For a given number of slices and people, coming up with the possible group sizes wasn’t too difficult. For example 7 slices between 3 people is [5 1 1], [4 2 1], [3 3 1], [3 2 2]. What was taking me longer to count was the number of ways each group could be uniquely applied. A 6 slice pizza can be grouped into [3 2 1] 12 different ways:

  1. (a b c) (d e) (f)
  2. (b c d) (e f) (a)
  3. (c d e) (f a) (b)
  4. (d e f) (a b) (c)
  5. (e f a) (b c) (d)
  6. (f a b) (c d) (e)
  7. (a b c) (d) (e f)
  8. (b c d) (e) (f a)
  9. (c d e) (f) (a b)
  10. (d e f) (a) (b c)
  11. (e f a) (b) (c d)
  12. (f a b) (c) (d e)

…but [2 2 2] just 2 ways:

  1. (a b) (c d) (e f)
  2. (b c) (d e) (f a)

After a few more pleasant sessions sitting outside, away from a computer, writing out the combinations I had the numbers for up to a 9 slice pizza. Though each number was getting progressively more difficult and I did feel that I was starting to make small mistakes. No grand patterns had leapt off the page so I decided to enter the numbers into a spreadsheet to play around with them. I was a little tempted to walk into town and buy some nice graph paper to continue the old-fashioned approach but the ease of google sheets was too tempting. Besides I still had not leapt into writing code (or googling the answer) which was the main challenge to myself.

graph up to 9 slice pizza

The graph looked pleasing and the numbers certainly follow some trend but I couldn’t see a formula. With the subtleties of how many applications a grouping could have based on how many rotations and reflections it had I was starting to loose faith that a nice equation even existed. Anytime a pattern started there was a place where it didn’t fit.

After delaying as much as possible I started to code. I could re-generate the data with some software and maybe after correcting any errors the patterns would hold better.

Clojure

To avoid errors I wanted to write a naive, slow, brute-force program. Avoiding clever optimizations should decrease the chance of error at the cost of time-to-run. As the program would only need to run once, performance is not critical. I used Clojure because it is great at producing and manipulating large streams of values - excellent when brute forcing. Also, when coding for fun, I try and use a language I do not get many other opportunities to use.

The program will form a stream of:

  1. Produce every group for a given size
  2. Filter out the invalid ones
  3. For each group, rotate it around a pizza, producing all the slice combinations
  4. Filter out duplicates
  5. Count the values

The simplest way to produce a stream is to define a function that, when given the nth item, will produce the n+1th item. The stream can then be produced by recursively applying the function (f (f (f (...)))). So I wrote the following function, that when given a group, will produce the next group. After the last group it produces a nil to signal the end.

(defn increment-group [base prev]
  (loop [v prev
         col (- (count prev) 1)
         overflow 1]
    (if (< col 0)
      (if (> overflow 0) nil v)
      (recur
        (update v col #(mod (+ overflow %) base))
        (dec col)
        (quot (+ overflow (get v col)) base)))))

> (increment-group 3 [0 0 0])[0 0 1]

> (increment-group 3 [0 0 1])[0 0 2]

> (increment-group 3 [0 0 2])[0 1 0]

> (increment-group 3 [0 1 0])[0 1 1]

> (increment-group 3 [2 2 2])nil

Next came, taking this function, converting it into a stream using iterate and filtering out invalid groups (wrong number of slices or people with no slices).

(defn groups [& {:keys [slices people]}]
  (->>
    (iterate
      #(increment-group (inc slices) %)
      (vec (for [_ (range people)] 0)))
    (take-while some?)
    (filter
      (fn valid-group [nums]
        (and
            (= slices (reduce + nums))
            (every? #(>= % 1) nums))))))

> (groups :slices 4 :people 2)([1 3] [2 2] [3 1])

Now for the rotations. I wanted a function that would take a group and a pizza and return which slices ended up in each part of the group, with an offset parameter to rotate the pizza.

(defn combos [& {:keys [pizza group offset]}]
  (if (empty? group)
    []
    (let [[head & tail] group
          offset-pizza (drop offset (concat pizza pizza))]
      (lazy-seq
        (cons
          (set (take head offset-pizza))
          (combos :pizza pizza :group tail :offset (+ offset head)))))))

> (for [r (range 6)]
    (combos :pizza ['a 'b 'c 'd 'e 'f] :group [3 2 1] :offset r))(({a b c} {d e} {f})
    ({b c d} {e f} {a})
    ({c d e} {f a} {b})
    ({d e f} {a b} {c})
    ({e f a} {b c} {d})
    ({f a c} {c d} {e}))

Finally I need to marry these two together, getting all combos for all streams and then use distinct to remove the duplicates. Clojure’s natural ability to compare all values including Sets and Lists really shines here. The whole program comes in at under 45 lines of code. That said the approach overall is, as expected, very slow to run for larger numbers of people with a big-o of O(Slices^People).

(defn pizza-options [& {:keys [slices people]}]
  (->>
    (for
      [group (groups :slices slices :people people)]
      (for
        [offset (range slices)]
        (set
          (combos
            :pizza (vec (range slices))
            :group group
            :offset offset))))
    (apply concat)
    (distinct)))

> (pizza-options :slices 4 :people 2)({{0} {1 2 3}}
    {{1} {2 3 0}}
    {{2} {3 0 1}}
    {{3} {0 1 2}}
    {{0 1} {2 3}}
    {{0 3} {1 2}})

> (count (pizza-options :slices 4 :people 2))6

> (time (count (pizza-options 9 7)))
"Elapsed time: 18.599 secs"36

Algebraically

With this new tool, I returned to the spreadsheet and entered in the new more reliable data.

1 2 3 4 5 6 7 8 9
1 1
2 1 1
3 1 3 1
4 1 6 4 1
5 1 10 10 5 1
6 1 15 20 15 6 1
7 1 21 35 35 21 7 1
8 1 28 56 70 56 28 8 1
9 1 36 84 126 126 84 36 9 1

There are certainly some nice patterns. Each row has a symmetry which gradually becomes more apparent. The ‘2 person’ column increments by 2,3,4,5,6,7,8. Though the ‘3 person’ column increments at the stranger rate of 3,6,10,15. Unperturbed I created a new sheet which lists how much larger each cell is compared to the one above it.

1 2 3 4 5 6 7 8 9
1 +1
2 0 +1
3 0 +2 +1
4 0 +3 +3 +1
5 0 +4 +6 +4 +1
6 0 +5 +10 +10 +5 +1
7 0 +6 +15 +20 +15 +6 +1
8 0 +7 +21 +35 +35 +21 +7 +1
9 0 +8 +28 +56 +70 +56 +28 +8 +1

These numbers looked nice and felt familiar. You get 1,2,3,4,5… running along column 2 and also diagonally below the 1s. A much much stronger pattern is there but it took me forever to spot it. When I did spot it I did feel like a kid at Christmas.

The amounts the cells increment by are the same numbers as the original numbers but shifted down and to the right. Looking again at the original numbers. Apart from the first two columns, each cell is the sum of the one above it and the one to its above left. I couldn’t believe it.

1 2 3 4 5 6 7
1 1
2 1 1
3 1 3 1
4 1 6 3+1= 4 1
5 1 10 6+4= 10 4+1= 5 1
6 1 15 10+10= 20 10+5= 15 5+1= 6 1
7 1 21 15+20= 35 20+15= 35 15+6= 21 6+1= 7 1

A trick to get around the annoying ‘2 person’ column not playing ball is to pretend the numbers for the first column are 1,2,3,4. Then it all falls into place. Back to pen, paper and high-school algebra I rearranged the parts into this:

g(n, n)            = 1
g(slices, 1)       = slices
g(slices, people)  = g(slices-1, people) + g(slices-1, people-1)

f(_, 1)            = 1
f(slices, people)  = g(slices, people)

and in Clojure (100,000 times faster than before)

(defn g [slices people]
  (cond
    (= slices people) 1
    (= 1 people) slices
    :else (+
            (g (dec slices) people)
            (g (dec slices) (dec people)))))

(defn faster-pizza-options [slices people]
  (if (= people 1)
      1
      (g slices people)))

> (time (faster-pizza-options 9 7))
"Elapsed time: 0.1969 msecs"36

I could now answer the question I was pondering during that first game. For an 11 slice pizza with 6 players there are 462 possible ways to divide it. No wonder it was taking me so long to play the game!

Pascal’s Slice

Satisfied with my solution I now turned to the internet for an explication. It did not take long to realise I had stumbled on a well known series of numbers called pascal’s triangle, which has been known for over a thousand years. Pascal’s triangle gives the answer to combination problems; in that way it is unsurprising the numbers I was calculating produced it. What I did find surprising is how easily the problem mapped onto basic combination calculations.

Dividing up the pizza felt more complicated than simply calculating combinations due to rejecting permutations of a combination if they were a rotation of an another permutation. I must be approaching the problem from the wrong perspective.

On the plus side updating the Clojure to incorporate the formula for calculating Pascal’s triangle (also called the Binomial coefficient) does gives an even more efficient solution.

(defn ! [n]
  "Calculate the factorial of n"
  (reduce * (range 1 (inc n))))

(defn pascal [n k]
  (/ (! n) (* (! k) (! (- n k)))))

(defn pascal-pizza [slices people]
  (if (= people 1)
      1
      (pascal slices people)))

> (time (faster-pizza-options 20 10))
"Elapsed time: 4.4781 msecs"
↳ 184756N

> (time (pascal-pizza 20 10))
"Elapsed time: 0.1957 msecs"
↳ 184756N

Can see here Clojure automatically kicking in to use BigInt, shown by the N after the number. Doing maths in Clojure certainly feels a lot safer than Javascript where mistakes can more easily go unnoticed.

Pascal’s triangle gives the answer to “N choose K”. In other words, if you have N things how many ways can you pick K of them. For example if you have the choice of 5 pizza toppings:

  • Peppers
  • Olives
  • Mushrooms
  • Sweetcorn
  • Pineapple

and you are allowed to choose two there are 5 choose 2 possibilities:

  • Peppers & Olives
  • Peppers & Mushrooms
  • Peppers & Sweetcorn
  • Peppers & Pineapple
  • Olives & Mushrooms
  • Olives & Sweetcorn
  • Olives & Pineapple
  • Mushrooms & Sweetcorn
  • Mushrooms & Pineapple
  • Sweetcorn & Pineapple

Notice that order does not matter. Picking peppers and olives is the same as picking olives and peppers, they are not two separate possibilities. Also you can’t pick the same thing twice. So why is dividing up a pizza with S slices between P people the same as having S of something and choosing P of them?

As it turns out by worrying about the sizes of each group I was making the problem much more complex than it needed to be. All we actually care about is where each new group starts. When dividing up the pizza we can see each group as choosing a slice where a new group should start. The size of the groups doesn’t matter, it’s just a side-effect of where the groups starts.

Say a pizza has 6 slices each with a label a, b, c, d, e, f. To split this into 2 groups, just pick any 2 slices. Say we pick a and e, this gives the groups: [a,b,c,d] and [e,f]. Or picking c and d, this gives the groups [c] and [d,e,f,a,b]. Much simpler. The only time this doesn’t work is when there is only one person. Pascal’s triangle would say there are many options but really there is only one - eating all of slices. And this is why, with a small tweak for P=1, the problem directly maps to S choose P.

Looking at the problem this way avoids all the worry about rotations, the ordering of the slices and that they form a cycle. They are all removed from the equation. I feel this adventure will be a lesson. When I am struggling to get something to fit together I should step back and try and see the issue from a new perspective.


Ashley Claymore

Hi! I'm Ashley Claymore. Like many others, pulling things apart to learn how they work brings me a lot of joy. This site serves as an outlet for these little projects.