Binary search program (+ quotes glitch, interfaces)

[gerard@dugdill.com]

Two things please:

• For a study project, I had to create a program where the computer guessed a number between 1 and 100 based on binary search. I paste it below at the very bottom. It’s nearly there but I think not quite perfect. It could perhaps be reworked better from first principles.

One thing I noticed is for example when I type in 33 as the input number for the computer to find, at one point the two previous computer guesses are 31 and 35, so the next one hopefully would have been 33, but it goes to 32 instead. I guess it’s a tiny element in the program that makes it not ideal.

I just wanted the program to find the number in seven attempts rather than eight. Maybe eight is the realistic maximum. Maybe it’s OK.

I hope I am not breaking the “spirit” of the forum by asking for precise feedback on a program. Sorry if so.

If there are no suggestions I will probably move on. I am only a beginner so am actually quite pleased that I have made this attempt. I am still working through all the tutorial notes etc (as well as trying to learn some other program basics at the same time, web, java, python… not to mention AI )

• One other point. When I type in quote marks from word into SDLIDE, it doesn’t like quote marks, eg PRINT “test” gives:

PRINT ENVELOPEANDCOUNTtestENVELOPEANDDEG

I find the interface fiddly to work with cf word for example.

At least though you can edit lines with SDLIDE compared with the BBC emulator (national computer history centre, which doesn’t seem to let you edit lines at all + fussy about copy and paste etc)

Sorry for the hassle, thanks for the help. kr

PROGRAM CODE:

10 CLS
20 LET MAX = 100 : LET MIN = 0 : LET RANGE = MAX - MIN
30 PRINT "GIVE ME A NUMBER BETWEEN 1 AND 100"
40 INPUT N : H$= ""
50 PRINT "OK, HERE IT IS - "; N : PRINT
60 ATTEMPT = 1 : PRINT "NOW LET ME GUESS IT IN 8 GOs. IS IT " : PRINT
70 LET G = ((RANGE / 2) + MIN) : GUESS = INT(G) : IF H$="H" GUESS = GUESS+1
80 PRINT GUESS;"? Y or N -"; " ATTEMPT NO. ";ATTEMPT
90 INPUT A$
100 IF A$="Y" THEN PRINT "GREAT" ELSE IF A$ = "N" THEN GOTO 105 ELSE GOTO 80
101 END
105 PRINT "IS IT HIGHER OR LOWER, H or L?" : INPUT H$
107 IF H$="H" MIN = MIN+(RANGE/2) ELSE IF H$= "L" MAX = MAX-(RANGE/2)
108 RANGE = MAX - MIN
109 ATTEMPT=ATTEMPT+1 : GOTO 70

[Richard Russell]

• For a study project, I had to create a program where the computer guessed a number between 1 and 100 based on binary search. I paste it below at the very bottom. It’s nearly there but I think not quite perfect. It could perhaps be reworked better from first principles.

Did you base your binary search on the flowchart given in the manual here? As far as I am aware, that algorithm if implemented accurately should work.

• One other point. When I type in quote marks from word into SDLIDE, it doesn’t like quote marks, eg PRINT “test” gives:

Indeed, Word (and some other word processors) uses 'smart quotes' by default, that is the left quote is automatically changed from " to “ and the right quote is automatically changed from " to ”.

This, not surprisingly, confuses SDLIDE. There may be some way of switching off smart quotes in Word, but I don't use it myself.

[gerard@dugdill.com]

Thanks. I am not sure I did to be honest. I just dived it and went for it so to speak.

OK on quotes. If the system is surprised...

I received another suggestion externally, which seems to work.

I guess I will look back at the algorithm when I reach that point in the manual.

Many thanks for your help,

Gerard

[DDRM]

The higher/lower code on 107 could be easier?

Why don't you simply:
a) If the guess is too low, set min to guess + 1
b) if the guess is too high, set max to guess - 1?

I suspect, but haven't worked through except for the first case, that what you are doing sets the min/max to guess (not one either side of it), which will worsen the performance a little.

I note also that your initial min = 0, but you are looking for a number between 1 and 100, so shouldn't it be 1? That means you'll need to adjust the calculation of range, and probably the guess.

2^ = 128, so you are right, you should always be able to get it in 7 goes.

D

[Richard Russell]

