RabbitFarm

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

Part 1: Acronyms

You are given an array of words and a word. Write a script to return true if concatenating the first letter of each word in the given array matches the given word, return false otherwise.

We can do this in a single predicate which uses maplist to get the first character from each word, which we’ll take as a list of character code lists.

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

Sample Run

$ gprolog --consult-file prolog/ch-1.p 
| ?- acronym(["Perl", "Weekly", "Challenge"], "PWC"). 
 
yes 
| ?- acronym(["Bob", "Charlie", "Joe"], "BCJ"). 
 
yes 
| ?- acronym(["Morning", "Good"], "MM"). 
 
no 
| ?-
    

Part 2: Friendly Strings

You are given two strings. Write a script to return true if swapping any two letters in one string match the other string, return false otherwise.

This is going to be a quick one. First we will check that we can subtract/3 the two words (character code lists) and obtain an empty list. Then we’ll check in which places the words differ. They must only differ in exactly two places.

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

Sample Run

$ gprolog --consult-file prolog/ch-2.p 
| ?- friendly("desc", "dsec"). 
 
yes 
| ?- friendly("cat", "dog"). 
 
no 
| ?- friendly("stripe", "sprite"). 
 
yes 
| ?-
    

References

The Weekly Challenge 317
Generated Code

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

Part 1: Circular

You are given a list of words. Write a script to find out whether the last character of each word is the first character of the following word.

We can do this in a single predicate which recursively examines the list of words, which we’ll take as a list of character code lists.

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

Sample Run

$ gprolog --consult-file prolog/ch-1.p 
| ?- circular(["perl", "loves", "scala"]). 
 
true ? 
 
(1 ms) yes 
| ?- circular(["love", "the", "programming"]). 
 
no 
| ?- circular(["java", "awk", "kotlin", "node.js"]). 
 
true ? 
 
yes 
| ?-
    

Part 2: Subsequence

You are given two strings. Write a script to find out if one string is a subsequence of another.

This is going to be a quick one, seeing as GNU Prolog has a sublist/2 predicate which does exactly this! As in the previous part we’ll take the strings as lists of character codes.

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

Sample Run

$ gprolog --consult-file prolog/ch-2.p 
| ?- subsequence("uvw", "bcudvew"). 
 
true ? 
 
yes 
| ?- subsequence("aec", "abcde"). 
 
no 
| ?- subsequence("sip", "javascript"). 
 
true ? 
 
yes 
| ?-
    

References

The Weekly Challenge 316
Generated Code

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

Part 1: Find Words

You are given a list of words and a character. Write a script to return the index of word in the list where you find the given character.

This can be done with a basic predicate with findall. Or we can use maplist! maplist is more fun in my opinion, so we’ll go with that.

First off a small utility predicate to see if a word contains a given letter.

You can see that we are sending that previous predicate a pair. The first element in that pair is an index. Let’s build a word index, mainly for the sake of avoiding the use of between and findall. Those builtin predicates are fine, but aesthetically to me it seems nicer to not use them if we absolutely don’t have to.

Now we’ll use maplist to find the words.

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

Sample Run

$ gprolog --consult-file prolog/ch-1.p 
| ?- find_words([the, weekly, challenge], e, Indices). 
 
Indices = [1,2,3] ? 
 
yes 
| ?- find_words([perl, raku, python], p, Indices). 
 
Indices = [1,3] ? 
 
yes 
| ?- find_words([abc, def, bbb, bcd], b, Indices). 
 
Indices = [1,3,4] ? 
 
yes 
| ?-
    

Part 2: Find Third

You are given a sentence and two words. Write a script to return all words in the given sentence that appear in sequence to the given two words.

In the first part I mentioned the between and findall predicates. Here we will use them to find successive words.

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

Sample Run

$ gprolog --consult-file prolog/ch-2.p 
| ?- find_third([’Perl’, is, a, my, favourite, language, but, ’Python’, is, my, favourite, too], my, favourite, Thirds). 
 
