Anagram Find -- Simple

michaeled314 · Post by **michaeled314** » Sat Jul 26, 2008 1:06 am

Download: http://www.cset.oit.edu/~yangs/CST420/l ... ionary.txt

Run:

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

AND51 · Post by **AND51** » Sat Jul 26, 2008 4:09 pm

Your code could be better.

You wrote:

Code: Select all

OpenFile(0,"dictionary.txt")

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!

michaeled314 · Post by **michaeled314** » Sat Jul 26, 2008 4:22 pm

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

rsts · Post by **rsts** » Sat Jul 26, 2008 4:31 pm

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

michaeled314 · Post by **michaeled314** » Sat Jul 26, 2008 4:36 pm

rsts how old ar you

you are so better than me at coding

milan1612 · Post by **milan1612** » Sat Jul 26, 2008 4:42 pm

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...

michaeled314 · Post by **michaeled314** » Sat Jul 26, 2008 4:51 pm

the other one took 1345238 ms.

rsts · Post by **rsts** » Sat Jul 26, 2008 5:24 pm

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

mback2k · Post by **mback2k** » Sat Jul 26, 2008 8:00 pm

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).

AND51 · Post by **AND51** » Sat Jul 26, 2008 8:47 pm

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...

mback2k · Post by **mback2k** » Sat Jul 26, 2008 9:06 pm

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.

MrMat · Post by **MrMat** » Sat Jul 26, 2008 10:47 pm

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()

AND51 · Post by **AND51** » Sat Jul 26, 2008 11:43 pm

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.