CODEWITHSUNDEEP
algorithm
Xantix
Xantix

Reputation: 3331

Guess the Subset Strategy

Guess the Subset Game

The game works like this. You play against an adversary.

Setup

Objective

You know A and k, and your job is to figure out the subset by making guesses.

Guessing

You guess a subset B.

The adversary tells you Yes if B ⊆ S (i.e. if all of the elements that you guessed are in the secret subset S) and No otherwise.

Question

What strategy can you use to figure out the subset in the fewest number of guesses?

Playable Version You can play the game here. Choose A and k, and you can make guesses. Reveal the Secret when you think you have it figured out. Re-run the snippet to try again.

// Random Integer in [min, max)
const getRandomInt = (min, max) => {
  min = Math.ceil(min);
  max = Math.floor(max);
  return Math.floor(Math.random() * (max - min)) + min;
};

class GuessSubsetGame extends React.Component {
  constructor(props) {
    super(props);
    this.state = {
      numGuesses: 0,
      guess: '',
      prevGuesses: [],
      revealed: false
    };
  }
  
  isValid = (guess) => guess
     .split(',')
     .map(val => val.trim())
     .every(element => this.props.secret.includes(element)) ? 'Yes' : 'No';
  
  onSubmit = (e) => {
    this.setState((state, props) => ({
      guess: '',
      numGuesses: state.numGuesses + 1,
      prevGuesses: [{guess: state.guess, valid: this.isValid(state.guess)}, ...state.prevGuesses]
    }));
    e.preventDefault();
  }
  
  renderPrevGuesses() {
    return this.state.prevGuesses.map(({guess, valid}) => {
      return (
        <div>
          {valid} - {guess}
        </div>
      );
    });
  };
  
  render() {
    return (
      <div>
        {this.state.revealed ? 'Secret was ' + this.props.secret : <button onClick={() => this.setState({revealed: true})} >Reveal Secret</button> }
        <div>
          {'Guess Number: ' + this.state.numGuesses}
        </div>
        <form onSubmit={this.onSubmit}>
          <div>
            <label for="guess">Guess a Subset (like 1,2,3): </label>
            <input 
              type="text" 
              name="guess" 
              id="guess"
              value={this.state.guess}
              onChange={(e) => this.setState({guess: e.target.value})} />
          </div>
          <div>
            <input type="submit" value="Guess" />
          </div>
        </form>
        <div>
          <div>History</div>
          {this.renderPrevGuesses()}
        </div>
      </div>
    );
  }
}

class GuessSubsetGameCreator extends React.Component {
  constructor(props) {
    super(props);
    this.state = {    
      isBuilt: false,
      A: '1,2,3,4,5,6',
      k: 2,
      secret: null
    };
  };
  
  onSubmit = (e) => {
    const actualK = getRandomInt(0, parseInt(this.state.k) + 1);
    const aAsArray = this.state.A.split(',');
    const shuffled = aAsArray.sort(() => 0.5 - Math.random());
    const secret = shuffled.slice(0, shuffled.length - actualK).sort();
    this.setState({
      isBuilt: true,
      secret
    });
    e.preventDefault();
  };
  
  render() {
    let result;
    if (!this.state.isBuilt) {
      return (
        <form onSubmit={this.onSubmit}>
          <div>
            <label for="A">What are the elements of A? </label>
            <input 
              type="text" 
              name="A" 
              id="A" 
              required 
              value={this.state.A}
              onChange={(e) => this.setState({A: e.target.value})} />
          </div>
          <div>
             <label for="k">How many elements can be removed? </label>
             <input 
               type="number" 
               name="k" 
               id="k" 
               required 
               value={this.state.k}
               onChange={(e) => this.setState({k: e.target.value})} />
          </div>
          <div>
            <input type="submit" value="Start Game" />
          </div>
        </form>
      );
    }
    else {
      return <GuessSubsetGame A={this.state.A} secret={this.state.secret} />
    }
    return result;
  }
}

ReactDOM.render(
  <GuessSubsetGameCreator />,
  document.getElementById("root")
);
div {
  padding-top: 5px;
}
<script src="https://cdnjs.cloudflare.com/ajax/libs/react/16.6.3/umd/react.production.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/react-dom/16.6.3/umd/react-dom.production.min.js"></script>

