! Author : Zac Brown ! Date : 11.01.2009 ! Filename : minconflicts.factor ! Description : Implementation of MinConflicts on 10 Southeastern ! United States states. USING: kernel math strings arrays hashtables assocs sequences accessors locals namespaces io random combinators sorting math.order system ; 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 ; inline : checkAssignment ( -- ? ) seCSP get [ checkConflictNeighbors ] map [ t = ] all? ; inline : getColorFromInt ( int -- string ) { { [ dup 0 = ] [ "RED" ] } { [ dup 1 = ] [ "BLUE" ] } { [ dup 2 = ] [ "GREEN" ] } { [ dup 3 = ] [ "PURPLE" ] } } cond swap drop ; inline : generateRandomAssignment ( -- ) seCSP get [| csp | csp [ stateName>> ] map [ 4 random getColorFromInt swap setStateColor ] each ] call ; inline : 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 ; inline : checkConflictColors ( string array -- int ) [| color neighbors | neighbors [ getStateColor color = ] map [ t = ] filter length ] call ; inline ! arguments: state, return color : selectMinConflictValue ( state -- string ) dup stateName>> print stateNeighbors>> [| neighbors | { 0 1 2 3 } dup [ getColorFromInt neighbors checkConflictColors ] map [ 2array ] 2map [ [ second ] bi@ <=> ] sort dup print first first getColorFromInt ] call ; inline PRIVATE> SYMBOLS: iterations count ; : minConflicts ( int -- ) iterations set 0 count set generateRandomAssignment [ count get iterations get < ] [ checkAssignment [ 1000000 count set ] [ selectConflictVariable dup selectMinConflictValue swap stateName>> setStateColor 1 count get + count set ] if ] while ; inline : 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 10 minConflicts assignment get print ; inline MAIN: runMinConflicts ! runMinConflicts