nuweb Source for TWC 325 (Prolog)
See http://www.rabbitfarm.com/cgi-bin/blosxom/prolog/2025/06/14
\documentclass{article} \usepackage{color} \definecolor{linkcolor}{rgb}{0, 0, 0.7} \usepackage{amsmath} \usepackage[backref, raiselinks, pdfhighlight=/O, pagebackref, hyperfigures, breaklinks, colorlinks, pdfpagemode=UseNone, pdfstartview=FitBH, linkcolor={linkcolor}, anchorcolor={linkcolor}, citecolor={linkcolor}, filecolor={linkcolor}, menucolor={linkcolor}, urlcolor={linkcolor}]{hyperref} \usepackage{datetime} \usepackage{listings} \lstset{extendedchars=true, keepspaces=true, language=perl} \lstnewenvironment{PROLOG}{\lstset{language=Prolog, frame=lines}}{} \lstnewenvironment{SHELL}{\lstset{language=bash, frame=lines}}{} \begin{document} \section*{The Weekly Challenge 325 (Prolog Solutions)} {\it The examples used here are from the weekly challenge problem statement and demonstrate the working solution.} \subsection*{Part 1: Consecutive One} {\it 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.} @s Our solution is short and will be contained in a single file that has the following structure. @o ch-1.p -i @{ @<state...@> @<count...@> @<consecutive...@> @} 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. @d state of the count @{ consecutive_ones(Consecutive), [Consecutive] --> [Consecutive]. consecutive_ones(C, Consecutive), [Consecutive] --> [C]. @} 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. @d count consecutive ones @{ 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([]) --> []. @} Finally, let’s wrap the calls to the DCG in a small predicate using phrase/3. @d consecutive ones @{ consecutive_ones(L, MaximumConsecutive):- phrase(count_ones(L), [[0, 0]], [Output]), !, [_, MaximumConsecutive] = Output. @} @S \subsubsection*{Sample Run} \begin{SHELL} $ 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 | ?- \end{SHELL} \subsection*{Part 2: Final Price} {\it 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).} @s The code required is fairly small, we'll just need a couple of predicates. @o ch-2.p -i @{ @<next smallest@> @<compute...@> @} Given a list and a price find the next smallest price in the list. @d next smallest @{ next_smallest([], _, 0). next_smallest([H|_], Price, H):- H =< Price, !. next_smallest([H|T], Price, LowestPrice):- H > Price, next_smallest(T, Price, LowestPrice). @} @d compute lowest prices @{ compute_lowest([], []). compute_lowest([H|T], [LowestPrice|LowestPrices1]):- compute_lowest(T, LowestPrices1), next_smallest(T, H, Discount), LowestPrice is H - Discount. @} @S \subsubsection*{Sample Run} \begin{SHELL} $ 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 | ?- \end{SHELL} \section*{References} \href{https://theweeklychallenge.org/blog/perl-weekly-challenge-325/} {The Weekly Challenge 325} \\ \href{https://github.com/manwar/perlweeklychallenge-club/tree/master/challenge-325/adam-russell} {Generated Code} \end{document}