When I loaded YouTube recently, one of the suggested videos was entitled “How To Solve Google’s 25-Horses Interview Question” by MindYourDecisions. The video cover image contained the text:

“What is the best way to find the 3 fastest horses? You can race 5 horses at a time, but you do not have a watch.”

– MindYourDecisions on YouTube

I did not watch the video since I thought this might be a fun exercise in BASIC. Instead, I fired up the excellent XRoar emulator and began writing a simple program that raced horses.

I started with an array big enough to hold the speed of 25 horses:

DIM H(24)

In Color BASIC, arrays are base-0, so that represents H(0) to H(24).

Next I initialized the array with a unique speed value by simply going through the loop and assigning each horse a speed of 0 to 24:

FOR I=0 TO 24:H(I)=I:NEXT

My next step was to randomize the entries, so I looked back on an earlier article I posted about Random BASIC shuffling. I implemented the suggested from James Jones to swap values in this array:

FOR I=0 TO 24
IF I/5=INT(I/5) THEN PRINT
J=I+INT(RND(25-I)-1)
T=H(I)
H(I)=H(J)
H(J)=T
PRINT H(I);
NEXT

Now I had an array of 25 horse speeds — H(0) to H(24) — that contains a random selection of values 0 (slowest) to 24 (fastest).

If you wanted to just find the fastest horse, you could simply scan the array and remember the fastest entry you found. At the end of the scan, you know the fastest horse. Something like this:

FH=-1:FS=-1
FOR I=0 TO 24
IF H(I)>FS THEN FH=I:FS=H(I)
NEXT
PRINT "FASTEST HORSE IS";FH

…but since this question requires racing no more than five horses at a time, I had to split that up in to code that would run five races of five horses, then a sixth race that raced the winners of each of the five races.

This is not the solution to the question, but it was a fun exercise. Here is the messy program I came up with. It will first print out the speeds of all 25 horses (five per line, matching how they will be raced) and then run the five races and final race of the winners:

0 ' HORSES1.BAS
1 '
2 ' 25 horses
3 ' Race up to 5 at a time
4 ' Find the fastest horse
5 '
10 ' H(x) - horse speed
15 DIM H(24)
20 '
21 ' Initialize each speed
22 '
25 FOR I=0 TO 24:H(I)=I:NEXT
30 '
31 ' Randomize
32 '
35 FOR I=0 TO 24
40 IF I/5=INT(I/5) THEN PRINT
45 J=I+INT(RND(25-I)-1)
50 T=H(I)
55 H(I)=H(J)
60 H(J)=T
65 PRINT H(I);
70 NEXT
75 PRINT:PRINT "RACE!"
100 '
101 ' Find fastest horse
102 '
105 DIM FH(4)
110 '
111 ' Race five sets of five
112 ' FH(x) - fastest horse
113 ' FS(x) - and its speed
114 '
115 FOR R=0 TO 4
120 FH(R)=-1:FS=-1
125 PRINT R;"-";
130 FOR I=R*5 TO R*5+4
135 PRINT I;
140 IF H(I)>FS THEN FH(R)=I:FS=H(I)
145 NEXT
150 PRINT "=";FH(R)
155 NEXT
160 '
161 ' Race the five winners
162 '
165 FH=-1:FS=-1
170 PRINT " F -";
175 FOR I=0 TO 4
180 PRINT FH(I);
185 IF H(FH(I))>FS THEN FH=FH(I):FS=H(FH)
190 NEXT
195 PRINT "=";FH
200 PRINT "WINNER IS HORSE";FH
500 END

And the result (also messy) looks like this:

But this isn’t the solution we are looking for.

The question was what is the fastest way to find the fastest three horses. I found the fastest by running six races. I expect the solution is simple, but I do not know it.

I thought I’d share this here and see if anyone else wants to work on it.

Any takers?

It seems like only yesterday that you had a dozens of choices in what computer you could buy. Most were not compatible with the others — and we liked it that way. Software companies, however, probably didn’t. To reach the largest market, they had to write their program multiple times for different systems. My Radio Shack Color Computer, sadly, did not get many of these official ports.

Side note: For a nice list of some of the official ports we actually did get, see this listing by Curtis Boyle.

