CODEWITHSUNDEEP
listprolog
CpCd0y
CpCd0y

Reputation: 710

Find repetitions in a list

How would I go about finding consecutive repetition of a string in a list in prolog.

What I'm exactly trying to find, for example, is this:

input => output
AAAAAA  =>  6*(A)
ABABAB  =>  3*(AB)
ABCABCABC  =>  3*(ABC)

I wrote a DCG grammar for this and I'm trying to have it give me this as a result.

Here's the grammar, if needed:

exp --> term.
exp --> term, [+], exp.

term --> factor.
term --> digit, [*], exp.

factor --> elem.
factor --> ['S'], ['['], sym, [']']. %S[(A)(B),(C)]
factor --> ['<'], alt, ['>'], ['/'], ['<'], alt, ['>']. %<(A)>/<(B)(C)(D)>
factor --> ['('], exp, [')'].

sym --> factor.
sym --> factor, [','], factor.
sym --> factor, sym.

alt --> factor.
alt --> factor, alt.

elem --> char.
elem --> char, elem.
char --> [D], {is_alnum(D)}.
digit --> [D], {is_alnum(D)}.
digit --> [D], {number(D)}.

nbr_to_char(N, Cs) :-
    name(Cs, [N]).
str_to_list(S, Cs) :-
    name(S, Xs),
    maplist(nbr_to_char, Xs, Cs).

eval(L) :-
    str_to_list(L, X),
exp(X, []).

Thanks for any help.

Upvotes: 2

Views: 156

Answers (1)

CapelliC
CapelliC

Reputation: 60004

I think what you're after is pack(dcg_util). But also consider append/2:

?- A=`ababab`.
A = [97, 98, 97, 98, 97, 98].

?- append([X,X,X],$A).
X = [97, 98],
A = [97, 98, 97, 98, 97, 98] ;
false.

Now, if we just find an easy way to make lists of repeated variables, we have a fairly powerful construct, we can use to tackle to problem. Let's try:

?- length(L,3),maplist(=(X),L).
L = [X, X, X].

So:

?- length(L,_),maplist(=(X),L),append(L,$A).
L = [[97, 98, 97, 98, 97, 98]],
X = A, A = [97, 98, 97, 98, 97, 98] ;
L = [[97, 98], [97, 98], [97, 98]],
X = [97, 98],
A = [97, 98, 97, 98, 97, 98] ;
^CAction (h for help) ? abort
% Execution Aborted

oops, never ending story... but a bit boring. Need a bit more code, enforcing the domain knowledge (bagging, really...)

?- length($A,U),between(1,U,N),length(L,N),maplist(=(X),L),append(L,$A).
U = 6,
N = 1,
L = [[97, 98, 97, 98, 97, 98]],
X = A, A = A, A = [97, 98, 97, 98, 97, 98] ;
U = 6,
N = 3,
L = [[97, 98], [97, 98], [97, 98]],
X = [97, 98],
A = A, A = [97, 98, 97, 98, 97, 98] ;
false.

Upvotes: 2

Related Questions