Secret santa assignment

.envrc

use_nix

input.lp

person(
	alice;
	bob;
	carol;
	dave;
	eve).

are_family(
	bob, carol;
	carol, dave).

Makefile

time_clingo: secret_santa.lp input.lp
	time \
	  clingo \
	    --models '0' \
	    --opt-mode 'optN' \
	    secret_santa.lp \
	    input.lp

time_python:
	time python -c 'exit'

secret_santa.lp

% Secret Santa assignment

% Generators
% ----------

% Everyone gives a single gift. (Each gifter must give a single gift)
1 { gives(Gifter, Giftee) : person(Giftee) } 1 :-
	person(Gifter).
% Everyone receives a single gift. (Each giftee must receive a single gift)
1 { gives(Gifter, Giftee) : person(Gifter) } 1 :-
  person(Giftee).


% Restrictions
% ------------

% Hard restrictions:
% * There must be at least 4 people. Solutions are not so secret otherwise.
:- { person(_) } < 4.

% * You can't give gifts to yourself.
:- gives(P, P).


% Soft restrictions:
#const penalty = 1.
% * Avoid giving gifts to family members.
:~ gives(P1, P2), are_family(P1, P2). [penalty,P1,P2]

are_family(P, P) :-
	person(P).
are_family(P1, P2) :-
	are_family(P2, P1).
are_family(P1, P2) :-
	person(P1),
	person(P2),
	person(P),
	are_family(P, P1),
	are_family(P, P2).


% Misc
% ----

% Only show `gives(A, B)`.
#show gives/2.

shell.nix

let
  pkgs = import <nixpkgs> {};
in
{
  programmeEnv = pkgs.stdenv.mkDerivation {
    name = "Secret_Santa";

    buildInputs = with pkgs; [
      clingo

      gnumake
    ];
  };
}

clingo secret_santa.lp input.lp

clingo version 5.6.2
Reading from secret_santa.lp ...
Solving...
Answer: 1
gives(alice,dave) gives(bob,eve) gives(carol,alice) gives(dave,bob) gives(eve,carol)
Optimization: 1
OPTIMUM FOUND

Models       : 1
  Optimum    : yes
Optimization : 1
Calls        : 1
Time         : 0.004s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.004s