RabbitFarm

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

missing(L, E, Member):-
    (member(E, L), Member = nil);
    (\+ member(E, L), Member = E).
missing_members([List1, List2], [Missing1, Missing2]):-
    maplist(missing(List2), List1, Missing1Nil),
    delete(Missing1Nil, nil, Missing1),
    maplist(missing(List1), List2, Missing2Nil),
    delete(Missing2Nil, nil, Missing2). 

Sample Run

% gprolog --consult-file prolog/ch-1.p
| ?- missing_members([[1, 2, 3], [2, 4, 6]] ,Missing).

Missing = [[1,3],[4,6]] ? 

yes
| ?- missing_members([[1, 2, 3, 3], [1, 1, 2, 2]] ,Missing).

Missing = [[3,3],[]] ? 

yes
| ?- missing_members([[1, 2, 3, 3], [1, 1, 2, 2]], Missing), maplist(sort, Missing, MissingNoDuplicates). 

Missing = [[3,3],[]]
MissingNoDuplicates = [[3],[]] ? 

yes
| ?- 

Notes

missing/3 is used in a maplist/3 to determine which elements are missing from an array. If they are not missing a nil is set for it. By deleting the nil elements all that remain are the ones that are missing. This solution doesn't itself remove duplicate missing elements that are identified. That said, as you can see in the example above that can be added, say, using sort/2.

Part 2

You are given n x n binary matrix. Write a script to flip the given matrix as below.

Solution

flip(B, F):-
    F is \ B /\ 1.
flip_matrix([], []).    
flip_matrix([Row|Matrix], [RowFlipped|MatrixFlipped]):-
    reverse(Row, RowReversed),
    maplist(flip, RowReversed, RowFlipped),
    flip_matrix(Matrix, MatrixFlipped).

Sample Run

% gprolog --consult-file prolog/ch-2.p 
| ?- flip_matrix([[1, 1, 0], [1, 0, 1], [0, 0, 0]], FlippedMatrix).

FlippedMatrix = [[1,0,0],[0,1,0],[1,1,1]]

yes
| ?- flip_matrix([[1, 1, 0, 0], [1, 0, 0, 1], [0, 1, 1, 1], [1, 0, 1, 0]], FlippedMatrix).

FlippedMatrix = [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

yes
| ?- 

Notes

For the given matrix we need only recursively consider each row, reverse it, do the necessary bit flips, and then assemble the newly flipped rows into the completed Flipped Matrix.

References

Challenge 242

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

use v5.38;
use boolean;
use Data::Dump q/pp/;
sub missing_members{
    my @r;
    my($a0, $a1) = @_;
    my $missing0 = [];
    missing_members_r([@{$a0}], [@{$a1}], $missing0);
    my $missing1 = [];
    missing_members_r([@{$a1}], [@{$a0}], $missing1);
    push @r, $missing0 if @{$missing0} > 0;
    push @r, $missing1 if @{$missing1} > 0;
    return @r;
}

sub missing_members_r{
    my($a0, $a1, $missing, $seen) = @_;
    $seen = [] if !defined($seen);
    my $x = shift @{$a0};
    push @{$missing}, $x if missing_r($x, [@{$a1}]) && !seen_r($x, $seen); 
    push @{$seen}, $x;
    missing_members_r($a0, $a1, $missing, $seen) if @{$a0} > 0;
}

sub missing_r{
    my($x, $a0) = @_;
    return true if @{$a0} == 0;
    if(@{$a0}){
        my $y = shift @{$a0};
        if($x == $y){ 
            return false;
        }
    }
    return missing_r($x, $a0);
}

sub seen_r{
    my($x, $seen) = @_;
    return false if @{$seen} == 0;
    my $y = shift @{$seen};
    if($x == $y){
        return true;
    }
    return seen_r($x, $seen);
}

MAIN:{
    my @array1 = (1, 2, 3);
    my @array2 = (2, 4, 6);
    say pp missing_members \@array1, \@array2;
    @array1 = (1, 2, 3, 3);
    @array2 = (1, 1, 2, 2);
    say pp missing_members \@array1, \@array2;
}

Sample Run

$ perl perl/ch-1.pl 
([1, 3], [4, 6])
[3]

Notes

So, yeah, this could just be a nice quick use of grep, but where is the fun in that!?!? Just looping over the arrays is not that exciting of an alternative, what other options are there? I know, how about a whole lot of recursion! That was pretty much my thought process here.

Really, all this code is doing is looping over the two arrays and looking for which elements are not contained in each. The looping, such as it is, happens recursively in missing_members_r() and missing_r(). Duplicates are possible and we avoid these, again recursively, using seen_r() rather than, say, grep or hash keys.

Part 2

You are given n x n binary matrix. Write a script to flip the given matrix as below.

Solution

use v5.38;
use Data::Dump q/pp/;
sub flip_matrix{
    return map { 
        my $row = $_;
        [map {~$_ & 1} reverse @{$row}]
    } @_;
}

MAIN:{
    my @matrix = ([1, 1, 0], [1, 0, 1], [0, 0, 0]);
    say pp flip_matrix @matrix;
    @matrix = ([1, 1, 0, 0], [1, 0, 0, 1], [0, 1, 1, 1], [1, 0, 1, 0]);
    say pp flip_matrix @matrix;
}

Sample Run

$ perl perl/ch-2.pl 
([1, 0, 0], [0, 1, 0], [1, 1, 1])
([1, 1, 0, 0], [0, 1, 1, 0], [0, 0, 0, 1], [1, 0, 1, 0])

Notes

After all the recursive exitment in part 1 of this week's challenge I just went with a quick nested map for part 2.

References

Challenge 242