RabbitFarm
2023-11-26
The Weekly Challenge 244 (Prolog Solutions)
The examples used here are from the weekly challenge problem statement and demonstrate the working solution.
Part 1
You are given an array of integers. Write a script to calculate the number of integers smaller than the integer at each index.
Solution
smaller([], _, 0).
smaller([H|Integers], X, Y):-
smaller(Integers, X, Y0),
((X > H, succ(Y0, Y));
(X =< H, Y = Y0)).
count_smaller(Integers, CountSmaller):-
maplist(smaller(Integers), Integers, CountSmaller).
Sample Run
% gprolog --consult-file prolog/ch-1.p
| ?- count_smaller([2, 2, 2], CountSmaller).
CountSmaller = [0,0,0]
yes
| ?- count_smaller([6, 5, 4, 8], CountSmaller).
CountSmaller = [2,1,0,3] ?
yes
| ?- count_smaller([8, 1, 2, 2, 3], CountSmaller).
CountSmaller = [4,0,1,1,3] ?
yes
| ?-
Notes
Probably this is the most obvious way to count up smaller elements as
required. In order to cut down on the recursion I call smaller/3
via
a maplist/3
.
Part 2
You are given an array of integers representing the strength. Write a script to return the sum of the powers of all possible combinations; power is defined as the square of the largest number in a sequence, multiplied by the smallest.
Solution
group_hero(Group, GroupHero):-
findall(Hero, (
sublist(SubList, Group),
max_list(SubList, Maximum),
min_list(SubList, Minimum),
Hero #= Maximum**2 * Minimum
), Heroes),
sum_list(Heroes, GroupHero).
Sample Run
% gprolog --consult-file prolog/ch-2.p
| ?- group_hero([2, 1, 4], GroupHero).
GroupHero = 141
yes
| ?-
Notes
The core of this problem is to enumerate all the Power Sets of the
Group list. In other programming languages enumerating all sublists of a
list is straightforward enough, but requires much more code. Here, with
Prolog, we need only call sublist/2
with backtracking. We use a
findall/3
to generate all the necessary backtracking and create the
list of intermediate sums, which are then all summed for the final
solution.
References
posted at: 15:01 by: Adam Russell | path: /prolog | permanent link to this entry