(BASIC) string handling advice

The place for codemasters or beginners to talk about programming any language for the Spectrum.
Post Reply
User avatar
Fahnn
Microbot
Posts: 135
Joined: Sun Jan 27, 2019 7:56 pm
Location: Redcar, UK
Contact:

(BASIC) string handling advice

Post by Fahnn »

I've started writing a new thing and without wanting to give anything away at this stage - don't want to spoil the surprise! - it involves quite a lot of free text input. The program then searches the string that you've entered for the presence of certain terms. I do have a method but it can be horrendously slow, especially if the initial string entered is long. Essentially I suppose what I'm asking is whether there's a fast way to simulate an INSTRING function on the Spectrum in an efficient manner.

e.g. if the input is something like "the quick brown fox jumped over the lazy dog, onto a crocodile then onto a tree stump", what would be fastest way to determine whether the term "dog" or "crocodile" or "stump" (or whatever) is within the original input? The position at which it occurs isn't important, just whether the search string appears. At the moment I'm just going through the input string character by character but there must be a quicker way.

I've searched around a bit but can't find anything on this so any advice would be much appreciated.
User avatar
Einar Saukas
Bugaboo
Posts: 3070
Joined: Wed Nov 15, 2017 2:48 pm

Re: (BASIC) string handling advice

Post by Einar Saukas »

Do you need to search for small strings within a (possible large) string? If so, forget complex solutions like the classic Knuth-Morris-Pratt algorithm, and just implement a straightforward Assembly routine to be accessed from BASIC.
User avatar
Fahnn
Microbot
Posts: 135
Joined: Sun Jan 27, 2019 7:56 pm
Location: Redcar, UK
Contact:

Re: (BASIC) string handling advice

Post by Fahnn »

Einar Saukas wrote: Thu May 23, 2019 7:49 pm forget complex solutions like the classic Knuth-Morris-Pratt algorithm
I didn't need to forget about that because I'd never heard of it! Interesting stuff though.
Einar Saukas wrote: Thu May 23, 2019 7:49 pmand just implement a straightforward Assembly routine to be accessed from BASIC.
I can't remember enough assembly to be able to do that, I'm afraid. Maybe that is the answer though and it would give me the impetus to get out of BASIC and into re-learning at least the basics of proper code. Is there genuinely no fast solution in BASIC?
User avatar
Einar Saukas
Bugaboo
Posts: 3070
Joined: Wed Nov 15, 2017 2:48 pm

Re: (BASIC) string handling advice

Post by Einar Saukas »

If you post your BASIC implementation here, people will certainly help with suggestions to improve it.

However the fastest solution is to use an Assembly routine you could call from BASIC. There's no need to implement it from scratch, it was already implemented here:

http://programandala.net/en.program.deffnder.html

I can compile it for you if you want, just let me know. Just remember to credit the original authors if you use it, as stated in their code license.
User avatar
Fahnn
Microbot
Posts: 135
Joined: Sun Jan 27, 2019 7:56 pm
Location: Redcar, UK
Contact:

Re: (BASIC) string handling advice

Post by Fahnn »

Einar Saukas wrote: Thu May 23, 2019 9:20 pm If you post your BASIC implementation here, people will certainly help with suggestions to improve it.

However the fastest solution is to use an Assembly routine you could call from BASIC. There's no need to implement it from scratch, it was already implemented here:

http://programandala.net/en.program.deffnder.html

I can compile it for you if you want, just let me know. Just remember to credit the original authors if you use it, as stated in their code license.
I've only had a quick glance but this has given me a lot to think about, thank-you! I look forward to going through it properly (and probably not understanding much of it) tomorrow. I really need to incorporate some code, I think it's the only way to get some of my more ambitious stuff off the ground. Thanks again, your help is really appreciated.
hikoki
Manic Miner
Posts: 576
Joined: Thu Nov 16, 2017 10:54 am

Re: (BASIC) string handling advice

Post by hikoki »

One idea would be to search as you type and show every word that starts with the first consonant letters, just the first three consonants.
User avatar
IvanBasic
Drutt
Posts: 48
Joined: Mon May 13, 2019 1:24 pm

Re: (BASIC) string handling advice

Post by IvanBasic »

What about this routine I have created -very quickly, sorry-?

https://drive.google.com/file/d/1gWF5-Z ... sp=sharing

