RabbitFarm

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

Part 1

You are given a string and an array of indices of same length as string. Write a script to return the string after re-arranging the indices in the correct order.

Solution

letter_shuffle(Shuffled, Letter, Index):-
    nth(Index, Shuffled, Letter).

Sample Run

$ gprolog --consult-file prolog/ch-1.p
| ?- length(L, 9), maplist(letter_shuffle(L), "lacelengh", [4, 3, 1, 6, 5, 9, 7, 8, 2]), atom_codes(A, L).

A = challenge
L = [99,104,97,108,108,101,110,103,101]

yes

Notes

Many Prologs, including GNU Prolog, treat double quoted strings as lists of the character codes representing each letter. So here maplist/3 is presented such a list as well as the given list of indices. We give a letter_shuffle/3 an empty list of the right length and all that is left is for nth/3 to assign the letters as needed.

Part 2

You are given an array of non-negative integers, @ints. Write a script to return the minimum number of operations to make every element equal zero.

Solution

subtract_minimum(Minimum, X, Y):-
    Y is X - Minimum.

zero_array(Numbers, Operations):-
    delete(Numbers, 0, NumbersNoZero),
    zero_array(NumbersNoZero, 0, Operations).
zero_array([], Operations, Operations).    
zero_array(Numbers, OperationsCounter, Operations):-
    delete(Numbers, 0, NumbersNoZero),
    min_list(NumbersNoZero, Minimum),
    maplist(subtract_minimum(Minimum), NumbersNoZero, NumbersSubtracted),
    succ(OperationsCounter, OperationsCounterNext), 
    delete(NumbersSubtracted, 0, NumbersSubtractedNoZero),
    zero_array(NumbersSubtractedNoZero, OperationsCounterNext, Operations).

Sample Run

$ gprolog --consult-file prolog/ch-2.p
| ?- zero_array([1, 5, 0, 3, 5], Operations).

Operations = 3 ? 

yes
| ?- zero_array([0], Operations).

Operations = 0 ? 

yes
| ?- zero_array([2, 1, 4, 0, 3], Operations).

Operations = 4 ? 

yes
| ?- 

Notes

A convenient issue with this problem is that once a list entry is zero we can ignore it. Since we can ignore it we can delete/3 it and thereby reduce the list eventually to the empty list, the base of our recursion. Each time we recurse we find the minimum element, subtract it from all others, and increment the number of operations.

References

Challenge 226