Three food problem – implementation details

See my previous post for what the three food problem is.

I decided to solve this problem using Python, as it is the language I’m most familiar with, and has several useful libraries. It took a day to get to a working program, and might have been less if I’d not decided to learn vim at the same time.

The program is divided up into 5 parts:

  • The recipe counter that checks how many recipes on allrecipes.com feature certain ingredients.
  • The word generator that gets words that are types of food from WordNet.
  • The food generator that generates a file containing words from the word generator that feature in at least one recipe on allrecipes.com. This means the program can avoid checking things like “low fat diet” that WordNet classifies as foods, but aren’t, and also obscure foods that don’t appear in any recipes.
  • The sampler, that picks combinations of 3 foods to be tested.
  • The tester, that checks that each pair of foods in a triad has at least one recipe on allrecipes.com, and that all three of them don’t appear together in any recipes.

I used three libraries for these tasks – requests, to make the searches, BeautifulSoup to find the recipe number on the results page, and NLTK to search WordNet for types of foods. This was the first time I’d used either BeautifulSoup or NLTK. I found them both easy to use, and well documented, although NLTK lacked an inbuilt function for something that seemed like core functionality to me (getting the name of a synset, e.g. `Synset(“maple_syrup.n.01”)` -> `”maple syrup”`). It wasn’t difficult to write some code to do this, but I was somewhat surprised that I had too.

Development was fairly straightforward. The only time I had to rewrite much code was when I realised the program would be much faster if I filtered the list of foods to only include those that appeared in any recipes. This reduced the foods from around 2300 to 1200, with a corresponding decrease in total triads to be checked of 1725515020 (or several hundred years).

The three food problem

The three food (incompatible food triad) problem is “an open problem in theoretical epicureanism”.
I found out about it a few months ago from the website of George W. Hart (professor at Stony Brook University, mathematical artist, and father of Vi Hart). He states the problem like this:

Can you find three foods such that all three do not go together (by any reasonable definition of foods “going together”) but every pair of them does go together?

He lists many attempts to solve it, but most of them are unsatisfactory, generally because one of the pairs doesn’t taste nice (to most palates at least).

I decided that this would be an interesting problem to try and solve programmatically. My approach has been to get triads of food, and test that a recipe website (I’ve used allrecipes.com) produces at least one recipe for each pair of foods, but none for all three. This seems to have worked quite well, although there were some problems.

Details of my implementation will follow in a later post. For now, the code (in Python) is on GitHub here.

Here are the last 10 possible solutions given by the program:

cheese, red wine, rump roast
corn, tart, dill pickle
hot pepper, cocoa, bun
apple, spinach, cup
cheddar, paprika, brown rice
split, tomato paste, maple syrup
crescent roll, cream cheese, apple pie
taco, pie, peanut butter
sour cream, honey, cup
vanilla, maraschino, grape

As you can see, it’s not perfect – for instance, “cup” isn’t a food. I hope to improve it by ranking solutions, so it easier to find good ones. I will post updated results when they are produced.

Knossos – a text-based psychological horror game

I released a game called KnossOS last Halloween.

It features a Unix-like operating system, retro modem sound effects, and blurring of lines between player and character. People have praised its “high-quality writing and very creative presentation” and called it “seriously spoopy”! It’s free! (And open source, code available on github).

You can find it on IndieDB or GitHub.

It also has a website.