Many things we take for granted today — such as sending text from one computer to another (via e-mail, text, etc.) — were not as simple back then. Not all systems used an industry standard character set, meaning the numeric code that represented a character on one system, might represent a different character on another.

The CoCo used ASCII – “American Standard Code for Information Interchange.” The defined numeric values represented the following characters in this clear and easy to understand chart:

If that chart doesn’t help, you are not alone. Just know that characters 0 to 127 were all defined to represented a standard set of letters, numbers, punctuation, symbols and control codes (such as 8 being BACKSPACE, 13 being CARRIAGE RETURN, etc.).

System like the Atari 400/800 and Commodore PET/VIC-20/64/etc. included non-ASCII graphical symbols in their character set. Each of these systems came up with their own standard — PETSCII from Commodore (which originated on the Commodore PET in 1977), and ATASCII from Atari (which originated on the Atari 400/800 in 1979).

Before WWW there was BBS

One of the first things I ever did with a computer was use one with a modem to dial other computers over a land line telephone. (Kid’s, ask your parents…) Folks would run Bulletin Board System software that let others call their computer and post messages for other folks to read who called in later.

This presented a problem. If the character sets were different between computers, how could an ASCII CoCo user dial in to an Atari ATASCII system or a Commodore PETSCII system?

To solve this problem, some BBS programs on the non-ASCII computers would first ask you if you wanted ASCII or ATASCII (or PETSCII or whatever). For ASCII users, the BBS would then translate the character codes.

Not all systems did this, of course. There were plenty of Commodore-only and Atari-only systems that made use of the extended character set to draw fancy menus and screens that ASCII computers couldn’t view.

However, the modem “terminal programs” that non-ASCII systems ran usually had an ASCII translation mode built in. Thus, a Commodore or Atari user could call any ASCII BBS. While I am sure they existed, I never did see a terminal program for my ASCII CoCo that let it call an ATASCII or PETSCII-only system. (TwilightTerm by SockMaster is similar, allowing a CoCo 3 to view the IBM PC ANSI character set and colors.)

When I lived in Lufkin, Texas, one of the local BBSes was running on an Atari 800 (via BBS Express software) and allowed ASCII systems to call in. This was how I first learned about the differences in ATASCII versus ASCII.

Here is what ASCII characters 32-127 looked like on the CoCo 1 and 2 (characters 0-31 are control codes and such):

And here is the same set of characters on a CoCo 3 40-column screen with row and column numbers (since I had more screen room):

From wikipedia, here is what ATASCII looks like:

I think this table is much easier to read that the ASCII one, as long as you know hexadecimal.

Starting at character 32 (0x20) is a space, followed by special characters and the alphabet. Although there are some symbol differences (like the ^ on CoCo being a diamond on the Atari), the main letters, numbers and symbols are the same.

But, if I were to write up a text file and send it to the Atari BBS so they could post it, it would not work. ASCII uses 13 (CR, carriage return) as a line ending, but ATASCII uses 155 (ATASCII CR). If I translated line endings, and avoided using things like ^, brackets (or curly braces), etc., I could then have a text file the Atari BBS could use.

The amazing ASCII to ATASCII Convert program!

So I wrote a simple ASCII to ATASCII converter:

0 REM ASCII TO ATASCII CONVERT
1 REM BY ALLEN HUFFMAN
2 REM (09/02/87)
3 REM
5 CLEAR1000
10 CLS:PRINT@3,"ASCII TO ATASCII CONVERTER":PRINT@40,"BY ALLEN HUFFMAN":PRINTSTRING$(32,131)
15 PRINT@96,"ASCII FILE TO CONVERT:":LINEINPUT">";F1$:IFF1A$=""THEN15
20 PRINT@192,"NAME OF NEW FILE:":LINEINPUT">";F2$:IFF2$=""THEN15
25 PRINT@289,"CONVERTING ASCII TO ATASCII...":OPEN"I",#1,F1$:OPEN"O",#2,F2$
30 LINEINPUT#1,A$:PRINT@320,A$:PRINT#2,A$+CHR$(155);:IFEOF(1)=0THEN30
35 PRINT#2,CHR$(26);:UNLOAD
40 PRINT@422,"CONVERSION COMPLETE!":END

In line 15, it asks for an INPUT filename (F1$).

