Count the timespans

Question

Inspired by a real-life scenario, which I have asked for an answer to here: https://superuser.com/questions/1312212/writing-a-formula-to-count-how-many-times-each-date-appears-in-a-set-of-date-ran

Given an array of timespans (or startdate-enddate pairs), output a count of how many timespans cover each day, for all days in the total range.

For example:

  #      Start      End
  1    2001-01-01 2001-01-01
  2    2001-01-01 2001-01-03
  3    2001-01-01 2001-01-02
  4    2001-01-03 2001-01-03
  5    2001-01-05 2001-01-05

Given the above data, the results should be as follows:

2001-01-01: 3 (Records 1,2,3)
2001-01-02: 2 (Records 2,3)
2001-01-03: 2 (Records 2,4)
2001-01-04: 0
2001-01-05: 1 (Record 5)

You only need to output the counts for each day (in order, sorted oldest-newest); not which records they appear in.

You can assume that each timespan only contains dates, not times; and so whole days are always represented.

I/O

Input can be any format that represents a set of timespans - so either a set of pairs of times, or a collection of (builtin) objects containing start- and end-dates. The date-times are limited to between 1901 and 2099, as is normal for PPCG challenges.

You can assume the input is pre-sorted however you like (specify in your answer). Input dates are inclusive (so the range includes the whole of the start and end dates).

You can also assume that, of the two dates in any given range, the first will be older or equal to the second (i.e. you won't have a negative date range).

Output is an array containing the count for each day, from the oldest to the newest in the input when sorted by Start Date.

So, the output for the above example would be {3,2,2,0,1}

It is possible that some days are not included in any time range, in which case 0 is output for that date.

Winning Criteria

This is code-golf, so lowest bytes wins. Usual exclusions apply

Pseudo-algorithm example

For each time range in input
    If start is older than current oldest, update current oldest
    If end is newer than current newest, update current newest
End For
For each day in range oldest..newest
   For each time range
       If timerange contains day
            add 1 to count for day
End For
Output count array

Other algorithms to get to the same result are fine.

Answer 1

APL (Dyalog Unicode), 32 bytes^SBCS

Full program. Prompts stdin for a list of pairs of International Date Numbers (like what Excel and MATLAB use). Both list and pairs may be given in any order, e.g. (End,Start). Prints list of counts to stdout.

¯1+⊢∘≢⌸(R,⊢)∊(R←⌊/,⌊/+∘⍳⌈/-⌊/)¨⎕ Try it online!

If this is invalid, a list of (Y M D) pairs can be converted for an additional 21 bytes, totalling 53:

¯1+⊢∘≢⌸(R,⊢)∊(R⌊/,⌊/+∘⍳⌈/-⌊/)¨{2⎕NQ#'DateToIDN'⍵}¨¨⎕ Try it online!

---

⎕ prompt console for evaluated input

(…)¨ apply the following tacit function to each pair

⌊/ the minimum (lit. min-reduction), i.e. the start date

⌈/- the maximum (i.e. end date) minus that

⌊/+∘⍳ the start date plus the range 1-through-that

⌊/, the start date prepended to that

R← assign this function to R (for Range)

∊ ϵnlist (flatten) the list of ranges into a single list

(…) apply the following tacit function to that:

 R,⊢ the result of applying R (i.e. the date range) followed by the argument
  ^{(this ensures that each date in the range is represented at least once, and that the dates appear in sorted order)}

…⌸ for each pair of unique (date, its indices of occurrence in the input), do:

 ⊢∘≢ ignore the actual date in favour of the tally of indices

¯1+ add -1 to those tallies (because we prepended one of each date in the range)

Answer 2

JavaScript (ES6), 85 bytes

Takes input as a list of Date pairs. Expects the list to be sorted by starting date. Returns an array of integers.

f=(a,d=+a[0][0])=>[a.map(([a,b])=>n+=!(r|=d<b,d<a|d>b),r=n=0)|n,...r?f(a,d+864e5):[]]

Try it online!

or 84 bytes if we can take JS timestamps as input (as suggested by @Shaggy)

Answer 3

JavaScript, 75 73 bytes

Takes input as a sorted array of arrays of date primitive pairs, outputs an object where the keys are the primitives of each date and the values the counts of those dates in the ranges.

a=>a.map(g=([x,y])=>y<a[0][0]||g([x,y-864e5],o[y]=~~o[y]+(x<=y)),o={})&&o

Try it

---

I was working on this 60 byte version until it was confirmed that dates that don't appear in any of the ranges must be included so hastily updated it to the solution above.

a=>a.map(g=([x,y])=>x>y||g([x+864e5,y],o[x]=-~o[x]),o={})&&o

Try it online (or with human readable dates in the output)

Answer 4

Octave, 63 bytes

@(x)histc(t=[cellfun(@(c)c(1):c(2),x,'un',0){:}],min(t):max(t))

Try it online!

Now that was ugly!

Explanation:

Takes the input as a cell array of datenum elements (i.e. a string "2001-01-01" converted to a numeric value, looking like this:

{[d("2001-01-01") d("2001-01-01")]
[d("2001-01-01") d("2001-01-03")]
[d("2001-01-01") d("2001-01-02")]
[d("2001-01-03") d("2001-01-03")]
[d("2001-01-05") d("2001-01-05")]};

where d() is the function datenum. We then use cellfun to create cells with the ranges from the first column to the second for each of those rows. We concatenate these ranges horizontally, so that we have a long horizontal vector with all the dates.

We then create a histogram using histc of these values, with bins given by the range between the lowest and the highest date.

Answer 5

R, 75 bytes

function(x,u=min(x):max(x))rowSums(outer(u,x[,1],">=")&outer(u,x[,2],"<="))

Try it online!

Input is a matrix whose first column is Start and second column is End. Assumes Start<=End but does not require Start dates to be sorted.

Answer 6

Python 2, 114 87 93 bytes

-27 bytes thanks to Jonathan Allan
+6 bytes thanks to sundar

Takes input as list of pairs of datetime objects.
Assumes that first pair starts with the lowest date.

def F(I):
 d=I[0][0]
 while d<=max(sum(I,[])):print sum(a<=d<=b for a,b in I);d+=type(d-d)(1)

Try it online!

Answer 7

Groovy, 142 bytes

{a={Date.parse('yyyy-mm-dd',it)};b=it.collect{a(it[0])..a(it[1])};b.collect{c->b.collect{it}.flatten().unique().collect{it in c?1:0}.sum()}}

​

Formatted out:

 {                                   // Begin Closure
    a={Date.parse('yyyy-mm-dd',it)}; // Create closure for parsing dates, store in a().
    b=it.collect{                    // For each input date pair...
        a(it[0])..a(it[1])           // Parse and create date-range.
    };
    b.collect{                       // For each date range...
        c->
        b.collect{                   // For each individual date for that range...
           it
        }.flatten().unique().collect{ // Collect unique dates.
            it in c?1:0
        }.sum()                      // Occurrence count.
    }
}

Answer 8

Red, 174 bytes

func[b][m: copy #()foreach[s e]b[c: s
until[m/(c): either none = v: m/(c)[1][v + 1]e < c: c + 1]]c: first sort b
until[print[either none = v: m/(c)[0][v]](last b)< c: c + 1]]

Quite long and literal implementation.

Try it online!

Readable:

f: func [ b ] [
    m: copy #()
    foreach [ s e ] b [
        c: s
        until [
            m/(c): either none = v: m/(c) [ 1 ] [ v + 1 ]   
            e < c: c + 1
        ]      
    ]
    c: first sort b
    until[
        print [ either none = v: m/(c) [ 0 ] [ v ] ]
        ( last b ) < c: c + 1
    ]      
]

Answer 9

R, 65 63 bytes

function(x)hist(unlist(Map(`:`,x[,1],x[,2])),min(x-1):max(x))$c

Try it online!

This is a collaboration between JayCe and myself, porting Stewie Griffin's answer over to R.

To quote JayCe:

Input is a matrix whose first column is Start and second column is End. Assumes Start<=End but does not require Start dates to be sorted.

Possibly, $c is unnecessary but it's not quite in the spirit of the challenge so I've included it.

Answer 10

Wolfram Language (Mathematica), 62 bytes

Lookup[d=DayRange;Counts[Join@@d@@@#],#[[1,1]]~d~#[[-1,1]],0]&

Try it online!

+35 bytes because OP specified that 0 must be included in the output.

If omitting an entry in a dictionary were allowed, 27 bytes

Counts[Join@@DayRange@@@#]&

Try it online!

The built-in DayRange accepts two DateObjects (or a string equivalent) and outputs a list of Dates between those dates (inclusive).

Answer 11

Powershell, 122 121 118 113 bytes

filter d{0..($_[-1]-($s=$_[0])).Days|%{$s.AddDays($_)}}$c=@{};$args|d|%{++$c.$_};,($c.Keys.Date|sort)|d|%{+$c.$_}

save it as count-timespan.ps1. Test script:

.\count-timespan.ps1 `
    @([datetime]"2001-01-01", [datetime]"2001-01-01")`
    @([datetime]"2001-01-01", [datetime]"2001-01-03")`
    @([datetime]"2001-01-01", [datetime]"2001-01-02")`
    @([datetime]"2001-01-03", [datetime]"2001-01-03")`
    @([datetime]"2001-01-05", [datetime]"2001-01-05")

Explanation

filter d{                           # define a function with a pipe argument (it's expected that argument is an array of dates)
    0..($_[-1]-($s=$_[0])).Days|%{  # for each integer from 0 to the Days
                                    # where Days is a number of days between last and first elements of the range
                                    # (let $s stores a start of the range)
        $s.AddDays($_)              # output to the pipe a date = first date + number of the current iteration
    }                               # filter returns all dates for each range
}                                   # dates started from first element and ended to last element
$c=@{}                              # define hashtable @{key=date; value=count}
$args|d|%{++$c.$_}                  # count each date in a array of arrays of a date
,($c.Keys.Date|sort)|d|%{+$c.$_}    # call the filter via pipe with the array of sorted dates from hashtable keys

# Trace:
# call d @(2001-01-01, 2001-01-01) @(2001-01-01, 2001-01-03) @(2001-01-01, 2001-01-02) @(2001-01-03, 2001-01-03) @(2001-01-05, 2001-01-05)
# [pipe]=@(2001-01-01, 2001-01-01, 2001-01-02, 2001-01-03, 2001-01-01, 2001-01-02, 2001-01-03, 2001-01-05)
# $c=@{2001-01-03=2; 2001-01-01=3; 2001-01-05=1; 2001-01-02=2}
# call d @(2001-01-01, 2001-01-02, 2001-01-03, 2001-01-05)
# [pipe]=@(2001-01-01, 2001-01-02, 2001-01-03, 2001-01-04, 2001-01-05)
# [output]=@(3, 2, 2, 0, 1)

Answer 12

J, 43 bytes

(],.[:+/@,"2="{~)&:((>./(]+i.@>:@-)<./)"1),

the input is a list of pairs of integers, where each integer is the offset from any arbitrary common 0-day.

ungolfed

(] ,. [: +/@,"2 ="{~)&:((>./ (] + i.@>:@-) <./)"1) ,

explanation

structure is:

(A)&:(B) C

• C creates a hook that gives the main verb A&:B the input on the left and the input flattened on the right
• B aka ((>./ (] + i.@>:@-) <./)"1) takes the min and max of a list and returns the resulting range, and acts with rank 1. hence it gives the total range on the right, and the individual ranges on the left.
• A then uses = with rank "0 _ (ie, rank of {) to count how many times each input appears in any of the ranges. finally it zips every year with those counts.

Try it online!

Answer 13

JavaScript (Node.js), 80 bytes

(a,u=[])=>a.map(g=([p,q])=>p>q||g([p,q-864e5],u[z=(q-a[0][0])/864e5]=-~u[z]))&&u

Try it online!

undefined means zero; First element should start earliest

(a,u=[])=>a.map(g=([p,q])=>p>q||g([p,q-1],u[z=(q-a[0][0])/864e5]=-~u[z]))&&u is shorter if you only see elements and use more stack

Answer 14

Julia 0.6, 77 bytes

M->[println(sum(d∈M[r,1]:M[r,2]for r∈1:size(M,1)))for d∈M[1]:max(M...)]

Try it online!

Inspired by @DeadPossum's Python solution.

Takes input as a matrix, where each row has two dates: the starting and ending dates of an input range. Assumes the input has the earliest date first, and that each row has the starting date first, but assumes no sorting beyond that between different rows.

---

Older solution:

Julia 0.6, 124 bytes

R->(t=Dict();[[d∈keys(t)?t[d]+=1:t[d]=1 for d∈g]for g∈R];[d∈keys(t)?t[d]:0 for d∈min(keys(t)...):max(keys(t)...)])

Try it online!

Accepts input as an array of date ranges. Does not assume any sorting among the different ranges in the array.

Answer 15

Ruby, 70 bytes

->s{f,=s.min;(p s.count{|a,b|(f-a)*(f-b)<=0};f+=86400)until f>s[0][1]}

Try it online!

Input:

Array of pairs of dates, sorted by ending date descending.

Answer 16

R (70)

function(x)(function(.)tabulate(.-min(.)+1))(unlist(Map(seq,x$S,x$E,"d")))

Presumes a data frame x with two columns (Start and End or possibly S and E) with dates (class Date).

Try it online