Thirds = [language,too] 
 
yes 
| ?- find_third([’Barbie’, is, a, beautiful, doll, also, also, a, beautiful, princess], a, beautiful, Thirds). 
 
Thirds = [doll,princess] 
 
yes 
| ?- find_third([we, will, we, will, rock, you, rock, you], we, will, Thirds). 
 
Thirds = [we,rock] 
 
yes 
| ?-
    

References

The Weekly Challenge 315
Generated Code

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

Part 1: Equal Strings

You are given three strings. You are allowed to remove the rightmost character of a string to make all equals. Write a script to return the number of operations to make it equal otherwise -1.

The approach we’ll take is to pop off the last letter of each and compare the remainders. If they are equal then we are done. Otherwise we’ll continue popping off letter until we’re done.

A special case to consider is when the strings are of unequal length. In that case we make sure to only pop off letters from equal length strings, although the untouched strings will still be used when checking to see if we are done.

We’re going to define some convenience predicates, some with the intention that they’re going to be called from a maplist.

We’ll define a predicate for doing all the co-ordination and overall logic.

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

Sample Run

$ gprolog --consult-file prolog/ch-1.p 
| ?- equal_strings(["abb", "ab", "abc"], Operations). 
 
Operations = 2 
 
yes 
| ?- equal_strings(["ayz", "cyz", "xyz"], Operations). 
 
Operations = -1 
 
yes 
| ?- equal_strings(["yza", "yzb", "yzc"], Operations). 
 
Operations = 3 
 
yes 
| ?-
    

Part 2: Sort Column

You are given a list of strings of same length. Write a script to make each column sorted lexicographically by deleting any non sorted columns. Return the total columns deleted.

We’ll start with a short predicate for convenience.

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

Sample Run

$ gprolog --consult-file prolog/ch-2.p 
| ?- sort_column(["swpc", "tyad", "azbe"], Removals). 
 
Removals = 2 
 
yes 
| ?- sort_column(["cba", "daf", "ghi"], Removals). 
 
Removals = 1 
 
yes 
| ?- sort_column(["a", "b", "c"], Removals). 
 
Removals = 0 
 
yes 
| ?-
    

References

The Weekly Challenge 314
Generated Code

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

Part 1: Minimum Time

You are given a typewriter with lowercase english letters a to z arranged in a circle. Typing a character takes 1 sec. You can move pointer one character clockwise or anti-clockwise. The pointer initially points at a. Write a script to return minimum time it takes to print the given string.

All the logic for computing the shortest move us contained in a single predicate.

We’ll use a DCG to process the list of letters (we’re using ASCII codes).

Finally, let’s combine the previous predicates into a file along with a predicate minimum_time/2 that ties everything together.

Sample Run

$ gprolog --consult-file prolog/ch-1.p 
| ?- minimum_time("abc", MinimumTime). 
 
MinimumTime = 5 
 
yes 
| ?- minimum_time("bza", MinimumTime). 
 
MinimumTime = 7 
 
yes 
| ?- minimum_time("zjpc", MinimumTime). 
 
MinimumTime = 34 
 
yes 
| ?-
    

Part 2: Balls and Boxes

There are $n balls of mixed colors: red, blue or green. They are all distributed in 10 boxes labelled 0-9. You are given a string describing the location of balls. Write a script to find the number of boxes containing all three colors. Return 0 if none found.

We’ll use a DCG here in Part 2, althought it’ll be just a little bit more intricate.

First off, we’ll be passing the state around via some helper predicates. At the end of processing we’ll have a set of pairs that hold the contents of each box.

Now the DCG. For each record given we’ll process each Ball/Box pair.

Finally, let’s assemble our completed code into a single file. We’ll also add a predicate to co-orindate calling the DCG and processing the final result.

Sample Run

$ gprolog --consult-file prolog/ch-2.p 
| ?- full_boxes("G0B1R2R0B0", FullBoxes). 
 
