Passing the picky pizza trolls
Wait a minute, do you feel that? It feels like someone… Wants to ruin a childhood game with math and computer science!
Too late, you’re stuck here now. Put on your best ‘I’m tolerating you’ smile and settle in for the first in a series of posts tackling the best strategies to beat a decades-old childrens’ computer game.
A history lesson
Back in the late 80s and early 90s, Broderbund was pumping out hit after digital hit. They’re the masterminds behind classics like the Carmen Sandiego series, the original Prince of Persia, and the venerable Kid Pix. In 1996, they released one of my favourite games of all-childhood-time; the educational puzzle that was the Logical Journey of the Zoombinis.
The fuck is a Zoombini?
A Zoombini is a lil blue sphere adorned with a lil coloured nose, a pair of lil eyes, some hair, and some adorable method of locomotion.
They’ve been the victims of a curiously-unmentioned race war with their cousins, the Fleens, who are Zoombinis but tall and green. Driven from their home, they’re forced to journey across treacherous terrain filled with sentient rock formations and several other cryptic bastards who force them to complete puzzles in order to pass through unharmed.
I say force them, I really mean force you.
Make me a pizza!
One of the puzzles you’ll encounter (and no doubt the most iconic one)
is the task of making a pizza for a very picky troll. The specifics vary according to the difficulty settings,
but the basic idea is that you’ve been given a machine that can spit out
a pizza with various toppings, and you have to find the right combination
of toppings to
pay the troll toll feed the troll and pass through.
Arno the pizza troll (and his family, when you meet them at higher difficulties)
will always give you enough chances to try every topping available on its own.
To put that in maths, you’ll always get
n + 3 pizza attempts, where
n is the
number of toppings or sundae ingredients on a particular difficulty level.
After that magical number, he’ll start punting your Zoombinis back from whence they
Seeing as we get so much leniency from the arboreal amante della pizza (pizza lover, in Italian for the sake of alliteration), making a separate pizza from every topping and then assembling one final, correct pizza is definitely a viable strategy that’ll win every time. Unfortunately, it isn’t quite a pedantic enough strategy, and it’ll offend every Italian you’ve ever met. Why? Cultural differences.
Oh, but also, you’re wasting a pizza! Every good Italian will tell you that their mother always instilled in them a compulsion to lick their plate clean of even the tiniest slicks of sauce, because wasting food is tantamount to a slap to the face.
Build off your mistakes
No, dear reader, we can make sure that we never waste even a single pinch of flour with a slightly different strategy; dynamic programming. Dynamic programming tries to solve problems by breaking them up into smaller, overlapping subproblems.
The big problem we’re trying to solve is which toppings to put on the pizza. We can break that up into smaller problems, one for each topping, where the small problem is whether the troll likes that topping or not. What sets this apart from the strategy above is something called memoization, which is a fancy way of saying ‘remember the solutions to the previous subproblem’. Instead of checking each topping individually, then, what we’ll do is this:
- Start with the first topping and see if the troll likes it
- If they do, add it to the next pizza
- Go back to step 1 and repeat with the next topping
By keeping the toppings the troll likes on our pizza when we’re checking a new topping, we can save on pizza dough because when we find the last topping they like, we don’t need to make a pizza with all the toppings on it; we’ve already got them all on it!
Let’s work through an example where Arno wants a pizza with olives and cheese. We start at step 1, making a pizza with just olives. Arno says he likes it, great. We then make a pizza with olives and capsicum. Arno says yuck, so we move on. We make a pizza with olives and mushrooms. Arno says yuck again. We make a pizza with olives and pepperoni. No dice. We make a pizza with olives and cheese. Bingo! Arno likes cheese, he likes olives, and he’s happy with the pie! If we were using our other approach, we’d make one pizza for each individual topping, which makes for 5 pizzas. Then we have to make one additional pizza with all the toppings we know Arno likes, which makes 6 pizzas. That’s a whole pizza extra than our new method, which only uses 5 slabs of dough.
Mamma would be so proud.