:- use_module(library(lists), [append/3]).

:- dynamic(memo_compress/2).
memo_compress([C],[C]).
memo_compress([C1,C2],[C1,C2]).

compress(Initial,Compressed) :-
	( memo_compress(Initial,Compressed) ->
	    true
	;
	    length(Initial,LenInitial),
	    CurrentBest = Initial,
	    LenCurrentBest = LenInitial,
	    compress(Initial,CurrentBest,LenCurrentBest,Compressed),
	    assert(memo_compress(Initial,Compressed))
	).

compress(Initial,CurrentBest,LenCurrentBest,Compressed) :-
	( compress_with_bound(Initial,LenCurrentBest,NewBest) ->
	    length(NewBest,NewLenBest),
	    compress(Initial,NewBest,NewLenBest,Compressed)
	;
	    Compressed = CurrentBest
	).

compress_with_bound(Initial,LenBound,Better) :-
	repetition_compress(Initial,LenBound,Better).
compress_with_bound(Initial,LenBound,Better) :-
	two_piece_compress(Initial,LenBound,Better).

repetition_compress(Initial,LenBound,Better) :-
	chopup(Initial,Piece,Repeated),
	( Piece = [C] ->
	    2 < LenBound,
	    Better = [C,Repeated]
	;
	    compress(Piece,CompressedPiece),
	    append(['('|CompressedPiece], [')',Repeated], Better),
	    length(Better,LenBetter),
	    LenBetter < LenBound
	).




two_piece_compress(Initial,LenBound,Better) :-
	append(Piece1,Piece2,Initial),
	Piece1 \== [],
	Piece2 \== [],
	compress(Piece1,Compressed1),
	length(Compressed1,LenCompressed1),
	LenCompressed1 < LenBound,
	compress(Piece2,Compressed2),
	length(Compressed2,LenCompressed2),
	LenCompressed1 + LenCompressed2 < LenBound,
	append(Compressed1,Compressed2,Better).

chopup(List,Part,Repeated) :-
	append(Part,Rest,List),
	Part \== [], Rest \== [],
	count_parts(Rest,Part,1,Repeated).

count_parts([],_,I,O) :- !, O = I.
count_parts(Rest,Part,I,O) :-
	append(Part,Rest1,Rest),
	I1 is I + 1,
	count_parts(Rest1,Part,I1,O).