RabbitFarm

2021-04-18

The Weekly Challenge 108 (Prolog Solutions)

The examples used here are from the weekly challenge problem statement and demonstrate the working solution. Also, the challenge statements are given in a Perl context although for Prolog solutions some adjustments are made to account for the differing semantics between the two languages.

Part 1

Write a script to declare a variable or constant and print it’s location in the memory.

Notes

This is a strange thing to do in Prolog since the very idea of a “variable” is dissimilar to that of imperative programming languages. Still, it is possible to do, especially with Gnu Prolog’s foreign/2, part of the Foreign Language Interface. This requires us to write some code in C and in this way we can surely report on the memory address used by whatever Prolog variable we want to examine. I will admit to being intrigued by this but at present did not have the opportunity to explore this. For now I am leaving these notes here as a placeholder to investigate this further if/when the opportunity allows.

Part 2

Write a script to display the first 10 Bell Numbers.

Solution


:-initialization(main).

addElement(Element, [FirstList | OtherLists], [ [Element|FirstList] | OtherLists]).
addElement(Element, [FirstList | OtherLists], [ FirstList | Temp] ):- 
    addElement(Element, OtherLists, Temp).

partition([Single], [[Single]]).
partition([First|Others], [[First] | Result]) :-
    partition(Others, Result).
partition([First|Others], Result) :-
    partition(Others, Temp),
    addElement(First, Temp, Result).

bell_numbers(N):-
    \+ N == 0,  
    N < 10,
    length(L0, N), 
    setof(P, partition(L0, P), Partitions), 
    length(Partitions, L),
    write('B_'), write(N), write(': '), write(L), nl,
    N0 is N + 1, 
    bell_numbers(N0).   
bell_numbers(N):-
    N == 0,
    write('B_'), write(N), write(': '), write(1), nl,
    N0 is N + 1,
    bell_numbers(N0).     
bell_numbers(_).   

main:-
    bell_numbers(0), 
    halt.    

Sample Run


$ gplc ch-2.p 
$ prolog/ch-2
B_0: 1
B_1: 1
B_2: 2
B_3: 5
B_4: 15
B_5: 52
B_6: 203
B_7: 877
B_8: 4140
B_9: 21147

Notes

This code uses a known Prolog idiom for computing partitions of the list for each Bell Number. It is, of course, possible to simply compute these using a closed form approach as I did for the Perl solution for this same problem. Since this is Prolog I figured this method may be a bit more fun!

Since we don’t really care about what is in the list, only that the elements be unique to allow for proper partitioning, that a list of uninstantiated variables works just fine.

And yeah, probably I should have started computing the numbers with 10 instead of 0 and used format/2 instead of a bunch of write/1s, but this code was just a quick bit of fun.

References

Challenge 108

Bell Numbers

Bell Triangle

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