RabbitFarm

2025-05-18

The Weekly Challenge 321 (Prolog Solutions)

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

Part 1: Distinct Average

You are given an array of numbers with even length. Write a script to return the count of distinct average. The average is calculate by removing the minimum and the maximum, then average of the two.

Our solution will be pretty short, contained in just a single file that has the following structure.

"ch-1.p" 1≡

: ⟨first last 2 ⟩
⟨distinct average 3 ⟩
◇

We’ll define a predicate for getting the minimum/maximum pairs. These will be the first/last pairs from a sorted list.

⟨first last 2 ⟩≡

: first_last([], []).
first_last(Numbers, FirstLastPairs):-
nth(1, Numbers, First),
last(Numbers, Last),
append([First|Rest], [Last], Numbers),
first_last(Rest, FirstLastPairs0),
append([[First, Last]], FirstLastPairs0, FirstLastPairs).
◇

: Fragment referenced in 1.

We just need a single predicate to sort the given list of numbers, call first_last/2, call maplist/2 with sum_list/2, sort/2 the results, and return the count of unique pairs. Since we only have pairs of numbers their averages will be the same if their sums are the same. (This also allows us to ignore potential floating point number annoyances). Also, remember that sort/2 will remove duplicates.

⟨distinct average 3 ⟩≡

: distinct_average(Numbers, DistinctAverage):-
sort(Numbers, NumbersSorted),
first_last(NumbersSorted, MinimumMaximumPairs),
maplist(sum_list, MinimumMaximumPairs, MinimumMaximumSums),
sort(MinimumMaximumSums, MinimumMaximumSumsSorted),
length(MinimumMaximumSumsSorted, DistinctAverage).
◇

: Fragment referenced in 1.

Sample Run

$ gprolog --consult-file prolog/ch-1.p 
| ?- distinct_average([1, 2, 4, 3, 5, 6], DistinctAverage). 
 
DistinctAverage = 1 ? 
 
yes 
| ?- distinct_average([0, 2, 4, 8, 3, 5], DistinctAverage). 
 
DistinctAverage = 2 ? 
 
yes 
| ?- distinct_average([7, 3, 1, 0, 5, 9], DistinctAverage). 
 
DistinctAverage = 2 ? 
 
yes 
| ?-

Part 2: Backspace Compare

You are given two strings containing zero or more #. Write a script to return true if the two given strings are same by treating # as backspace.

We’ll use a DCG approach to process the strings and maintain an list of characters.

"ch-2.p" 4≡

: ⟨state of the character list 5 ⟩
⟨process string 6 ⟩
⟨backspace compare 7 ⟩
◇

Let’s have some predicates for maintaining the state of a character list as the DCG processes the string.

⟨state of the character list 5 ⟩≡

: characters(Characters), [Characters] --> [Characters].
characters(C, Characters), [Characters] --> [C].
◇

: Fragment referenced in 4.

Now we need to process the strings, which we’ll treat as lists of character codes.

⟨process string 6 ⟩≡

: process(String) --> characters(C, Characters),
{String = [Code | Codes],
last(C, PreviousCharacter),
((Code \== 35, char_code(C0, Code),
append(C, [C0], Characters));
(append(Characters, [PreviousCharacter], C))), !},
process(Codes).
process([]) --> [].
◇

: Fragment referenced in 4.

Finally, let’s wrap the calls to the DCG in a small predicate using phrase/3. This will process both strings and then compare the results.

⟨backspace compare 7 ⟩≡

: backspace_compare(String1, String2):-
phrase(process(String1), [[’’]], [R1]),
delete(R1, ’’, R2),
atom_chars(Result1, R2),
phrase(process(String2), [[’’]], [R3]),
delete(R3, ’’, R4),
atom_chars(Result2, R4),
Result1 == Result2.
◇

: Fragment referenced in 4.

Sample Run

$ gprolog --consult-file prolog/ch-2.p 
| ?- backspace_compare("ab#c", "ad#c"). 
 
yes 
| ?- backspace_compare("ab##", "a#b#"). 
 
yes 
| ?- backspace_compare("a#b", "c"). 
 
no 
| ?-

References

The Weekly Challenge 321
Generated Code

posted at: 13:02 by: Adam Russell | path: /prolog | permanent link to this entry