RabbitFarm

2022-07-03

The Weekly Challenge 171 (Prolog Solutions)

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

Part 1

Write a script to generate the first twenty Abundant Odd Numbers.

Solution


proper_divisors(X, Divisors):-
    Half is X // 2,
    findall(Divisor,(
        between(1, Half, Divisor),
        M is mod(X, Divisor),
        M == 0
    ), Divisors).

abundants_odd(_) --> [].
abundants_odd(Previous) --> [X], {abundant_odd(Previous, X)}, abundants_odd(X).

abundant_odd(Previous, X):-
    current_prolog_flag(max_integer, MAX_INTEGER),
    between(Previous, MAX_INTEGER, X),
    X > Previous,
    M is mod(X, 2),
    M == 1,
    proper_divisors(X, Divisors),
    sum_list(Divisors, DivisorsSum),
    DivisorsSum > X.

n_abundants(N, Abundants):-
    length(Abundants, N), 
    phrase(abundants_odd(-1), Abundants). 

Sample Run


$ gprolog --consult-file prolog/ch-1.p 
| ?- n_abundants(20, Abundants).  

Abundants = [945,1575,2205,2835,3465,4095,4725,5355,5775,5985,6435,6615,6825,7245,7425,7875,8085,8415,8505,8925] ? 

Notes

The use of a DCG here seems appropriate as we are generating a sequence of numbers of a DCG will allow us to reason on such lists. The logic for inclusion in the sequence is a bit complex and so it further seems natural to break that into its own predicate.

Part 2

Create sub compose($f, $g) which takes in two parameters $f and $g as subroutine refs and returns subroutine ref i.e. compose($f, $g)->($x) = $f->($g->($x)).

Solution


f(S, T):-
    T is S + S.

g(S, T):-
    T is S * S.

compose(F, G, H):-
    asserta((h(X, Y) :- call(G, X, X0), call(F, X0, Y))),
    H = h.

Sample Run


$ gprolog --consult-file prolog/ch-2.p
| ?- compose(f, g, H), A =.. [H, 7, X], A.

A = h(7,98)
H = h
X = 98

yes
| ?- 

Notes

This challenge is posed as being Perl specific and while most any language is able to do more or less what is asked for, this is a bit of a strange thing to do in Prolog.

In general, Prolog would dicate the use of a meta-interpreter for this sort of thing, instead of this sort of Functional Programming practice. Sticking to the letter of the challenge I was able to cobble something together with asserta/1 and the univ operator (=..)/2.

An assumption made in my code is that we know ahead of time the number of arguments to predicates F and G and that we also know which variables are instantiated or not. Those assumptions greatly simplify things and we can compose the two predicates in this way. Without that assumption the code would explode in complexity as we would need to examine whether variables are instantiated or not and then make possibly incorrect new assumptions that they, in fact, should have been or not.

References

Challenge 171

A Couple of Meta-interpreters in Prolog

posted at: 13:18 by: Adam Russell | path: /prolog | permanent link to this entry

Abundant Composition

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

Part 1

Write a script to generate the first twenty Abundant Odd Numbers.

Solution


use strict;
use warnings;
sub proper_divisors{
    my($n) = @_;
    my @divisors;
    for my $x (1 .. $n / 2){
        push @divisors, $x if $n % $x == 0;
    }
    return @divisors;
}

sub n_abundant_odd{
    my($n) = @_; 
    my $x = 0;
    my @odd_abundants;
    {
        push @odd_abundants, $x if $x % 2 == 1 && unpack("%32I*", pack("I*", proper_divisors($x))) > $x;
        $x++;
        redo if @odd_abundants < $n;
    }
    return @odd_abundants;
}

MAIN:{
    print join(", ", n_abundant_odd(20)) . "\n";
}

Sample Run


$ perl perl/ch-1.pl
945, 1575, 2205, 2835, 3465, 4095, 4725, 5355, 5775, 5985, 6435, 6615, 6825, 7245, 7425, 7875, 8085, 8415, 8505, 8925

Notes

The solution here incorporated a lot of elements from previous weekly challenges. That is to say it is quite familiar, I continue to be a fan of redo as well as the pack/unpack method of summing the elements of an array.

Part 2

Create sub compose($f, $g) which takes in two parameters $f and $g as subroutine refs and returns subroutine ref i.e. compose($f, $g)->($x) = $f->($g->($x)).

Solution


use strict;
use warnings;
sub f{
    my($x) = @_;
    return $x + $x;
}

sub g{
    my($x) = @_;
    return $x * $x;
}

sub compose{
    my($f, $g) = @_;
    return sub{
        my($x) = @_;
        return $f->($g->($x));
    };
}

MAIN:{
    my $h = compose(\&f, \&g);
    print $h->(7) . "\n";
}

Sample Run


$ perl perl/ch-2.pl
98

Notes

This problem incorporates some interesting concepts, especially from functional programming. Treating functions in a first class way, that is, passing them as parameters, manipulating them, dynamically generating new ones are commonly performed in functional programming languages such as Lisp and ML. Here we can see that Perl can quite easily do these things as well!

References

Challenge 171

posted at: 12:39 by: Adam Russell | path: /perl | permanent link to this entry