FullBoxes = 1 
 
yes 
| ?- full_boxes("G1R3R6B3G6B1B6R1G3", FullBoxes). 
 
FullBoxes = 3 
 
yes 
| ?- full_boxes("B3B2G1B3", FullBoxes). 
 
FullBoxes = 0 
 
yes 
| ?-
    

References

The Weekly Challenge 312
Generated Code

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

Part 1: Upper Lower

You are given a string consists of english letters only. Write a script to convert lower case to upper and upper case to lower in the given string.

GNU Prolog defines a predicate lower_upper/2 which does pretty much what this problem is asking for. We could also just use the character code values instead of chars, but using chars seems a little more elegant as it avoids ASCII math.

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

Sample Run

$ gprolog --consult-file prolog/ch-1.p 
| ?- upper_lower(’pERl’, UpperLower). 
 
UpperLower = ’PerL’ ? 
 
yes 
| ?- upper_lower(’rakU’, UpperLower). 
 
UpperLower = ’RAKu’ ? 
 
yes 
| ?- upper_lower(’PyThOn’, UpperLower). 
 
UpperLower = pYtHoN ? 
 
yes 
| ?-
    

Part 2: Group Digit Sum

You are given a string, $str, made up of digits, and an integer, $int, which is less than the length of the given string. Write a script to divide the given string into consecutive groups of size $int (plus one for leftovers if any). Then sum the digits of each group, and concatenate all group sums to create a new string. If the length of the new string is less than or equal to the given integer then return the new string, otherwise continue the process.

To solve this problem we need to do the following

1. divide the list into groups of the given size
2. compute the sums
3. recombine
4. repeat as needed

Let’s look at each of those pieces individually and then combine them together into one predicate.

We can compute the sums using the GNU Prolog builtin predicate sum_list/2.

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

Sample Run

$ gprolog prolog/ch-2.p 
| ?- group_digit_sum(’111122333’, 3, GroupDigitSum). 
 
GroupDigitSum = ’359’ 
 
yes 
| ?- group_digit_sum(’1222312’, 2, GroupDigitSum). 
 
GroupDigitSum = ’76’ 
 
yes 
| ?- group_digit_sum(’100012121001’, 4, GroupDigitSum). 
 
GroupDigitSum = ’162’ 
 
yes 
| ?-
    

References

The Weekly Challenge 311
Generated Code

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.

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.

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

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

1. seperate the odd and even indexed numbers
2. sort the two lists as directed
3. 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.

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.

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

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

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

Part 1: Min Gap

You are given an array of integers, @ints, increasing order. Write a script to return the element before which you find the smallest gap.

There are probably a few good approaches to this problem. Here we’ll use a DCG approach. Ultimately this problem is at its core is to process a list of integers, and processing a list is something a DCG is well suited to handle.

We will be passing the state of the minimal gap found through the list processing predicates. The plan is that every time we find a new smallest gap the element where we found it will be appended to the list, along with the size of the gap. At the end of processing the final element will contain where the smallest gap was found.

Let’s give this DCG a simple interface. We’ll write a utility predicate that calls the DCG and sets the location of the smallest gap found.

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

Sample Run

$ gprolog --consult-file prolog/ch-1.p 
| ?- min_gap([2, 8, 10, 11, 15], MinGapLocation). 
 
MinGapLocation = 11 
 
(1 ms) yes 
| ?- min_gap([1, 5, 6, 7, 14], MinGapLocation). 
 
MinGapLocation = 6 
 
yes 
| ?- min_gap([8, 20, 25, 28], MinGapLocation). 
 
MinGapLocation = 28 
 
yes 
| ?-
    

Part 2: Min Diff

You are given an array of integers, @ints. Write a script to find the minimum difference between any two elements.

From Part 1 we know that if we sort the list we know we need to only check adjacent elements to find the minimum difference.

Much of the code is going to be the same. In fact there’s going to be less code since all we need to do is track the gap sizes and not the locations.

