Overlap

June 8, 2018

A little bit of thinking (and a few trials when I thought backwards) gives this solution:

(define (overlap xlo xhi ylo yhi)
  (if (or (< xhi ylo) (< yhi xlo)) '()
    (list (max xlo ylo) (min xhi yhi))))

If an overlap exists, it starts at the maximum of the lo values and ends at the minimum of the hi values. Here are some examples:

> (overlap 17 25 12 19)
(17 19)
> (overlap 12 17 19 25)
()
> (overlap 19 25 12 17)
()
> (overlap 19 25 22 30)
(22 25)

You can run the program at https://ideone.com/c7a0XU.

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: