RabbitFarm

2025-03-02

The Weekly Challenge 310 (Prolog Solutions)

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

Part 1: Arrays Intersection

You are given a list of array of integers. Write a script to return the common elements in all the arrays.

Let’s define a predicate that can be called via maplist. This will just wrap member and be used to return a list of common elements. We’ll also remove duplicates (via sort).

Note that because the predicate used with maplist must be true for all list elements we’ll return a nil value if there is no match. We just need to make sure to delete all the nils before further using the list.

⟨common element finder 1 ⟩≡

: common_elements(L0, L1, Common):-
maplist(common_element(L0), L1, C0),
sort(C0, C1),
delete(C1, nil, Common).
common_element(L, X, X):-
member(X, L).
common_element(L, X, nil):-
\+ member(X, L).
◇

: Fragment referenced in 3.

The plan is to find the common elements in the first two lists and then compare those common elements against the rest of the lists, only keeping elements that continue to be in common. We’ll use tail recursion and an accumulator here.

⟨process lists 2 ⟩≡

: intersections(Lists, Intersections):-
intersections(Lists, [], Intersections).
intersections([H0, H1|[]], [], Intersections):-
common_elements(H0, H1, Intersections).
intersections([H0, H1|[]], IntersectionsAccum, Intersections):-
common_elements(H0, H1, Common),
common_elements(Common, IntersectionsAccum, Intersections).
intersections([H0, H1|T], IntersectionsAccum, Intersections):-
common_elements(H0, H1, Common),
append(IntersectionsAccum, Common, I),
intersections([Common|T], I, Intersections).
◇

: Fragment referenced in 3.

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

"ch-1.p" 3≡

: ⟨common element finder 1 ⟩
⟨process lists 2 ⟩
◇

Sample Run

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

Part 2: Sort Odd Even

You are given an array of integers. Write a script to sort odd index elements in decreasing order and even index elements in increasing order in the given array.

To solve this problem we need to do the following

seperate the odd and even indexed numbers
sort the two lists as directed
combine the results

This problem was written with 0-based indices in mind so we will keep that in mind when calculating whether an index is odd or even.

⟨seperate the odd and even indexed numbers 4 ⟩≡

: odd_even_indexed(List, Odds, Evens):-
length(List, L),
findall(Odd,(
between(1, L, Index),
succ(I, Index),
M is I rem 2,
\+ M == 0,
nth(Index, List, Odd)
), Odds),
findall(Even,(
between(1, L, Index),
succ(I, Index),
M is I rem 2,
M == 0,
nth(Index, List, Even)
), Evens).
◇

: Fragment referenced in 8.

We’ll need a few more predicates to contain most of the rest of the work needed. To do the descending sort we’ll take the negatives of the numbers. We also need to combine the final result.

⟨negate numbers 5 ⟩≡

: negate(X, Y):-
Y is -1 * X.
◇

: Fragment referenced in 8.

⟨combine 6 ⟩≡

: combine(OddsSorted, EvensSorted, Combined):-
combine(OddsSorted, EvensSorted, 0, [], Combined).
combine([], [], _, Combined, Combined).
combine([O|OT], EvensSorted, Index, CombinedAccum, Combined):-
M is Index rem 2,
\+ M == 0,
append(CombinedAccum, [O], C),
succ(Index, I),
combine(OT, EvensSorted, I, C, Combined).
combine(OddsSorted, [E|ET], Index, CombinedAccum, Combined):-
M is Index rem 2,
M == 0,
append(CombinedAccum, [E], C),
succ(Index, I),
combine(OddsSorted, ET, I, C, Combined).
◇

: Fragment referenced in 8.

⟨sort odd evens 7 ⟩≡

: sort_odd_evens(List, Sorted):-
odd_even_indexed(List, Odds, Evens),
maplist(negate, Odds, OddsNegated),
sort(OddsNegated, OddsNegatedSorted),
maplist(negate, OddsNegatedSorted, OddsSorted),
sort(Evens, EvensSorted),
combine(OddsSorted, EvensSorted, Sorted).
◇

: Fragment referenced in 8.

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

"ch-2.p" 8≡

: ⟨seperate the odd and even indexed numbers 4 ⟩
⟨negate numbers 5 ⟩
⟨combine 6 ⟩
⟨sort odd evens 7 ⟩
◇

Sample Run

$ gprolog prolog/ch-2.p 
| ?- sort_odd_evens([4, 1, 2, 3], Sorted). 
 
Sorted = [2,3,4,1] ? 
 
yes 
| ?- sort_odd_evens([3, 1], Sorted). 
 
Sorted = [3,1] ? 
 
yes 
| ?- sort_odd_evens([5, 3, 2, 1, 4], Sorted). 
 
Sorted = [2,3,4,1,5] ? 
 
yes 
| ?-

References

The Weekly Challenge 310
Generated Code

posted at: 23:09 by: Adam Russell | path: /prolog | permanent link to this entry