%% A Prolog program that assigns tasks to people
%%  based on the people's capabilities and time available.
%%  Very limited error checking on whether parameters are in correct format.
%%
%% Author: Zach Tomaszewski
%% Date: 27 Nov 2002
%%

%%
%% assign_tasks(Tasks,  % list of tasks to assign 
%                       %   Each task/element is of the form:
%                       %   [Task-name, Task-class, Task-time]
%%             People,  % list people and their available times
%                       %   Each person-time pair/element is of the form:
%                       %   [Person-name, Amount-of-time-available]
%%             Skills,  % list of people capable of performing a Task-class
%                       %   Each element is of the form:
%                       %   [Task-class, [Person1-name, Person2-name, ... ]]
%%        Assignments)  % list of assignments
%                       %   Each element is of the form:
%                       %   [Task-name, Person-name] 
%% Tasks can be done by only one person who has both the skill and time
%% available to do it.
%%

  %base case: there are no more tasks to assign.
assign_tasks([], People, Skills, []).

  %matches true if can assign the first task.
assign_tasks(Tasks, People, Skills, Assignments):-
  [FirstTask|_] = Tasks,  	%grab the first task in the list
  capable(FirstTask, Skills, Capable),  %get list of people capable of this task 
  assign_a_task(Tasks, Capable, People, Skills, Assignments).



%% assign_tasks(Tasks,  % the list of tasks to assign
%                       %  (The first task in the list--Task--is primarily
%                       %   used here.)
%%            Capable,  % simple list of people who have the skills to undertake
%                       %   the first task in tasks
%%             People,  % list people and their available times
%%             Skills,  % list of people capable of performing a Task-class
%%        Assignments)  % list of assignments
%
%% See assign_tasks for documenation for the format of the
%  Tasks, People, Skills, and Assignments lists.
%  Determines whether a capable person has enough time.  
%   If so, it add the assignment to Assignments 
%      and tries assign-tasks on RestOfTasks
%   Otherwise it tries assigning the task to next capable person.
%%

%
%base case: out of capable people to try.  
%
assign_a_task(Tasks, [], People, Skills, Assignments):-
  fail.

%
%normal, successful case: they have enough time,
%so assign this task and the rest of them
%
assign_a_task([Task|RestOfTasks], [FirstCapable|RestOfCapable], 
              People, Skills, 
              [[TaskName, FirstCapable]|Assignments]):-
  member([FirstCapable, PersonTime], People),  %check that FirstCapable has
  [TaskName, _, TaskTime] = Task,              %enough time to do the task
  PersonTime >= TaskTime,
  NewTime is PersonTime - TaskTime,              %update their time in People   
  substitute([FirstCapable, PersonTime], People,  %creating the list NewPeople
             [FirstCapable, NewTime], NewPeople), 
  assign_tasks(RestOfTasks, NewPeople, Skills, Assignments). 
   
%
%Otherwise, this task can't be assigned to the first Capable person.
%Try assigning to the next one.
%
assign_a_task(Tasks, [FirstCapable|RestOfCapable], 
              People, Skills, Assignments):-
   assign_a_task(Tasks, RestOfCapable, People, Skills, Assignments). 


 
%%
%% capable(   Task,    %  In the form: [Task-name, Task-class, Task-time]
%%            Skills,  %  list of people capable of performing a Task-class
%                      %   Each element is of the form:
%                      %   [Task-class, [Person1-name, Person2-name, ... ]]
%%           Capable   %  simple list of those people capable of the given task. 
%
capable(Task, Skills, Capable):-
  [_, TaskClass, _]=Task,                %get the class of the task
  member([TaskClass, Capable], Skills).  %and use it to match the list of
                                           %those people with that skill.


%%
%% substitute(Item,            % an item
%%            List,            % a list
%%            ReplacementItem  % a replacement for Item
%%            ResultingList    % List with the first instance of Item replaced
%%                             % by ReplacementItem (only one substitution)
%%
%% (This function code and docs by Dr. Chin.)
%%
substitute(_, [], _, []).
substitute(Item, [Item | Rest], NewItem, [NewItem | Rest]) :- !.
substitute(Item, [DiffItem | Rest], NewItem, [DiffItem | NewRest]) :-
    substitute(Item, Rest, NewItem, NewRest).


%%
%% member (Item,          %some item
%%         List)            %a list of items
%%
%% Resolves to true if Item is an element in List.
%% (Already exists in some Prolog implementations.)
%%
member(Item, [Item|_]).
member(Item, [_|List]):-
  member(Item, List).