USING: kernel math strings arrays hashtables assocs sequences accessors locals namespaces random combinators sorting math.order system prettyprint io.launcher.unix io ; IN: minconflicts ! state data information TUPLE: state { stateName string read-only } { stateNeighbors array read-only } ; : ( string array -- state ) state boa ; SYMBOLS: seCSP assignment selectedVar ; ! ////////////////////////////////////////////////////////////////////////////// ! min conflicts implementation ! ////////////////////////////////////////////////////////////////////////////// > swap stateNeighbors>> swap getStateColor [| neighbors col | neighbors [ col hasConflict ] map ] call [ f = ] all? not ; : checkAssignment ( -- ? ) seCSP get [ checkConflictNeighbors ] map [ f = ] all? ; : getColorFromInt ( int -- string ) H{ { 0 "RED" } { 1 "BLUE" } { 2 "GREEN" } { 3 "PURPLE" } } at ; : generateRandomAssignment ( -- ) seCSP get [| csp | csp [ stateName>> ] map [ 4 random getColorFromInt swap setStateColor ] each ] call ; : selectConflictVariable ( -- state ) seCSP get [| csp | csp length random selectedVar set [ selectedVar get csp nth checkConflictNeighbors f = ] [ csp length random selectedVar set ] while selectedVar get csp nth ] call ; : checkConflictColors ( string array -- int ) [| color neighbors | neighbors [ getStateColor color = ] map [ t = ] filter length ] call ; ! arguments: state, return color : selectMinConflictValue ( state -- string ) stateNeighbors>> [| neighbors | { 0 1 2 3 } dup [ getColorFromInt neighbors checkConflictColors ] map [ 2array ] 2map [ [ second ] bi@ <=> ] sort first first getColorFromInt ] call ; PRIVATE> SYMBOLS: iterations count ; : minConflicts ( int -- ) iterations set 0 count set generateRandomAssignment [ count get iterations get < ] [ checkAssignment [ iterations get count get + count set ] [ selectConflictVariable dup selectMinConflictValue swap stateName>> setStateColor 1 count get + count set ] if ] while checkAssignment [ "SUCCESS: " print assignment get . ] [ "FAILURE." print ] if flush ; : runMinConflicts ( -- ) { T{ state { stateName "NC" } { stateNeighbors { "VA" "TN" "SC" "GA" } } } T{ state { stateName "VA" } { stateNeighbors { "NC" "TN" "KY" "WV" } } } T{ state { stateName "WV" } { stateNeighbors { "VA" "KY" } } } T{ state { stateName "TN" } { stateNeighbors { "KY" "NC" "VA" "MS" "AL" "GA" } } } T{ state { stateName "MS" } { stateNeighbors { "TN" "AL" } } } T{ state { stateName "AL" } { stateNeighbors { "MS" "GA" "FL" "TN" } } } T{ state { stateName "GA" } { stateNeighbors { "AL" "FL" "SC" "TN" "NC" } } } T{ state { stateName "FL" } { stateNeighbors { "AL" "GA" } } } T{ state { stateName "SC" } { stateNeighbors { "GA" "NC" } } } T{ state { stateName "KY" } { stateNeighbors { "TN" "VA" "WV" } } } } seCSP set H{ { "NC" "none" } { "VA" "none" } { "WV" "none" } { "TN" "none" } { "MS" "none" } { "AL" "none" } { "GA" "none" } { "FL" "none" } { "SC" "none" } { "KY" "none" } } assignment set 1000 minConflicts ; MAIN: runMinConflicts