RabbitFarm

2025-06-29

The Weekly Challenge 327 (Prolog Solutions)

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

Part 1: Missing Integers

You are given an array of n integers. Write a script to find all the missing integers in the range 1..n in the given array.

Our solution is short and will be contained in a single file that has the following structure.

"ch-1.p" 1≡


⟨missing integers 2 ⟩
◇

This problem is straightforward to solve using member/2.

⟨missing integers 2 ⟩≡


missing_integers(L, Missing):-
length(L, Length),
findall(M, (
between(1, Length, M),
\+ member(M, L)
), Missing).
◇

Fragment referenced in 1.

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

Part 2: MAD

You are given an array of distinct integers. Write a script to find all pairs of elements with minimum absolute difference (MAD) of any two elements.

The code required is fairly small, we’ll just need a single predicate and use GNU Prolog’s clp(fd) solver.

"ch-2.p" 3≡


⟨compute MAD and find pairs 4 ⟩
◇

This is a good use of GNU Prolog’s clp(fd) solver. We set up the finite domain variables I and J to take values from the given list. We then find the minimum value of the differences and return all pairs having satisfied that constraint.

⟨compute MAD and find pairs 4 ⟩≡


mad(L, Pairs):-
fd_max_integer(MAX_INT),
fd_domain([I, J], L),
fd_domain(D, 1, MAX_INT),
J #> I,
fd_minimize((D #= J - I, fd_labeling([D])), D),
findall(Pair, (fd_labeling([I, J]), Pair = [I, J]), Pairs).
◇

Fragment referenced in 3.

Sample Run
$ gprolog --consult-file prolog/ch-2.p 
| ?- mad([4, 1, 2, 3], Pairs). 
 
Pairs = [[1,2],[2,3],[3,4]] 
 
yes 
| ?- mad([1, 3, 7, 11, 15], Pairs). 
 
Pairs = [[1,3]] 
 
yes 
| ?- mad([1, 5, 3, 8], Pairs). 
 
Pairs = [[1,3],[3,5]] 
 
yes 
| ?-

References

The Weekly Challenge 327
Generated Code

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

Missing Integers Don’t Make Me MAD, Just Disappointed

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

Part 1: Missing Integers

You are given an array of n integers. Write a script to find all the missing integers in the range 1..n in the given array.

The core of the solution is contained in a single subroutine. The resulting code can be contained in a single file.

"ch-1.pl" 1≡


use v5.40;
⟨find missing 2 ⟩
⟨main 3 ⟩
◇

The approach we take is to use the given array as hash keys. Then we’ll iterate over the range 1..n and see which hash keys are missing.

⟨find missing 2 ⟩≡


sub find_missing{
my %h = ();
my @missing = ();
do{ $h{$_} = -1 } for @_;
@missing = grep {!exists($h{$_})} 1 .. @_;
return @missing;
}
◇

Fragment referenced in 1.

Just to make sure things work as expected we’ll define a few short tests.

⟨main 3 ⟩≡


MAIN:{
say q/(/ . join(q/, /, find_missing 1, 2, 1, 3, 2, 5) . q/)/;
say q/(/ . join(q/, /, find_missing 1, 1, 1) . q/)/;
say q/(/ . join(q/, /, find_missing 2, 2, 1) . q/)/;
}
◇

Fragment referenced in 1.

Sample Run
$ perl perl/ch-1.pl 
(4, 6) 
(2, 3) 
(3)

Part 2: MAD

You are given an array of distinct integers. Write a script to find all pairs of elements with minimum absolute difference (MAD) of any two elements.

We’ll use a hash based approach like we did in Part 1. The amount of code is small, just a single subroutine.

"ch-2.pl" 4≡


use v5.40;
⟨compute MAD and find pairs 5 ⟩
⟨main 6 ⟩
◇

Since we need to have a nested loop to access all pairs we’ll make an effort to only do it once. What we’ll do is store the pairs in a list keyed by the differences. We’ll also track the minimum difference in a variable to avoid sorting to find it later.

⟨compute MAD and find pairs 5 ⟩≡


sub mad_pairs{
my %mad = ();
my $mad = ~0;
for my $i (0 .. @_ - 1){
for my $j ($i + 1 .. @_ - 1){
my $d = abs($_[$i] - $_[$j]);
$mad = $d if $d < $mad;
push @{$mad{$d}}, [$_[$i], $_[$j]];
}
}
return @{$mad{$mad}};
}
◇

Fragment referenced in 4.

The main section is just some basic tests. Yeah, we’ll do lazy string formatting with chop!

⟨main 6 ⟩≡


MAIN:{
my $s = q//;
do{
$s .= q/[/ . join(q/, /, @{$_}) . q/], /;
} for mad_pairs 4, 1, 2, 3;
chop $s;
chop $s;
say $s;
$s = q//;

do{
$s .= q/[/ . join(q/, /, @{$_}) . q/], /;
} for mad_pairs 1, 3, 7, 11, 15;
chop $s;
chop $s;
say $s;
$s = q//;

do{
$s .= q/[/ . join(q/, /, @{$_}) . q/], /;
} for mad_pairs 1, 5, 3, 8;
chop $s;
chop $s;
say $s;
$s = q//;
}
◇

Fragment referenced in 4.

Sample Run
$ perl perl/ch-2.pl 
[4, 3], [1, 2], [2, 3] 
[1, 3] 
[1, 3], [5, 3]

References

The Weekly Challenge 327
Generated Code

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