Is there a quick PB alternative to Associative Arrays?
Posted: Mon Jun 08, 2009 2:14 pm
On this web page:
http://thraxil.org/users/anders/posts/2 ... nt-Lenses/
is posed the problem "Take the names of two U.S. States, mix them all together, then rearrange the letters to form the names of two other U.S. States. What states are these?"
The Python solution proposed there is amazingly efficient, mainly because of it's good use of an Associative Array (Dictionary). This got me thinking as to which tools/techniques (perhaps even SQLite) would result in the most efficient solution in PureBasic. How super-quick a solution can you find?
If you wish to have a try ...
So that benchmark comparisions are possible, I suggest you determine the ratio of the elapsed time of your solution with that of mine below (even though mine only finds one of the two pairs of U.S. states) and of all the proposed solutions we we can see which has the best time ratio with my version.
My version is:
http://thraxil.org/users/anders/posts/2 ... nt-Lenses/
is posed the problem "Take the names of two U.S. States, mix them all together, then rearrange the letters to form the names of two other U.S. States. What states are these?"
The Python solution proposed there is amazingly efficient, mainly because of it's good use of an Associative Array (Dictionary). This got me thinking as to which tools/techniques (perhaps even SQLite) would result in the most efficient solution in PureBasic. How super-quick a solution can you find?
If you wish to have a try ...
So that benchmark comparisions are possible, I suggest you determine the ratio of the elapsed time of your solution with that of mine below (even though mine only finds one of the two pairs of U.S. states) and of all the proposed solutions we we can see which has the best time ratio with my version.
My version is:
Code: Select all
; U.S. States
; thraxil.org/users/anders/posts/2007/10/30/A-Simple-Programming-Puzzle-Seen-Through-Three-Different-Lenses
DataSection
Data.i 50
Data.s "alabama","alaska","arizona","arkansas","california","colorado"
Data.s "connecticut","delaware","florida","georgia","hawaii","idaho"
Data.s "illinois","indiana","iowa","kansas","kentucky","louisiana"
Data.s "maine","maryland","massachusetts","michigan","minnesota"
Data.s "mississippi","missouri","montana","nebraska","nevada"
Data.s "newhampshire","newjersey","newmexico","newyork","northcarolina"
Data.s "northdakota","ohio","oklahoma","oregon","pennsylvania","rhodeisland"
Data.s "southcarolina","southdakota","tennessee","texas","utah","vermont"
Data.s "virginia","washington","westvirginia","wisconsin","wyoming"
Data.s ""
EndDataSection
Declare.s Sort(txt$)
Define time, states, state, state1, state2, seen$=" ", key$, txt$
time = ElapsedMilliseconds()
; Get the data
Read states
Dim states$(states)
For state = 1 To states
Read.s states$(state)
Next state
; Solve (find only the first solution)
For state1 = 2 To states
For state2 = 1 To state1-1
key$ = states$(state1)+states$(state2)
key$ = Sort(key$)
If FindString(seen$, " "+key$+" ", 1)
time - ElapsedMilliseconds()
txt$ = "Found: "+states$(state1)+" and "+states$(state2)+#CRLF$
txt$ + "The corresponding other two states are undetermined"+#CRLF$+#CRLF$
txt$ + "Elapsed time = "+Str(-time)+" milliseconds"
MessageRequester("U.S. States Solution", txt$)
Break
EndIf
seen$ + key$+" "
Next state2
Next state1
End
Procedure.s Sort(txt$)
; Sort individual characters within txt$
Protected size, p
size = Len(txt$)
Dim a$(size)
; Copy txt$ to array
For p = 1 To size
a$(p) = Mid(txt$, p, 1)
Next p
SortArray(a$(), #PB_Sort_Ascending)
; Copy array to txt$
txt$ = ""
For p = 1 To size
txt$ + a$(p)
Next p
ProcedureReturn txt$
EndProcedure