As before let’s give this DCG a simple interface. We’ll write a utility predicate that calls the DCG and sets the smallest gap found.

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

Sample Run

$ gprolog prolog/ch-2.p 
| ?- min_gap([1, 5, 8, 9], MinGap). 
 
MinGap = 1 
 
yes 
| ?- min_gap([9, 4, 1, 7], MinGap). 
 
MinGap = 2 
 
yes 
| ?-
    

References

The Weekly Challenge 309
Generated Code

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

Part 1: String Compression

You are given a string of alphabetic characters, $chars. Write a script to compress the string with run-length encoding.

A compressed unit can be either a single character or a count followed by a character.

BONUS: Write a decompression function.

There are probably a few good approaches to this problem. Here we’ll use a DCG approach. Ultimately this problem is at its core is to process a list of characters, something a DCG is best suited to handle.

For convenience, let’s define a clause for checking that we have a valid ascii character code. Maybe this is more my opinion than anything else, but working with character codes versus, say, characters seems to simplify matters for this particular problem.

We will be passing the state of the partial encoding through the encoding predicates.

Let’s give this DCG a simple interface. We’ll write some utility predicates.

Ok, so that’s the main part, but what about decoding for the bonus? We can also do that with a DCG. This proceeds about the same as the encoding process. We have a main DCG and then some utility predicates.

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

Sample Run

$ gprolog --consult-file prolog/ch-1.p 
| ?- encoder("abbc", Encoded). 
 
Encoded = a2bc ? 
 
yes 
| ?- encoder("aaabccc", Encoded). 
 
Encoded = ’3ab3c’ ? 
 
yes 
| ?- encoder("abcc", Encoded). 
 
Encoded = ab2c ? 
 
yes 
| ?- encoder("abbc", Encoded), atom_codes(Encoded, C), decoder(C, DecodedString). 
 
C = [97,50,98,99] 
DecodedString = abbc 
Encoded = a2bc ? 
 
yes 
| ?- encoder("abbbbbbccccccccccc", Encoded), atom_codes(Encoded, C), decoder(C, DecodedString). 
 
C = [97,54,98,49,49,99] 
DecodedString = abbbbbbccccccccccc 
Encoded = a6b11c ? 
 
yes 
| ?-
    

Part 2: Matchstick Square

You are given an array of integers, @ints. Write a script to find if it is possible to make one square using the sticks as in the given array @ints where $ints[$i] is the length of ith stick.

In order to make a square we need four sides that are of the same length. Let’s view this problem as how we can divide the list into four sublists which all sum to the same thing.

Seeing as it is just four sides the code can be a bit rote without looking too horrible.

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

Sample Run

$ gprolog prolog/ch-2.p 
| ?- matchstick_square([1, 2, 2, 2, 1]). 
 
(8 ms) yes 
| ?- matchstick_square([2, 2, 2, 4]). 
 
(2 ms) no 
| ?- matchstick_square([2, 2, 2, 2, 4]). 
 
(187 ms) no 
| ?- matchstick_square([3, 4, 1, 4, 3, 1]). 
 
(1 ms) yes 
| ?-
    

References

The Weekly Challenge 296
Generated Code

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

Part 1: Word Break

You are given a string, $str, and list of words, @words.

Write a script to return true or false whether the given string can be segmented into a space separated sequence of one or more words from the given list.

This is a good example of doing recursion in Prolog! Everything can be contained within a short recursive predicates.

At each recursive step we select a word form the list and see if it can be removed form the beginning of the final string. If we can whittle the final string down to the empty string then we know we have succeeded.

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

Sample Run

$ gprolog --consult-file prolog/ch-1.p 
| ?- word_break(weeklychallenge, [challenge, weekly]). 
 
true ? 
 
yes 
| ?- word_break(perlrakuperl, [raku, perl]). 
 
true ? 
 
yes 
| ?- word_break(sonsanddaughter, [sons, sand, daughters]). 
 
no 
| ?-
    

Part 2: Jump Game

You are given an array of integers, @ints. Write a script to find the minimum number of jumps to reach the last element. $ints[$i] represents the maximum length of a forward jump from the index $i. In case last element is unreachable then return -1.

In some ways this has a very similar approach as part 1. That is, a recursive solution which explores all possible “jumps”.

When using the jump

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

Sample Run

$ gprolog prolog/ch-2.p 
| ?- findall(Moves, jump_game([2, 3, 1, 1, 4], 1, Moves), AllMoves), sort(AllMoves, AllMovesSorted), nth(1, AllMovesSorted, MinimumMoves). 
 
AllMoves = [4,3,2,3] 
AllMovesSorted = [2,3,4] 
MinimumMoves = 2 
 
yes 
| ?- findall(Moves, jump_game([2, 3, 0, 4], 1, Moves), AllMoves), sort(AllMoves, AllMovesSorted), nth(1, AllMovesSorted, MinimumMoves). 
 
AllMoves = [2] 
AllMovesSorted = [2] 
MinimumMoves = 2 
 
yes 
| ?- findall(Moves, jump_game([2, 0, 0, 4], 1, Moves), AllMoves), sort(AllMoves, AllMovesSorted), nth(1, AllMovesSorted, MinimumMoves). 
 
no 
| ?-
    

References

The Weekly Challenge 290
Generated Code

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

Part 1: Double Exist

You are given an array of integers, @ints. Write a script to find if there exist two indices $i and $j such that:

1. $i≠$j
2. 0 ≥ $i < size @ints and 0 ≥ $j < size @ints
3. $ints[$i] = 2 ∗ $ints[$j]

This is a nice problem for Constraint Logic Programming. The solution is contained in just a single predicate which uses GNU Prolog’s finite domain (FD) constraint solver.

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

Sample Run

$ gprolog --consult-file prolog/ch-1.p 
| ?- double_exist([6, 2, 3, 3], I, J). 
 
I = 1 
J = 3 
 
yes 
| ?- double_exist([3, 1, 4, 13], I, J). 
 
no 
| ?- double_exist([2, 1, 4, 2], I, J). 
 
I = 1 
J = 2 ? 
 
(1 ms) yes 
| ?- double_exist([2, 1, 4, 2], I, J). 
 
I = 1 
J = 2 ? ; 
 
I = 3 
J = 1 
 
yes 
| ?-
    

Part 2: Luhn’s Algorithm

You are given a string $str containing digits (and possibly other characters which can be ignored). The last digit is the payload; consider it separately. Counting from the right, double the value of the first, third, etc. of the remaining digits. For each value now greater than 9, sum its digits. The correct check digit is that which, added to the sum of all values, would bring the total mod 10 to zero. Return true if and only if the payload is equal to the correct check digit.

This is essentially a list processing problem and is quite amenable to a DCG solution. Here I just use some ordinary predicates though.

For convenience we’ll have a predicate for summing the digits of numbers > 10.

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

Sample Run

$ gprolog prolog/ch-2.p 
| ?- luhn([1, 7, 8, 9, 3, 7, 2, 9, 9, 7, 4]). 
 
yes 
| ?- luhn([4, 1, 3, 7, 8, 9, 4, 7, 1, 1, 7, 5, 5, 9, 0, 4]). 
 
yes 
| ?- luhn([4, 1, 3, 7, 8, 9, 7, 4, 1, 1, 7, 5, 5, 9, 0, 4]). 
 
no 
| ?-
    

References

The Weekly Challenge 290
Generated Code

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

Part 1: Third Maximum

You are given an array of integers, @ints. Write a script to find the third distinct maximum in the given array. If a third maximum doesn’t exist then return the maximum number.

The majority of the work can be done in a couple of lines. We need only sort the distinct integers in the list and then return either the third largest number or, if none exists, the largest.

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

Sample Run

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

Part 2: Jumbled Letters

