| Bytes | Lang | Time | Link |
|---|---|---|---|
| 022 | Haskell + hgl | 250625T044904Z | Wheat Wi |
| 037 | Haskell | 250625T041234Z | Wheat Wi |
| 042 | Ruby | 250611T025325Z | Value In |
| 026 | APLDyalog Unicode | 250617T110219Z | Mat_rdv |
| 112 | Mathematica | 250616T105058Z | Chris De |
| 057 | Python 3 | 250614T233617Z | Lucenapo |
| 513 | JavaScript Node.js | 250616T110529Z | Chris De |
| 036 | Uiua | 250611T104539Z | Maki |
| nan | Commodore 64 Assembler | 250611T092810Z | Jani Joe |
| 051 | JavaScript Node.js | 250610T114037Z | l4m2 |
| 009 | Jelly | 250611T013410Z | Jonathan |
| 020 | K ngn/k | 250610T183746Z | att |
| 070 | Haskell | 250610T151214Z | Ibozz91 |
| 023 | Charcoal | 250610T060356Z | Neil |
| 071 | JavaScript ES6 | 250610T100447Z | Arnauld |
| 010 | 05AB1E | 250610T084554Z | Kevin Cr |
Haskell + hgl, 22 bytes
cnT<jl2(lt<>cr><ge<st)
Explanation
This is a loose port of my vanilla haskell answer.
jl2run a function over all pairs in the list.ltthe first interval is less than the second.cr><ge<stthe end of the first interval is greater than or equal to the start of the second.cnTcount the number of true elements.
Reflection
This is completely satisfactory. There's nothing really missing and my suggestions are sort of a reach.
- What we are doing is counting the number of pairs that satisfy some predicate. We have to do that in two parts: 1. run the predicate over pairs 2. count the number of
Trues. It would maybe be useful to have a function which does both at once. That is counts the number of pairs that satisfy a predicate. We would want a couple of versions of this. cr><ge<stis a little expensive. I could possibly add a function of the type:
Which would let me construct this sort of thing. I'm not sure exactly what type fits??? :: (a -> b -> c) -> p d a -> p b e -> cpbest though.- A built in interval type or interval handling functions on tuples could be useful.
Haskell, 37 bytes
f a=sum[1|u<-a,v<-a,u<v,fst v<=snd u]
We count the number of pairs u and v where
u<v, that is the start point ofuis before or equal to the start point ofv(and if they are equal than the end point ofuis before that ofv)- The end point of
uis after the start point ofv
By 1. we already know the start point of u is before that of v, so we can check for intersection rather simply with just 2.
This also avoids a couple of issues we could run into:
- Since we only count pairs where
u<vwe don't count reflexive pairs twice. - For the same reason we don't count the intersection of an interval with itself.
We don't have to spend any bytes correcting for these over counts.
Ruby, 69 51 42 bytes
-18 -27 bytes from G B.
->a{a.sum{|x,y|a.count{y>=_1&&_2>=x}-1}/2}
->a{
a.sum{|x,y| # For each interval [L1,R1], get value and sum
a.count{ # Count all intervals [L2,R2] where
y>=_1&&_2>=x # R1 is NOT below L2 and L1 is NOT above R2
# (if R1 < L2 OR L1 > R2 there's no overlap;
# invert via De Morgan's Law)
}-1 # Account for interval comparing to itself
}/2 # Account for all pairs being counted twice
}
APL(Dyalog Unicode),
2÷⍨{+/,∨∘⍉⍨∨⌿⍤2≠/×∘.-⍨⍵}-≢
An argument is a matrix of shape n×2.
Explanation
The main part, dfn:
{ } dfn
⍵ the right argument
⍨ Selfie: f⍨ Y ←→ Y f Y
-
∘. Outer product
(table of all combinations of elements of both arguments)
∘.-⍨⍵ Array of differences of shape n×2×n×2
× Signum (positive→1, negative→¯1, 0→0)
/ Reduction (along the last axis)
≠ Not equal
≠/ if for some point p: (× p - L2) ≠ (× p - R2), hence p∊[L2, R2]
now the array has a shape n 2 n
⍤2 at Rank 2
⌿ Reduce first
⌿⍤2 Reduce along the 2nd axis from the end
∨ Logical or
∨⌿⍤2≠/∘.-⍨⍵ n×n matrix, each cell shows
whether at least one end of the [L1, R1] lies in the [L2, R2]
(thus two ranges intersect except when the second lies inside the first)
⍨
⍉ Transpose
∘ X f∘g Y ←→ X f (g Y)
∨
∨∘⍉⍨ matrix ∨-symmetrization
∨∘⍉⍨∨⌿⍤2≠/∘.-⍨⍵ Intersection table
, Ravel (list elements of the matrix in one vector)
/
+
+/ sum
{+/,∨∘⍉⍨∨⌿⍤2≠/×∘.-⍨⍵} Number of intersections but
including selfintersections and doubling others
Tacit function: (f g h) Y ←→ (f Y) g (h Y) and (A f g) Y ←→ A f (g Y)
≢ Tally (size of the first axis, n)
-
{+/,∨∘⍉⍨∨⌿⍤2≠/×∘.-⍨⍵}-≢ Doubled number of intersections
⍨ Commute: X f⍨ Y ←→ Y f X
÷ Divide
2÷⍨{+/,∨∘⍉⍨∨⌿⍤2≠/×∘.-⍨⍵}-≢ solution
Mathematica 112 characters
p = {{0, 3}, {3, 4}, {3, 8}, {5, 6}, {8, 9}};
Length@Select[{##,Or[#1[[1]]<=#2[[1]]<= #1[[2]],#2[[1]]<=#1[[1]]<=#2[[2]]]}&
@@@Union[Sort/@Subsets[p,{2}]],Last]
5
These are the 5 unique intersecting pairs for the above case.
L1,R1 L2,R2
{{0,3},{3,4} L1 <= L2 <= R1
{{0,3},{3,8} L1 <= L2 <= R1
{{3,4},{3,8} L1 <= L2 <= R1 and L2 <= L1 <= R2
{{3,8},{5,6} L1 <= L2 <= R1
{{3,8},{8,9} L1 <= L2 <= R1
With the sort, if the first test is passed the second is unnecessary.
Therefore, in 68 characters
Count[#1[[1]]<=#2[[1]]<=#1[[2]]&@@@Union[Sort/@Subsets[p,{2}]],True]
Python 3, 57 bytes
lambda x:-len(x)/2-sum((b<c)-.5for a,b in x for c,d in x)
Takes input as [[1,2],[3,4],[5,6]].
Python 2, 49 bytes
lambda x,y:sum(.5-(b<c)for b in y for c in['']+x)
JavaScript (Node.js), 513 bytes
function c(p) {
function s(v) {
let r = [];
for (let i = 0; i < v.length; i++) {
for (let j = i + 1; j < v.length; j++) {
r.push([v[i], v[j]]);
}
}
return r;
}
function t(q) {
let [a, b] = q;
return (
(a[0] <= b[0] && b[0] <= a[1]) ||
(b[0] <= a[0] && a[0] <= b[1])
);
}
let u = s(p).map(k => k.sort((x, y) => x[0] - y[0] || x[1] - y[1]));
return [...new Set(u.filter(t).map(JSON.stringify))].length;
}
const p = [[0, 3], [3, 4], [3, 8], [5, 6], [8, 9]];
console.log(c(p));
This finds 5 unique intersecting pairs in agreement with my Mathematica answer.
L1,R1 L2,R2
[[0,3], [3,4]] L1 <= L2 <= R1 0 <= 3 <= 3
[[0,3], [3,8]] L1 <= L2 <= R1 0 <= 3 <= 3
[[3,4], [3,8]] L1 <= L2 <= R1 3 <= 3 <= 4
[[3,8], [5,6]] L1 <= L2 <= R1 3 <= 5 <= 8
[[3,8], [8,9]] L1 <= L2 <= R1 3 <= 8 <= 8
Uiua, 50 44 42 41 37 36 bytes
/+/+×⊞⊃(>∩□|⊢≤⇌).⍆
Uiua is read right-to-left.
First we sort the list of input pairs lexicographically with ⍆.
Then we duplicate that list . and build two tables in parallel ⊞⊃, using the carthesian product of the copies. In the first table >∩□, the upper right triangle (without the diagonal) is 1, and the rest is 0
The second becomes a table of all intersections ⊢≤⇌, which gives 0 for no intersection and 1 for intersection, using the knowledge the list is already sorted to skip the L1 <= L2 check.
Finally, we multiply these tables element by element with ×, which is equivalent to a boolean and, and sum up all the 1s with /+/+ to get the final result.
Note: /+♭ would be shorter in characters, but is longer in bytes using UTF-8
Commodore 64 Assembler, 39 Bytes (6502/KickAssembler)
According to the author: "You may write a full program or a function. Input is the array in any reasonable form". I interpreted this so that only the size of the routine (function) itself counts, and it doesn't really matter how the input array is passed to the routine.
Thus for convenience, I made a test program where the array is just a list of bytes and gets compiled with the program itself. There would have been other options to input the array (create a separate routine to read user input, read from screen, read from a file etc.) but as the point is just to prove that the routine itself works, this was the easiest solution that required least effort.
Explanation
- Usage: Set the byte pairs (i.e. array elements) on the
array. Values from 1 to 255 are allowed, zero (null terminator) is reserved for telling the routine where the array ends. Compile and run. - The routine starts by comparing array element 1 with elements 2 to n. After those comparisons are done, it compares element 2 with elements 3 to n and so on, until it reaches the end of the array. This guarantees that each comparison is unique.
- For each element pair, code checks if the element 1 ends before element 2 starts (no overlap), or if element 2 ends before element 1 starts (no overlap). If neither comparison is true, the elements must overlap and the intersections count is incremented.
- Routine could have been 4 bytes shorter (memory address $2 is already zeroed on system start and X is already zeroed on program start), however to respect the thought of the code needing to represent a standalone function that can be called by anything from anywhere, as many times as one wishes, and always provide the same result, I do reset both X (1st array element pointer) and address $2 (intersections count) at the start of the routine.
Complete Test Program
BasicUpstart2(start) // Basic program to help us run our machine language
// routine with RUN, without typing in a SYS command
start: ldx #0 // Reset [L1,R1] array element pointer
stx $2 // Reset intersections count on zero page
inc_1: inx // Increase [L1,R1] array element pointer
inx // (starts from first element)
txa // Copy [L1,R1] array element pointer...
tay // ...to [L2,R2] pointer
inc_2: iny // Increase [L2,R2] array element pointer
iny // (starts from element after [L1,R1])
lda array-1,x // Load R1 to A
beq print // [0,0] indicates end of array - we're done
cmp array-2,y // Compare to L2
bcc inc_2 // If R1 ends before L2 starts, no overlap
lda array-1,y // Load R2 to A
beq inc_1 // If [L2,R2] = [0,0], a round is done
cmp array-2,x // Compare to L1
bcc inc_2 // If R2 ends before L1 starts, no overlap
inc $2 // Otherwise, there must be overlap - increase count
bcs inc_2 // Continue to next comparison (branch always taken)
print: ldx $2 // Load number of intersections to X
jmp $bdcf // Call ROM routine to print it out in decimal
.print "ROUTINE SIZE: " + toIntString(*-start)
array: .by 1,2,5,6,1,5,4,7
.by 0,0 // Null termination of the array
Routine Breakdown
start: ldx #0 // Reset [L1,R1] array element pointer
stx $2 // Reset intersections count on zero page
Resetting the 1st element pointer (held in X) and intersections count on zero page address $2 on every run of the routine. Intersections count is kept on zero page to be able to use an 8bit address instead of 16bit address when referring to it, thus saving a couple bytes in the routine.
inc_1: inx // Increase [L1,R1] array element pointer
inx // (starts from first element)
txa // Copy [L1,R1] array element pointer...
tay // ...to [L2,R2] pointer
inc_1 is what we could call an outer loop, where we increase the 1st array element pointer and reset the 2nd element pointer to prepare for inner loop. Pointers will actually point one element too deep into the array, but we'll correct the offset later when accessing the array.
inc_2: iny // Increase [L2,R2] array element pointer
iny // (starts from element after [L1,R1])
In the inner loop, as the first thing increment 2nd array element pointer. This guarantees that an element is never compared to itself.
lda array-1,x // Load R1 to A
beq print // [0,0] indicates end of array - we're done
cmp array-2,y // Compare to L2
bcc inc_2 // If R1 ends before L2 starts, no overlap
First comparison (lda and cmp): Does 1st element end before 2nd element starts? If so, there cannot be any overlap - bcc will branch to beginning of inner loop. Even before comparison,beq checks if 1st element is already a null element, and if so, whole array is processed and we can branch to printing the result.
lda array-1,y // Load R2 to A
beq inc_1 // If [L2,R2] = [0,0], a round is done
cmp array-2,x // Compare to L1
bcc inc_2 // If R2 ends before L1 starts, no overlap
Second comparison: Does second element end before first element starts? If so, there cannot be any overlap - bcc will branch to beginning of inner loop. Even before comparison,beq checks if 2nd element is already a null element, and if so, we've compared 1st element to all subsequent elements in array and can exit to the outer loop to increase 1st element pointer.
inc $2 // Otherwise, there must be overlap - increase count
bcs inc_2 // Continue to next comparison (branch always taken)
If both comparisons were false, the elements must overlap, thus increase the intersections count and continue the inner loop.
print: ldx $2 // Load number of intersections to X
jmp $bdcf // Call ROM routine to print it out in decimal
If we've reached this far, whole array is processed - print out the total number of intersections with a ROM routine. After it is done, the ROM routine does an rts (return to system), thus ending the execution of our whole routine (and in this case, returning to BASIC prompt).
JavaScript (Node.js), 51 bytes
x=>x.map(a=>x.map(b=>r-=a[1]<b[0]||-1,r--),r=0)|r/2
By default each ordered pair(including self to self) score 1, reduce 2 for every segment pair A,B s.t. A is on left of B, reduce 1 for each segment(self pairs)
JavaScript (Node.js), 61 bytes
f=([e,...x],c=0)=>e&&x.map(t=>c+=t[0]>e[1]^t[1]>=e[0])|f(x,c)
Note: Last map operation returns an array of a single number, which is or'ed with undefined
Jelly, 9 bytes
r/€Œcf/ƇL
A monadic Link that accepts a list of pairs of integers and yields the number of overlapping pairs.
How?
r/€Œcf/ƇL - Link: list of pairs of integers
€ - for each pair:
/ - reduce by:
r - inclusive range
Œc - unordered pairs of those ranges
Ƈ - keep those for which:
/ - reduce by:
f - filter keep
L - length
K (ngn/k), 20 bytes
+/>/&{~x>,\y}/+.1<:\
Port of Kevin Cruijssen's approach.
.1<:\ sort
{~x>,\y}/+ l_i ≤ r_j for i≥j
+/>/& count
>/ for i>j
Haskell, 70 bytes
f a=div(sum[1|(w,x)<-a,(y,z)<-a,(w<=y&&y<=x)||(y<=w&&w<=z)]-length a)2
Takes in a list of tuples.
Charcoal, 24 23 bytes
ＩΣ⭆θ⭆Ｅ…θκ⟦ιλ⟧¬›§⌈λ⁰§⌊λ¹
Try it online! Link is to verbose version of code. Explanation:
θ Input array
⭆ Map over elements and join
θ Input array
… Truncated to length
κ Current index
Ｅ Map over elements
⟦ιλ⟧ Pair outer and inner element
⭆ Map over pairs and join
§⌈λ⁰ Lower end of upper range
¬› Is less than or equal to
§⌊λ¹ Upper end of lower range
Σ Count the `1`s
Ｉ Cast to string
Implicitly print
Edit: Saved 1 byte by porting @KevinCruijssen's approach of just checking the ends of the maximum and minimum range.
JavaScript (ES6), 71 bytes
Very basic.
a=>a.map(([b,c],i)=>a.map(([d,e],j)=>n+=i<j&!(b>d|d>c&&d>b|b>e)),n=0)|n
05AB1E, 10 bytes
.Æʒ{`R@θ}g
Explanation:
Instead of checking both \$L1 \leq L2 \leq R1\$ and \$L2 \leq L1 \leq R2\$ with a logical OR in between them, I first sort the pair of pairs based on the \$L\$s:
- If \$L1<L2\$ → \$[[L1,R1],[L2,R2]]\$ remains unchanged
- If \$L2<L1\$ → \$[[L1,R1],[L2,R2]]\$ becomes \$[[L2,R2],[L1,R1]]\$
- If \$L1=L2\$ → Sort based on the \$R\$s, so could becomes either
After which I can simply check for \$l2 \leq r1\$.
.Æ # Get all 2-element combinations of the (implicit) input-list
ʒ # Filter this list of pairs of pairs by:
{ # Sort the pair of pairs based on the first elements
# (aka, sort [[L1,R1],[L2,R2]] based on just the L1 & L2)
# let's call this sorted pair [[l1,r1],[l2,r2]]
` # Pop and push both pairs separated to the stack
# → [l1,r1] and [l2,r2]
R # Reverse the top/second pair
# → [l1,r1] and [r2,l2]
@ # Do an >= check
# → [l1>=r2,r1>=l2]
θ # Pop and leave the last check of the pair
# → r1>=l2
}g # After the filter: pop and push the length
# (which is output implicitly as result)