Skip to content

Instantly share code, notes, and snippets.

@Engelberg
Created October 7, 2015 04:03
Show Gist options
  • Save Engelberg/d8007588ce5a83fd0303 to your computer and use it in GitHub Desktop.
Save Engelberg/d8007588ce5a83fd0303 to your computer and use it in GitHub Desktop.
Loco model for splitting a sequence of numbers into two equally-sized parts, minimizing the disparity of their sums
(ns mark.teamsplit
(:require [loco.core :as l]
[loco.constraints :refer :all]))
; Although this problem was stated in terms of a group of players
; with multiple attributes, we can just represent each player by
; a single number, so this function just takes the list of numbers.
(defn find-teams
"Players is a list of player strengths, timeout is in milliseconds"
[players timeout]
(let [n (count players),
team-vars (for [i (range n)] [:t i])
; For each player i, t_i is either -1 or 1, depending on team assignment.
team-fd (for [v team-vars]
($in v -1 1)),
; Previous constraint says -1<=t_i<=1. Now, we eliminate 0 as an option.
not-zero (for [v team-vars]
($!= v 0))
; Ensure the two teams are the same size, i.e.,
; the number of 1's equals the number of -1's, i.e.,
; they all add up to 0 (or can be off by one, if odd number of players)
size-fd [($in :size-disparity -1 1)]
same-size [($= (apply $+ team-vars) :size-disparity)]
; We create a variable representing the disparity to minimize.
disparity-fd [($in :disparity 0 2147483646 :bounded)] ; might as well use largest int
; The formula for disparity.
disparity [($= :disparity
($abs ($scalar team-vars players)))]
; Build our model from all these constraints.
model (concat
team-fd not-zero size-fd same-size disparity-fd disparity),
; Find the solution, using the timeout.
solution (l/solution model :minimize :disparity :feasible false :timeout timeout)
; Now, we'll need to interpret the return results, building the subsequences
; out of the -1 and 1 assignments. For that, it will be useful to have players as vector.
players (vec players)]
{:team1
(for [i (range (count players))
:when (pos? (get solution [:t i]))]
(players i)),
:team2
(for [i (range (count players))
:when (neg? (get solution [:t i]))]
(players i)),
:disparity (:disparity solution)}))
;Usage:
;(find-teams [71 8 50 9 78 35 76 83 94 33 38 60 17 41 41 52 55 57 73 78 54 55 65 4] 1000)
;{:team1 (71 8 9 78 83 33 17 55 73 78 54 55), :team2 (50 35 76 94 38 60 41 41 52 57 65 4), :disparity 1}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment