RabbitFarm

2024-10-06

The Weekly Challenge 289 (Prolog Solutions)

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

Part 1: Third Maximum

You are given an array of integers, @ints. Write a script to find the third distinct maximum in the given array. If a third maximum doesn’t exist then return the maximum number.

The majority of the work can be done in a couple of lines. We need only sort the distinct integers in the list and then return either the third largest number or, if none exists, the largest.

⟨sort and return the third largest (or just the largest) 1 ⟩≡

: third_maximum(L, ThirdMaximum):-
sort(L, Sorted),
reverse(Sorted, SortedReverse),
(nth(3, SortedReverse, ThirdMaximum), !;
last(Sorted, ThirdMaximum)).
◇

: Fragment referenced in 2.

The rest of the code just wraps this predicate into a file.

"ch-1.p" 2≡

: ⟨sort and return the third largest (or just the largest) 1 ⟩
◇

Sample Run

$ gprolog --consult-file prolog/ch-1.p 
| ?- third_maximum([5, 6, 4, 1], X). 
 
X = 4 
 
yes 
| ?- third_maximum([4, 5], X). 
 
X = 5 
 
yes 
| ?- third_maximum([1, 2, 2, 3], X). 
 
X = 1 
 
yes 
| ?-

Part 2: Jumbled Letters

Your task is to write a program that takes English text as its input and outputs a jumbled version

The rules for jumbling are given as follows:

The first and last letter of every word must stay the same.
The remaining letters in the word are scrambled in a random order (if that happens to be the original order, that is OK).
Whitespace, punctuation, and capitalization must stay the same.
The order of words does not change, only the letters inside the word.

Looking closer at these rules the main thing we need to concern ourselves with is jumbling the letters with the exception of the first and last. The use of map will ensure the words are processed in order. To make sure the first/last letters are unchanged also depends on detecting punctuation.

Let’s first concern ourselves with identifying punctuation. We need to maintain a record of where they were located so we can put them back in later. We do this by recursively examining each character code to see if it is in the range for punctuation and, if it matches, creating an Index-Punctuation pair.

⟨identify punctuation 3 ⟩≡

: punctuation_index(Codes, IndexPunctuation):-
punctuation_index(Codes, 1, IndexPunctuation).
punctuation_index([], _, []).
punctuation_index([Code|Codes], I, [I-P|IndexPunctuation]):-
((Code >= 33, Code =< 46);
(Code >= 58, Code =< 64)),
P = Code,
succ(I, J),
punctuation_index(Codes, J, IndexPunctuation).
punctuation_index([_|Codes], I, IndexPunctuation):-
succ(I, J),
punctuation_index(Codes, J, IndexPunctuation).
◇

: Fragment referenced in 7.

With these Index-Punctuation pairs created let’s write some code which will put them back in when we’re done with the jumbling of the other characters.

⟨add punctuation back into the jumbled word 4 ⟩≡

: add_punctuation(Word, IndexPunctuation, PunctuatedWord):-
add_punctuation(Word, 1, IndexPunctuation, PunctuatedWord).
add_punctuation([], _, [], []).
add_punctuation([Code|Codes], _, [], [Code | PunctuatedWord]):-
add_punctuation(Codes, _, [], PunctuatedWord).
add_punctuation([], _, [_-P|IndexPunctuation], [P | PunctuatedWord]):-
add_punctuation([], _, IndexPunctuation, PunctuatedWord).
add_punctuation([Code|Codes], I, [I-P|IndexPunctuation], [P, Code | PunctuatedWord]):-
succ(I, J),
add_punctuation(Codes, J, IndexPunctuation, PunctuatedWord).
add_punctuation([Code|Codes], I, [X-P|IndexPunctuation], [Code | PunctuatedWord]):-
succ(I, J),
add_punctuation(Codes, J, [X-P|IndexPunctuation], PunctuatedWord).
◇

: Fragment referenced in 7.

The bulk of the work is done in jumble_word/2 which, after the punctuation has been located and removed from further consideration, permutates the remaining letters and then randomly selects a permutation. This is then combined with the first/last letters.

Words that are one or two characters in length are not jumbled.

⟨jumble a single word 5 ⟩≡

: jumble_word(Word, Jumble):- atom_length(Word, Length), Length > 2, atom_codes(Word, Codes), punctuation_index(Codes, IndexPunctuation), !, subtract(Codes, [33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 58, 59, 60, 61, 62, 63, 64], PunctuationRemoved), append([First|Middle], [Last], PunctuationRemoved), findall(Permutation, (permutation(Middle, Permutation)), Permutations), length(Permutations, NP), succ(NP, NumberPermutations), randomize, random(1, NumberPermutations, R), nth(R, Permutations, P), append([First|P], [Last], J), add_punctuation(J, IndexPunctuation, JP), atom_codes(Jumble, JP). jumble_word(Word, Jumble):- atom_length(Word, Length), Length =< 2, Jumble = Word.
◇

: Fragment referenced in 7.

Jumbling words is done by using maplist/3 to call jumble_word/2 on the list of words.

⟨jumble words 6 ⟩≡

: jumble_words(Words, Jumble):-
maplist(jumble_word, Words, Jumble).
◇

: Fragment referenced in 7.

Finally, let’s assemble our completed code into a single file.

"ch-2.p" 7≡

: ⟨identify punctuation 3 ⟩
⟨add punctuation back into the jumbled word 4 ⟩
⟨jumble a single word 5 ⟩
⟨jumble words 6 ⟩
◇

Sample Run

$ gprolog prolog/ch-2.p 
| ?- jumble_words([in, the, ’ASCII’, range, match, all, ’non-controls.’], Jumbled). 
 
Jumbled = [in,the,’ASCII’,rgnae,mtach,all,’nnc-troolons.’] ? 
 
(161 ms) yes 
| ?-

References

The Weekly Challenge 289
Generated Code

posted at: 18:42 by: Adam Russell | path: /prolog | permanent link to this entry