# RabbitFarm

### 2021-08-29

#### Conflicting Lists and Intervals

*The examples used here are from The Weekly Challenge problem statement and demonstrate
the working solution.*

## Part 1

*You are given two sets with unique numbers. Write a script to figure out if they are
disjoint.*

### Solution

```
use strict;
use warnings;
use boolean;
sub disjoint{
my($list1, $list2) = @_;
my @a = map { my $n = $_; grep $n == $_ , @{$list2} } @{$list1};
return boolean(@a == 0);#boolean() used for better stringification
}
MAIN:{
my(@S1, @S2);
@S1 = (1, 2, 5, 3, 4);
@S2 = (4, 6, 7, 8, 9);
print disjoint(\@S1, \@S2) . "\n";
@S1 = (1, 3, 5, 7, 9);
@S2 = (0, 2, 4, 6, 8);
print disjoint(\@S1, \@S2) . "\n";
}
```

### Sample Run

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

### Notes

I cannot think of a way of determining conflicts between these two lists which is all that
more efficient than comparing them in this way. Sorting helps a little in some cases but
if the overlapping element(s) are at the end of the sorted list you need to traverse the
entire list anyway. Sorting would help the average case and since we need only find one
overlapping element and then stop looking this would have some noticeable effect in the
case of very large lists. But then I'd have to write a for-loop in order to break out of
the loop early and instead I wanted to experiment with this `grep`

inside a `map`

construct! This worked without too much hassle, the only consideration really being to
assign map's list value alias `$_`

to a variable so as to not conflict with grep's `$_`

.

The use of `boolean()`

is just to make sure that a 1 or 0 is printed as the final result.

## Part 2

*You are given a list of intervals. Write a script to determine conflicts between the
intervals.*

### Solution

```
use strict;
use warnings;
sub conflicts{
my @intervals = @_;
my @conflicts;
@intervals = sort { $a->[1] <=> $b->[1] } @intervals;
{
my $interval = pop @intervals;
my($i, $j) = @{$interval};
for $interval (@intervals){
my($m, $n) = @{$interval};
do { unshift @conflicts, [$i, $j]; last } if $i >= $m && $i <= $n;
}
redo if @intervals;
}
return @conflicts;
}
MAIN:{
my(@Intervals);
@Intervals = ([1, 4], [3, 5], [6, 8], [12, 13], [3, 20]);
map { print "[" . join(", ", @{$_}) . "] " } conflicts(@Intervals);
print "\n";
@Intervals = ([3, 4], [5, 7], [6, 9], [10, 12], [13, 15]);
map { print "[" . join(", ", @{$_}) . "] " } conflicts(@Intervals);
print "\n";
}
```

### Sample Run

```
$ perl perl/ch-2.pl
[3, 5] [3, 20]
[6, 9]
```

### Notes

The examples given in the problem statement are with the `[minimum, maximum]`

intervals
sorted by the maximum value. This makes the problem a bit easier since then we need only
check to see, when working down the sorted list, if the minimum is in one of the other
intervals.

Since it isn't totally clear if this is something that should be assumed for all inputs
I added a sort in `conflicts()`

to ensure this is the case.

## References

posted at: 17:18 by: Adam Russell | path: /perl | permanent link to this entry

#### The Weekly Challenge 127 (Prolog Solutions)

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

## Part 1

*You are given two sets with unique numbers. Write a script to figure out if they are
disjoint.*

### Solution

```
:-initialization(main).
conflicts(List0, List1):-
member(X, List0),
member(X, List1).
disjoint(List0, List1):-
\+ conflicts(List0, List1).
main:-
((disjoint([1, 2, 5, 3, 4], [4, 6, 7, 8, 9]), write(1)); (write(0))),
nl,
((disjoint([1, 3, 5, 7, 9], [0, 2, 4, 6, 8]), write(1)); (write(0))),
nl,
halt.
```

### Sample Run

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

### Notes

The `conflcts/2`

predicate establishes whether or not if there is any overlapping elements
in the two lists. To establish whether the sets are disjoint `disjoint/2`

examines the
negation of this result.

Remember, Prolog only backtracks on failure and not success. This fits nicely for what we
want. We only care if the lists have any overlap whatsoever. So using backtracking
`conflicts/2`

will backtrack for all members of List0 until it either succeeds in finding
an element that is also in List1 or, if none, fails completely indicating a disjoint set.
Since we actually consider the discovery of disjoint sets a success we negate the result
with `\+`

in `disjoint/2`

.

## Part 2

*You are given a list of intervals. Write a script to determine conflicts between the
intervals.*

### Solution

```
:-initialization(main).
conflicts(Intervals, Conflicts):-
conflicts(Intervals, Conflicts, []).
conflicts([_|[]], Conflicts, ConflictsAccum):-
sort(ConflictsAccum, Conflicts).
conflicts([H|T], Conflicts, ConflictsAccum):-
last(T, Last),
append(Intervals, [Last], T),
append([H], Intervals, CompareIntervals),
comparisons(Last, CompareIntervals, HasConflicts),
append(ConflictsAccum, HasConflicts, ConflictsAccumUpdated),
conflicts(CompareIntervals, Conflicts, ConflictsAccumUpdated).
comparisons(Interval, CompareIntervals, Conflicts):-
comparisons(Interval, CompareIntervals, Conflicts, []).
comparisons(_, [], Conflicts, Conflicts).
comparisons(Interval, [[H0|T0]|T], Conflicts, ConflictsAccum):-
[I|J] = Interval,
I >= H0,
I =< T0,
comparisons([I|J], T, Conflicts, [Interval|ConflictsAccum]).
comparisons([I|J], [_|T], Conflicts, ConflictsAccum):-
comparisons([I|J], T, Conflicts, ConflictsAccum).
main:-
conflicts([[1, 4], [3, 5], [6, 8], [12, 13], [3, 20]], Conflicts0),
write(Conflicts0), nl,
conflicts([[3, 4], [5, 7], [6, 9], [10, 12], [13, 15]], Conflicts1),
write(Conflicts1), nl,
halt.
```

### Sample Run

```
$ gplc prolog/ch-2.p
$ prolog/ch-2
[[3,5],[3,20]]
[[6,9]]
```

### Notes

The examples given in the problem statement are with the `[minimum, maximum]`

intervals
sorted by the maximum value. This makes the problem a bit easier since then we need only
check to see if, when working down the sorted list, if the minimum is in one of the other
intervals.

This is mostly all handled using recursion which keeps with the nature of the examples in the problem statement. This is fine, and obviously works, but after having worked out the details of finding a solution it seems there is room to make this more, well, logical?

Preferring *reasoning over recursion* as a principle of Prolog development seems to be
reasonable (pun intended!). Here we might, for example, arrange the intervals in
Key-Value pairs stored in the Prolog database and make better use of built in
backtracking. But even that would include a little extra work as we would need to sort
the pairs by value and ultimately the same number of lines of code would be written as
shown here, it would just arguably be a bit more *Prological*.

Sometimes the best solution to a problem is only discovered after working on it for a bit using alternative means!

## References

posted at: 11:21 by: Adam Russell | path: /prolog | permanent link to this entry