Skip to content

Instantly share code, notes, and snippets.

@mlms13
Created March 22, 2020 19:33
Show Gist options
  • Save mlms13/7dd4f9a658445f4a4afd314415d95cbd to your computer and use it in GitHub Desktop.
Save mlms13/7dd4f9a658445f4a4afd314415d95cbd to your computer and use it in GitHub Desktop.
Distribute work evenly among participants
module Main where
import Prelude
import Data.List (List(..), (:), fromFoldable, sortBy, reverse)
data Task = Task String Int
sortTasksByWeightDesc :: List Task -> List Task
sortTasksByWeightDesc = sortBy compareEffort >>> reverse where
compareEffort (Task _ a) (Task _ b) = compare a b
tasks :: List Task
tasks = fromFoldable
[ Task "Dishes to the kitchen" 2
, Task "Start a load of laundry" 3
, Task "Take out recycling" 4
, Task "Vacuum living room" 4
, Task "Take out compost" 5
, Task "Change laundry" 5
, Task "Fold laundry" 6
, Task "Load the dishwasher" 7
]
-- a naive function to distribute work among 3 participants...
-- step through each task (from biggest to smallest), assigning
-- it to the participant who currently has the lightest load
-- however! this simple algorithm yields 11 | 13 | 12, but
-- an optimal possible solution is 12 | 12 | 12
distributeTasks = sortTasksByWeightDesc >>> go init where
init =
{ a: { tasks: Nil, sum: 0}
, b: { tasks: Nil, sum: 0}
, c: { tasks: Nil, sum: 0}
}
-- assign a task to a participant
addTask {tasks, sum} task@(Task title weight) =
{ tasks: (task:tasks), sum: sum + weight}
-- find the participant with the lightest load and update their list
giveToLightest members@{a, b, c} task
| (a.sum <= b.sum && a.sum <= c.sum) = members {a = (addTask a task)}
| (b.sum <= c.sum) = members {b = (addTask b task)}
| otherwise = members {c = (addTask c task)}
go acc Nil = acc
go acc (x : xs) =
go (giveToLightest acc x) xs
distributed = distributeTasks $ sortTasksByWeightDesc tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment