Continuing my exploration of Prolog, I decided to write a program to generate a schedule for peer reviews.

Each week, each developer in the team is paired with a different developer. In an ideal world there would be a simple rotation – e.g. with 4 developers it might look like this:

  • Week 1: Dev 1 + Dev 2; Dev 3 + Dev 4
  • Week 2: Dev 1 + Dev 3; Dev 2 + Dev 4
  • Week 3: Dev 1 + Dev 4; Dev 2 + Dev 3
  • Repeat…

But in practice it isn’t that simple – sometimes developers take holidays so aren’t available for a week, and sometimes new people join or old ones leave.

This means we need to:

  1. Keep a record of historical pairings
  2. Attempt to pair developers who haven’t worked together for the longest time
  3. Maximise the total time between pairings across all developers

I currently do this manually each week using a Google Sheets – but below is a Prolog script I created to do that (peer-reviews.pl).

Warning: It’s a bit rough around the edges! I probably won’t use it in practice – it was just for practice – so I’ve not spent any time polishing it.

#!/usr/bin/env swipl

%---------------------------------------
% Configuration
%---------------------------------------

% List of developers currently available
% (comment out anyone currently on holiday or unavailable)
developer(charnieze).
developer(danny).
developer(dave).
developer(fletcher).
developer(heidi).
developer(izzy).
developer(matt).
developer(nick).
developer(pete).
developer(sam).
developer(vaiva).

% History - one line per week, most recent week first
% "-" indicates no pairing for that developer for that week
history([
   [[charnieze,dave], [danny,fletcher], [heidi,pete], [izzy,-], [matt,sam], [nick,vaiva]],
   [[charnieze,heidi], [danny,izzy], [dave,fletcher], [matt,nick], [pete,sam], [vaiva,-]],
   [[charnieze,-], [danny,pete], [heidi,izzy], [matt,vaiva], [nick,sam]],
   [[charnieze,danny], [dave,vaiva], [fletcher,-], [heidi,nick], [izzy,sam], [matt,pete]],
   [[charnieze,sam], [danny,matt], [dave,-], [fletcher,nick], [heidi,vaiva], [izzy,pete]],
   [[charnieze,vaiva], [danny,sam], [dave,matt], [fletcher,pete], [heidi,-], [izzy,nick]],
   [[charnieze,pete], [danny,dave], [fletcher,izzy], [heidi,matt], [nick,-], [sam,vaiva]],
   [[charnieze,nick], [danny,vaiva], [dave,heidi], [fletcher,sam], [izzy,matt]],
   [[charnieze,matt], [danny,nick], [dave,izzy], [fletcher,vaiva], [heidi,sam], [pete,-]],
   [[charnieze,fletcher], [danny,heidi], [dave,sam], [izzy,vaiva], [matt,-], [nick,pete]],
   [[charnieze,izzy], [danny,-], [dave,pete], [fletcher,heidi], [matt,sam], [nick,vaiva]],
   [[charnieze,heidi], [danny,izzy], [dave,nick], [fletcher,matt], [pete,vaiva], [sam,-]],
   [[charnieze,dave], [danny,fletcher], [heidi,pete], [izzy,-], [matt,vaiva], [nick,sam]],
   [[charnieze,danny], [dave,fletcher], [heidi,izzy], [matt,nick], [pete,sam], [vaiva,-]]
]).

%---------------------------------------
% Program
%---------------------------------------

% Generate a set (alphabetical list) of all developers
% To manually test it, run this in the interactive interpreter:
% all_developers(X).
all_developers(Result) :-
    setof(Developer, developer(Developer), Result).

% Ensure there is an even number of developers - if not, pair someone with no-one ('-')
% all_developers_even(X).
all_developers_even(Result) :-
    all_developers(Developer),
    developers_even(Developer, Result).

developers_even([], []).

developers_even([Developer], [Developer, -]).

developers_even([Dev1, Dev2 | Remaining], [Dev1, Dev2 | Result]) :-
    developers_even(Remaining, Result).

% Select a pair of developers from a list of available developers
% Always selects the first available member of developers and then one other
% all_developers_even(Developer), select_pair(Developer, Pair, Remaining).
select_pair(Available, Pair, Remaining) :-
    [Developer_1 | Developer_N] = Available,
    select(Developer_2, Developer_N, Remaining),
    Pair = [Developer_1, Developer_2].

% A week consists of a list of pairs of developers with no duplicates
% week(X).
week(Pairs) :-
    all_developers_even(Developers),
    week_accumulator(Developers, [], Pairs).

week_accumulator([], Pairs, PairsSorted) :-
    sort(Pairs, PairsSorted).

week_accumulator(Available, Pairs, Result) :-
    select_pair(Available, Pair, Remaining),
    week_accumulator(Remaining, [Pair | Pairs], Result).

% Next we need to score each pair based on the last time that pair occurred
% score([chris, danny], X).
% score([danny, deborah], X).
% score([heidi, fred], X).
score(Pair, Score) :-
    history(History),
    last_occurrence(Pair, History, 1, Score).

last_occurrence(_, [], _, 1000).

last_occurrence(Pair, [Pairs | _], WeekNum, WeekNum) :-
    member(Pair, Pairs),
    !.

last_occurrence(Pair, [_ | OlderHistory], WeekNum, Result) :-
    NextWeekNum is WeekNum + 1,
    last_occurrence(Pair, OlderHistory, NextWeekNum, Result).

% Calculate the sum of the scores for a week
% week(Week), score_week(Week, X).
score_week(Week, Result) :-
    maplist(score, Week, Scores),
    sum_list(Scores, Score),
    Result = result{ week: Week, score: Score }.

% Generate every possible week in a list
% all_weeks(Weeks).
all_weeks(Weeks) :-
    findall(Week, week(Week), Weeks).

% Score each week
% all_weeks_scored(X).
all_weeks_scored(Result) :-
    all_weeks(Weeks),
    maplist(score_week, Weeks, Result).

% Sort the weeks by score descending
% best_weeks(X).
best_weeks(Result) :-
    all_weeks_scored(Weeks),
    sort(score, @>=, Weeks, Result).

% Pretty-print the results
print_week([]).

print_week([Pair]) :-
    write(Pair),
    !.

print_week([Pair | Pairs]) :-
    write(Pair),
    write(', '),
    print_week(Pairs).

print_results([]).

print_results([Result | Results]) :-
    % Prints in reverse order so the best scoring are displayed last
    % (The rest may scroll off the screen)
    print_results(Results),
    format('~d~6+[', [ Result.score ]),
    print_week(Result.week),
    % Trailing comma allows easier copy-pasting into the history list (above)
    write('],'),
    nl.

go :-
    best_weeks(Result),
    print_results(Result),
    !.

% Automatically execute and run the script
main :-
    go,
    halt.

% Comment this line out to allow interactive testing
:- initialization main.

This is the output:

6  [[charnieze,dave], [danny,fletcher], [heidi,pete], [izzy,-], [matt,sam], [nick,vaiva]],
10 [[charnieze,-], [danny,izzy], [dave,fletcher], [heidi,pete], [matt,sam], [nick,vaiva]],
10 [[charnieze,heidi], [danny,pete], [dave,fletcher], [izzy,-], [matt,sam], [nick,vaiva]],
<snip...>
64 [[charnieze,fletcher], [danny,heidi], [dave,nick], [izzy,matt], [pete,vaiva], [sam,-]],
67 [[charnieze,izzy], [danny,-], [dave,nick], [fletcher,matt], [heidi,sam], [pete,vaiva]],
69 [[charnieze,izzy], [danny,heidi], [dave,nick], [fletcher,matt], [pete,vaiva], [sam,-]],

The lowest value is the same as the previous week (first item in the history list). The highest is the one that maximises the number of weeks between repeating pairs across all developers. Here is a copy of the history list from above, with those pairs highlighted:

history([
   % Remember the top entries are the most recent here:
   [[charnieze,dave], [danny,fletcher], [heidi,pete], [izzy,-], [matt,sam], [nick,vaiva]],
   [[charnieze,heidi], [danny,izzy], [dave,fletcher], [matt,nick], [pete,sam], [vaiva,-]],
   [[charnieze,-], [danny,pete], [heidi,izzy], [matt,vaiva], [nick,sam]],
   [[charnieze,danny], [dave,vaiva], [fletcher,-], [heidi,nick], [izzy,sam], [matt,pete]],
   [[charnieze,sam], [danny,matt], [dave,-], [fletcher,nick], [heidi,vaiva], [izzy,pete]],
   [[charnieze,vaiva], [danny,sam], [dave,matt], [fletcher,pete], [heidi,-], [izzy,nick]],
   [[charnieze,pete], [danny,dave], [fletcher,izzy], [heidi,matt], [nick,-], [sam,vaiva]],
   [[charnieze,nick], [danny,vaiva], [dave,heidi], [fletcher,sam], [izzy,matt]],
   [[charnieze,matt], [danny,nick], [dave,izzy], [fletcher,vaiva], [heidi,sam], [pete,-]],
   [[charnieze,fletcher], [danny,heidi], [dave,sam], [izzy,vaiva], [matt,-], [nick,pete]],
   [[charnieze,izzy], [danny,-], [dave,pete], [fletcher,heidi], [matt,sam], [nick,vaiva]],
   [[charnieze,heidi], [danny,izzy], [dave,nick], [fletcher,matt], [pete,vaiva], [sam,-]],
   [[charnieze,dave], [danny,fletcher], [heidi,pete], [izzy,-], [matt,vaiva], [nick,sam]],
   [[charnieze,danny], [dave,fletcher], [heidi,izzy], [matt,nick], [pete,sam], [vaiva,-]]
]).

Note that [charnieze,heidi] and [danny,izzy] from the same row as the other four aren’t selected because they also appear further up in the history, so they score less.

With 11 or 12 developers, the script takes 3 seconds to run. However, with 13 or 14 developers it takes 47 seconds, and with 15 or more it fails completely:

ERROR: /home/dave/prolog/peer-reviews.pl:162: Initialization goal raised exception:
ERROR: Out of global stack

If I were to write it again, I would probably change the strategy – instead of generating all possible permutations for the week and then scoring them, I would accept the first result above a target score for each developer – e.g. “> 10 weeks ago”. Prolog would then attempt to combine these into a valid week, and backtrack if that is not possible. It there are no possible permutations above that score, I would then reduce the target score by 1 week at a time.

Other improvements could include:

  • Read the staff list and history from CSV files or a database
  • Append the best result to the history automatically, or allow the user to choose
  • Additional scoring constraints – e.g.
    • Some developers like to be paired for 2 weeks at a time instead of 1 week
    • Some developers already work closely together, so don’t need to be paired as often