Prolog Puzzles

MinimiseCandies.pl

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
/*

How few candies does the teacher need?
--------------------------------------

Problem:
Alice is a teacher of kindergarten. She wants to give some candies to
the children in her class. All the children sit in a line and each of
them has a rating score according to his or her usual performance.
Alice must give at least 1 candy for each children, and she must give
her candies according to the children's ratings subject to the
condition that for any two adjacent children, if one's rating is
higher than the other's, s/he must get more candies than the other.
Alice wants to save money, so she wants to give as few candies as
possible in total.

Assume:
- Child rating is integer in [0;5].

Solutions:
- 'mc_00' is a deterministic solution in plain Prolog;
- 'mc_11' is a fully relational solution in CLP(FD).
NOTE: No input validation in place.

Latest version:
<https://gist.github.com/jp-diegidio/c3e2f6e25eba99f8297f>

Adapted from:
<https://groups.google.com/d/msg/sci.math/r6RNg1ZGASk/gZSzYdgqIkAJ>
<http://stackoverflow.com/questions/11292913/candies-interviewstreet>

Examples:

?- mc_00([1,2,2], Counts, Sum).
Counts = [1, 2, 1],
Sum = 4.

?- mc_11([1,2,2], Counts, Sum).
Counts = [1, 2, 1],
Sum = 4.

?- time(mc_00([2,3,4,4,4,2,1,3,4], Counts, Sum)).
% 63 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
Counts = [1, 2, 3, 1, 3, 2, 1, 2, 3],
Sum = 18.

?- time(mc_11([2,3,4,4,4,2,1,3,4], Counts, Sum)).
% 34,904 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
Counts = [1, 2, 3, 1, 3, 2, 1, 2, 3],
Sum = 18.

?- S=3, MaxRC=[2,3], mc_11(Rs,Cs,S,MaxRC), mc_write(Rs,Cs,S),nl, fail.
[0,1] => [1,2] (3)
[0,2] => [1,2] (3)
[1,0] => [2,1] (3)
[1,2] => [1,2] (3)
[2,0] => [2,1] (3)
[2,1] => [2,1] (3)
[0,0,0] => [1,1,1] (3)
[1,1,1] => [1,1,1] (3)
[2,2,2] => [1,1,1] (3)
false.

?- set_random(seed(0)),findall(R,(between(1,30,I),R is random(5)),Rs).
Rs = [3, 0, 1, 3, 0, 2, 3, 4, 3|...].

?- time(mc_00($Rs,Cs,S)).
% 228 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
Cs = [2, 1, 2, 3, 1, 2, 3, 4, 1|...],
S = 53.

?- time(mc_11($Rs,Cs,S)).
% 181,285 inferences, 0.047 CPU in 0.047 seconds (100% CPU, 3873586 Lips)
Cs = [2, 1, 2, 3, 1, 2, 3, 4, 1|...],
S = 53.

*/
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%(SWI-Prolog 7.2.3)

:- use_module(library(lists)).
:- use_module(library(clpfd)).

mc_write(Rs, Cs, S) :-
	format('~w => ~w (~w)', [Rs, Cs, S]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  mc_00(+Ratings, -Counts, -Sum) is det.
%%
%%  Direct deterministic solution.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

mc_00(Rs, Cs, S) :-
	mc_00__do(Rs, Cs, S).

mc_00__do([], [], 0).
mc_00__do([R| Rs], [C| Cs], S) :-
	mc_00__do__i(Rs, _, Cs, [R, 1, C], S).

mc_00__do__i([], [], [], [_, B0, B0], B0).
mc_00__do__i([R| Rs], [B| Bs], [C| Cs], [R0, B0, C0], S0) :-
	(R0 < R -> B is B0 + 1; B is 1),
	mc_00__do__i(Rs, Bs, Cs, [R, B, C], S),
	(R0 > R, B0 =< C -> C0 is C + 1; C0 is B0),
	S0 is S + C0.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  mc_11(?Ratings, ?Counts, ?Sum)         is nondet.
%%  mc_11(?Ratings, ?Counts, ?Sum, +MaxRC) is nondet.
%%
%%  Fully relational solution in CLP(FD).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% NOTE: Since we label Rs first, R_max
%       affects the search space significantly!
mc_11__sup(r, 5).
mc_11__sup(c, 10_000).	% virtually unlimited

mc_11(Rs, Cs, S) :-
	mc_11__sup(r, R_max),
	mc_11__sup(c, C_max),
	mc_11(Rs, Cs, S, [R_max, C_max]).

mc_11(Rs, Cs, S, MaxRC) :-
	mc_11__gen(Rs, Cs, S),
	mc_11__rel(Rs, Cs_rel, S_rel, MaxRC),
	mc_11__sol(Rs, Cs_rel, S_rel, Cs, S).

mc_11__gen(Rs, Cs, S) :-
	same_length(Rs, Cs),
	(	var(S)            -> true
	;	length(Cs, L),
		(	S < L         -> !, fail
		;	S > (L+1)*L//2 -> fail
		;	true
		)
	).

mc_11__sol(Rs, Cs_rel, S_rel, Cs, S) :-
	labeling([], Rs),
	once(labeling([min(S_rel)], [S_rel])),
	S = S_rel,
	labeling([], Cs_rel),
	Cs = Cs_rel.

mc_11__rel(Rs, Cs, S, MaxRC) :-
	mc_11__dom(Rs, Cs, S, MaxRC),
	mc_11__con(Rs, Cs, S).

mc_11__dom(Rs, Cs, _, [R_max, C_max]) :-
	same_length(Rs, Cs),
	Rs ins 0 .. R_max,
	Cs ins 1 .. C_max.

mc_11__con([], [], 0).
mc_11__con([R| Rs], [C| Cs], S) :-
	sum([C| Cs], #=, S),
	mc_11__con__i(Rs, Cs, R, C).

mc_11__con__i([], [], _, _).
mc_11__con__i([R| Rs], [C| Cs], R0, C0) :-
	R0 #< R #==> C0 #< C,
	R0 #> R #==> C0 #> C,
	mc_11__con__i(Rs, Cs, R, C).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%