4
\$\begingroup\$

Problem statement

Two players - Alice and Bob. Alice needs to guess a number \$n\$, from range \$[1, N]\$, \$N \le 200\$

  • In \$i\$th turn, Alice guesses a number \$i\$
  • Bob chooses to tell the relation between \$i\$ and \$n\$ (\$n \lt i\$, \$n = i\$ or \$n \gt i\$). Bob could tell what he wants, unless it conflicts with what he says before
  • Each turn costs \$i\$
  • Alice wants to minimize the total costs
  • Bob wants to maximum the total costs

What is the minimal cost if both players take the best strategy?

Any performance improvement ideas in terms of algorithm time complexity, code bugs or code style advice is appreciated.

More specific question: I do not know how Bob could make sure there is no conflict to what he said in the past -- if he tells number wrong at one time. For example, if \$n\$ is 20, Alice guess \$i\$ = 50, if Bob tells alice \$i\$ is smaller (Bob lies), then Alice will always guess a number > 50, how could Alice achieve the final goal? I think Bob could lie, but finally he should help Alice achieve the final goal, even if in the middle Alice may take more steps (more costs) -- because of some conclusion Bob tells in the middle is not correct.

If anyone have any ideas about how Bob could lie (which will maximum cost for Bob as one goal), while at the same time he still make sure no conflict in the future (and finally guide Alice to the right number), it will be great.

The major ideas of my code is, I try to use Dynamic programming approach to build dp structure from bottom up, dp[(i,j)] means for numbers start from i and ends with j, what are minimal cost for Alice. Both i and j are inclusive.

