How did you come up with this logic

[spiritualbeingm]

First of all, thanks for posting the solution here on github really helped me out while trying the exercise from the book. I tried doing this question of guessing the number by asking various questions, but they were a lot and I could not get that done in not more than 7 tries.

So would love to know what was your approach, while writing the code for this exercise question I mean the thought process which brought you to apply this logic.

Thanks

[bewuethr]

Hi @spiritualbeingm, which task specifically are you referring to?

[spiritualbeingm]

Hello,
I was referring to chapter 4 task no 6 as posted in solutions by you.
I would love to know how you arrived at this specific logic before writing the code.

[bewuethr]

Just to make sure we're talking about the same thing: task 6 in chapter 4 of the first edition of the book reads

6. Make a vector holding the ten string values "zero", "one", ... "nine". Use that in a program that converts a digit to its corresponding spelled out value; e.g., the input 7 gives the output seven. Have the same program, using the same input loop, convert spelled-out numbers into their digit form; e.g., the input seven gives the output 7.

That doesn't sound like a number guessing game. Did you mean exercise 4 in chapter 4?

4. Write a program to play a numbers guessing game. [...]

[bewuethr]

Ah, I read the original question again – this has to be about exercise 4, where you have to write a program to guess a number between 1 and 100 in at most 7 guesses.

The idea is that you always cut the range containing the secret number in half. The first guess is 50; if the answer is larger, then the new range is 51-100; if it is smaller, the new range is 1-49.

Say the secret number is 78. This is what the algorithm does:

#	Range	Guess	Answer	Next guess
1	1-100	50	larger	50 + 25 = 75
2	51-100	75	larger	75 + 13 = 88
3	76-100	88	smaller	88 - 6 = 82
4	76-87	82	smaller	82 - 3 = 79
5	76-81	79	smaller	79 - 2 = 77
6	76-78	77	larger	77 + 1 = 78
7	78-78	78	correct	n/a

Notice how the size of the range roughly behaves like 100, 50, 25, ..., until it is 0; this is controlled with the number that is being added to the current number, which is taken from the differences vector, containing the values cutting the range in half (rounded to an integer). This is more or less a binary search.

Because continuously dividing 25 by 2 brings us down to 1 in less than 7 steps, we should always be able to guess the number in 7 steps.

The algorithm and implementation are far from perfect:

• Instead of having the step sizes explicit in differences, we could calculate the next step size as we go with something like step /= 2.
• If the user cheats, the program loses; if we kept track of the range, we would be able to know for sure when the user contradicts something they said earlier.

Hope this helps!