CODEWITHSUNDEEP
prolog
Brody2019
Brody2019

Reputation: 87

Prolog Run Length Encoding

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'].```

Upvotes: 2

Views: 761

Answers (1)

Will Ness
Will Ness

Reputation: 71099

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?

Upvotes: 3

Related Questions