RabbitFarm

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

Part 1

You are given a string with alphabetic characters only: A..Z and a..z. Write a script to find out if the usage of Capital is appropriate if it satisfies at least one of the rules.

Solution

all_small([]).
all_small([H|T]):-
    H >= 97,
    H =< 122,   
    all_small(T).

all_capitals([]).
all_capitals([H|T]):-
    H >= 65,
    H =< 90,   
    all_capitals(T).

capital_detection([]).
capital_detection([H|T]):-
    H >= 65,
    H =< 90,
    all_capitals(T).
capital_detection([H|T]):-
    H >= 65,
    H =< 90,
    all_small(T).    
capital_detection([H|T]):-
    H >= 97,
    H =< 122,
    all_small(T).    

Sample Run

$ gprolog --consult-file prolog/ch-1.p
| ?- capital_detection("Perl").

true ? 

yes
| ?- capital_detection("TPF"). 

true ? 

(1 ms) yes
| ?- capital_detection("PyThon").

no
| ?- capital_detection("raku").  

yes

Notes

The rules to be satisfied are:

1) Only first letter is capital and all others are small.

2) Every letter is small.

3) Every letter is capital.

While I know it is not everyone's favorite way of handling strings in Prolog, I prefer to stick with the codes representation of double quotes strings. Here the solution is pretty straightforward, with the code being in most ways a direct translation of the rules.

Part 2

You are given an encoded string consisting of a sequence $s of numeric characters: 0..9. Write a script to find the all valid different decodings in sorted order.

Solution

digits([1, 2]).

alphabet(1, 'A').
alphabet(2, 'B').
alphabet(3, 'C').
alphabet(4, 'D').
alphabet(5, 'E').
alphabet(6, 'F').
alphabet(7, 'G').
alphabet(8, 'H').
alphabet(9, 'I').
alphabet(10,'J').
alphabet(11, 'K').
alphabet(12, 'L').
alphabet(13, 'M').
alphabet(14, 'N').
alphabet(15, 'O').
alphabet(16, 'P').
alphabet(17, 'Q').
alphabet(18, 'R').
alphabet(19, 'S').
alphabet(20, 'T').
alphabet(21, 'U').
alphabet(22, 'V').
alphabet(23, 'W').
alphabet(24, 'X').
alphabet(25, 'Y').
alphabet(26, 'Z').

list_chunks(_, [], []).
list_chunks(List, [H|T], [PrefixNumber|RestNumbers]):-
    length(Prefix, H),
    prefix(Prefix, List),
    append(Prefix, Rest, List),
    number_codes(PrefixNumber, Prefix),
    list_chunks(Rest, T, RestNumbers).

sum(Digits, Length):-
    sum([], Digits, Length, 0).

sum(Digits, Digits, _, _). 
sum(Partial, Digits, Length, Sum):-   
    Sum < Length, 
    digits(L),
    member(X, L),
    S is Sum + X,
    sum([X | Partial], Digits, Length, S). 

decode(Encoded, Decoded):-
    number_codes(Encoded, EncodedCodes),
    length(EncodedCodes, EncodedLength),
    findall(Digits,(
        sum(Digits, EncodedLength), 
        sum_list(Digits, EncodedLength)), DigitList),
    findall(Chunks, (
        member(ChunkSizes, DigitList),
        list_chunks(EncodedCodes, ChunkSizes, Chunks)), ChunkList),
    findall(DecodedChunk,(
        member(C, ChunkList),
        maplist(alphabet, C, DecodedChunkChars),
        atom_chars(DecodedChunk, DecodedChunkChars)), Decoded).  

Sample Run

$ gprolog --consult-file prolog/ch-2.p
| ?- decode(11, Decoded).

Decoded = ['AA','K']

yes
| ?- decode(1115, Decoded).

Decoded = ['AAAE','KAE','AKE','AAO','KO']

(1 ms) yes
| ?- decode(127, Decoded). 

Decoded = ['ABG','LG']

yes

Notes

There is an element of this task which reminded me of a much older problem presented back in TWC 075. In brief, the question was how many ways could coins be used in combination to form a target sum. My solution used a mix of Prolog and Perl since Prolog is especially well suited for elegant solutions to these sorts of combinatorial problems.

I recognized that this week we have a similar problem in how we may separate the given encoded string into different possible chunks for decoding. Here we know that no chunk may have value greater than 26 and so we can only choose one or two digits at a time. How many ways we can make these one or two digit chunks is the exact same problem, somewhat in hiding, as in TWC 075!

For the Perl Solutions to this problem I re-used much of that older code mentioned above. Also, that Prolog code which was embedded in the Perl code was used as the basis for this pure Prolog solution.

decode/2 is the main predicate. We need to work across all possible splits of the list of the number and it's easiest to use findall/3 to cover the splitting of the number, the chunking, and the final decoding of all possible combinations.

References

Challenge 190