droneKingxiiiiiiiDaddy's blog

By droneKingxiiiiiiiDaddy, history, 8 years ago, In English

Hi guys ! Please provide editorial for this problem : Interactive Bulls and Cows (Hard)

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

u can just google it u know..

»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

In total there are 5040 (=10*9*8*7) different possible solutions. You can put them all into a list. We have too make sure, that each solution can be guessed in a total of maximal 7 moves.

The choice of the guesses matter a lot. A bad guess would be 0000. Because if the response is 0 0, than you still have 3024 possible solutions in your list, which is way too many. In the worst case (if the solution doesn't contain a zero) we will probably not be able to determine the solution with the remaining six guesses.

A much better first guess would be 0011. If the response is 0 0, only 1680 possibilities remain in your list. If the response is 0 1 only 1344, and with the responses 0 2, 1 1 or 2 0 only 224 remain. Therefore in the worst case we can still eliminate 66.6% of all the entries in our list.

With each guess we want to eliminate as many possible solutions of our list as possible. But since the approach should always work, we have to make sure that we eliminate as much as possible if we receive the worst bulls/cows response.

So how do we compute a good guess? Simply by simulating. For each possible guess, compute how many in the list survive for each possible response. Choose the guess, where the maximal list size under all responses is minimal.

Here is my solution: 23398322. The code is not beautiful at all. In the vector left I keep all answers, that are still possible. The function choose_best does the simulation and function guess prints a guess, reads the bulls/cows response and updates left.

Such an approach is also known as MinMax-Algorithm. However MinMax often simulates the complete game (What is the best move, so that with the opponents best move and my best response after it and his best response, ... lets me win.) But this is not necessary here. Only simulating the first move and all possible bulls/cows responses is enough to always find the answer in 7 guesses.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Can you please explain why is it necessary to include the this condition while rejecting ? That is why should we include num when it produces same left vector size and is present in the left also.

    Condition-> "else if (worst == worst_result && count(left.begin(), left.end(), num)) { best = num; }".

    I really like your solution so simple to understand and with such a clean implementation.This is the only solution i found which does not use randomization and is deterministic.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't think that it is really necessary. It probably also works without it.

      I guess the intuition for it is, that if the guess is one of the remaining possible solutions, then there is a small chance that we actually guess correctly and finish early. If the guess is no longer possible, then there is zero chance of finishing early.