How to approach a number guessing game (with a twist) algorithm?

Question

I am learning programming (Python and algorithms) 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 (i.e. 100 apples, 20 pears, and one orange). The only output 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.). The prices of fruit can change(at random) so the total value may change based on that also (for simplicity I am not changing fruit prices in this 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 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.

Question:

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, if 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).

Answer 1

We can solve this problem by combining graph-theory and probability:

We can start by building a set of all feasible solutions. Lets denote the solutions set as A1={a1(1), a1(2),...,a1(n)}.

Then build one more solution set A2.

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

Basically, we are building a connected directed acyclic graph.

All paths in the graph look equal. You can find an exact solution only when there is a single edge from Am to Am+1.

You will find that some nodes of graphs 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 the number of paths that leads to this node, there is no need to keep all history, but only the previous day.

Hope this answer helps.

If you wish to learn about python algorithms visit this Data Science with Python Course.