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

%%% Find a binary Hamming code (N,D) with K elements.

hamming_code(N,D,K) :-
   M is N*K, length(Code,M),
   domain(Code,0,1),
   first_zero(N,Code), %%% [0,...,0] is a word
   constraints(Code,D,N),
 %  lessico(Code,N),
%%%   unflat(Code,DeCode,N),
%%% BUILT-IN IN SICStus   lex_chain(DeCode),
   statistics(runtime,_),
   labeling([ffc],Code),!,
   statistics(runtime,[_,T]),
   write('Solution found (msecs): '),write(T),nl,
   write(N,N,Code),nl.
hamming_code(_,_,_) :-
   statistics(runtime,[_,T]),
   write('No solution (msecs): '),
   write(T),nl,fail.

%%% Constraints

constraints(Code,_,N) :-
   length(Code,CL),
   CL =< N, !.
constraints(Code,D,N) :-
   extract(N,Code,First,Last),
   allpairs(Last,First,D,N),
   constraints(Last,D,N).

allpairs([],_,_,_).
allpairs(Code,Current,D,N) :-
  extract(N,Code,First,Last),
  pair(Current,First,D),
  allpairs(Last,Current,D,N).

pair(Word1,Word2,D) :-
  diffvars(Word1,Word2,Diff),
  domain(Diff,0,1),
  sum(Diff,'#>=',D).

diffvars([],[],[]).
diffvars([A|R],[B|S],[D|T]) :-
  D #= abs(A-B),
  diffvars(R,S,T).

first_zero(0,_).
first_zero(N,[0|R]):-
  N > 0, M is N -1,
  first_zero(M,R).

extract(N,Code,First,Last) :-
  length(First,N),
  append(First,Last,Code).

unflat(Code,[Code],N) :-
   length(Code,M),
   M =< N, !.
unflat(Code,[ First |R],N) :-
   extract(N,Code,First,Last),
   unflat(Last,R,N).

%%% PLAY WITH 7,4,9 OR 8,5,5 =>

lessico(Code,N) :-
   length(Code,M),
   M =< N, !.
lessico(Code,N) :-
   extract(N,Code,First,Last),
   extract(N,Last,Second,_),
   less(First,Second,1),
   lessico(Last,N).
   
less([],[],0).
less([A|R],[B|S],Out) :-
   less(R,S,Flag),
   Out #<=> (A #< B #\/ (A #= B #/\ Flag)).
 %   (A,B,Flag,Out) in [(0,1,0,1),(0,1,1,1),(0,0,0,0),(0,0,1,1),(1,1,0,0),(1,1,1,1),(1,0,0,0),(1,0,1,0)].
   
   
%%%%%%% PRINT RESULT:

write(_,_,[]) :- !.
write(0,N,Code) :-
   !,nl, write(N,N,Code).
write(M,N,[A|Code]) :-
   M1 is M -1,
   write(A),write(' '),
   write(M1,N,Code).