<div id="root"></div>

Thoughts

Upvotes: 2

Views: 243

Answers (1)

j_random_hacker
j_random_hacker

Reputation: 51226

The following C++ program will report the length of an optimal strategy, computed according to a generalisation of the minimax game tree strategy I mentioned in a comment, and using dynamic programming for speed. It can optionally output a trace showing a maximum-length sequence of queries under this strategy. (It would not be difficult to output the entire tree, but as this could be a nearly complete binary tree with more than 20 levels, it's not very interesting to a human.)

Essentially it turns out that the complete state of knowledge about all elements can be represented succinctly, even if we allow queries that involve elements from multiple different earlier queries. A state of knowledge is represented in the program as a vector in which the first element is k, the second is the number of items in A about which we know nothing (I forgot about this aspect of state in my comment), and all remaining vector elements are the sizes of disjoint "marked" subsets of A, listed in increasing order. A "marked" subset is a subset that we know misses at least one element of S. Knowledge state vectors are always normalised (see the normalise() function). The same vector representation is used for representing a "player move" (a choice of some number of elements from each of the disjoint subsets of A), even though the first element (where k would be) is meaningless in this context.

One surprise was the discovery that there exist worst-case sequences of queries that cause loops in the sequence of knowledge states -- that is, there are query sequences that are infinitely long in the worst case. Fortunately the DP could be adjusted to take care of this.

To run the program, specify k as the first command-line parameter and |A| as the second. To add a traceback showing a particular maximum-length sequence of queries under the optimal strategy, give -t as the first parameter.

For example, running fewest_tests -t 5 30 produces:

Minimum number of queries required in the worst case: 20
One possible maximum-length sequence of queries that follow an optimal strategy:
Height=20.  Knowledge state: [5 30]
Choose [0 3]: Adversary replies YES.  (Other answer also leads to height-19 subtree.)
Height=19.  Knowledge state: [5 27]
Choose [0 3]: Adversary replies YES.  (Other answer also leads to height-18 subtree.)
Height=18.  Knowledge state: [5 24]
Choose [0 3]: Adversary replies YES.  (Other answer also leads to height-17 subtree.)
Height=17.  Knowledge state: [5 21]
Choose [0 2]: Adversary replies YES.  (Other answer also leads to height-16 subtree.)
Height=16.  Knowledge state: [5 19]
Choose [0 2]: Adversary replies YES.  (Other answer also leads to height-15 subtree.)
Height=15.  Knowledge state: [5 17]
Choose [0 2]: Adversary replies YES.  (Other answer also leads to height-14 subtree.)
Height=14.  Knowledge state: [5 15]
Choose [0 2]: Adversary replies YES.  (Other answer also leads to height-13 subtree.)
Height=13.  Knowledge state: [5 13]
Choose [0 1]: Adversary replies YES.  (Other answer leads to height-11 subtree.)
Height=12.  Knowledge state: [5 12]
Choose [0 1]: Adversary replies YES.  (Other answer also leads to height-11 subtree.)
Height=11.  Knowledge state: [5 11]
Choose [0 1]: Adversary replies YES.  (Other answer also leads to height-10 subtree.)
Height=10.  Knowledge state: [5 10]
Choose [0 1]: Adversary replies YES.  (Other answer also leads to height-9 subtree.)
Height=9.  Knowledge state: [5 9]
Choose [0 1]: Adversary replies YES.  (Other answer also leads to height-8 subtree.)
Height=8.  Knowledge state: [5 8]
Choose [0 1]: Adversary replies YES.  (Other answer also leads to height-7 subtree.)
Height=7.  Knowledge state: [5 7]
Choose [0 1]: Adversary replies YES.  (Other answer also leads to height-6 subtree.)
Height=6.  Knowledge state: [5 6]
Choose [0 1]: Adversary replies YES.  (Other answer also leads to height-5 subtree.)
Height=5.  Knowledge state: [5 5]
Choose [0 1]: Adversary replies YES.  (Other answer also leads to height-4 subtree.)
Height=4.  Knowledge state: [5 4]
Choose [0 1]: Adversary replies YES.  (Other answer also leads to height-3 subtree.)
Height=3.  Knowledge state: [5 3]
Choose [0 1]: Adversary replies YES.  (Other answer also leads to height-2 subtree.)
Height=2.  Knowledge state: [5 2]
Choose [0 1]: Adversary replies YES.  (Other answer also leads to height-1 subtree.)
Height=1.  Knowledge state: [5 1]
Choose [0 1]: Adversary replies YES.  (Other answer also leads to height-0 subtree.)
Height=0.  Knowledge state: [5 0]

This takes about 16s on my laptop, and uses about 110Mb. Note that I needed to increase the default stack size (/L on MSVC++); with the default of 1Mb, the largest problem that could be tackled without crashing was 5 23. I increased it to 512Mb to be on the safe side.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <cassert>

using namespace std;

bool verbose = false;

//DEBUG: Enable output of vectors
template <typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
    os << '[';
    for (unsigned i = 0; i < v.size(); ++i) {
        if (i > 0) {
            os << ' ';
        }

        os << v[i];
    }

    os << ']';
    return os;
}