Your task is to write a program that takes English text as its input and outputs a jumbled version

The rules for jumbling are given as follows:

1. The first and last letter of every word must stay the same.
2. The remaining letters in the word are scrambled in a random order (if that happens to be the original order, that is OK).
3. Whitespace, punctuation, and capitalization must stay the same.
4. The order of words does not change, only the letters inside the word.

Looking closer at these rules the main thing we need to concern ourselves with is jumbling the letters with the exception of the first and last. The use of map will ensure the words are processed in order. To make sure the first/last letters are unchanged also depends on detecting punctuation.

Let’s first concern ourselves with identifying punctuation. We need to maintain a record of where they were located so we can put them back in later. We do this by recursively examining each character code to see if it is in the range for punctuation and, if it matches, creating an Index-Punctuation pair.

With these Index-Punctuation pairs created let’s write some code which will put them back in when we’re done with the jumbling of the other characters.

The bulk of the work is done in jumble_word/2 which, after the punctuation has been located and removed from further consideration, permutates the remaining letters and then randomly selects a permutation. This is then combined with the first/last letters.

Words that are one or two characters in length are not jumbled.

Jumbling words is done by using maplist/3 to call jumble_word/2 on the list of words.

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

Sample Run

$ gprolog prolog/ch-2.p 
| ?- jumble_words([in, the, ’ASCII’, range, match, all, ’non-controls.’], Jumbled). 
 
Jumbled = [in,the,’ASCII’,rgnae,mtach,all,’nnc-troolons.’] ? 
 
(161 ms) yes 
| ?-
    

References

The Weekly Challenge 289
Generated Code

The standard way that graphs are taught in Prolog is to represent the graph edges in the Prolog database and then, as needed, manipulate the database using assertz/1 and retract/1. There really is nothing wrong with this for many applications. However, when dealing with large graphs the overhead of writing to the database may not be worth the performance gain (via indexing) when querying. Especially in cases when the amount of querying may be low, there may not be any “return on investment”.

An alternative method, promoted by Markus Triska, is the use of attributed variables. In this way a variable represents a graph node and the attributes represent edges. Additionally, beyond that basic representation, additional attributes can be used for other information on the node and to add attributes to the edges such as a weight or other information on the relationship between nodes.

To be clear, attributed variables are primarily intended for use when building libraries, such as for constraint logic programming. There the default Prolog unification algorithm is less convenient than an extended version using attributed variables. In these cases hooks are used to determine, say, domain constraints on variables. Here will not concern ourselves with such advanced topics!

Not all Prologs provide attributed variables. Scryer and SWI are among those that do. All of our code is implemented and tested using SWI-Prolog.

Examples

Let’s start off with the most basic example: a small set of otherwise meaningless nodes connected at random.

This small graph, adapted from an example in Clocksin’s Clause and Effect, can be represented in Prolog in the traditional way as follows.

As needed additional edges can be added and removed from the Prolog database dynamically using assertz/1 and retract/1.

How might we change this to an attributed variables representation?

First off, we need to keep in mind that only an uninstantiated variable can have an attribute set unless we also provide an attribute hook. Since we otherwise have no need for a hook, we will restrict ourselves to having only uninstantiated variables as nodes. Of course, we need to maintain information for each node and edge. In both cases the node information and the edge information are kept as attributes. At first this sounds more complicated than it really is. Let’s see how it comes together in practice.

To build a bridge from the old to the new we will first create a predicate, edges_attributed/2 which converts a list of edges (e.g. [edge(a, b), edge(b, f), edge(f, c)]) to a list of attributed variables where the edges are attributes on the nodes. The attributes on each node are a list of edges to other node and, also, an attribute containing the node label.

For now we are only concerning ourselves with simple graphs like the example, so nodes are just unique atoms (e.g. a, b, c, ...). We’re also assuming that all edges are directed as given.

A lot of work is happening in helper predicates via maplist/3. For the most part these are just one or two lines each.

