[Blatant Alias Abuse] Anyone want to help out with a coding problem?

From: Mike Christensen <mike(at)kitchenpc(dot)com>
To: "pgsql-general(at)postgresql(dot)org" <pgsql-general(at)postgresql(dot)org>
Subject: [Blatant Alias Abuse] Anyone want to help out with a coding problem?
Date: 2010-06-17 11:49:14
Message-ID: AANLkTikBwvA7MMw2rOrrKeyo5eC0UzcrnG3JqcCMxh4y@mail.gmail.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-general

Hi all – I apologize for the misuse of this alias, but I figured I
have the audience that might be interested in helping me out with a
rather difficult coding problem. In fact, if I can find someone who’s
looking for some part-time work and is interested in a bit of extra
cash, then it’ll be worth it.

First off, a friend and I are starting a little dot-com here in
Seattle that focuses on recipes and meal planning. We’re building on
a typical LAMP stack (Linux, Apache, Mono, Postgres – why what did you
think I meant?) so we need someone with those skills as well as pretty
serious computer science skills (probably Masters of PhD).

Here’s the problem. Imagine you have a set of one or more recipes.
Each recipe requires one or more ingredients along with an amount of
that ingredient. You also have a given user, who has an available set
of ingredients and amounts in their inventory. The job is to find the
most efficient set of n recipes you can make with the given
ingredients, resulting in the fewest number of leftover amounts.
Sounds like your typical NP-Complete “multiple-knapsack” problem,
right? I’ll make it a bit more complicated now. This user also has a
set of “ratings” associated with zero or more recipes (0 stars, user
hates the recipe, 5 stars, they love it). One of the parameters of
the function is to take a sliding scale (between 1 and 10) that
indicates how much their ratings will play into the recipes the
function chooses. A scale of zero will tell the algorithm to ignore
their ratings and pick the most efficient set. A value of ten will
try to use their available ingredients if possible, but worry more
about picking recipes they’re probable to like. A default setting of
5 would pick some sort of even balance.

Here’s the data you have to work with:

- All recipes will be in RAM, no database access required. The
recipes contain only a guid, a list of required ingredients and
amounts, and a public average rating.
- There might be 100,000 recipes for all you know, so a brute-force
“try every combination” approach is out of the question. Scalability
is key.
- I’d prefer an algorithm that results in more accurate results the
longer it runs, as the available system resources and system load
could dictate how long to run the algorithm before telling it to stop.
- The engine is given a user profile (their inventory, all their
ratings, and how many recipes they want to cook)

Here’s my requirements for a solution:

- Scalable of course. Needs to be fast with lots of recipes, lots of
ratings, and able to work with multiple users at once. RAM is cheap.
- Algorithm functions as both a “suggestions” engine (think of the
Netflix algorithm for movie recommendations) and a “what can I make?”
algorithm, and can trend towards one side or the other.
- All code needs to be written in C#. I have a basic outline and all
data structures prepared, I just need to fill in the main function.
- Code needs to have unit tests, proving it works.

If this sounds like something you’d want to spend a weekend or two on,
lemme know. I’m willing to pay a grand or so. I’m also willing to
donate that grand to the PostgreSQL USA organization. Please reply to
me privately (mike at kitchenpc dot com) so we don’t clutter up this
list with an off-topic thread. Thanks!!

Mike

Responses

Browse pgsql-general by date

  From Date Subject
Next Message stefano bonnin 2010-06-17 11:55:41 Re: Given N, finding the interval of N hours with max(sum(..))
Previous Message Allan Kamau 2010-06-17 11:39:25 Re: Re: Monitoring activities of PostgreSQL ("Everlasting" function execution)