In line 20, it asks for an OUTPUT file name (F2$).

In line 25, it opens the first file as input (“I”) and the second file for output (“O”).

In line 30, it loops reading a raw line from the first file, displaying it on the screen (so the user can see what is going on), then writes the text out to the output file with a CHR$(155) at the end and NO ASCII carriage return (by using the semicolon). If end-of-file is not reached, it goes back to 30 to process the next line.

In line 35, it writes out a final CHR$(26) (control-Z) to the ATASCII output file — but I do not recall why. It then uses the UNLOAD command to close any open files.

I had to look up UNLOAD, as I had forgotten this existed. The description reads:

“Closes any open files on the disk in the drive you specify. If you do not specify a drive number, the com­puter uses Drive 0 (or the drive you specified in the DRIVE command).”

Disk Extended BASIC manual

Not much to it, but it worked and it let me write bulletins and such that I could upload to the Atari BBS.

I thought I would share this code in case any CoCo user out there needs to upload some text files to an Atari BBS.

Until next time…

Previously I discussed several approaches to printing out the Christmas tree pattern for this challenge.

The method that produced the smallest Color BASIC program looked like this:

0 FORC=1TO14:W=ASC(MID$("ACEGCGKOEKQWCC",C,1))-64:PRINTTAB(16-W/2)STRING$(W,42):NEXT

That uses 66 byte of BASIC program space (though will use more RAM for strings as it runs).

It appears there are still optimizations to make! In the comments. Stewart Orchard pointed out this one:

Not a big gain but two bytes can be saved by removing the third argument from MID$().

The two argument version of MID$() returns the remainder of the string starting from the specified position, and ASC() returns its result based on the first character of its argument.

– Stewart Orchard

In Color BASIC, MID$ can accept three parameters:

If you had as string of 10 characters, and wanted to print the third character, you could do it like this:

A$="ABCDEFGHIJ"
OK
PRINT MID$(A$,3,1)
C

Stewart pointed out that if you left off the final parameter, it returns the rest of the string:

A$="ABCDEFGHIJ"
OK
PRINT MID$(A$,3,1)
CDEFGHIJ

Now that I look at it, it appears MID$ with two parameters is sort of like an inverted RIGHT$. MID$ would give you all the characters starting at the one you specify, and RIGHT$ gives you the number of ending characters you specify.

PRINT MID$(A$,3)
CDEFGHIJ

PRINT RIGHT$(A$,3)
HIJ

I don’t recall using MID$ like this, but I have simulated the same behavior using RIGHT$ like:

PRINT RIGHT$(A$,LEN(A$)-3+1)
CDEFGHIJ

PRINT MID$(A$,3)
CDEFGHIJ

I am a bit embarrassed to admit I think I even did something like this:

PRINT MID$(A$,3,LEN(A$)-3)
CDEFGHIJ

…but let’s not speak of that.

And if MID$ can work like RIGHT$, it can also work like LEFT$:

PRINT LEFT$(A$,3)
ABC

PRINT MID$(A$,1,3)
ABC

But I digress…

If MID$(A$,3,1) gives you one character starting as location 3, and MID$(A$,3) gives you all the characters starting at position 3, how does that work? Stewart explained that ASC will still work if you pass it a string since it only works on the first character of the string. It is even documented that way:

Thus, ASC(“HELLO”) produces the same result as ASC(“H”) — the ASCII value of letter H.

With that in mind, we can remove “,1” from the program and reduce it by two bytes:

0 FORC=1TO14:W=ASC(MID$("ACEGCGKOEKQWCC",C))-64:PRINTTAB(16-W/2)STRING$(W,42):NEXT

64 bytes!

Thank you, Stewart, for leaving that comment.

Until next time…

Another programming challenge seems to be occupying folks this Christmas season:

http://logiker.com/Vintage-Computing-Christmas-Challenge-2021

The challenge is simple: Write a program that prints out a centered text Christmas tree using the same layout of their example program. I thought it would be fun to work through several methods to do this.

PRINT

We start with their simple example, which displays the centered tree using PRINT statements. Here is their example with spaces altered so it centers on the CoCo’s 32 column screen:

