Guess number with lower or higher hints

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):

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

StackExchange Code Review Q#154655, answer score: 6