import sys
from collections import defaultdict
class Solution(object):
    def getMoneyAmount(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = defaultdict(lambda : sys.maxint) # key: tuple (start, end), value: min cost
        for end in range(1, n+1):
            for start in range(end, 0, -1):
                if start == end:
                    dp[(start, end)] = 0
                elif start + 1 == end:
                    dp[(start, end)] = start
                else:
                    for d in range(end-1, start, -1):
                        dp[(start, end)] = min(dp[(start, end)], d + max(dp[(d+1, end)], dp[(start, d-1)]))

        return dp[(1, n)]
if __name__ == "__main__":
    s = Solution()
    print s.getMoneyAmount(10)
\$\endgroup\$
6
\$\begingroup\$

If I were Alice, the most optimum strategy, well, there are two. The binary search, or in Python is the bisection method, or I would use the Fibonacci method, which is mathematically superior and faster than the binary search method.

Anyway, that would be what Alice would have to do to get to the number in the least number of guesses.

Bob, on the other hand, should make the number a floating point, say with four of five decimal places. Your original question did not state either integer or floating point.

Trying to guess a floating point number is harder. Try to figure out what the \$\sqrt{32}\$ is. It is not an even square, so in math, without a program or calculator, you really need to use the brute force method. However, unlike guessing a number between 1 to 200, here you can get a good starting point.

You know the number has to be between the \$\sqrt{25} = 5\$ and \$\sqrt{36} = 6\$. Since 32 is close to the midpoint, you can start at 5.5 (\$5.5^2 = 30.25\$), which still makes it difficult, as you will need to go to at least 4 decimal places for the right answer (\$\sqrt{32} = 5.6569\$).

Bob's strategy will be to make sure the number has some decimal places in it.

This way, Alice may use the binary or Fibonacci method to get to the integer, but will have to start over for the decimal places. She can get to it quick enough, but not as quickly as with just an integer.

Now Alice, if she knows the number can be a floating point, may want to start her guesses with a .5 or .25 at the end of every number. This will shorten the guesses for when she gets \$5.25 \gt i\$, but \$5.5 \lt i\$.

You can find the Fibonacci method and algorithm here. I could not find a corresponding Python function, but it is similar to the binary search, except you use just the Fibonacci numbers to narrow down your search.

What I was going to say about Bob picking a fractional number (floating point) instead of just an integer, he doesn't have to lie when Alice guesses 5 and Bob says GT and when she says 6 he says LT. Now it is up to Alice to realize she's dealing in decimals.

Bob maximizes his chances by using decimals. However, if Alice suspects this, she can always start off with a .5 or .25 at the end of every number. She can still minimize her guesses this way, as she needs to get to the integer first. With adding a decimal to it, she has a head start at guessing the decimal number.

Edited on 2/8/2017: I though more about your question and about looking at how, if I were Bob, I could optimize my chances to maximize my costs without violating bullet point #2.

Besides using decimals, or even if just using integers, Bob could give more details that would not only be true, it could be misleading Alice as well.

Let's say Bob picks 30 as his number, and Alice starts her guess with 100, the midpoint in a Binary search pattern.

If Bob believes that she is using this, instead of saying her guess was greater than the number, he could say it is greater than by at least 10! This is not a lie, but if Alice decides to stick to the Binary search, it Change her next mid-point guess.

Instead of guessing 50, which she would if he had just said her guess was greater than, she knows his number is between 1 and 90. Instead, she guesses 45.

You may think that oh, no, she's actually closer, but it now all depends on what Bob now says. He has a choice, but what ever he says next will in no way be in conflict nor even contradict what he has said before. And can increase the number of guesses she makes, which is his goal.

If I were Bob, I would want Alice to make her next guess far enough away from his number that her third choice will be what optimizes his chances.

Bob can say, Guess is greater than. He's not obligated to say anything more and in no way is in conflict with what he as said so far.

Now is where Alice is on the hook. She has to guess a number between 1 and 44.

If she just got the GT or LT answers, her guesses would be 100, 50, 25.

Now she, if she sticks with the binary method, has to go with 22, and that is 3 away from her normal guess of 25.

Now, if you can see how this plays out, Bob can say her guess is less than, and see if he gets her to make more guesses if he adds to what he says.

This is a simplistic approach, but with some more thought, Bob could probably anticipate this, find the right number that would be far enough away to cause Alice to make one or more guesses than she would normally have. Becaus there will come a time where she will guess in increments of one, and Bob needs her to have extra guesses due to his word manipulation.

Without working on a formula and computer program, which I can do, I could show how this would play out and find that one or more magic numbers, probably a prime number (just a guess right now but sounds logical) that will increase Alice's cost and optimizes Bob's costs.

Let me know if this does it for you, or if anyone else has improvements on or another way Bob can perform his optimization.

Let me know if you want me to work on a program.

Edited on 02/17/2017: My original formula in the comments was just a starting point. It failed when a second or more guess was given.

After writing a few formulas into a computer program and executing them, along with manual calculaton, the following formula shows that no matter what answer Bob gives, there is always a relationship given to Alice between his chosen number and her guess.

And while Alice may not be able to use this formula to get the answer quickly, according to the rules set in the question, there is no misunderstanding of the rules, which states that Bob can give any answer as long as it does not conflict with any others given prior.

I believe that I demonstrated that in word/pseudo form that by giving Alice not only a GT/LT/EQ answer, he can add a hint that minimizes his payout, and still gives Alice a truthful answer.

In addition, if Bob qualifies his answer by saying "your guess is at least 30 greater than," if Alice was to guess a number that was 35 less than her last one, and it is still greater than Bob's number, Bob would not be in conflict if he said Alice's second guess was still greater than. The reason is he said "at least." That could mean his number is 100 less than Alice's guess. There is no conflict there, as Alice should be familiar with Number Theory and even Mathematical Logic.

Regardless of Bob's number of Alice's guess, I have come up with this formula that will always show that Bob always gives the relationship to his number based on Alice's guess.

It is expressed as (Total Numbers - Bob's Number - Bob's misdirection) is equal to (Total Numbers - Alice's Guess - Bob's misdirection)±X

In this simple equation, Alice's Guess ±X will always be the inverse of Bob's number, and when added to Alice's guess will equal Bob's number.

Formula: (T-N-B)=(T-G-B)±X

Let's run some examples: T=200, N=44, B=0. G=150.

(200-44-0)=(200-150-0)±X
156=50±X
X=106
G-X=N
150-106=44

Of course, we can simplify the formula using algebra as: N=G±X

N=47, G=50
47=50±X
X=-3

Done with the full formula:

(200-47-0)=(200-50-0)±X
47=50±X
X=-3
47=50-3
47-47

Regardless of the number picked and the guess, a relationship with each number is always established.

One last where Bob says that Alice's guess is greater than by 25. Bob guesses 12. Alice guesses 60.

(200-12-25)=(200-60-25)±X
163=115±X
163=115+48
163=163

Now, to get to Bob's answer, since he said Alice's guess is greater than, we need to SUBTRACT X from G.

G-X=N
60-48=12

Any answer Bob gives, whether or not he adds an addition, which by the rules set in this question is perfectly legal, always shows the relationship between the number selected and the guess made.

\$\endgroup\$
  • 2
    \$\begingroup\$ The way the problem statement is formulated (using n as the number to guess) suggests to me that it has to be an integer (even though you are right and it is not clearly defined). \$\endgroup\$ – Graipher Feb 7 '17 at 6:28
  • 3
    \$\begingroup\$ And you can use LaTex here, see the edits by Jama. Basically you write \$ instead of $ for inline math. \$\endgroup\$ – Graipher Feb 7 '17 at 6:30
  • 1
    \$\begingroup\$ Thanks @Graipher for the tip on LaTex. I'm actually new to posting links and such so It was very helpful when Jama did edit my post. I got to see how it was done as the help isn't quite right. And n is "type n: int" but I am not sure it was there when I started writing my post. I may have missed it as I have been learning Python. Of the 50+ years in computer science, my last 15 were webservers and intranets and networked servers, and I never really learned Python. Was always a PERL, VBScript/ASP and PHP coder. It's getting exciting out there again. \$\endgroup\$ – George McGinn Feb 7 '17 at 11:06
  • 1
    \$\begingroup\$ @LinMa No, and that is because of the way binary searches work. You just get so many guesses before the answer is known, and that is a mathematical certainty. So the number he uses must be fractional. \$\endgroup\$ – George McGinn Feb 9 '17 at 20:56
  • 1
    \$\begingroup\$ @LinMa BTW: Fibonacci numbers are a factorial number. So I like number lines, but instead, let's look at the 1st 20 Fib Numbers: 0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765. So for your second comment, the first 13 numbers are less than 200. And the longer the string of Fib numbers, the larger they grow very quickly. That makes those statements both true in that the numbers in your problem are uniform, but are low enough that the Fibonacci search works a little better than the binary. Once the numbers > 200, then the non-uniformity should be self-evident. \$\endgroup\$ – George McGinn Feb 9 '17 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.