Another programming challenge seems to be occupying folks this Christmas season:
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.
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 " ***
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.
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)"***
That looks icky, but produces the same result with less code space.
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…
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
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:
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
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.
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,
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:
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
If we compress the lines together, we can shrink it even further:
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…
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.
That is a great tip! I would not have thought of that, though I was aware that ASC could take a string and just did the first character. Thanks!
New article includes your tip. Thanks!
Just as a Christmas aside, I did johngineer’s vector christmas tree on an arduino.
That’s really cool! I think I saw a scope at work. I may have to talk to my boss and see if he’ll let me play with it. I have an UNO on my desk.
Thanks for the rabbit hole :) I spent a few minutes trying to write a CoCo program to render that Hershey vector font. I didn’t get it going, yet, due to not understanding how the data is stored, but I will…
Cool! Your final code is in fact very similar to the C64 BASIC entry I submitted to the challenge! Unfortunately, the C64 doesn’t have any STRING$ function, so I had to use a different approach for printing the asterisks.
I can’t claim the final version – I saw Jim Gerrie do it first on an MC-10. I don’t think he had STRING$ either, and was using LEFT$ of a row of asterisks, maybe?
The read/data version is probably the shortest, but if you want to have another go at the math solution you could do a single loop that counts 0-13 and use the low two bits the same way as you used your inner loop and the next two bits the same way as your outer loop, and simply combine all that into one calculation generating the width. Either a separate if statement or relying on true/false being well known integer values could handle the bottom section.
I’m going to go get my note pad and draw this out. I am intrigued.
Pingback: Tackling the Logiker Vintage Computing Christmas Challenge 2021 follow-up | Sub-Etha Software
Pingback: Typing in an un-typable BASIC program… | Sub-Etha Software
Pingback: Tackling the Logiker Vintage Computing Christmas Challenge 2021 – part 1 | Sub-Etha Software
Pingback: Tackling the Logiker 2022 Vintage Computing Christmas Challenge – part 1 | Sub-Etha Software