The lengthiest of the predicates used in a maplist/3 is graph_attributed/3. This is where the final assembly of the graph of attributed variables takes place.

Testing this predicate out, with just a small set of edges, we can get a sense of this new representation. A weight attribute, with default value of 1, has been added to demonstrate the possibility of attributed edge variables, but we won’t make any further use of this here.

?- Edges = [edge(a, b), edge(b, c), edge(b, d)], 
edges_attributed(Edges, Attributed). 
Edges = [edge(a, b), edge(b, c), edge(b, d)], 
Attributed = [a-_A, b-_B, c-_C, d-_D], 
put_attr(_A, node, a), 
put_attr(_A, edges, [edge(_E, a-_A, _B)]), 
put_attr(_B, node, b), 
put_attr(_B, edges, [edge(_F, b-_B, _C), edge(_G, b-_B, _D)]), 
put_attr(_C, node, c), 
put_attr(_C, edges, []), 
put_attr(_D, node, d), 
put_attr(_D, edges, []), 
put_attr(_E, weight, 1), 
put_attr(_F, weight, 1), 
put_attr(_G, weight, 1).

That looks nice, but let’s put it to work with a basic traversal.

To start with, let’s defines a predicate to determine if any two nodes are connected by a directed edge. If one or both of the two node arguments are uninstantiated then member/2 will find one for us, otherwise this will just confirm they are in the Graph, which we will be passed to all predicates that need it. This small amount of extra bookkeeping is part of the trade-off for no longer using the dynamic database.

Also, speaking of extra bookkeeping, we’ll try and maintain a level of encapsulation around the use of attributed variables. For example, in the following predicates we only need worry about the handling of attributes when determining connectedness. When building on this code for more complex purposes that is an important part of the design to keep in mind: encapsulate the low level implementation details and provide predicates which have a convenient higher level of interface.

In the spirit of building a big example, the following code does the same connectedness check, but for undirected edges. We’re not worrying too much about such graphs, but this is one way to do it.

Finally we can use this connectedness check to define path finding predicates that look a lot like any standard Prolog example of path finding you may have seen before!

Closing

At this point you should understand how to build a graph using attribute variables in Prolog. The example code here can be further extended as needed. You’ll find that this approach can take on quite a good deal of complexity!

All the code above is structured in a single file as shown. A link to this is in the References section.

Indices

Files

"graph.p" Defined by 14.

Fragments

⟨ Construct a graph of attributed variables. 6 ⟩ Referenced in 2.

⟨ Convert list of edges to attributed variables. 2 ⟩ Referenced in 14.

⟨ Create a K-V pair for each node. 8 ⟩ Referenced in 14.

⟨ Create a unique list of nodes. 4 ⟩ Referenced in 2.

⟨ Determine if two nodes are connected by a directed edge. 11 ⟩ Referenced in 14.

⟨ Determine if two nodes are connected by an undirected edge. 12 ⟩ Referenced in 14.

⟨ Example Graph (Standard) 1 ⟩ Referenced in 14.

⟨ Extract the nodes from all edges. 3 ⟩ Referenced in 2.

⟨ Find a path between any two nodes, if such a path exists. 13 ⟩ Referenced in 14.

⟨ From the node pairs, create the graph of attributed variables. 10 ⟩ Referenced in 14.

⟨ Generate attribute edge list. 9 ⟩ Referenced in 14.

⟨ Helper predicate for extracting nodes from edges. 7 ⟩ Referenced in 14.

⟨ Make the list of K-V pairs for the nodes. 5 ⟩ Referenced in 2.

References

This method has been promoted by Markus Triska on Stack Overflow, but publicly available examples are rare. Hopefully this page will be useful to any interested persons looking for more information.

Stack Overflow Post #1

Stack Overflow Post #2

Strongly Connected Components An implementation of Tarjan’s strongly connected components algorithm which uses this graph representation.

graph.p

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

Part 1

You are given two array of languages and its popularity. Write a script to sort the language based on popularity.

Solution

make_pairs(K, V, K-V).

sort_language(Languages, Popularity, SortedLanguages):-
    maplist(make_pairs, Popularity, Languages, PopularityLanguages),
    keysort(PopularityLanguages, SortedPopularityLanguages),
    findall(Language,  member(_-Language, SortedPopularityLanguages), SortedLanguages).

Sample Run

% gprolog --consult-file prolog/ch-1.p
| ?- sort_language([2, 1, 3], [perl, c, python], SortedLanguages). 

SortedLanguages = [1,2,3]

yes
| ?- 

Notes

A pretty standard Prolog convention is the - separated Pair. So here all we need do is generate the pairs of popularity and language, and then use keysort/2 to get everything in the right order.

Part 2

You are given an array of integers >= 0. Write a script to return the largest number formed by concatenating some of the given integers in any order which is also multiple of 3. Return -1 if none found.

Solution

largest_of_three(Numbers, LargestOfThree):-
    findall(Number,(
        sublist(SubList, Numbers),
        \+ SubList = [],
        permutation(SubList, SubListPermutation),
        number_codes(Number, SubListPermutation),
        0 is Number mod 3), NumbersOfThree),
    ((NumbersOfThree = [], LargestOfThree = -1);
     (max_list(NumbersOfThree, LargestOfThree))). 

Sample Run

% gprolog --consult-file prolog/ch-2.p 
| ?- largest_of_three("819", LargestOfThree).

LargestOfThree = 981

yes
| ?- largest_of_three("86710", LargestOfThree).

LargestOfThree = 8760

(1 ms) yes
| ?- largest_of_three("1", LargestOfThree).    

LargestOfThree = -1 ? 

yes
| ?- 

Notes

This is perhaps the most naive solution to the problem: generate sublists and sort the matching permutations of those sublists.

References

Challenge 245

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

Challenge 244

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 return the number of reverse pairs in the given array.

Solution

reverse_pair(X, Y, Z):-
    (X =\= Y, X > Y + Y, Z = 1, !); Z = 0.
reverse_pairs([], 0).    
reverse_pairs([H|T], ReversePairs):-
    reverse_pairs(T, R),
    maplist(reverse_pair(H), T, RP),
    sum_list(RP, Sum),
    ReversePairs is R + Sum.  

Sample Run

% gprolog --consult-file prolog/ch-1.p
| ?- reverse_pairs([1, 3, 2, 3, 1], ReversePairs).  

ReversePairs = 2

yes
| ?- reverse_pairs([2, 4, 3, 5, 1], ReversePairs).  

ReversePairs = 3

yes
| ?- 

Notes

reverse_pair/3 implements the reverse pair criteria and is called via a maplist/3 in reverse_pairs/3 which recurses over the list and counts up all Reverse Pairs found.

Part 2

You are given an array of positive integers (>=1). Write a script to return the floor sum.

Solution

floor_sum_pair(X, Y, Z):-
    Z is floor(X / Y).

floor_sum(Integers, FloorSum):-
    floor_sum(Integers, Integers, FloorSum).
floor_sum([], _, 0).    
floor_sum([H|T], L, FloorSum):-
    floor_sum(T, L, F),
    maplist(floor_sum_pair(H), L, FS),
    sum_list(FS, Sum),
    FloorSum is F + Sum.  

Sample Run

% gprolog --consult-file prolog/ch-2.p 
| ?- floor_sum([2, 5, 9], FloorSum).

FloorSum = 10

yes
| ?- floor_sum([7, 7, 7, 7, 7, 7, 7], FloorSum).

FloorSum = 49

(1 ms) yes
| ?- 

Notes

The process here is, co-incidentally, much the same as the first part above. We recurse over the list and use a maplist/3 to build an incremental sum at each step.

References

Challenge 243

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

Part 1

You are given two arrays of integers. Write a script to find out the missing members in each other arrays.

Solution