Last active
August 29, 2015 14:27
-
-
Save jp-diegidio/c3e2f6e25eba99f8297f to your computer and use it in GitHub Desktop.
Prolog Puzzles
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
/* | |
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). | |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment