Overlap
June 8, 2018
We have today a simple exercise to spice up your Friday lunch hour:
A range of integers is specified by its endpoints; for instance, the range [19, 25] includes the values 19, 20, 21, 22, 23, 24, and 25. The overlap of two ranges is those values that appear in both; for instance, given the ranges [19, 25] and [22, 30], the overlap is the range [22, 25]. The ranges [19, 25] and [12, 17] have no overlap.
Your task is to write a program that takes the endpoints of two ranges and returns their overlap, or reports that they have no overlap. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
In Ruby. Using Ranges (built-in)
Outout:
22..25
nil
Here’s a solution in C.
#include <stdio.h> #include <stdlib.h> void print_usage_and_exit(char* prog) { fprintf(stderr, "Usage: %s min1 max1 min2 max2\n", prog); exit(EXIT_FAILURE); } int main(int argc, char* argv[]) { if (argc != 5) { print_usage_and_exit(argv[0]); } int min1 = atoi(argv[1]); int max1 = atoi(argv[2]); int min2 = atoi(argv[3]); int max2 = atoi(argv[4]); if (max1 < min1 || max2 < min2) { print_usage_and_exit(argv[0]); } if (min1 <= max2 && max1 >= min2) { int min3 = min1 > min2 ? min1 : min2; int max3 = max1 < max2 ? max1 : max2; printf("%d %d\n", min3, max3); } return EXIT_SUCCESS; }Example:
A Haskell version. For clarity we create a type for ranges.
data Range a = R a a | Empty deriving (Show) mkRange :: Ord a => a -> a -> Range a mkRange x y | x <= y = R x y | otherwise = Empty overlap :: Ord a => Range a -> Range a -> Range a overlap (R x1 y1) (R x2 y2) = let (x, y) = (max x1 x2, min y1 y2) in if x <= y then R x y else Empty overlap _ _ = Empty main :: IO () main = do print $ overlap (mkRange 19 25) (mkRange 22 30) print $ overlap (mkRange 19 25) (mkRange 12 17) print $ overlap (mkRange 'k' 'o') (mkRange 'a' 'm')Python
def overlap(a_min, a_max, b_min, b_max): '' return list(sorted(set(range(a_min, a_max+1)) & set(range(b_min, b_max+1)))) if __name__ == "__main__": '' print (overlap(19, 25, 22, 30)) print (overlap(12, 17, 19, 25))[22, 23, 24, 25]
[]
> def does_overlap(a, b, c, d): overlap = set(range(a, b+1)).intersection(set(range(c, d+1))) print(sorted(overlap)) if overlap else print("No overlap")Here’s a solution in Python.
def overlap(min1, max1, min2, max2): if min1 <= max2 and max1 >= min2: return max(min1, min2), min(max1, max2) return None print(overlap(17, 25, 12, 19)) print(overlap(12, 17, 19, 25)) print(overlap(19, 25, 12, 17)) print(overlap(19, 25, 22, 30))Output:
Mumps version
Klong version
pairs::{[a b]; a::(x@0)|(y@0); b::(x@1)&(y@1); :[b<a; []; a,b]} :dyad pairs([1 18]; [19 25]) [] pairs([1 19]; [19 25]) [19 19] pairs([1 20]; [19 25]) [19 20] pairs([19 20]; [19 25]) [19 20] pairs([20 20]; [19 25]) [20 20] pairs([20 24]; [19 25]) [20 24] pairs([20 25]; [19 25]) [20 25] pairs([20 26]; [19 25]) [20 25] pairs([24 26]; [19 25]) [24 25] pairs([25 26]; [19 25]) [25 25] pairs([26 26]; [19 25]) []racket version
(define (overlap a b) (cond [(and (empty? a) (empty? b)) empty] [(or (empty? a) (empty? b)) 'NoOverlap] [else (let* ((x (if (< (car a) (car b)) a b)) (y (if (equal? x a) b a))) (if (> (car y) (cadr x)) 'NoOverlap (list (car y) (min (cadr x) (cadr y)))))]))Testing