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.

Advertisements

Pages: 1 2

9 Responses to “Overlap”

  1. V said

    In Ruby. Using Ranges (built-in)

    def overlap(a, b)
      o = a.to_a & b.to_a
      o.size < 2 ? nil : (o.first..o.last)
    end
    
    # Test
    puts overlap((19..25), (22..30))
    puts overlap((19..25), (12..17)).inspect
    

    Outout:

    22..25
    nil

  2. Daniel said

    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:

    $ ./overlap 17 25 12 19
    17 19
    
    $ ./overlap 12 17 19 25
    
    $ ./overlap 19 25 12 17
    
    $ ./overlap 19 25 22 30
    22 25
    
  3. Globules said

    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')
    
    $ ./overlap
    R 22 25
    Empty
    R 'k' 'm'
    
  4. Milbrae said

    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]
    []

  5. thebillywayne said
    > 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")
    
    > does_overlap(19, 25, 22, 30)
    [22, 23, 24, 25]
    > does_overlap(19, 25, 12, 17)
    "No overlap"
    
  6. Daniel said

    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:

    (17, 19)
    None
    None
    (22, 25)
    
  7. Steve said

    Mumps version

    JSG	;
    	Q
    	;
    PAIRS(X1,X2)	;
    	N A,B,I,MAXA,MINB,VAR
    	F I=1,2 S VAR="X"_I,A(I)=$P(@VAR,","),B(I)=$P(@VAR,",",2)
    	S MAXA=$S(A(1)>A(2):A(1),1:A(2)),MINB=$S(B(1)<B(2):B(1),1:B(2))
    	Q $S(MAXA>MINB:"",1:MAXA_","_MINB)
    vista@steve-VirtualBox:~/EHR/r$ gtm
    
    GTM>S X1="19,25" F X2="22,30","1,18","26,30","10,23","19,25","19,30","18,26","20,25","20,30" W !,X1," & ",X2," --> ",$$PAIRS^JSG(X1,X2)
    
    19,25 & 22,30 --> 22,25
    19,25 & 1,18 --> 
    19,25 & 26,30 --> 
    19,25 & 10,23 --> 19,23
    19,25 & 19,25 --> 19,25
    19,25 & 19,30 --> 19,25
    19,25 & 18,26 --> 19,25
    19,25 & 20,25 --> 20,25
    19,25 & 20,30 --> 20,25
    GTM>
    
  8. 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])
    []
            
    
  9. Kevin said

    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

    (overlap '() '()) ==> '()
    (overlap '() '(22 30)) ==> 'NoOverlap
    (overlap '(22 30) '()) ==> 'NoOverlap
    (overlap '(19 25) '(22 30)) ==> '(22 25)
    (overlap '(22 30) '(19 25)) ==> '(22 25)
    (overlap '(10 30) '(12 22)) ==> '(12 22)
    (overlap '(12 22) '(10 30)) ==> '(12 22)
    (overlap '(19 25) '(12 17)) ==> 'NoOverlap
    (overlap '(12 17) '(19 25)) ==> 'NoOverlap
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: