Programming Praxis

10 Responses to “Television Time”

1. Mithran said

   March 20, 2018 at 9:17 AM

   intervals_list = [(1, 4), (6, 8), (2, 4), (7, 9)]
   on_times = set()

   for start, end in intervals_list:
   for time in range(start, end):
   on_times.add(time)

   print list(on_times)
2. Globules said

   March 21, 2018 at 2:03 AM

   A Haskell version.

   import Data.List.Ordered (nubSort)
   
   timesOn :: (Enum a, Ord a) => [(a, a)] -> [a]
   timesOn = nubSort . concatMap (\(s, e) -> [s .. pred e])
   
   main :: IO ()
   main = do
     print $ timesOn [(1, 4), (6, 8), (2, 4), (7, 9)]
     print $ timesOn [(1, 4)]
     print $ timesOn ([] :: [(Int, Int)])
     -- Works with non-integers, too.
     print $ timesOn [('c', 'f'), ('j', 'm'), ('d', 'h')]
   

   $ ./teletime
   [1,2,3,6,7,8]
   [1,2,3]
   []
   "cdefgjkl"
   
3. chaw said

   March 21, 2018 at 3:39 PM

   Here is a solution in standard Scheme. with time- and
   space-complexity linear in the size of the input. (I believe the
   other solutions, so far, require space and time that are exponential
   in the size of the input.)

   (import (scheme base)
           (scheme write)
           (only (srfi 95) sort)
           (only (srfi 8) receive))
   
   (define (intervals-cover-length intervals)
     (let f ((intervals (sort intervals < car))
             (marker -inf.0)
             (len 0))
       (if (null? intervals)
           len
           (receive (start stop) (apply values (car intervals))
             (let ((marker (max marker start)))
               (f (cdr intervals)
                  (max marker stop)
                  (+ len (max 0 (- stop marker)))))))))
   
   (display (intervals-cover-length '((1 4) (6 8) (2 4) (7 9))))
   (display (intervals-cover-length '((0 1e9))))
   (newline)
   
4. Globules said

   March 22, 2018 at 4:28 AM

   Here’s an alternate version in Haskell, which (like chaw’s) just prints the total time spanned by the intervals.

   import Data.List (sort)
   import Data.Ratio ((%))
   
   -- Collapse the sorted argument into the equivalent list of disjoint intervals.
   -- We assume that the start value of each interval is less than the end value.
   collapse :: Ord a => [(a, a)] -> [(a, a)]
   collapse (i1@(s1, e1) : i2@(s2, e2) : is)
     | e1 >= s2  = collapse ((s1, max e1 e2) : is)
     | otherwise = i1 : collapse (i2 : is)
   collapse is = is
   
   -- The total length of "time" covered by the intervals.  We ignore intervals in
   -- which the start time is greater than the end time.
   timeOn :: (Num a, Ord a) => [(a, a)] -> a
   timeOn = sum . map (uncurry subtract) . collapse . sort . filter (uncurry (<))
   
   main :: IO ()
   main = do
     print $ timeOn [(1, 4), (6, 8), (2, 4), (7, 9)]
     print $ timeOn [(2, 2), (1, 4)]
     print $ timeOn [(3, 2)]
     print $ timeOn [(0, 1e9)]
   
     -- Works with rationals, too.
     print $ timeOn [(5 % 8, 11 % 8), (2 % 1, 5 % 2), (1 % 8, 7 % 8)]
   

   $ ./teletime2
   6
   3
   0
   1.0e9
   7 % 4
   
5. Steve said

   March 22, 2018 at 5:07 PM

   MUMPS language

   XJSG     ;
            Q
            ;
   TIMES(STR) ;
            ; DECLARE VARIABLES
            N I,J,MAX,MIN,SEG,TIMES
            ; INITIALIZE COUNTER
            S TIMES=0
            ; LOOP THROUGH SEGMENTS
            F I=1:1:$L(STR,",") D
            . ; FOR EACH SEGMENT, GET MIN AND MAX
            . S SEG=$P(STR,",",I),MIN=$P(SEG," "),MAX=$P(SEG," ",2)
            . ; FOR EACH NUMBER THROUGH MIN AND MAX-1
            . ;   IF NUMBER NOT ALREADY ACCUMULATED, ACCUMULATE IT
            . ;      AND INCREMENT COUNT OF TIMES
            . F J=MIN:1:MAX-1 S:'$D(TIMES(J)) TIMES=TIMES+1,TIMES(J)=""
            Q TIMES
   
   ---
    
   Without comments:
   XJSG     ;
            Q
            ;
   TIMES(STR) ;
            N I,J,MAX,MIN,SEG,TIMES
            S TIMES=0
            F I=1:1:$L(STR,",") D
            . S SEG=$P(STR,",",I),MIN=$P(SEG," "),MAX=$P(SEG," ",2)
            . F J=MIN:1:MAX-1 S:'$D(TIMES(J)) TIMES=TIMES+1,TIMES(J)=""
            Q TIMES
   

   LAB>W $$TIMES^XJSG(“1 4,6 8,2 4,7 9”)
   6
6. Steve said

   March 22, 2018 at 5:52 PM

   @Mithran: I always like to see short solutions. Language?
7. Daniel said

   March 26, 2018 at 4:01 AM

   Here’s a solution in C.

   #include <stdio.h>
   #include <stdlib.h>
   
   typedef unsigned int uint_t;
   
   typedef struct {
     uint_t start;
     uint_t end;
   } interval_t;
   
   static int compar(const void* a, const void* b) {
     uint_t a_start = ((interval_t*)a)->start;
     uint_t b_start = ((interval_t*)b)->start;
     if (a_start > b_start) {
       return 1;
     } else if (a_start < b_start) {
       return -1;
     } else {
       return 0;
     }
   }
   
   // destructive: sorts intervals
   uint_t calc_television_time(
       interval_t* intervals, size_t n) {
     if (n == 0) return 0;
     qsort(intervals, n, sizeof(interval_t), compar);
     uint_t television_time = 0;
     uint_t start = intervals[0].start;
     uint_t end = intervals[0].end;
     for (size_t i = 1; i < n; ++i) {
       if (intervals[i].start > end) {
         television_time += end - start;
         start = intervals[i].start;
       }
       if (intervals[i].end > end) {
         end = intervals[i].end;
       }
     }
     television_time += end - start;
     return television_time;
   }
   
   int main(void) {
     interval_t intervals[] = {
       {1, 4},
       {6, 8},
       {2, 4},
       {7, 9}
     };
     size_t n = sizeof(intervals) / sizeof(interval_t);
     uint_t television_time = calc_television_time(intervals, n);
     printf("%u\n", television_time);
     return EXIT_SUCCESS;
   }
   

   Output:

   6
   
8. Mike said

   March 27, 2018 at 11:27 PM

   @steve, Mithran’s answer looks like Python that had the leading whitespace eaten.

   Here’s a Python answer in a functional style:

   import itertools as it
   
   def on_times(intervals):
       return len(set().union(*it.starmap(range,intervals)))
   
9. Steve said

   March 28, 2018 at 4:24 AM

   Thanks, Mike!

   Klong language

   fh2::{?(z,(x+!(y-x)))}
   fh::{[l t]; l::[]; t::x; {l::fh2(x@0; x@1; l)}'t; l::{#(l@x)}'<l; .p(l); .p(#l); "end"}
   

       fh([[6 8] [1 4] [2 4] [7 9]])
   

   [1 2 3 6 7 8]
   6
   “end”

       fh([[6 8] [1 4] [2 4] [7 9] [11 20]])
   

   [1 2 3 6 7 8 11 12 13 14 15 16 17 18 19]
   15
   “end”
10. Steve said

    March 28, 2018 at 3:28 PM

    Klong language – Commented version

    
    steve@steve-VirtualBox:~/klong$ cat tv-time.kg 
    :" Televsion Time - Programming Praxis"
    :""
    .comment("end-of-comments")
    [l] -       Declare a local variable
    l::[] -     Assign empty list to l
    ? -        Input list, output unique elements of list
    l1,l2 -   Concatenate 2 lists
    x@n -  Return nth element of list (0-based)
    !n -      Return list of integers form 0 to n-1
    {...} -    Definition of function
    {...}'n - Execute function for every element of list n
    #l -       Return length of list
    <l -       Return list where each element is the sorted position 
               of original list.  So if l = [2 1 3] then <l = [1 0 2],
               because l@1 is 1, l@0 is 2 and l@2 is 3.
    .p(x) -  Print x
    end-of-comments
    
    fh::{[l]; l::[]; {l::?(l,((x@0)+!((x@1)-(x@0))))}'x; l::{#(l@x)}'<l; .p(l); .p(#l); "end"}
    
    

    steve@steve-VirtualBox:~/klong$ ./kg
    Klong 20180213
    ]l tv-time.kg
    loading “./tv-time.kg”
    fh([[1 4] [6 8] [2 4] [7 9]])
    [1 2 3 6 7 8]
    6
    “end”
    fh([[1 4] [10 15] [6 8] [2 4] [7 9]])
    [1 2 3 6 7 8 10 11 12 13 14]
    11
    “end”