Page 1 of 1
Anagram Find -- Simple
Posted: Sat Jul 26, 2008 1:06 am
by michaeled314
Download:
http://www.cset.oit.edu/~yangs/CST420/l ... ionary.txt
Run:
Code: Select all
If OpenFile(0,"dictionary.txt")
While Not Eof(0)
Current = Loc(0)
Word$ = ReadString(0)
While Not Eof(0)
a=1
Anagram$ = ReadString(0)
If Len(Word$) = Len(Anagram$)
For i = 1 To Len(Word$)
If CountString(Word$,Mid(Word$,i,1)) = CountString(Anagram$,Mid(Word$,i,1))
Else
a = 0
EndIf
Next
If a = 1
Debug Word$+":"+Anagram$
EndIf
EndIf
Wend
a=1
FileSeek(0,Current)
junk$ = ReadString(0)
Wend
EndIf
PS save it in the same directory
Posted: Sat Jul 26, 2008 4:09 pm
by AND51
Your code could be better.
You wrote:Code: Select all
If CountString(Word$,Mid(Word$,i,1)) = CountString(Anagram$,Mid(Word$,i,1))
Else
For example this two code snippets:
Why do you use
OpenFile() instead of
ReadFile()?
And why do you use "If/Else" with no code inbetween? You could easily change this, if you would use "<>" instead of "=".
However, your code is very nice!
Here is my code. It is the very improved version of yours.
It first reads the whole dictionary into a linked list and analyses it (first step) and then compares (second step).
Code: Select all
If ReadFile(0,"dictionary.txt")
Structure anagram
word.s
len.l
letter.l[26]
EndStructure
Define n, found, current.anagram, *currentElement
NewList dict.anagram()
While Not Eof(0) ; READING + ANALYSING
AddElement(dict())
dict()\word=ReadString(0)
dict()\len=MemoryStringLength(@dict()\word)
For n=0 To 25
dict()\letter[n]=CountString(dict()\word, Chr(n+'a'))
Next
Wend
CloseFile(0)
ForEach dict() ; COMPARING
*currentElement=@dict()
current\word=dict()\word
current\len=dict()\len
For n=0 To 25
current\letter[n]=dict()\letter[n]
Next
While NextElement(dict())
found=1
If current\len = dict()\len
For n=0 To 25
If current\letter[n] <> dict()\letter[n]
found=0
Break
EndIf
Next
Else
found=0
EndIf
If found
Debug current\word+"="+dict()\word
EndIf
Wend
ChangeCurrentElement(dict(), *currentElement)
Next
EndIf
I must go offline now, but when I return later, I will tell you the result of my speed test.
Your code took 1 433 734 milliseconds = 23 minutes.
My code is running, but not finished yet. See you!
Posted: Sat Jul 26, 2008 4:22 pm
by michaeled314
Anyway u ar probably an expert programmer
I don't know yur age but I'm turning 14 in about half a month
I'm not a qualified programmer just a hobby outside of high school
Posted: Sat Jul 26, 2008 4:31 pm
by rsts
I doubt Mr AND51 meant it as criticism. He's just a bit direct and likes the spirit of competition
He's also a good source for techniques.
(but a lot are over my head and I'm a bit older than you)
cheers
Posted: Sat Jul 26, 2008 4:36 pm
by michaeled314
rsts how old ar you
you are so better than me at coding
Posted: Sat Jul 26, 2008 4:42 pm
by milan1612
michaeled314 wrote:rsts how old ar you
you are so better than me at coding
I don't think these forums are here to show how good somebody is at coding
Anyway, funny idea, I didn't know that there were so many anagrams in the English language...
Posted: Sat Jul 26, 2008 4:51 pm
by michaeled314
the other one took 1345238 ms.
Posted: Sat Jul 26, 2008 5:24 pm
by rsts
michaeled314 wrote:rsts how old ar you
you are so better than me at coding
Add about a half century to you. I can't say I'm any better than you - maybe a bit more experienced.
cheers
Posted: Sat Jul 26, 2008 8:00 pm
by mback2k
Code: Select all
OpenConsole()
If ReadFile(0, "dictionary.txt")
Structure anagram
len.l
letter.l[26]
word.s
EndStructure
Define n, start, *currentElement.anagram
NewList dict.anagram()
While Not Eof(0) ; READING + ANALYSING
AddElement(dict())
dict()\word = ReadString(0)
dict()\len = MemoryStringLength(@dict()\word)
For n = 0 To 25
dict()\letter[n] = CountString(dict()\word, Chr(n+'a'))
Next
Wend
CloseFile(0)
start = ElapsedMilliseconds()
ForEach dict() ; COMPARING
*currentElement = @dict()
While NextElement(dict())
If CompareMemory(*currentElement, @dict(), OffsetOf(anagram\word))
PrintN(*currentElement\word+"="+dict()\word)
EndIf
Wend
ChangeCurrentElement(dict(), *currentElement)
Next
PrintN(Str(ElapsedMilliseconds()-start)+"ms")
EndIf
Input()
Running this with a Pentium D 2.8 GHz (Dual Core) took me around 60 seconds (60359ms).
Posted: Sat Jul 26, 2008 8:47 pm
by AND51
michaeled314 wrote:Anyway u ar probably an expert programmerI don't know yur age but I'm turning 14 in about half a month
Sorry, I didn't know that you're just turning 14 and my post was really not a critisizing statement. (By the way, I'm 19 and also a 'hobby programer'.)
My intention was to help you to optimize your program (this one and your future programs). That's why I often re-write other peoples programs.
And rsts said it right, I like "the spirit of competition".
Anyway, I hope my code helps you and if you've goit some questions left you can ask me, of course.
@ Topic:
My code needs 890 453 ms = 14 minutes.
I must add that this machine is very slow, so don't be surprized. My personal PC will be repaired soon and then my results will be okay again. ^^
@ mback2k:
In my opinion, you must measure the entire code...
However, thank you for the trick with
CompareMemory(), I wanted to use this, too, but I didn't know if this was the right way...
And your result (60 s) is quite impressive!
Could you measure the entire code again on your machine? I'm interested in the result...
Posted: Sat Jul 26, 2008 9:06 pm
by mback2k
Code: Select all
start = ElapsedMilliseconds()
OpenConsole()
If ReadFile(0, "dictionary.txt")
Structure anagram
len.l
letter.l[26]
word.s
EndStructure
Define n, start, *currentElement.anagram
NewList dict.anagram()
While Not Eof(0) ; READING + ANALYSING
AddElement(dict())
dict()\word = ReadString(0)
dict()\len = MemoryStringLength(@dict()\word)
For n = 0 To 25
dict()\letter[n] = CountString(dict()\word, Chr(n+'a'))
Next
Wend
CloseFile(0)
ForEach dict() ; COMPARING
*currentElement = @dict()
While NextElement(dict())
If CompareMemory(*currentElement, @dict(), OffsetOf(anagram\word))
PrintN(*currentElement\word+"="+dict()\word)
EndIf
Wend
ChangeCurrentElement(dict(), *currentElement)
Next
EndIf
PrintN(Str(ElapsedMilliseconds()-start)+"ms")
Input()
@AND51
1st run: 60125ms
2nd run: 59234ms
3rd run: 59422ms
Dunno why the other run was slower. As you can see, reading the file does not really add much time.
I am running the code without debugger, compiled as Console application and with dynamic CPU optimizations.
Posted: Sat Jul 26, 2008 10:47 pm
by MrMat
Hi. Try this
Code: Select all
start = ElapsedMilliseconds()
Structure anagram
word.s
count.s
EndStructure
Structure match
word.s
match.s
EndStructure
NewList dict.anagram()
NewList matches.match()
Dim letters.b(26)
OpenConsole()
fileno.l = ReadFile(#PB_Any, "dictionary.txt")
If fileno = 0
PrintN("Cannot open dictionary.txt")
EndIf
While Not Eof(fileno)
AddElement(dict())
dict()\word = ReadString(fileno)
For n = 0 To 25
letters(n) = '0' + CountString(dict()\word, Chr(n + 'a'))
Next
dict()\count = PeekS(@letters(), 26)
Wend
CloseFile(fileno)
SortStructuredList(dict(), #PB_Sort_Ascending, OffsetOf(anagram\count), #PB_Sort_String)
ForEach dict()
*currentElement.anagram = @dict()
While NextElement(dict())
If *currentElement\count = dict()\count
If *currentElement\word <> dict()\word
AddElement(matches())
matches()\word = *currentElement\word
matches()\match = dict()\word
EndIf
Else
Break
EndIf
Wend
ChangeCurrentElement(dict(), *currentElement)
Next
SortStructuredList(matches(), #PB_Sort_Ascending, OffsetOf(anagram\word), #PB_Sort_String)
ForEach matches()
PrintN(matches()\word + " = " + matches()\match)
Next
PrintN("Matches: " + Str(CountList(matches())))
PrintN(Str(ElapsedMilliseconds() - start) + "ms")
Input()
Posted: Sat Jul 26, 2008 11:43 pm
by AND51
mback2k wrote:compiled as Console application and with dynamic CPU optimizations
I assume that "Console application" has no effect, you could also create a "normal" EXE. or is there a difference?
But I'm sure that dynamic CPU optimizations has got no effect, since you're only using PB-commands. As the manual says, there is no PB-command that makes use of CPU-optimizsations yet.
Thank you for your results.