Prolog Run Length Encoding

Question

Since I am stuck at home with nothing to do due to the virus I've decided to start learning Prolog I've been working through different questions from learn Prolog and from 99 Prolog problems.

I am currently stuck on a Run Length Encoding question and would appreciate any help or guidance regarding the problem.

Here is the question I am stuck on:

Write a predicate encode/2 that takes the uncompressed list as a first parameter and returns the compressed list as shown as the second parameter. For example:

encode(['a','b','b','c','c','c','d','d'],X) should yield X = [ (a, 1), (b, 2), (c, 3), (d, 2)] .
encode(['a','p','p','l','e'],X) should yield X = [ (a, 1), (p, 2), (l, 1), (e, 1)] .```

And then to decode it:

Write a predicate decode/2 that takes the compressed list as a first parameter and returns the uncompressed list as shown as the second parameter. For example:
```decode([],X) should yield X = [].
decode([(a,1), (b,2), (c,3), (d,2)],X) should yield X = ['a','b','b','c','c','c','d','d'] .
decode([(a,1), (p,2), (l,1), (e,1)],X) should yield X =  ['a','p','p','l','e'].```

yes you recap the question but what is your difficulty? where are you stuck? have you written anything, something? please include it in your question so we can try help you get unstuck. do you not know where to even start? what is the problem exactly? — Will Ness

Will Ness Will Ness · Accepted Answer · 2020-04-27T14:57:38

You can start from what you already have:

encode(['a','b','b','c','c','c','d','d'], X) :-
    X = [ (a, 1), (b, 2), (c, 3), (d, 2) ] .

which means it is also the case that

encode(['b','b','c','c','c','d','d'], X2) :-
    X2 = [ (b, 2), (c, 3), (d, 2) ] .

and thus

encode(['a','b','b','c','c','c','d','d'], X) :-
    encode(['b','b','c','c','c','d','d'], X2)
    X = [ (a, 1) | X2 ] .

which is the same as

encode( L, X) :-
    L = ['a','b','b','c','c','c','d','d'],
    L = [ H | T ],
    encode( T, X2),
    X = [ (a, 1) | X2 ] .

which is the same as

encode( L, X) :-
    L = ['a','b','b','c','c','c','d','d'],
    L = [ H | T ],
    encode( T, X2),
    add_encoded( H, X2, X).

add_encoded( 'a', [ (b, 2), (c, 3), (d, 2) ], X2 ) :-
    X2 = [ (a, 1) | [ (b, 2), (c, 3), (d, 2) ] ] .

Do you see? Do you see how the code writes itself when we generalize our concrete cases by replacing concrete terms with logical variables? Can you proceed with this further still?

Prolog Run Length Encoding

1 Answers