I attached a solution to the general case. I can't call it "my"
solution because I've borrowed some ideas from code Steve Hunter
sent me (the most notable being the use of set intersection to
reject invalid pair couples like: X:Y & Y:Z (same state name
used twice) - I had been using a more brute-force check.
There are two commented-out lines in getStates() that can be
individually uncommented to test various perversities in input.
(The first just checks the fact that case should be insignificant,
the second produces multiple valid pair couples (15 new ones).
I hope people have (are still having) fun with this!
--
Steve Wampler -- [EMAIL PROTECTED]
The gods that smiled on your birth are now laughing out loud.
procedure main()
st := &time
states := mapList(getStates())
equivClasses := table()
statePairs := table()
# Pass one builds a table of equivalence classes (all state pairs in the
# same equivalence class have the same characters in them)
# It also does a little bookkeeping to avoid work later.
every (state1 := |get(states)) & (state2 := !states) do {
if state1 ~== state2 then {
if state2 << state1 then statePair := state2||":"||state1
else statePair := state1||":"||state2
signature := getClassSignature(statePair)
/equivClasses[signature] := set()
insert(equivClasses[signature], statePair)
statePairs[statePair] := set(state1, state2)
}
}
# Pass two produces all valid state pair couples in each equivalence class.
# The expense here is in discarding couples such as "X:Y and Z:X".
every equivClass := !equivClasses do {
while *equivClass > 1 do {
delete(equivClass, lastPair := ?equivClass)
every *(statePairs[lastPair] ** statePairs[pair := !equivClass]) =
0 do {
write(lastPair," and ", pair)
}
}
}
write("Time: ", (&time-st)/1000.0)
end
# Build a signature identifying the equivalence class for state pair s.
# (All the letters in alphabetic order).
procedure getClassSignature(s)
ns := ""
every ns ||:= (upto(c := !cset(s), s), " " ~== c)
return ns
end
# Map all state names to LC.
procedure mapList(aList)
every put(nL := [], map(!aList))
return nL
end
procedure getStates()
return ["Alabama", "Alaska", "Arizona", "Arkansas", "California",
"Colorado", "Connecticut", "Delaware", "Florida", "Georgia",
"Hawaii", "Idaho", "Illinois", "Indiana", "Iowa", "Kansas",
"Kentucky", "Louisiana", "Maine", "Maryland", "Massachusetts",
"Michigan", "Minnesota", "Mississippi", "Missouri", "Montana",
"Nebraska", "Nevada", "New Hampshire", "New Jersey",
"New Mexico", "New York", "North Carolina", "North Dakota",
"Ohio", "Oklahoma", "Oregon", "Pennsylvania", "Rhode Island",
"South Carolina", "South Dakota", "Tennessee", "Texas", "Utah",
"Vermont", "Virginia", "Washington", "West Virginia",
# "NeW kORy", "nEW KorY", "Wen Kory", "York New", "Kory New",
# "York New", "York New", "New Kory", "Wen Kory", "Kory New",
"Wisconsin", "Wyoming"]
end
-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys-and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
_______________________________________________
Unicon-group mailing list
[EMAIL PROTECTED]
https://lists.sourceforge.net/lists/listinfo/unicon-group