// Call f with every valid choice of items.
template <typename F>
void for_each_choice(vector<unsigned>& v, F f, vector<unsigned>& u, bool takenSomethingYet) {
    unsigned i = u.size();
    if (i == v.size()) {
        // We have chosen amounts to take from every subset.
        if (takenSomethingYet) {
            if (verbose) cerr << "From " << v << " we have chosen " << u << "." << endl;     //DEBUG
            f(u);
        }
    } else {
        // "+ (i == 1)": Only try choosing all the items in a subset for the unknown subset, v[1].
        // "(i <= 2 ... u[i - 1])": For a sequence of equal-size subsets, only choose a nondecreasing sequence of item counts (symmetry).
        u.push_back(0); 
        for (unsigned j = (i <= 2 || v[i] != v[i - 1] ? 0 : u[i - 1]); j < v[i] + (i == 1); ++j) {
            // Try choosing j items from this set
            u.back() = j;
            for_each_choice(v, f, u, takenSomethingYet);
            takenSomethingYet = true;
        }
        u.pop_back();
    }
}

// For convenience.
template <typename F>
void for_each_choice(vector<unsigned>& v, F f) {
    vector<unsigned> u(1, 0);       // First position, where k would be, is ignored
    for_each_choice(v, f, u, false);
}

void normalise(vector<unsigned>& r) {
    if (verbose) cerr << "normalise(" << r << ") called." << endl;       //DEBUG
    // Get rid of all subsets of size 0 or 1.
    unsigned j = 2;
    for (unsigned i = 2; i < r.size(); ++i) {
        if (r[i] <= 1) {
            r[0] -= r[i];       // Decrease k whenever we have a singleton marked subset: its single member must be marked
        } else {
            r[j++] = r[i];
        }
    }
    r.erase(r.begin() + j, r.end());

    // If the maximum possible number of marked elements are already accounted for by disjoint marked subsets, then all "unknown" elements
    // are really known not to be marked.
    if (r.size() == r[0] + 2) {
        r[1] = 0;
    }

    sort(r.begin() + 2, r.end());
    if (verbose) cerr << "Result of normalise(): " << r << "." << endl;       //DEBUG
}

// Return configuration resulting from the adversary saying "yes" to the choice u
vector<unsigned> yes(vector<unsigned> v, vector<unsigned> u) {
    if (verbose) cerr << "From " << v << ", answer YES to " << u << "." << endl;     //DEBUG
    vector<unsigned> r = v;
    for (unsigned i = 1; i < v.size(); ++i) {
        r[i] -= u[i];
    }

    normalise(r);
    return r;
}

// Return configuration resulting from the adversary saying "no" to the choice u
// Note that, because normalise() sets v[1] to 0 if all marked elements are already exhausted by marked disjoint subsets, this function can never
// produce a contradictory knowledge state (that is, one with more than v[0] disjoint marked subsets).
vector<unsigned> no(vector<unsigned> v, vector<unsigned> u) {
    if (verbose) cerr << "From " << v << ", answer NO to " << u << "." << endl;     //DEBUG
    vector<unsigned> r = v;
    r.push_back(0);
    for (unsigned i = 1; i < v.size(); ++i) {
        if (u[i] > 0) {
            r[1] += v[i] - u[i];    // Tricky: In every subset that we chose some elements from, every *unchosen* element goes back in the "we dunno" pile.
            r[i] -= v[i];           // For all i >= 2, this will set r[i] to 0, and this element will be deleted by normalise()
            r.back() += u[i];
        }
    }

    normalise(r);
    return r;
}

