RabbitFarm

2025-06-14

The Weekly Challenge 325 (Prolog Solutions)

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

Part 1: Consecutive One

You are given a binary array containing only 0 or/and 1. Write a script to find out the maximum consecutive 1 in the given array.

Our solution is short and will be contained in a single file that has the following structure.

"ch-1.p" 1≡

: ⟨state of the count 2 ⟩
⟨count consecutive ones 3 ⟩
⟨consecutive ones 4 ⟩
◇

We’ll define a DCG to count the ones in the list. First, let’s have some predicates for maintaining the state of the count of consecutive ones.

⟨state of the count 2 ⟩≡

: consecutive_ones(Consecutive), [Consecutive] --> [Consecutive].
consecutive_ones(C, Consecutive), [Consecutive] --> [C].
◇

: Fragment referenced in 1.

The DCG for this is not so complex. Mainly we need to be concerned with maintaining the state of the count as we see each list element.

⟨count consecutive ones 3 ⟩≡

: count_ones(Input) --> consecutive_ones(C, Consecutive),
{Input = [H|T],
H == 1,
[Count, Maximum] = C,
succ(Count, Count1),
((Count1 > Maximum, Consecutive = [Count1, Count1]);
(Consecutive = [Count1, Maximum]))
},
count_ones(T).
count_ones(Input) --> consecutive_ones(C, Consecutive),
{Input = [H|T],
H == 0,
[_, Maximum] = C,
Consecutive = [0, Maximum]},
count_ones(T).
count_ones([]) --> [].
◇

: Fragment referenced in 1.

Finally, let’s wrap the calls to the DCG in a small predicate using phrase/3.

⟨consecutive ones 4 ⟩≡

: consecutive_ones(L, MaximumConsecutive):-
phrase(count_ones(L), [[0, 0]], [Output]), !,
[_, MaximumConsecutive] = Output.
◇

: Fragment referenced in 1.

Sample Run

$ gprolog --consult-file prolog/ch-1.p 
| ?- consecutive_ones([0, 1, 1, 0, 1, 1, 1], MaximumCount). 
 
MaximumCount = 3 
 
yes 
| ?- consecutive_ones([0, 0, 0, 0], MaximumCount). 
 
MaximumCount = 0 
 
yes 
| ?- consecutive_ones([1, 0, 1, 0, 1, 1], MaximumCount). 
 
MaximumCount = 2 
 
yes 
| ?-

Part 2: Final Price

You are given an array of item prices. Write a script to find out the final price of each items in the given array. There is a special discount scheme going on. If there’s an item with a lower or equal price later in the list, you get a discount equal to that later price (the first one you find in order).

The code required is fairly small, we’ll just need a couple of predicates.

"ch-2.p" 5≡

: ⟨next smallest 6 ⟩
⟨compute lowest prices 7 ⟩
◇

Given a list and a price find the next smallest price in the list.

⟨next smallest 6 ⟩≡

: next_smallest([], _, 0).
next_smallest([H|_], Price, H):-
H =< Price, !.
next_smallest([H|T], Price, LowestPrice):-
H > Price,
next_smallest(T, Price, LowestPrice).
◇

: Fragment referenced in 5.

⟨compute lowest prices 7 ⟩≡

: compute_lowest([], []).
compute_lowest([H|T], [LowestPrice|LowestPrices1]):-
compute_lowest(T, LowestPrices1),
next_smallest(T, H, Discount),
LowestPrice is H - Discount.
◇

: Fragment referenced in 5.

Sample Run

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

References

The Weekly Challenge 325
Generated Code

posted at: 15:33 by: Adam Russell | path: /prolog | permanent link to this entry