100 PRINT "               *
110 PRINT "              ***
120 PRINT "             *****
130 PRINT "            *******
140 PRINT "              ***
150 PRINT "            *******
160 PRINT "          ***********
170 PRINT "        ***************
180 PRINT "             *****
190 PRINT "          ***********
200 PRINT "       *****************
210 PRINT "    ***********************
220 PRINT "              ***
230 PRINT "              ***

386 bytes.

You will see one memory optimization they did was leaving off the ending quote. BASIC will stop parsing a quoted string if it reaches the end of a line, so the ending quote is only necessary if more statements follow the PRINT.

I do not know if the space between PRINT and the quote is required for the system they wrote this example, but on the CoCo we could remove it and save 23 bytes of program space right there.

PRINT TAB

Speaking of spaces, each space takes up a character. BASIC has a command that will jump forward a certain amount of spaces — TAB. It works like this:

PRINT TAB(5);"FIVE SPACES OVER"

From my test, it appears TAB takes up one byte(for the “TAB(” portion, then a byte for each digit, then a byte for the closing parenthesis. If tabbing a single digit of spaces, it takes three bytes of program space. Thus, any time we are spacing over more than 3 spaces, it would save memory to use TAB. Also, the semicolon between TAB and the item being printed is optional, so we can leave that out as well.

For the tree example centered on a 32 column screen, every line starts with at least 4 spaces, so using TAB should save memory. Let’s try this:

100 PRINT TAB(15)"*
110 PRINT TAB(14)"***
120 PRINT TAB(13)"*****
130 PRINT TAB(12)"*******
140 PRINT TAB(14)"***
150 PRINT TAB(12)"*******
160 PRINT TAB(10)"***********
170 PRINT TAB(8)"***************
180 PRINT TAB(13)"*****
190 PRINT TAB(10)"***********
200 PRINT TAB(7)"*****************
210 PRINT TAB(4)"***********************
220 PRINT TAB(14)"***
230 PRINT TAB(14)"***

279 bytes.

That looks icky, but produces the same result with less code space.

Pattern Matching

If we take a look at the tree design, we see it has a pattern to how each of the three seconds is printed:

           *            1
          ***           3
         *****          5
        *******         7
          ***           3
        *******         7
      ***********       11
    ***************     15
         *****          5
      ***********       11
   *****************    17
*********************** 23
          ***           3
          ***           3

It is drawing three sections, with the first expanding on each side by 1 (adding two asterisks to each row), then the next section expanded each side by 2 (adding four asterisks to each row), then the final section expands each side by 3 (adding six asterisks to each row).

There is probably a simple way to math it. But first…

Centering

Since one of the requirements is centering the tree on the screen, let’s look at how we center a string. To do this, we simply subtract the length of the string we want to center from the width of the string then divide the result by two:

A$="CENTER THIS"
PRINT TAB((32-LEN(A$))/2);A$

Or, to eliminate some parenthesis, we can start with half the width of the screen (the center of the screen) and subtract half the length of the string:

A$="CENTER THIS"
PRINT TAB(16-LEN(A$)/2);A$

With that out of the way, now we need to figure out how to draw the three triangle shapes of the tree, each time getting wider.

Numbers and patterns.

I decided to lookat the number sequences of each line length for each section of the tree (skipping the trunk lines).

Section 1: 1  3  5  7
Section 2: 3  7 11 15
Section 3: 5 11 17 23

I could easily create the first pattern by doing a FOR/NEXT loop with a step of 2:

FOR I=1 TO 7 STEP 2:PRINT I:NEXT

And then I could do 3 to 15 with a STEP 4, and 5 to 23 with a STEP 6.

FOR I=1 TO 7 STEP 2:PRINT I:NEXT
FOR I=3 TO 15 STEP 4:PRINT I:NEXT
FOR I=5 TO 23 STEP 6:PRINT I:NEXT

This would generate the number sequence I need, and then I could simply print a centered string of that many asterisks, and manually print the tree trunk at the end.

10 FOR I=1 TO 7 STEP 2:GOSUB 50:NEXT
20 FOR I=3 TO 15 STEP 4:GOSUB 50:NEXT
30 FOR I=5 TO 23 STEP 6:GOSUB 50:NEXT
40 I=3:GOSUB 50:GOSUB 50:END
50 PRINT TAB(16-I/2)STRING$(I,42):RETURN

127 bytes.

That’s much better! Though, I saved a bit more by combining lines, and I could save even more by removing spaces and combining lines further:

10 FORI=1TO7STEP2:GOSUB50:NEXT:FORI=3TO15STEP4:GOSUB50:NEXT:FORI=5TO23STEP6:GOSUB50:NEXT:I=3:GOSUB50:GOSUB50:END
50 PRINTTAB(16-I/2)STRING$(I,42):RETURN

(Compressed down to 94 bytes.)

Now we’re getting somewhere! But ignoring the compressing, can we do better than 127 using better math?

Math. Why did there have to be math?

I am slow and bad at math, but I am convinced there is a math solution to this, as well.

Let’s look at how the numbers for START value and STEP value work. I know there are going to be three sections of the tree, so it seems logical I’d start with something like this:

10 FOR I=1 TO 3
20 PRINT I*2-1
30 NEXT

That would print out 1, 3 and 5, which is the start width of each section of the tree. I could have also done the FOR loop using 0 to 2 and added 1 to get the same result:

10 FOR I=0 TO 2
20 PRINT I*2+1
30 NEXT

Maybe one will be more useful than the other depending on what comes next…

Once we know how wide a section starts, we need to know how much the length increases for each line.

Section 1 increases by 2 each row, section 2 increases by 4 each row, and section 3 increases by 6 each row. That is a pattern of 2, 4, 6. It looks like I could get those values by taking the section (1 to 3) and multiplying it by 2. This will print 2, 4, 6:

10 FOR J=1 TO 3
20 PRINT J*2
30 NEXT

I am bad with math, as I mentioned, but I was able to work out that taking a value of 1 to 4 (for each layer of a section) and multiply that by the section (1 to 3), and subtracting one, I could get this:

10 FOR I=1 TO 3
20 FOR J=1 TO 4
30 PRINT J*I*2-1
60 NEXT
70 NEXT

The math looks like this:

 J * I       * 2       - 1
-------   -------   -------
(1 * 1) = (1 * 2) = (2 - 1) = 1
(2 * 1) = (2 * 2) = (4 - 1) = 3
(3 * 1) = (3 * 2) = (6 - 1) = 5
(4 * 1) = (4 * 2) = (8 - 1) = 7

(1 * 2) = (2 * 2) = (4 - 1) = 3
(2 * 2) = (4 * 2) = (8 - 1) = 7
(3 * 2) = (6 * 2) = (12 - 1) = 11
(4 * 2) = (8 * 2) = (16 - 1) = 15

(1 * 3) = (3 * 2) = (6 - 1) = 5
(2 * 3) = (6 * 2) = (12 - 1) = 11
(3 * 3) = (9 * 2) = (18 - 1) = 17
(4 * 3) = (12 * 2) = (24 - 1) = 23

…and that gets our number sequence we want:

Section 1: 1  3  5  7
Section 2: 3  7 11 15
Section 3: 5 11 17 23

To print the row of asterisks, I use the STRING$ function. It takes the number of characters to print, then the ASCII value of the character. The asterisk is ASCII character 42 so it I wanted to print ten of them I would do:

PRINT STRING$(10,42)

I can now print the layers of the tree like this:

10 FOR I=1 TO 3
20 FOR J=1 TO 4
30 W=J*I*2-1
50 PRINT TAB(16-W/2);STRING$(W,42)
60 NEXT
70 NEXT

But that still doesn’t handle the “trunk” at the bottom of the tree.

Since the trunk does not follow any pattern, I will simply treat it like an extra section, and increase the section loop (FOR I) by one, and add an IF that says if we are on that layer, the width will be 3. Then, since I don’t want this section to be four layers thick, I can use a second IF after the one that checks for the fourth section to know when to exit (checking for J to be larger than 2):

10 FOR I=1 TO 4
20 FOR J=1 TO 4
30 W=J*I*2-1
40 IF I>3 THEN W=3:IF J>2 THEN END
50 PRINT TAB(16-W/2);STRING$(W,42)
60 NEXT
70 NEXT

162 bytes.

Ah, well, being clever seems to have increase beyond the 127 bytes of just using three FOR/NEXT loops. I suspect it’s the overhead of the way I am trying to print the trunk section. Indeed, without it (like 40, above, and adjusting the I loop to 3) makes it 125.

Sometimes being clever doesn’t help. Even without trying to be clever about the trunk section, the “W=J*I*2-1” stuff takes up as much space as just doing another FOR/NEXT and a GOSUB to print the line.

DATA

We could just have a table to line lengths, and do it like this:

10 READ W
20 IF W=0 THEN END
30 PRINT TAB(16-W/2);STRING$(W,42):GOTO 10
40 DATA 1,3,5,7,3,7,11,16,5,9,13,17,3,3,

98 bytes.

Not bad at all! And that is before compressing it to fewer lines. Here’s a 79 byte attempt, removing spaces, removing the semicolon, altering the logic just a bit to be on LINE 0 (so you can just say GOTO) and changing the IF so there is no END token:

0 READW:IFW>0THENPRINTTAB(16-W/2)STRING$(W,42):GOTO:DATA1,3,5,7,3,7,11,16,5,9,13,17,3,3,

Another “DATA” technique which I have seen Jim Gerrie use is to simply encode the line lengths as characters in a string, and use that as data. For example, ASCII “A” (character 65) will represent 1, “B” will represent 2, and so on. Make a string of the appropriate characters and retrieve them using MID$() and get the ASCII value using ASC() then subtract 64 from that value and you have something like this.

10 FOR C=1 TO 14
20 W=ASC(MID$("ACEGCGKOEKQWCC",C,1))-64
30 PRINT TAB(16-W/2);STRING$(W,42)
40 NEXT

97 bytes.

If we compress the lines together, we can shrink it even further:

10 FORC=1TO14:W=ASC(MID$("ACEGCGKOEKQWCC",C,1))-64:PRINTTAB(16-W/2)STRING$(W,42):NEXT

66 bytes!

Is this as small as it gets? (Technically, this uses more memory, since string space has to be used to create temporary strings for MID$(), but we are only looking at program size and not memory usage.)

What else can we try? Leave a comment.

Until next time…

Revisiting my Color BASIC String Theory series… Here is one to ponder…

CLEAR 0 can be used to reserve 0 bytes for string storage. With no string space, we obviously expect something like this to NOT work:

A$="THIS WON'T WORK WITH CLEAR 0"

Indeed, that would give us “?OS ERROR” — Out of string space.

The exception to this rule are “constant strings” that are embedded inside the BASIC program itself. In a YouTube video I recently posted, I demonstrated how constant strings in a program do not use string space:

You can see twenty nine other short Color BASIC videos I posted to YouTube during the month of #SepTandy 2021.

But I digress…

Here are some other things that won’t work without string space, even if, at first glance, it seems like they would:

It seems you can’t SAVE, LOAD or even PRINT a “constant” string if there is no string space.

But why?

Consider this… The same thing happens with string functions such as LEFT$, RIGHT$, MID$ and even INSTR:

Looking at those, and recalling my String Theory article, we know LEFT$, RIGHT$ and MID$ are trying to create a new string. With no string space, there is no way to create it. That must be why they fail. This makes sense.

But INSTR does not create any strings. It merely returns the position where one string appears inside of another, or 0 if the string is not found. (Or 1 if you give it an empty string, which truly does seem like a bug but other flavors Microsoft BASIC behave the same way with their implementations of INSTR. But I digress…)

And SAVE, LOAD and PRINT are similar. They just print something, not create a string.

That does not make sense.

Let’s speculate a bit.

What’s all this, then?

Without consulting the Color BASIC Unravelled disassembly, my guess is that the ROM code for SAVE, LOAD, PRINT, etc. probably expects some register to be pointing to where the string exists in memory (a location pointer in the variable data). This might be code space, in the case of a constant string embedded in a BASIC line, or string space, in the case of a dynamic string.

But when you are entering a command directly in to BASIC, there is no program memory for that command (even though it seems like it could just point to the keyboard input buffer and then make the ROM call). BASIC needs to put that constant string data somewhere before jumping to the ROM call.

That’s weird, and quite possibly unnecessary, but would, at least, make sense.

I am going to add this to my “look this up in the disassembly to see what’s going on” list for future investigation.

In the meantime … I wonder what else won’t work without string space?

Until next time…