74 lines
1.7 KiB
Prolog
74 lines
1.7 KiB
Prolog
:- dynamic score/2.
|
|
|
|
best_shuffle :-
|
|
maplist(best_shuffle, ["abracadabra", "eesaw", "elk", "grrrrrr",
|
|
"up", "a"]).
|
|
|
|
best_shuffle(Str) :-
|
|
retractall(score(_,_)),
|
|
length(Str, Len),
|
|
assert(score(Str, Len)),
|
|
calcule_min(Str, Len, Min),
|
|
repeat,
|
|
shuffle(Str, Shuffled),
|
|
maplist(comp, Str, Shuffled, Result),
|
|
sumlist(Result, V),
|
|
retract(score(Cur, VCur)),
|
|
( V < VCur -> assert(score(Shuffled, V)); assert(score(Cur, VCur))),
|
|
V = Min,
|
|
retract(score(Cur, VCur)),
|
|
writef('%s : %s (%d)\n', [Str, Cur, VCur]).
|
|
|
|
comp(C, C1, S):-
|
|
( C = C1 -> S = 1; S = 0).
|
|
|
|
% this code was written by P.Caboche and can be found here :
|
|
% http://pcaboche.developpez.com/article/prolog/listes/?page=page_3#Lshuffle
|
|
shuffle(List, Shuffled) :-
|
|
length(List, Len),
|
|
shuffle(Len, List, Shuffled).
|
|
|
|
shuffle(0, [], []) :- !.
|
|
|
|
shuffle(Len, List, [Elem|Tail]) :-
|
|
RandInd is random(Len),
|
|
nth0(RandInd, List, Elem),
|
|
select(Elem, List, Rest),
|
|
NewLen is Len - 1,
|
|
shuffle(NewLen, Rest, Tail).
|
|
|
|
|
|
% letters are sorted out then packed
|
|
% If a letter is more numerous than the rest
|
|
% the min is the difference between the quantity of this letter and
|
|
% the sum of the quantity of the other letters
|
|
calcule_min(Str, Len, Min) :-
|
|
msort(Str, SS),
|
|
packList(SS, Lst),
|
|
sort(Lst, Lst1),
|
|
last(Lst1, [N, _]),
|
|
( N * 2 > Len -> Min is 2 * N - Len; Min = 0).
|
|
|
|
|
|
|
|
% almost the same code as in "run_length" page
|
|
packList([],[]).
|
|
|
|
packList([X],[[1,X]]) :- !.
|
|
|
|
|
|
packList([X|Rest],[XRun|Packed]):-
|
|
run(X,Rest, XRun,RRest),
|
|
packList(RRest,Packed).
|
|
|
|
|
|
run(Var,[],[1,Var],[]).
|
|
|
|
run(Var,[Var|LRest],[N1, Var],RRest):-
|
|
run(Var,LRest,[N, Var],RRest),
|
|
N > 0,
|
|
N1 is N + 1.
|
|
|
|
|
|
run(Var,[Other|RRest], [1,Var],[Other|RRest]):-
|
|
dif(Var,Other).
|