Guess 4-digit random number with a testing function


  • 0
    D

    You are given a 4-digit random number ranging 1111-6666. Your task is to guess the number. There is a test function tell you how many digits you've guess correctly. Write the strategy and a program to determine the worse case tries needed to find the right number.


  • 0

    @dukeforever said in Guess 4-digit random number with a testing function:

    You are given a 4-digit random number ranging 1111-6666.

    Neat, then I'll just "guess" that number :-)


  • 0
    D

    @StefanPochmann Is it tough or too easy for you? Lol


  • 0

    @dukeforever I assume you mean the problem you meant to ask? Don't know, didn't think about that yet. Just wanted to point out that it's probably not a good idea to give me the number that I'm then supposed to guess.


  • 1
    D

    I found it to be difficult. Here is what I can think of:

    Use 1111,2222,3333,4444,5555 to test and see what are the results. But I don't know how to proceed then.


  • 1
    P

    @dukeforever You can get to know the digits in the number by comparing it with 1111, 2222, 3333, 4444, 5555. Then you know that the number is a permutation of these digits.

    In worst case, u can try all the 4! permutations of these digits.

    If you want to improve upon his, try looking into the following facts:

    Try all rotations of a permutation, record the results.
    Note here, sum of results should be 4.
    The results will either be a permutation of either {0, 0, 0, 4} or {1, 1, 2, 0}
    In the first case, you already know the result.
    In the second case, you have 4*2 candidates. You can try all.

    So, with this approach, worst case tries will be 5 + 4 + 4*2 = 17.


  • 1
    L

    @PriyamSirohi ,

    I think it can be done with less than 17 tries.

    As you said, doing the first round of comparison you already know what are the numbers. We can test each number, for each position, using one of the unused numbers as the "filler", e.g.:

    Suppose we checked and it has the numbers 1,2,4,5

    We then can do:
    1333, 3133, 3313, 3331 > Figure the position of number 1
    Then
    233, 323, 332, > figure the position of 2
    Same thing for 4
    43, 34,
    By exclusion, we know where 5 is

    In this case, we will need 5 + 4 + 3 + 2 = 14 guesses on the worst case


  • 4

    I claim we can know the secret within 9 guesses. For convenience I'm going to assume we are guessing a string of 4 letters chosen from {A, B, C, D, E, F}. Also, sometimes the remaining possibilities is low and I omit the details.

    Guess AAAA BBBB CCCC DDDD. Your next guess is going to be either EEEE or of the form XXYY. Here, eg. [AAB] denotes that we know there is two A's, one B, no C's, and no D's in the final answer. Let's say +N to mean that we need at most N additional guesses.

    When we know there is say, exactly one A and exactly one B, then guessing AABB has 4 states where you get result 0, 4 states where you get result 1, and 4 states where you get result 2, all of which are easy to find ways to distinguish within 2 additional guesses. This is what I mean by "place AB in +3".

    [AAAB]: 4 possibilities = +2.
    [AAA]: Guess EEEE, then it becomes like [AAAB], so +3.
    [AABB]: 6 possibilities = +3.
    [AABC]: Guess BBCC, +3.
    [AAB]: Guess AABB, +4.
    [AA]: Guess EEEE. Now it's like [AABB] or [AABC] which are +3, so answer +4.
    [ABCD]: Place AB in +3, now distinguish C and D in +1, answer +4.
    [ABC]: Place AB in +3, now find C in +1 and distinguish E/F in +1, so answer +5.
    [AB]: Place AB in +3. Now from the remaining places it's the four possibilities EE EF FE FF, so answer +5.
    [A]: Guess EEEE. It's either like [AAAB] or [AABC], so answer +4.
    []: Guess EEEE. It's either like [EEEE] (+0), [EEEF] (+2), [EEFF] (+3), so answer +4.


  • 0
    P

    @awice Hey, do you have sample code?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.