Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I posted this on stackoverflow, but was advised to also post here. It's kind of a math/algo question so I think it's kind of stuck between both worlds of math and computer science. I believe this to be ontopic but if not, please let me know and I'll delete it. Here's the link to the stackoverflow post.

I am learning programming (python and algo’s) and was trying to work on a project that I find interesting. I have created a few basic python scripts but I’m not sure how to approach a solution to a game I am trying to build.

Here’s how the game will work:

Users will be given items with a value. For example

Apple = 1
Pears = 2
Oranges  = 3

They will then get a chance to choose any combo of them they like (e.g. 100 apples, 20 pears, and 1 orange). The only input the computer gets is the total value (in this example, it's currently $143). The computer will try to guess what they have. Which obviously it won’t be able to get correctly the first turn.

         Value  quantity(day1)  value(day1)
Apple    1      100             100
Pears    2      20              40
Orange   3      1               3
Total           121             143

The next turn the user can modify their numbers but no more than 5% of the total quantity (or some other percent we may chose. I’ll use 5% for example.). Using the above example, on day 2 of the game, the user returns a value of \$152 and \$164 on day 3. Here's an example.

quantity(day2)  %change(day2)   value(day2) quantity(day3)  %change(day3)   value(day3)
104                             104         106                             106
21                              42          23                              46
2                               6           4                               12
127             4.96%           152         133             4.72%           164

(I hope the tables show up right, I had to manually space them so hopefully it's not just doing it on my screen; if it doesn't work let me know and I'll try to upload a screenshot).

I am trying to see if I can figure out what the quantities are over time (assuming the user will have the patience to keep entering numbers). I know right now my only restriction is that the total value cannot be more than 5%, so I cannot be within 5% accuracy right now, so the user will be entering it forever.

What I have done so far

Here’s my solution so far (not much). Basically I take all the values and figure out all the possible combos of them (I am done this part). Then I take all the possible combos and put them in a database as a dictionary (so for example for \$143, there could be a dictionary entry {apple:143, Pears:0, Oranges :0}… all the way to {apple:0, Pears:1, Oranges :47}. I do this each time I get a new number so I have a list of all possibilities.

Here’s where I’m stuck. Using the rules above, how can I figure out the best possible solution? I think I’ll need a fitness function that automatically compares the two days' data and removes any possibilities that have more than 5% variance of the previous days data.

Questions:

So my question with user changing the total and me having a list of all the probabilities, how should I approach this? What do I need to learn? Is there any algorithms out there or theories that I can use that are applicable? Or, to help me understand my mistake, can you suggest what rules I can add to make this goal feasible (if it's not in its current state. I was thinking adding more fruits and saying they must pick at least 3, etc.)? Also, I only have a vague understanding of genetic algorithms but I thought I could use them here; is there something I can use?

I'm very very eager to learn so any advice or tips would be greatly appreciated (just please don't tell me this game is impossible).

Thanks in advance.

UPDATE: Getting feedback that this is hard to solve. So I thought I'd add another condition to the game that won't interfere with what the player is doing(game stays the same for them) but everyday the value of the fruits change price(randomly). Would that make it easier to solve? Because within a 5% movement and certain fruit value changes, only a few combo's are probable over time. Day 1, anything is possible and getting a close enough range is almost impossible, but as the prices of fruits change and the user can only choose a 5% change, then shouldn't(over time) the range be narrow and narrow. In the above example, if prices are volatile enough I think I could brute force a solution that gave me a range to guess in, but I'm trying to figure out if there's a more elegant solution or other solutions to keep narrowing this range over time.

share|improve this question
2  
This game is impossible. (Just kidding. But in general, with sufficiently large values, this will be impractical to do in any reasonable amount of time. The Subset sum problem and Knapsack problem are NP-complete, etc. But you can get approximations, and you may also be able to get exact answers when the numbers are small.) –  ShreevatsaR Oct 8 '11 at 6:50
    
Whoa you scared me for a second. I was just using those numbers as a example I think if i can find a non brute force approach I can scale it. I can use smaller numbers if it helps. –  Lostsoul Oct 8 '11 at 7:01

3 Answers 3

up vote 2 down vote accepted
+150

This can be treated as a Hidden Markov Model. It is extremely soluble. The people who are telling you that this is intractible are wrong, or more accurately, they are referring to the wrong problem.

Yes, if you have a large set of values and you are only allowed to include each value once (as opposed to taking 20 apples), this is the subset-sum problem. That is not the case here.

You have a sequence of hidden states, characterized by the number of each object at time-step T. You have a nice known linear map from your hidden state to an observed value, and a known transition function from states at T to states at T+1. There are strong Bayesian methods to find the hidden states -- but you can expect them to take a long time to converge.

This is even doable if you don't know the linear map or the transition function, so long as you know they have nice properties.

N.B. This is assuming the human player is not adversarial. As mentioned above, if the human player is purposely staying away from extreme patterns, this is probably intractable. If the human player is essentially making adjustments at random, it is tractable. With random fluctuations in value, this is probably tractable.

share|improve this answer
    
I'm a noob when it comes to deep math to let me work on this, thank you. But your correct in your understanding, they are not adversarial, just picking at random(or logic of their choice) and I'm merely trying to guess their result based on the total value that they are giving me and my knowledge of the current value of the fruits. –  Lostsoul Oct 10 '11 at 22:07
    
Thank you Craig. I might post more questions later, but I have looked and create a few sample apps and seems to be what I need(not 100% sure yet but seems very prob). I rewarded you the points, and unless there's no earth shattering new answer I'll give you at vote as well. I just had one more question. I asked this question on various boards and you are the only one who gave me an answer that worked, how did you know it? Is there a book or site that has similar types of problems? I'm interested in these types of problems very much. –  Lostsoul Oct 12 '11 at 18:02
    
I think it may be more about how the question is presented. Lots of people know about Hidden Markov Models, but they know about it in other contexts. Basically, any situation where there's some underlying state(s) that you can't observe directly, but you can observe some things and you have an idea of how states transition from one to another -- think HMM. There are examples in machine vision, some (bad) stock market models, crypto, etc. –  Craig Oct 12 '11 at 18:15
    
Thank you Craig. You answer really did send me down a very interesting path, I have basically been reading up on it and its really amazing stuff. I think I'm going to apply a modified version of the Viterbi algorithm(en.wikipedia.org/wiki/Viterbi_algorithm) I just am trying to figure out how to connect the states together. Like in the examples, they pre-assign probabilities to certain actions, I cannot do this manually so trying to figure out how to apply it directly to my situation. –  Lostsoul Oct 12 '11 at 18:27
    
You can preassign probabilities, if you assume the human player is behaving randomly. In your example, from (100,20,1), you can add/subtract at most a total of 6. There are ~300 states (100+x, 20+y, 1+z) accessible with |x|+|y|+|z| <= 6 and all three coordinates non-negative. Assign each of them equal probability. –  Craig Oct 12 '11 at 19:26

If I have understood your question, then this will be hopeless if the only information are the total values and whether previous guesses are correct.

With your example with an initial value of 143, the number of possible patterns is 1776, ranging from 143 apples to 47 oranges and a pear. The computer guesses, and probably gets it wrong.

Next turn the the player declares a value is 149. There are now 1925 possible patterns, of which at most one has been eliminated, so the computer guesses, and probably gets it wrong. And so it goes on, with more possibilities being added and very few being eliminated each time. You might get lucky, but I would expect there is a positive probability the computer never gets the correct answer, especially if the player stays away from extreme patterns. Having more types of fruit would only make this worse.

share|improve this answer
    
Thank you so much Henry, I understand what your saying. But I thought about it and updated the question so that what if the values of the fruits change everyday. Wouldn't there be a way that certain total values would be impossible under certain types of fruit values. So if apple's value jumps to $100 but the player has a total value of 149, then we know they most likely did not have any apples(or at most one). Does that make it more possible? –  Lostsoul Oct 8 '11 at 15:56
    
If fruits prices are changing, wouldn't certain possibilities be less likely and over time the possibilities actually decrease to something more accurate? –  Lostsoul Oct 8 '11 at 15:59
    
@Lostsoul: If the computer is allowed to change the fruit prices, then it may be possible (e.g. first set apple price very high, get number of apples, then set orange price very high, etc.), but with random variation, I doubt it. –  ShreevatsaR Oct 9 '11 at 4:22
    
@ShreevatsaR yes it would have to be random. I cannot change the prices otherwise I could simply cheat and get the answer. The fruits can be random or the user can change them..but not the computer. –  Lostsoul Oct 9 '11 at 4:25

We'll combine graph-theory and probability:

On the 1st day, build a set of all feasible solutions. Lets denote the solutions set as A1={a1(1), a1(2),...,a1(n)}.

On the second day you can again build the solutions set A2.

Now, for each element in A2, you'll need to check if it can be reached from each element of A1 (given x% tolerance). If so - connect A2(n) to A1(m). If it can't be reached from any node in A1(m) - you can delete this node.

Basically we are building a connected directed acyclic graph.

All paths in the graph are equally likely. You can find an exact solution only when there is a single edge from Am to Am+1 (from a node in Am to a node in Am+1).

Sure, some nodes appear in more paths than other nodes. The probability for each node can be directly deduced based on the number of paths that contains this node.

By assigning a weight to each node, which equals to the number of paths that leads to this node, there is no need to keep all history, but only the previous day.

Also, have a look at non-negative-values linear diphantine equations - A question I asked a while ago. The accepted answer is a great way to enumarte all combos in each step.

share|improve this answer
    
Thanks I'll look into it. I will read up on graph-theory and probability this weekend. –  Lostsoul Oct 8 '11 at 15:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.