The idea is to separate every single word and put it in a array z$(w,l); it is supossed that words are separated by a blank space. The max number of words in the sentence is w, the max lenght of your commands is l.

After that, you have an array with 10 words; you can add more if you want larger sentences to analyse.

Then, for each word in the array, the first letter of the word z$(a,1) is linked to a line according to its CODE. In my example I did GO SUB 1000+CODE Z$(a,1)

If you write the commands in the correspondent line, you can check very fast if each word of the sentence matches with any of your commands.

Sorry, I know it is difficult to explain, let´s see an example:

-In my program, I defined as commands the words "cat","dog" and "lion".
-You can enter a sentence with many words (but the array will work with the first ten words, you can increase it if you want)
-Then, all words will be listed each one in a row.
-If one word is equal to a command, the program will tell you.

(Please note that all commands must start by different letters, in this quick version of the algorithm).

So, if you type "a tiger is sleeping in the jungle", the program will show these words one by one, but no command is detected.
If you type "a tiger is playing with a dog in the jungle", the program will list the words, recognizing "dog" as a command. Try "a lion and a cat are playing with a dog"

An improvement of the program should be:

- the ability to manage upper case and lower case characters, and even numbers.
- the detection of different commands that start with the same letter. Maybe using 1000+10*CODE z$(a,1) will allow space to use consecutive IF to check all commands starting by the same letter.

But for now, I believe this is a fast way to detect the different commands into a sentence.

Hope it is useful for your adventure!
User avatar
Fahnn
Microbot
Posts: 135
Joined: Sun Jan 27, 2019 7:56 pm
Location: Redcar, UK
Contact:

Re: (BASIC) string handling advice

Post by Fahnn »

hikoki wrote: Thu May 23, 2019 10:17 pm One idea would be to search as you type and show every word that starts with the first consonant letters, just the first three consonants.
Yes, I'm definitely going to do something like this, nice idea! It will have the added benefit of the program then being able to (deliberately) confuse similar words (e.g. "plan" and "play" or "woman" and "wombat"), which will be perfect for what I have in mind.
User avatar
Fahnn
Microbot
Posts: 135
Joined: Sun Jan 27, 2019 7:56 pm
Location: Redcar, UK
Contact:

Re: (BASIC) string handling advice

Post by Fahnn »

IvanBasic wrote: Fri May 24, 2019 1:22 am What about this routine I have created -very quickly, sorry-?
Thanks Ivan, very neat! It's not a million miles away from what I'm already doing (although your version is more compact) but because the input can potentially be quite long with a lot of terms to search, I'm finding it a little bit too slow at the moment. Really appreciate you doing this, though!
IvanBasic wrote: Fri May 24, 2019 1:22 amHope it is useful for your adventure!
Oh, it's not an adventure ;)
User avatar
Joefish
Rick Dangerous
Posts: 2041
Joined: Tue Nov 14, 2017 10:26 am

Re: (BASIC) string handling advice

Post by Joefish »

I'd always start by splitting the input up into words by scanning along it and anything that's 'whitespace' (space, returns, commas, quotes, colons, end of the string etc.) becomes a point at which you break off a separate word and store it. Then you look up each word. Otherwise you end up with partial matches and think 'Scunthorpe' is a swearword... Which is is, in a way. Just not that way. :lol:
User avatar
Fahnn
Microbot
Posts: 135
Joined: Sun Jan 27, 2019 7:56 pm
Location: Redcar, UK
Contact:

Re: (BASIC) string handling advice

Post by Fahnn »

Joefish wrote: Fri May 24, 2019 1:08 pm I'd always start by splitting the input up into words by scanning along it and anything that's 'whitespace' (space, returns, commas, quotes, colons, end of the string etc.) becomes a point at which you break off a separate word and store it. Then you look up each word.
I'd not even considered punctuation. Man, I am dense sometimes. However...
Joefish wrote: Fri May 24, 2019 1:08 pmOtherwise you end up with partial matches and think 'Scunthorpe' is a swearword... Which is is, in a way. Just not that way. :lol:
You've just given me the most amazing idea! My thinking about this has been backwards from the start but now I know exactly what course I'm going to take. Not only will it really speed things up, it's going to contribute massively to the "confused interpretation" thing I want to get going. I honestly can't thank you enough for this!
Post Reply