58 lines
1.8 KiB
Text
58 lines
1.8 KiB
Text
link factors
|
|
|
|
procedure GNsolve(S)
|
|
local min, max
|
|
st := &time
|
|
equivClasses := table()
|
|
statePairs := table()
|
|
/S := getStates()
|
|
every put(states := [], map(!S)) # Make case insignificant
|
|
min := proc("min",0) # Link "factors" loses max/min functions
|
|
max := proc("max",0) # ... these statements get them back
|
|
|
|
# Build a table of equivalence classes (all state pairs in the
|
|
# same equivalence class have the same characters in them)
|
|
# Output new pair couples *before* adding each state pair to class.
|
|
|
|
every (state1 := |get(states)) & (state2 := !states) do {
|
|
if state1 ~== state2 then {
|
|
statePair := min(state1, state2)||":"||max(state1,state2)
|
|
if /statePairs[statePair] := set(state1, state2) then {
|
|
signature := getClassSignature(state1, state2)
|
|
/equivClasses[signature] := set()
|
|
every *(statePairs[statePair] ** # require 4 distinct states
|
|
statePairs[pair := !equivClasses[signature]]) == 0 do {
|
|
write(statePair, " and ", pair)
|
|
}
|
|
insert(equivClasses[signature], statePair)
|
|
}
|
|
}
|
|
}
|
|
|
|
write(&errout, "Time: ", (&time-st)/1000.0)
|
|
end
|
|
|
|
# Build a (Godel) signature identifying the equivalence class for state pair s.
|
|
|
|
procedure getClassSignature(s1, s2)
|
|
static G
|
|
initial G := table()
|
|
/G[s1] := gn(s1)
|
|
/G[s2] := gn(s2)
|
|
return G[s1]*G[s2]
|
|
end
|
|
|
|
procedure gn(s) # Compute the Godel number for a string (letters only)
|
|
static xlate
|
|
local p, i, z
|
|
initial {
|
|
xlate := table(1)
|
|
p := create prime()
|
|
every i := 1 to 26 do {
|
|
xlate[&lcase[i]] := xlate[&ucase[i]] := @p
|
|
}
|
|
}
|
|
z := 1
|
|
every z *:= xlate[!s]
|
|
return z
|
|
end
|