Why don't you simply:
a) If the guess is too low, set min to guess + 1
b) if the guess is too high, set max to guess - 1?

I've not studied the OP's code (it contains GOTOs, so I refuse to look at it!) but when I've coded a binary search it has been necessary for at least one of min and max be set equal to guess, not one away.

The reason is that you don't want to add a test for equality inside the loop, because this adds an overhead to every iteration which is wasteful. Rather you only want a single conditional test inside the loop, and that means if the guess is correct the new range must contain it.

Of course this does mean that the loop will always execute the maximum number of iterations, rather than exit prematurely when the guess is correct, but statistically you win on overall performance (I think) because an additional comparison is expensive..

[Ric]

Evening Gerard,
just thought id have a go at your challange and this was the result, there are no error traps, but it works in 7 guesses or less every time

Code: Select all

    
      INPUT "Please input a number between 1 and 100 ";num%
      min% = 1
      max% = 100
      atempt% = 0
      REPEAT
        PRINT "Your number is ";num%
        guess% = (min% + max%) / 2
        PRINT "My guess is ";guess%
        IF num% < guess% THEN max% = guess% ELSE min% = guess%
        atempt% += 1
      UNTIL num% = guess%
      PRINT "Did it in ";atempt%;" goes"

Hope this helps

[Richard Russell]

INPUT "Please input a number between 1 and 100 ";num%

"Between" here is somewhat ambiguous, but assuming it means from 1 to 100 inclusive your code doesn't work correctly if 100 is entered.

[gerard@dugdill.com]

Apologies, guys. Someone contacted me with a way of doing it and I ran it and it worked. I'll take a look at this other possible + the comment. I didn't click get email ping.

* On another point, I recently switched to BBC Basic for Windows (Trial) which seems slightly more comprehensive and user friendly than SDL, for what my thought is worth, and am looking through the correct user manual for that. I wondered if there was a way to change font size in the output window for BBC Windows, which seems a bit small. I can change the size in the editing pane, but not output window, unless it's under my biggish nose....

Thanks,

[Richard Russell]

I recently switched to BBC Basic for Windows (Trial) which seems slightly more comprehensive and user friendly than SDL

I don't know about user friendliness, but in most respects BBCSDL is more comprehensive than BB4W. The exception is of course in providing access to the Windows API, which is inevitably far more extensive in the latter, and is the reason I continue to support it.

Personally I no longer use BBC BASIC for Windows (or, at least, very rarely) for the following reasons:

• Windows is no longer the dominant Operating System, and I want my programs to run in MacOS, Linux, Android, iOS or as a web application.
• It's 32-bit specific. Every other major OS has either dropped support for 32-bit apps (MacOS, iOS) or is in the process of deprecating it.
• It's closed-source, so will become unmaintainable, looking to the (possibly near) future.
• The graphics are very slow, unless you're prepared to drop into assembly language (e.g. using David Williams' GFXLIB).

If you can let me know in what specific ways you find BBCSDL less user friendly, I will consider improving it. Failing that you can make changes yourself, since unlike BB4W the User Interface is itself entirely written in BBC BASIC and is amenable to customising.

I wondered if there was a way to change font size in the output window for BBC Windows, which seems a bit small. I can change the size in the editing pane, but not output window

If you mean change the default font then no, other than through Windows settings (BB4W should act on accessibility settings, like Large Fonts). But you can of course change the current font used in your program(s) so in practice that's not a limitation. Hopefully you are not doing any significant work in Immediate Mode!

[gerard@dugdill.com]

Maybe it's just me but I found the whole way of inputting and manipulating text clunky, slow/delayed and a bit un-responsive, eg compared to word processing in Word.

Maybe I should revert to focusing on SDL from what you write. I am still very much a beginner in the programming game, and just wanted to get a basic familiarity with a bit of coding and website manipulation for projects in the future. I think the BBC materials and programs on offer are a very good way of getting to grips with programming in general, as well as being a flashback to the cool 80s and so forth. I am not sure how well BASICS can be applied to "the real world", eg web design.

What I meant was the font size in the output window in BBC4W; it just seems tiny, maybe 9-10 pt, when I run a sample program, eg from chapter 6 of the user's manual (strings).

Many thanks, I'll pick up any replies in the week,

Gerard