Exchanging data variables?

[chopnhack]

This is homework so no spoilers please!

The goal of the assignment is to create a program to guess your secret number from 0(inclusive)-100(not inclusive). I have made some headway, but I am having trouble creating a proper iteration that will collect the response and then based on the three possible scenarios of 'h' - high guess, 'l' - low guess (lowercase L) or c - correct guess do three different tasks.

If the guess is 'h' or 'l' I would need to iteratively guess by bisection search.

It's supposed to look like this in practice:

Is your secret number 91?
Enter 'h' to indicate the guess is too high. Enter 'l' to indicate the guess is too low. Enter 'c' to indicate I guessed correctly. y
Sorry, I did not understand your input.
Is your secret number 91?
Enter 'h' to indicate the guess is too high. Enter 'l' to indicate the guess is too low. Enter 'c' to indicate I guessed correctly. c

This is the code that I have produced so far - note the variables have not been cleaned up - as I started writing I tried one method and used some variables and tested other methods so the variables have grown.

choice = 0
guess = 50
win = 0
y = 100
hi = y
x = 0
lo = x

print 'Please think of a number between 0 and 100!'
print 'Is your secret number 50?'
while (win != 1):
      choice = raw_input('Enter "h" to indicate the guess is too high. Enter "l" to indicate the guess is too low. Enter "c" /
                to indicate I guessed correctly. ')
      if choice == 'h':
         guess = ((guess+lo)/2)+1
         print guess
      if choice == 'l':
         guess = ((guess+hi)/2)-1
         print guess
      if choice == 'c':
         print 'Game over. Your secret number was: ', guess
         win += 1
         break

if choice != 'h' or 'l' or 'c':
print 'Sorry, I did not understand your input.'

As you can see I am having trouble with setting up the iteration. And handling the data structure. And passing the data back for processing... How should I approach this? Point me in the correct direction if you can or do I need to start from the ground up?

Thanks!!

 

[Harald Kapp]

I'm not familiar with the programming language you use (is it Python?).

Anyway:

The last 2 statements (choice !=..., print...) need to be within the while loop, at the same nesting level (indentation) as the other if statements. You want to check incorrect input each time you run through the loop. By the way, pesonally I'd check for incorrect input first, that's probably a matter of personal style, but I think it's good practice to avoid running onto trouble from incorrect input (unlikely in this simple scheme, bit how about processing more complex input e.g. from a website where someone may attack with malicious intentions?).

The break in the third if statement (choice =0'c') is unnecessary. The loop while terminate with win = 1, which is achieved by win +=1 within this if statement.

Instead of using 0 and 1 for the variable win, I'd prefer to use a boolean variable having values TRUE and FALSE. This makes the code much clearer.

Can you elaborate on your problems with data structures and handling data back for processing? I can't see neither any data structures in your code nor any code that passes data back (except the raw input method).

 

[BobK]

Think of it this way:

You have an upper limit and a lower limit on what the secret number could be. Originally these are 0 and 99. Each guess refines your lower and upper limit, depending on whether your guess is high, low or correct. If coded correctly, those two limits and the next guess should be the only three variables you need.

Bob

 

[Laplace]

Before starting to code, one should become intimately familiar with the algorithm to be implemented. Then make decisions about how to implement its operation. For instance, what should be the starting point, what should be the +/- delta offsets at each bisection? Should the implementation be for a specific range, N=100, or should it be generalized for an arbitrary range? If there is extra credit to be had, then a generalized version should be worth more credit. Attached image shows two possible bisection strategies for N=100.

 

[Gryd3]

This is homework so no spoilers please!

The goal of the assignment is to create a program to guess your secret number from 0(inclusive)-100(not inclusive). I have made some headway, but I am having trouble creating a proper iteration that will collect the response and then based on the three possible scenarios of 'h' - high guess, 'l' - low guess (lowercase L) or c - correct guess do three different tasks.

If the guess is 'h' or 'l' I would need to iteratively guess by bisection search.

It's supposed to look like this in practice:

Is your secret number 91?
Enter 'h' to indicate the guess is too high. Enter 'l' to indicate the guess is too low. Enter 'c' to indicate I guessed correctly. y
Sorry, I did not understand your input.
Is your secret number 91?
Enter 'h' to indicate the guess is too high. Enter 'l' to indicate the guess is too low. Enter 'c' to indicate I guessed correctly. c

This is the code that I have produced so far - note the variables have not been cleaned up - as I started writing I tried one method and used some variables and tested other methods so the variables have grown.

choice = 0
guess = 50
win = 0
y = 100
hi = y
x = 0
lo = x

print 'Please think of a number between 0 and 100!'
print 'Is your secret number 50?'
while (win != 1):
      choice = raw_input('Enter "h" to indicate the guess is too high. Enter "l" to indicate the guess is too low. Enter "c" /
                to indicate I guessed correctly. ')
      if choice == 'h':
         guess = ((guess+lo)/2)+1
         print guess
      if choice == 'l':
         guess = ((guess+hi)/2)-1
         print guess
      if choice == 'c':
         print 'Game over. Your secret number was: ', guess
         win += 1
         break

if choice != 'h' or 'l' or 'c':
print 'Sorry, I did not understand your input.'

As you can see I am having trouble with setting up the iteration. And handling the data structure. And passing the data back for processing... How should I approach this? Point me in the correct direction if you can or do I need to start from the ground up?

Thanks!!

When I do things like this, I usually write in comments first, then fill in the functions and variables. It helps me to narrow down what needs to happen. It also helps to manually write out the first 2 or 3 iterations by hand how you would solve this puzzle then write the program to solve in this way... This way you have an expected output that you can compare your program's output to.

In any case, there are some tweaks you can make. As mentioned above, you can trim down the amount of variables being used.
I would urge you to dig into the 'else' statement, as well as making sure your values are returned as whole numbers without a decimal point. (I wrote something similar on my TI-84 a while back to provide a method of working backwards from a specific key function... It would run indefinitely and output the most recent match. The longer it ran, the more decimal points it would solve for )

In any case, I'd like to see you make notes first. How would you instruct a human to do it?

 

[chopnhack]

You gents are the best!! Thank you all. I will try some variants of what you all are suggesting and come back and let you know where I am at. Harald - specifically the problem I am having is being able to get an input, depending on what that is, do a specific loop that takes a value, does an operation and then takes the value from this computation and uses it in the next computation if there is one required. I have seen very elegant examples that the teacher has done, but none are forming for me yet!

@BobK - thanks!! I might be on to something here!! 0<= x < 100

 

[chopnhack]

No go, there was a spark, but it fizzled...

@Gryd3 - If I had to explain to another person what I was doing or how I thought the program should work:

1. Ask for the player to think of a number from 0-100.
2. Ask if the # is the 1/2 way point of our range (call it variable guess)
3. Let player know rules, 'h' for high, if the guess is not high enough, 'l' for guess too low and 'c' for guess is correct
   
4. Wait for player to input - if input is not 'h', 'l' or 'c' - say sorry I didnt understand and then loop back to waiting for input
   
5. If 'c', guess is correct, print game over, your # is guess
6. If either 'h' or 'l', (work in progress), test secret # against mid point, if too lo, test from guess to max and divide by 2. If hi, test guess to min and divide by 2

 

[Gryd3]

No go, there was a spark, but it fizzled...

@Gryd3 - If I had to explain to another person what I was doing or how I thought the program should work:

1. Ask for the player to think of a number from 0-100.
2. Ask if the # is the 1/2 way point of our range (call it variable guess)
3. Let player know rules, 'h' for high, if the guess is not high enough, 'l' for guess too low and 'c' for guess is correct
   
4. Wait for player to input - if input is not 'h', 'l' or 'c' - say sorry I didnt understand and then loop back to waiting for input
   
5. If 'c', guess is correct, print game over, your # is guess
6. If either 'h' or 'l', (work in progress), test secret # against mid point, if too lo, test from guess to max and divide by 2. If hi, test guess to min and divide by 2

Sounds good. Add another step or two for additional guesses. The first guess is easy to type out

 

[BobK]

Your problem is at step 6. What can you do at that step that allows you to back to step 2 and have the process eventually stop with the correct answer?

Bob

 

[chopnhack]

Your problem is at step 6. What can you do at that step that allows you to back to step 2 and have the process eventually stop with the correct answer?

Bob

This is where I get stuck guys - its supposed to be a guess and check pattern based on bisection. So, the variable starts at 50 - they were merciful here... but there are two possible choices that can cause a change to this variable the third causes the program to cease.

If we could use x<= guess < z as the check statement but have guess and the limits rebind each time the pattern has to be repeated with the new values... that might work.

 

[Gryd3]

This is where I get stuck guys - its supposed to be a guess and check pattern based on bisection. So, the variable starts at 50 - they were merciful here... but there are two possible choices that can cause a change to this variable the third causes the program to cease.

If we could use x<= guess < z as the check statement but have guess and the limits rebind each time the pattern has to be repeated with the new values... that might work.

Well, There was a tip dropped further up. Think of it this way.
Your choice can be 0 - 99 (Inclusive)
So you guess 50. Which is simply (Max-Min)/2
If the guess is too low, the next guess should be 75, correct? How can we modify the (Max-Min)/2 equation so that we can simply change one piece of it and re-use it? (Note, we can either rewrite a completely new formula for subsequent guesses, or we can make some modifications to the existing formula to make it work with all guesses including the first)
I'm being difficult on purpose

So... how about you write the formula for the second guess.
Remember that your first guess is between Min and Max.
For all subsequent guesses...
If Guess > HiddenNumber Then "HiddenNumber must be between Min and Guess"
ElseIf Guess < HiddenNumber Then "HiddenNumber must be between Guess and Max"
ElseIf Guess = HiddenNumber Then "Problem Solved!"
Else "Some Error has occurred..."


Edit: If I'm too vague, speak up! I don't want to give you the answer, but I also want to be transparent enough for it to click into place for you without relying on provided code. Let me know and I can try to tailor my answers accordingly.

 

[chopnhack]

Well, There was a tip dropped further up. Think of it this way.
Your choice can be 0 - 99 (Inclusive)
So you guess 50. Which is simply (Max-Min)/2
If the guess is too low, the next guess should be 75, correct? How can we modify the (Max-Min)/2 equation so that we can simply change one piece of it and re-use it? (Note, we can either rewrite a completely new formula for subsequent guesses, or we can make some modifications to the existing formula to make it work with all guesses including the first)
I'm being difficult on purpose

So... how about you write the formula for the second guess.
Remember that your first guess is between Min and Max.
For all subsequent guesses...
If Guess > HiddenNumber Then "HiddenNumber must be between Min and Guess"
ElseIf Guess < HiddenNumber Then "HiddenNumber must be between Guess and Max"
ElseIf Guess = HiddenNumber Then "Problem Solved!"
Else "Some Error has occurred..."


Edit: If I'm too vague, speak up! I don't want to give you the answer, but I also want to be transparent enough for it to click into place for you without relying on provided code. Let me know and I can try to tailor my answers accordingly.

No, you probably have laid it out pretty clearly... I think my brain stopped processing a few hours ago..the body is too stupid to realize it and thinks it can continue - I will sleep on it, its been >18 hours since my last recharge anyway

Thanks Gryd3

 

[Laplace]

If instead of doing a programmed integer tree search, and the bisection strategy is a calculated narrowing of the range, then the solution could converge faster if the range was narrowed from both sides. In that case, whenever the guess is high the new maximum value of the range is set equal to the guess and whenever the guess is low the new minimum value of the range is set equal to the guess. So the extreme terminal case will be min=(N-1), max=(N+1), and N=(correct guess), and the next guess value would be calculated as guess=(min+max)/2=N. Except in the case where {N=0, min=0, max=1} or {N=99, min=98, max=99} where calculating the next bisecton guess may be problematic depending upon the roundoff behavior of the integer arithmetic engine, or it could be a special exception that is tested for and handled separately. But I would investigate extending the initial range by -1 or +1 depending on the integer roundoff behavior when dividing by 2.

 

[chopnhack]

If instead of doing a programmed integer tree search, and the bisection strategy is a calculated narrowing of the range, then the solution could converge faster if the range was narrowed from both sides. In that case, whenever the guess is high the new maximum value of the range is set equal to the guess and whenever the guess is low the new minimum value of the range is set equal to the guess. So the extreme terminal case will be min=(N-1), max=(N+1), and N=(correct guess), and the next guess value would be calculated as guess=(min+max)/2=N. Except in the case where {N=0, min=0, max=1} or {N=99, min=98, max=99} where calculating the next bisecton guess may be problematic depending upon the roundoff behavior of the integer arithmetic engine, or it could be a special exception that is tested for and handled separately. But I would investigate extending the initial range by -1 or +1 depending on the integer roundoff behavior when dividing by 2.

Laplace, I thought I understood where you were going with this, it seemed familiar - is it the Newton - Raphson approach? I haven't learned that well yet. I tried to construct code using your variables, but I didnt understand the argument "guess=(min+max)/2=N" - Can you double assign like this? My IDE gave an error so I set guess to equal N on the following line. Not withstanding, variables min + max resolves to [N-1] + [N+1] which is simply N, there is no change, my output stays at 50 if I use this for code.

Did I misunderstand how you intended the algorithm to work?
The purpose is to rebind the new limits, I get that and that is central to making the algorithm work. Can you elaborate a little further while I work on the other method?
Thanks!!

 

[chopnhack]

Well, There was a tip dropped further up. Think of it this way.
Your choice can be 0 - 99 (Inclusive)
So you guess 50. Which is simply (Max-Min)/2
If the guess is too low, the next guess should be 75, correct? How can we modify the (Max-Min)/2 equation so that we can simply change one piece of it and re-use it? (Note, we can either rewrite a completely new formula for subsequent guesses, or we can make some modifications to the existing formula to make it work with all guesses including the first)
I'm being difficult on purpose

Fresh eyes - You are saying that when guess is too low, I should rebind (Max-Min)/2 (which is 50) to Min creating the next of 100+50/2 = 75 - which is what I thought I did above with guess=guess+hi/2 - but I need to swap out one of the guess variable for another variable so the value can pass between them instead of resetting the guess value. I think I see it - I will have to develop the thought further this afternoon

Edit: If I'm too vague, speak up! I don't want to give you the answer, but I also want to be transparent enough for it to click into place for you without relying on provided code. Let me know and I can try to tailor my answers accordingly.

Not at all, I think you are being brilliant, its much harder to coach someone on than it is to simply spill the beans, so I thank you very much for your time and efforts!!!

 

[BobK]

So you started with a max of 0 and min of 99.

Your guess should be the middle of the range which is (max + min) / 2 which is 49 (not 50 because of truncation in integer divides). Call this number guess.

So, say the user says guess (49) is too high. Then you know that the number cannot be 49 or any number higher than 49. So how should you update max and min to reflect this new range?

Same for if the user says it is too low. In this case you know it cannot be 49 or any number lower than 49. How do you update min and max to reflect this new range?


Extra credit: This method is known as a binary search. Binary, because each iteration cuts the possibilities in half. So, if the range is 0 to 99, what is the maximum number of guesses it will take?

Bob

 

[Gryd3]

Fresh eyes - You are saying that when guess is too low, I should rebind (Max-Min)/2 (which is 50) to Min creating the next of 100+50/2 = 75 - which is what I thought I did above with guess=guess+hi/2

Don't forget your brackets!
100+50/2 != 75
(100+50)/20 = 75

I will have to develop the thought further this afternoon

Of course. I'll take a look when you post it.

Remember that your existing program branches off based on the user's response on high, low, or correct. You could easily use this to rebind your Min or Max value

 

[Laplace]

"guess=(min+max)/2=N" - Can you double assign like this?

Actually, that was not code - it was just saying that if the number you are looking for, 'N', has not been guessed yet, then the final condition will be that the lower limit 'min' will have converged to the value (N-1) and the upper limit 'max' will have converged to the value (N+1). So in that case the average of 'min' & 'max' will be 'N'.

I have no idea what any of these algorithms might be named, if they have a name. But I'm fairly certain that in their normal application they are not constrained by integer arithmetic. FWIW, in doing a tree search I would not do division arithmetic at all but instead store the delta offsets in an array variable and increment the index value for each iteration of finding the next guess.

 

[chopnhack]

So you started with a max of 0 and min of 99.

Your guess should be the middle of the range which is (max + min) / 2 which is 49 (not 50 because of truncation in integer divides). Call this number guess.

So, say the user says guess (49) is too high. Then you know that the number cannot be 49 or any number higher than 49. So how should you update max and min to reflect this new range?

Same for if the user says it is too low. In this case you know it cannot be 49 or any number lower than 49. How do you update min and max to reflect this new range?


Extra credit: This method is known as a binary search. Binary, because each iteration cuts the possibilities in half. So, if the range is 0 to 99, what is the maximum number of guesses it will take?

Bob

I think I see it!!!!

mini = 0
maxi = 100
guess = (mini+maxi)/2
win = False

print 'Please think of a number between 0 and 100!'
print 'Is your secret number %d?' , guess
          while (win == False):
          choice = raw_input('Enter "h" to indicate the guess is too high. Enter "l" to indicate the guess is too low. Enter "c" to indicate I guessed correctly. ')
               if choice == 'h':
                 maxi = guess
                 guess = (mini+maxi)/2
                 print 'Is your secret number %d?' , guess
              if choice == 'l': 
                 mini = guess
                 guess = (mini+maxi)/2
                 print 'Is your secret number %d?' , guess
              if choice == 'c':
                 print 'Game over. Your secret number was: ' , guess
                win = True

This passes the test, however, I am having trouble with my error checking routing when incorrect entries are made. If I put the "
if choice != 'h' or 'l' or 'c':
print 'Sorry, I did not understand your input.'
"
code in the while loop I get unanticipated recursions of the printed statement. If I put it at the end, it will print with the correct choice 'c' Game over statement.
Any logic to that issue? I want the test to be performed each time, a scan of the input to ensure input is in the valid range. It seems to be picking up the statement generated after an authorized keystroke (like 'h', 'l' or 'c'), "Is your secret number" or the following statement "Enter 'h'..."

@BobK - I had reasoned 7, after running the test a few times 6 seems to be the number required to get to the answer, 7 if you include the initial guess.

 

[Gryd3]

Actually, that was not code - it was just saying that if the number you are looking for, 'N', has not been guessed yet, then the final condition will be that the lower limit 'min' will have converged to the value (N-1) and the upper limit 'max' will have converged to the value (N+1). So in that case the average of 'min' & 'max' will be 'N'.

I have no idea what any of these algorithms might be named, if they have a name. But I'm fairly certain that in their normal application they are not constrained by integer arithmetic. FWIW, in doing a tree search I would not do division arithmetic at all but instead store the delta offsets in an array variable and increment the index value for each iteration of finding the next guess.

An array would be a nice way of doing it, but I see two drawbacks:
1) Arrays can be tricky to work with when learning.
2) Limits upper and lower limit to predetermined values. (Would need a formula to autopopulate list, or would need to manually fill it out when adjusting the limits)

The method Chopnhack appeared to have started could work for any combination of min and max values.