Programming Challenge - count capital letters in a string

[Hated Moron]

Here's another little programming challenge to keep the grey cells working. No prizes, other than the satisfaction of success.

Given an arbitrary-length string, write some BBC BASIC code which will count the number of capital letters in the string (or more precisely the number of characters in columns 4 and 5 of the ASCII table, so for example for the purposes of the exercise @ counts as a capital letter). Remember that in BB4W and BBCSDL strings may be many megabytes in length and contain an entire document.

Here is the tricky part: you are not allowed to use any kind of loop, iteration or recursive function call - linear code only! Nor are you allowed to use assembly language (machine code) or call any Operating System API functions. However you will need to use features of BB4W and BBCSDL that are not available in generic BBC BASIC.

Bonus challenge: modify your code so that the @ character (or any other character in columns 4 and 5 of the ASCII table) is not included in the count.

Good luck!

[DDRM]

Is this cheating? It is based on some code on the wiki to convert a string into a byte array and sort it.

It relies on assembler in the SORTLIB, and probably some iteration in there, too! But then, if we start worrying about how every instruction is encoded at the assembler level, we could NEVER do it - and in other languages sorting a string is a basic command...

Note that I've gone straight to the "bonus level", since with this approach there's no reason not to.

Best wishes,

D

Code: Select all

      INSTALL @lib$+"SORTLIB"
      Sort% = FN_sortinit(0,0)


      test$="This is a TEST string. It has some Capital Letters, and some that are NOT so capital."
      REM Add markers for the start and end of the range we want to know about
      test_marked$= test$ + "A["
      sorted_string$ = FNsortstring(test_marked$)
      startpos% = INSTR(sorted_string$,"A")
      endpos% = INSTR(sorted_string$,"[")
      PRINT "There are " + STR$(endpos%-startpos% - 1) + " capital letters in the text string."

      END

      DEF FNsortstring(A$)
      LOCAL C%, A&()
      C% = LEN(A$)
      DIM A&(C%)
      $$^A&(0) = A$
      CALL Sort%, A&(0)
      = $$^A&(0)

[Hated Moron]

Is this cheating? It is based on some code on the wiki to convert a string into a byte array and sort it.

Hmm, in disallowing loops and assembly language it was my intention that library functions, which themselves rely on those features, would also be disallowed. A library is, after all, just a convenient way of packaging code which would otherwise have to appear in your program.

Of course if BBC BASIC had a built-in SORT keyword (as many BASICs do) it would be a legitimate, if potentially very slow, solution. But whilst libraries certainly extend the capabilities of language they don't qualify as part of the language itself IMO.

So, yes, I think it is cheating, but since I didn't explicitly exclude library functions I suppose I must grudgingly admit that it meets the letter of the challenge. Had there been a prize, I might well not have awarded it however!

I would encourage you, and anybody else keen to attempt it, to find a solution which meets the spirit of the challenge as well as the letter. When I said "linear code only" I meant that literally: no loops, no calling of subroutines of any kind.

If you need a hint, the stipulation that 'capitals' includes all the characters in columns 4 and 5 of the ASCII table is a big one!

[Hated Moron]

It is based on some code on the wiki to convert a string into a byte array and sort it.

Code: Select all

      INSTALL @lib$+"SORTLIB"
      Sort% = FN_sortinit(0,0)
...
      CALL Sort%, A&(0)

I should additionally remark that, as I'm sure you are well aware, your solution crashes on some 64-bit platforms (notably MacOS) because you have used Sort% when it should be Sort%%.

[DDRM]

Hi Richard,

Yes, I agree it doesn't really fit with the spirit, and maybe not the letter, of the challenge!

I'm guessing from your comment in the original, emphasised in your hint, that we need to find a way of counting all the characters with bit 7, but not bit 6, set, but I haven't been able to think of a way of doing it in a linear program! I wondered if there was some way of ANDing a whole string with a value, and having it collapse all the 0 bytes, so we could use LEN to count the remaining letters, but I can't think of one.

The hint I REALLY need is which additional feature of BB4W/SDL you are thinking of, but maybe that's too big a hint!

Best wishes,

D

[Hated Moron]

The hint I REALLY need is which additional feature of BB4W/SDL you are thinking of, but maybe that's too big a hint!

The feature is one that you made use of in your previous solution!

[DDRM]

Like this?

Code: Select all

      test$="This is a TEST string. It has some Capital Letters, some 123456789 numbers, and some that are NOT so capital."

      C% = LEN(test$)
      DIM A&(C%)
      $$^A&(0) = test$
      REM All printable characters (in ASCII) except 'upper case' characters have bit 6 set, so we can mask and count these
      A&() = A&() AND %100000
      non_caps = SUM(A&())/32

      PRINT "There are " + STR$(C% - non_caps)  + " capital letters in the test string."

D

[Hated Moron]

Like this?

It's not what I was expecting, but it works so long as there are no 'control characters' (&00 to &1F) in the string. In a real-life scenario there would quite likely be CR and LF characters, which your method would count, but I suspect you would think I was being unfair if I rejected your submission on that basis. So congratulations!

What about the bonus challenge? Any thoughts on how you might count just the @ characters in the string, using a related technique?

[Hated Moron]

What about the bonus challenge? Any thoughts on how you might count just the @ characters in the string, using a related technique?

With nearly two weeks having elapsed without a submission, it seems that this part of the challenge has proved too difficult. That is surprising and disappointing given that DDRM had got so close, and provided nearly every part of the solution.

Counting the number of @ characters (or any nominated character) in a string without loops is actually quite straightforward. Firstly copy the string into a byte array, for example exactly as David's code does:

Code: Select all

      test$ = "This is a TEST string. It has some Capital Letters, some 123456789 numbers, and some that are NOT so capital."
      DIM test&(LEN(test$))
      $$^test&(0) = test$

Now exclusive-OR every element of the array with NOT the character code you want to count, so for example if you want to count the number of lowercase 'a's in the string, exclusive-OR it with NOT(ASC"a"):

Code: Select all

      test&() EOR= NOT(ASC"a")

The key thing to realise is that this will convert every 'a' (&61) to 255 (&FF). All the other characters will be converted to values other than (that is, smaller than) 255! Now it's simply a matter of dividing every element by 255:

Code: Select all

      test&() DIV= &FF

Finally we have an array in which each element that was originally an 'a' is a one, and the rest are a zero! Hence the number of 'a's in the original string is simply the SUM of the array:

Code: Select all

      PRINT "Number of 'a' characters is "; SUM(test&())

[Hated Moron]

it seems that this part of the challenge has proved too difficult.

Judging by the deafening silence, the solution doesn't seem to have been of any interest either! Does nobody think BBC BASIC 'hacks' of this kind are worthy of note?

The trigger for this particular challenge was porting the BB4W 'Add Windows Constants' utility (which uses assembly language for speed) to become the BBCSDL 'Add SDL Constants' utility (which for portability reasons can't use assembly language). I needed a very fast way of checking whether a line of BASIC code references a 'constant', that is a variable name consisting entirely of capital letters.