RabbitFarm

2025-02-23

The Weekly Challenge 309 (Prolog Solutions)

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

Part 1: Min Gap

You are given an array of integers, @ints, increasing order. Write a script to return the element before which you find the smallest gap.

There are probably a few good approaches to this problem. Here we’ll use a DCG approach. Ultimately this problem is at its core is to process a list of integers, and processing a list is something a DCG is well suited to handle.

We will be passing the state of the minimal gap found through the list processing predicates. The plan is that every time we find a new smallest gap the element where we found it will be appended to the list, along with the size of the gap. At the end of processing the final element will contain where the smallest gap was found.

⟨gap state 1 ⟩≡


gap(Gap), [Gap] --> [Gap].
gap(G, Gap), [Gap] --> [G].
◇

Fragment referenced in 4, 7.

⟨find all gaps/locations 2 ⟩≡


min_gap([]) --> [].
min_gap(Integers) --> {[_] = Integers}.
min_gap(Integers) -->
gap(G, Gap),
{[X,Y|T] = Integers, D is Y - X, var(G), G = D, append([], [G-Y], Gap)},
min_gap([Y|T]).
min_gap(Integers) -->
gap(G, Gap),
{[X,Y|T] = Integers, D is Y - X, last(G, GCurrent-_), D < GCurrent, append(G, [D-Y], Gap)},
min_gap([Y|T]).
min_gap(Integers) -->
gap(G, Gap),
{[X,Y|T] = Integers, D is Y - X, last(G, GCurrent-_), D >= GCurrent, Gap = G},
min_gap([Y|T]).
◇

Fragment referenced in 4.

Let’s give this DCG a simple interface. We’ll write a utility predicate that calls the DCG and sets the location of the smallest gap found.

⟨gap location finder 3 ⟩≡


min_gap(Integers, MinGapLocation):-
phrase(min_gap(Integers), [_], [Gaps]),
last(Gaps, _-MinGapLocation), !.
◇

Fragment referenced in 4.

The rest of the code just wraps this predicate into a file.

"ch-1.p" 4≡


⟨gap state 1 ⟩
⟨find all gaps/locations 2 ⟩
⟨gap location finder 3 ⟩
◇

Sample Run
$ gprolog --consult-file prolog/ch-1.p 
| ?- min_gap([2, 8, 10, 11, 15], MinGapLocation). 
 
MinGapLocation = 11 
 
(1 ms) yes 
| ?- min_gap([1, 5, 6, 7, 14], MinGapLocation). 
 
MinGapLocation = 6 
 
yes 
| ?- min_gap([8, 20, 25, 28], MinGapLocation). 
 
MinGapLocation = 28 
 
yes 
| ?-

Part 2: Min Diff

You are given an array of integers, @ints. Write a script to find the minimum difference between any two elements.

From Part 1 we know that if we sort the list we know we need to only check adjacent elements to find the minimum difference.

Much of the code is going to be the same. In fact there’s going to be less code since all we need to do is track the gap sizes and not the locations.

⟨find all gaps 5 ⟩≡


min_gap([]) --> [].
min_gap(Integers) --> {[_] = Integers}.
min_gap(Integers) -->
gap(G, Gap),
{[X,Y|T] = Integers, D is Y - X, var(G), G = D, append([], [G], Gap)},
min_gap([Y|T]).
min_gap(Integers) -->
gap(G, Gap),
{[X,Y|T] = Integers, D is Y - X, last(G, GCurrent), D < GCurrent, append(G, [D], Gap)},
min_gap([Y|T]).
min_gap(Integers) -->
gap(G, Gap),
{[X,Y|T] = Integers, D is Y - X, last(G, GCurrent), D >= GCurrent, Gap = G},
min_gap([Y|T]).
◇

Fragment referenced in 7.

As before let’s give this DCG a simple interface. We’ll write a utility predicate that calls the DCG and sets the smallest gap found.

⟨gap finder 6 ⟩≡


min_gap(Integers, MinGap):-
msort(Integers, SortedIntegers),
phrase(min_gap(SortedIntegers), [_], [Gaps]),
last(Gaps, MinGap), !.
◇

Fragment referenced in 7.

Finally, let’s assemble our completed code into a single file.

"ch-2.p" 7≡


⟨gap state 1 ⟩
⟨find all gaps 5 ⟩
⟨gap finder 6 ⟩
◇

Sample Run
$ gprolog prolog/ch-2.p 
| ?- min_gap([1, 5, 8, 9], MinGap). 
 
MinGap = 1 
 
yes 
| ?- min_gap([9, 4, 1, 7], MinGap). 
 
MinGap = 2 
 
yes 
| ?-

References

The Weekly Challenge 309
Generated Code

posted at: 20:01 by: Adam Russell | path: /prolog | permanent link to this entry

Gap Minimizations

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

Part 1: Min Gap

You are given an array of integers, @ints, increasing order. Write a script to return the element before which you find the smallest gap.

The complete solution is contained in one file that has a simple structure.

"ch-1.pl" 1≡


⟨preamble 2 ⟩
⟨Min Gap subroutine. Contains all the important code for this problem. 3 ⟩
⟨main 4 ⟩
◇

For this problem we do not need to include very much. We’re just specifying to use the current version of Perl, for all the latest features in the language. This fragment is also used in Part 2.

⟨preamble 2 ⟩≡


use v5.38;
◇

Fragment referenced in 1, 5.

Let’s not even store anything. Instead go down the list and update two variables: one to store the current minimum gap, and the other to store the element before the current smallest gap found.

I use a small trick here. A way of saying The Maximum Integer is 0 + q/inf/.

⟨Min Gap subroutine. Contains all the important code for this problem. 3 ⟩≡


sub min_gap{
my($min_gap, $element_min_gap) = (0 + q/inf/, 0 + q/inf/);
{
my $x = shift @_;
my $y = shift @_;
if($x && $y){
my $gap = $y - $x;
if($gap < $min_gap){
$min_gap = $gap;
$element_min_gap = $y;
}
}
unshift @_, $y;
redo if @_ > 1;
}
return $element_min_gap;
}
◇

Fragment referenced in 1.

Now all we need are a few lines of code for running some tests.

⟨main 4 ⟩≡


MAIN:{
say min_gap 2, 8, 10, 11, 15;
say min_gap 1, 5, 6, 7, 14;
say min_gap 8, 20, 25, 28;
}
◇

Fragment referenced in 1.

Sample Run
$ perl perl/ch-1.pl 
11 
6 
28

Part 2: Min Diff

You are given an array of integers, @ints. Write a script to find the minimum difference between any two elements.

"ch-2.pl" 5≡


⟨preamble 2 ⟩
⟨Min Diff subroutine. All the code for solving the problem is here. 6 ⟩
⟨main 7 ⟩
◇

From Part 1 we know that if we sort the list we know we need to only check adjacent elements to find the minimum difference.

⟨Min Diff subroutine. All the code for solving the problem is here. 6 ⟩≡


sub min_diff{
my $min_gap = 0 + q/inf/;
my @i = sort {$a <=> $b} @_;
{
my $x = shift @i;
my $y = shift @i;
if($x && $y){
my $gap = $y - $x;
$min_gap = $gap if $gap < $min_gap;
}
unshift @i, $y;
redo if @i > 1;
}
return $min_gap;
}
◇

Fragment referenced in 5.

Finally, here’s a few tests to confirm everything is working right.

⟨main 7 ⟩≡


MAIN:{
say min_diff 1, 5, 8, 9;
say min_diff 9, 4, 1, 7;
}
◇

Fragment referenced in 5.

Sample Run
$ perl ch-2.pl 
1 
2

References

The Weekly Challenge 309
Generated Code

posted at: 19:58 by: Adam Russell | path: /perl | permanent link to this entry