Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p><em>Disclaimer: I changed my answer dramatically after temporarily deleting my answer and re-reading the question carefully as I misread some critical parts of the question. While still referencing similar topics and algorithms, the answer was greatly improved after I attempted to solve some of the problem in C# myself.</em></p> <h2>Hollywood version</h2> <ul> <li>The problem is a <a href="http://en.wikipedia.org/wiki/Constraint_satisfaction_problem#Dynamic_CSPs" rel="nofollow">Dynamic constraint satisfaction problem</a> (DCSP), a variation on <a href="http://en.wikipedia.org/wiki/Constraint_satisfaction_problem" rel="nofollow">Constraint satisfaction problems</a> (CSP.)</li> <li>Use <a href="http://en.wikipedia.org/wiki/Monte_Carlo_algorithm" rel="nofollow">Monte Carlo</a> to find potential solutions for a given day if values and quantity ranges are not tiny. Otherwise, use brute force to find every potential solutions.</li> <li>Use <em>Constraint Recording</em> (related to DCSP), applied in cascade to previous days to restrict the potential solution set.</li> <li>Cross your fingers, aim and <em>shoot</em> (Guess), based on probability.</li> <li><em>(Optional)</em> Bruce Willis wins.</li> </ul> <h2>Original version</h2> <p>First, I would like to state what I see two main problems here:</p> <ol> <li><p>The sheer number of possible solutions. Knowing only the number of items and the total value, lets say 3 and 143 for example, will yield <em>a lot</em> of possible solutions. Plus, it is not easy to have an algorithm picking valid solution without inevitably trying invalid solutions (total not equal to 143.)</p></li> <li><p>When possible solutions are found for a given day D<sub>i</sub>, one must find a way to eliminate potential solutions with the added information given by { D<sub>i+1</sub> .. D<sub>i+n</sub> }.</p></li> </ol> <p>Let's lay down some bases for the upcoming examples:</p> <ul> <li>Lets keep the same item values, the whole game. It can either be random or chosen by the user.</li> <li>The possible item values is bound to the very limited range of [1-10], where no two items can have the same value.</li> <li>No item can have a quantity greater than 100. That means: [0-100].</li> </ul> <p>In order to solve this more easily <strong>I took the liberty to change one constraint</strong>, which makes the algorithm converge faster:</p> <ul> <li>The "total quantity" rule is overridden by this rule: You can add or remove any number of items within the [1-10] range, total, in one day. However, you cannot add or remove the same number of items, total, more than twice. This also gives the game a maximum lifecycle of 20 days.</li> </ul> <p>This rule enables us to rule out solutions more easily. And, with non-tiny ranges, renders <a href="http://en.wikipedia.org/wiki/Backtracking" rel="nofollow">Backtracking algorithms</a> still useless, just like your original problem and rules.</p> <p>In my humble opinion, this rule is not the <em>essence</em> of the game but only a facilitator, enabling the computer to solve the problem.</p> <h3>Problem 1: Finding potential solutions</h3> <p>For starters, <em>problem 1.</em> can be solved using a <a href="http://en.wikipedia.org/wiki/Monte_Carlo_algorithm" rel="nofollow">Monte Carlo algorithm</a> to find a set of potential solutions. The technique is simple: Generate random numbers for item values and quantities (within their respective accepted range). Repeat the process for the required number of items. Verify whether or not the solution is acceptable. That means verifying if items have distinct values and the total is equal to our target total (say, 143.)</p> <p>While this technique has the advantage of being easy to implement it has some drawbacks:</p> <ul> <li>The user's solution is not guaranteed to appear in our results.</li> <li>There is a lot of "misses". For instance, it takes more or less 3,000,000 tries to find 1,000 potential solutions given our constraints.</li> <li>It takes a lot of time: around 4 to 5 seconds on my lazy laptop.</li> </ul> <p>How to get around these drawback? Well...</p> <ul> <li>Limit the range to smaller values and</li> <li>Find an adequate number of potential solutions so there is a good chance the user's solution appears in your solution set.</li> <li>Use heuristics to find solutions more easily (more on that later.)</li> </ul> <p>Note that the more you restrict the ranges, the less useful while be the Monte Carlo algorithm is, since there will be few enough valid solutions to iterate on them all in reasonable time. For constraints { 3, [1-10], [0-100] } there is around 741,000,000 valid solutions (not constrained to a target total value.) Monte Carlo is usable there. For { 3, [1-5], [0-10] }, there is only around 80,000. No need to use Monte Carlo; brute force <code>for</code> loops will do just fine.</p> <p>I believe the <em>problem 1</em> is what you would call a <a href="http://en.wikipedia.org/wiki/Constraint_satisfaction_problem" rel="nofollow">Constraint satisfaction problem</a> (or CSP.)</p> <h3>Problem 2: Restrict the set of potential solutions</h3> <p>Given the fact that <em>problem 1</em> is a CSP, I would go ahead and call <em>problem 2</em>, and the problem in general, a <a href="http://en.wikipedia.org/wiki/Constraint_satisfaction_problem#Dynamic_CSPs" rel="nofollow">Dynamic CSP</a> (or DCSP.)</p> <blockquote> <p>[DCSPs] are useful when the original formulation of a problem is altered in some way, typically because the set of constraints to consider evolves because of the environment. DCSPs are viewed as a sequence of static CSPs, each one a transformation of the previous one in which variables and constraints can be added (restriction) or removed (relaxation).</p> </blockquote> <p>One technique used with CSPs that might be useful to this problem is called <em>Constraint Recording</em>:</p> <ul> <li>With each change in the environment (user entered values for D<sub>i+1</sub>), find information about the new constraint: What are the possibly "used" quantities for the add-remove constraint.</li> <li>Apply the constraint to every preceding day in cascade. Rippling effects might significantly reduce possible solutions.</li> </ul> <p>For this to work, you need to get a new set of possible solutions every day; Use either brute force or Monte Carlo. Then, compare solutions of D<sub>i</sub> to D<sub>i-1</sub> and keep only solutions that can succeed to previous days' solutions without violating constraints.</p> <p>You will probably have to keep an history of what solutions lead to what other solutions (probably in a directed graph.) Constraint recording enables you to <em>remember</em> possible add-remove quantities and rejects solutions based on that.</p> <p>There is a lot of other steps that could be taken to further improve your solution. Here are some ideas:</p> <ul> <li>Record constraints for item-value combinations found in previous days solutions. Reject other solutions immediately (as item values must not change.) You could even find a smaller solution sets for each existing solution using solution-specific constraints to reject invalid solutions earlier.</li> <li>Generate some "mutant", full-history, solutions each day in order to "repair" the case where the D<sub>1</sub> solution set doesn't contain the user's solution. You could use a genetic algorithm to find a mutant population based on an existing solution set.)</li> <li>Use heuristics in order find solutions easily (e.g. when a valid solution is found, try and find variations of this solution by substituting quantities around.)</li> <li>Use behavioral heuristics in order to predict some user actions (e.g. same quantity for every item, extreme patterns, etc.)</li> <li>Keep making some computations while the user is entering new quantities.</li> </ul> <p>Given all of this, try and figure out a ranking system based on occurrence of solutions and heuristics to determine a candidate solution.</p>
    singulars
    1. This table or related slice is empty.
    1. POHow to approach a number guessing game (with a twist) algorithm?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USBryan Menard
    1. USBryan Menard
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUndeletion
    1. COYou should give a proof that it is NP-hard ...
      singulars
      1. PO
      1. USFoo Bah
    2. COI will try to tomorrow, but I'm not too good at formal proofs. However, I can safely say that the problem looks like an optimisation problem, which is more often than not NP rather than P.
      singulars
      1. PO
      1. USBryan Menard
    3. COI finally removed the NP-hard assumption (and refactored my answer a great deal), since I initially though the problem was an optimization problem. The problem might still be of NP-*something* complexity, but I'm not certain.
      singulars
      1. PO
      1. USBryan Menard
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload