RabbitFarm

2021-01-17

The Weekly Challenge 095 (Prolog Solutions)

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

Part 1

Write a script to figure out if the given number is Palindrome. Print 1 if true otherwise 0.

Solution


:-initialization(main).

palindrome_even([]).  
palindrome_even([H|T]):-
    last(T, Last), 
    H == Last, 
    append(L, [Last], T), 
    palindrome_even(L).   

palindrome_odd([_|[]]).  
palindrome_odd([H|T]):-
    last(T, Last), 
    H == Last, 
    append(L, [Last], T), 
    palindrome_odd(L).   

palindrome(N):-
    N > 0, 
    number_chars(N, C), 
    length(C, Length), 
    M is Length mod 2,
    M == 0,
    palindrome_even(C).   
palindrome(N):-
    N > 0, 
    number_chars(N, C), 
    length(C, Length), 
    M is Length mod 2,
    M == 1,
    palindrome_odd(C).  

is_palindrome(N):-
    palindrome(N),
    write(1), nl.
is_palindrome(N):-
    \+ palindrome(N),
    write(0), nl.

main:-
    is_palindrome(1221),
    is_palindrome(-101),
    is_palindrome(90),
    halt.  

Sample Run


$ gplc prolog/ch-1.p
$ prolog/ch-1
1
0
0

Notes

This is a Prolog version of Perl code I wrote for the same problem. The basic approach is roughly the same as the Perl implementation: starting at both ends of the number work inwards comparing one pair of digits at a time. Here we define all negative numbers as being non-palindromic due to the inherent asymmetry of the ‘-’.

It is slightly odd in Prolog to print out a 0 or 1 as asked in this problem statement. In languages like Perl doing so is really just as simple as printing out a boolean value returned from some comparison or function call. Although odd it is not unheard of, however, and the best advice I have seen on the matter is to define a small predicate to wrap the predicate(s) doing the real work and print whatever is needed. That job here is done by is_palindrome/1

Part 2

Demonstrate Stack operations.

Solution


:-initialization(main).

new_stack([]).

push(Stack, Value, [Value|Stack]).

pop([H|T], H, T).

top([H|_], H).

min(Stack, Min):-
    min_list(Stack, Min).

main:-
    new_stack(Stack),
    push(Stack, 2, NewStack0),
    push(NewStack0, -1, NewStack1),
    push(NewStack1, 0, NewStack2),
    pop(NewStack2, Top0, NewStack3),
    write(Top0), nl,
    top(NewStack3, Top1),
    write(Top1), nl,
    push(NewStack3, 0, NewStack4),
    min(NewStack4, Min),
    write(Min), nl,
    halt.

Sample Run


$ gplc prolog/ch-2.p
$ prolog/ch-2
0
-1
-1

Notes

Just writing this code made me feel like I was committing a crime against Prolog! Implementing this sort of data structure in Prolog is really just writing some small predicates which wrap otherwise ordinary list operations. Then again, implementing Stacks in Prolog is not entirely unheard of. This sort of thing is done as an exercise when studying data structures. The excellent text by Luger and Stubblefield describes a Stack implementation, among other Abstract Data Types, in Prolog.

References

Challenge 095

AI Algorithms, Data Structures, and Idioms in Prolog, Lisp, and Java

posted at: 16:03 by: Adam Russell | path: /prolog | permanent link to this entry

Perl Weekly Challenge 095

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

Part 1

You are given a number $N. Write a script to figure out if the given number is a Palindrome. Print 1 if true, otherwise 0.

Solution


use strict;
use warnings;

use boolean;

sub is_palindrome{
    my($n) = @_;
    return false if $n < 0;
    my @digits = split(//, $n);
    if(@digits % 2 == 0){
        do{
            my $a = shift @digits;
            my $b = pop @digits;
            return false if $a != $b;
        }while(@digits);
        return true;
    }
    while(@digits != 1){
        my $a = shift @digits;
        my $b = pop @digits;
        return false if $a != $b;
    };
    return true;
}

MAIN:{
    print is_palindrome(1221);
    print "\n";
    print is_palindrome(-101);
    print "\n";
    print is_palindrome(90);
    print "\n";
}

Sample Run


$ perl perl/ch-1.pl
1
0
0

Notes

One assumption is made and that is that the input is a valid integer.

My approach here is straightforward iteration and matches what one might do manually: work inwards from both ends and if at any point there is not a match of the two elements being compared then return false. If we make it all the way to the middle then return true. Here the middle is either an empty array, in the case of an even number of elements or, in the case of an odd number of elements, an array of length 1.

The case of a single digit has no special handling, if the number has an odd number of digits but that odd number happens to be 1 then the loop is not entered and we just return true.

Part 2

Write a script to demonstrate Stack operations.

Solution


use strict;
use warnings;

use Stack;

my $stack = new Stack();
$stack->push(2);
$stack->push(-1);
$stack->push(0);
$stack->pop;       
print $stack->top . "\n"; 
$stack->push(0);
print $stack->min . "\n"; 

The Stack module used is of my own making. The next listing is that code.


use strict;
use warnings;
package Stack{
    use boolean;
    use Class::Struct;

    struct(
        data => q/@/
    );

    sub push{
        my($self, $n) = @_;
        push @{$self->data()}, $n;
    }

    sub pop{
        my($self, $n) = @_;
        pop @{$self->data()};
    }

    sub top{
        my($self, $n) = @_;
        @{$self->data()}[@{$self->data()} - 1];
    }
    
    sub min{
        my($self, $n) = @_;
        my @sorted = sort {$a <=> $b} @{$self->data()};
        return $sorted[0];
    }
    true;
}  

Sample Run


$ perl -Iperl perl/ch-2.pl
-1
-1

Notes

Like last week’s LinkedList module I use Class::Struct to create the Stack module.

Class::Struct creates accessors for all the class variables automatically. In this way, by calling $self->data(), we get a reference to the internal array data and perform the required Stack operations.

posted at: 14:49 by: Adam Russell | path: /perl | permanent link to this entry