// First element is k, the maximum number of marked items.
// Second element is number of items about which we know nothing.
// Remaining items are in sorted order, and are the sizes of disjoint subsets of items: we know that each of these subsets contains at least one marked item.

map<vector<unsigned>, int> memo_;           // Holds solutions already computed
map<vector<unsigned>, vector<unsigned>> nextMove_;      // Holds a best move for already-computed solutions

unsigned solve(vector<unsigned> v) {
    if (verbose) cerr << "solve(" << v << ") called." << endl;      //DEBUG

    auto us = memo_.find(v);
    if (us != memo_.end() && (*us).second == -1) {
        if (verbose) cerr << "solve(" << v << ") returning " << (UINT_MAX - 1) << " because the current state already appeared in the history, indicating an infinite loop." << endl;      //DEBUG
        return UINT_MAX - 1;            // -1 so that it survives the +1 it gets later
    }

    // Because v has been normalised, we have identified all marked states iff there are no unknown elements and no marked subsets.
    if (v.size() == 2 && v[1] == 0) {
        if (verbose) cerr << "solve(" << v << ") returning 0 since no unknown elements could be marked." << endl;      //DEBUG
        return 0;
    }

    if (us == memo_.end()) {
        // Haven't computed the solution to this subproblem yet: do it now
        us = memo_.insert(make_pair(v, -1)).first;      // Tell descendant calls that this state is in the history and would lead to a worst-case infinite loop

        // Generate every possible successor state
        unsigned best = UINT_MAX;
        vector<unsigned> bestMove;
        for_each_choice(v, [&](vector<unsigned> u) {
            unsigned cur = 1U + max(solve(yes(v, u)), solve(no(v, u)));
            if (cur < best) {
                best = cur;
                bestMove = u;
            }
        });

        (*us).second = best;
        nextMove_[v] = bestMove;
    }

    if (verbose) cerr << "solve(" << v << ") returning " << (*us).second << "." << endl;      //DEBUG
    return (*us).second;
}

// You must call solve() first to populate nextMove_[].
void traceBack(vector<unsigned> v) {
    cout << "One possible maximum-length sequence of queries that follow an optimal strategy:\n";
    while (true) {
        unsigned iSteps = solve(v);
        vector<unsigned> u = nextMove_[v];
        cout << "Height=" << iSteps << ".  Knowledge state: " << v << endl;

        if (iSteps == 0) {
            break;
        }

        cout << "Choose " << u << ": Adversary replies ";

        unsigned hYes = solve(yes(v, u));
        unsigned hNo = solve(no(v, u));
        if (hYes == iSteps - 1) {
            cout << "YES.  (Other answer " << (hYes == hNo ? "also " : "") << "leads to height-" << hNo << " subtree.)\n";
            v = yes(v, u);
        } else {
            assert(hNo == iSteps - 1);
            cout << "NO.  (Other answer " << (hYes == hNo ? "also " : "") << "leads to height-" << hNo << " subtree.)\n";
            v = no(v, u);
        }
    }
}

int main(int argc, char** argv) {
    int nArgs = 0;
    bool showTraceback = false;

    if (string(argv[1]) == "-v") {
        verbose = true;
        ++nArgs;
    }

    if (string(argv[nArgs + 1]) == "-t") {
        showTraceback = true;
        ++nArgs;
    }

    unsigned k = atoi(argv[nArgs + 1]);
    unsigned n = atoi(argv[nArgs + 2]);

    vector<unsigned> v(2);
    v[0] = k;
    v[1] = n;

    normalise(v);       // Needed in case k=0.

    cout << "Minimum number of queries required in the worst case: " <<  solve(v) << endl;

    if (showTraceback) {
        traceBack(v);
    }

    return 0;
}

Upvotes: 1

Related Questions