Range consolidation: Difference between revisions
Ada version |
Added Easylang |
||
(51 intermediate revisions by 25 users not shown) | |||
Line 1: | Line 1: | ||
{{task}} |
{{task}} |
||
Define a range of numbers |
Define a range of numbers '''R''', with bounds '''b0''' and '''b1''' covering all numbers ''between and including both bounds''. |
||
: <code>[b0, b1]</code><br> |
|||
or equally as:<br> |
|||
That range can be shown as: |
|||
: <code>[b1, b0]</code>. |
|||
::::::::: '''[b0, b1]''' |
|||
:::::::: or equally as: |
|||
::::::::: '''[b1, b0]''' |
|||
Given two ranges, the act of consolidation between them compares the two ranges: |
Given two ranges, the act of consolidation between them compares the two ranges: |
||
* If one range covers all of the other then the result is that encompassing range. |
* If one range covers all of the other then the result is that encompassing range. |
||
* If the ranges touch or intersect then the result is ''one'' new single range covering the overlapping ranges. |
* If the ranges touch or intersect then the result is ''one'' new single range covering the overlapping ranges. |
||
* Otherwise the act of consolidation is to return the two non-touching ranges. |
* Otherwise the act of consolidation is to return the two non-touching ranges. |
||
Given N ranges where N>2 then the result is the same as repeatedly replacing all combinations of two ranges by their consolidation until no further consolidation between range pairs is possible. If N<2 then range consolidation has no strict meaning and the input can be returned. |
|||
Given '''N''' ranges where '''N > 2''' then the result is the same as repeatedly replacing all combinations of two ranges by their consolidation until no further consolidation between range pairs is possible. |
|||
;'''Example 1:''' |
|||
:Given the two ranges <tt>[1, 2.5]</tt> and <tt>[3, 4.2]</tt> then there is no |
|||
:common area between the ranges and the result is the same as the input. |
|||
;'''Example 2:''' |
|||
:Given the two ranges <tt>[1, 2.5]</tt> and <tt>[1.8, 4.7]</tt> then there is |
|||
:an overlap <tt>[2.5, 1.8]</tt> between the ranges and the result is the single |
|||
:range <tt>[1, 4.7]</tt>. Note that order of bounds in a range is not, (yet), stated. |
|||
;'''Example 3:''' |
|||
:Given the two ranges <tt>[6.1, 7.2]</tt> and <tt>[7.2, 8.3]</tt> then they |
|||
:touch at <tt>7.2</tt> and the result is the single range <tt>[6.1, 8.3]</tt>. |
|||
;'''Example 4:''' |
|||
:Given the three ranges <tt>[1, 2]</tt> and <tt>[4, 8]</tt> and <tt>[2, 5]</tt> |
|||
:then there is no intersection of the ranges <tt>[1, 2]</tt> and <tt>[4, 8]</tt> |
|||
:but the ranges <tt>[1, 2]</tt> and <tt>[2, 5]</tt> overlap and consolidate to |
|||
:produce the range <tt>[1, 5]</tt>. This range, in turn, overlaps the other range |
|||
:<tt>[4, 8]</tt>, and so consolidates to the final output of the single range |
|||
:<tt>[1, 8]</tt> |
|||
If '''N < 2''' then range consolidation has no strict meaning and the input can be returned. |
|||
;'''Task:''' |
|||
Let a normalized range display show the smaller bound to the left; and show the |
|||
range with the smaller lower bound to the left of other ranges when showing multiple |
|||
ranges. |
|||
Output the ''normalised'' result of applying consolidation to these five sets of ranges: |
|||
;Example 1: |
|||
<pre> |
|||
: Given the two ranges '''[1, 2.5]''' and '''[3, 4.2]''' then |
|||
[1.1, 2.2] |
|||
: there is no common region between the ranges and the result is the same as the input. |
|||
[6.1, 7.2], [7.2, 8.3] |
|||
[4, 3], [2, 1] |
|||
[4, 3], [2, 1], [-1, -2], [3.9, 10] |
|||
;Example 2: |
|||
[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6] |
|||
: Given the two ranges '''[1, 2.5]''' and '''[1.8, 4.7]''' then |
|||
</pre> |
|||
: there is : an overlap '''[2.5, 1.8]''' between the ranges and |
|||
Show output here. |
|||
: the result is the single range '''[1, 4.7]'''. |
|||
<br> |
|||
: Note that order of bounds in a range is not (yet) stated. |
|||
<br> |
|||
'''See also''' |
|||
;Example 3: |
|||
: Given the two ranges '''[6.1, 7.2]''' and '''[7.2, 8.3]''' then |
|||
: they touch at '''7.2''' and |
|||
: the result is the single range '''[6.1, 8.3]'''. |
|||
;Example 4: |
|||
: Given the three ranges '''[1, 2]''' and '''[4, 8]''' and '''[2, 5]''' |
|||
: then there is no intersection of the ranges '''[1, 2]''' and '''[4, 8]''' |
|||
: but the ranges '''[1, 2]''' and '''[2, 5]''' overlap and |
|||
: consolidate to produce the range '''[1, 5]'''. |
|||
: This range, in turn, overlaps the other range '''[4, 8]''', and |
|||
: so consolidates to the final output of the single range '''[1, 8]'''. |
|||
;Task: |
|||
Let a normalized range display show the smaller bound to the left; and show the |
|||
range with the smaller lower bound to the left of other ranges when showing multiple ranges. |
|||
Output the ''normalized'' result of applying consolidation to these five sets of ranges: <big> |
|||
[1.1, 2.2] |
|||
[6.1, 7.2], [7.2, 8.3] |
|||
[4, 3], [2, 1] |
|||
[4, 3], [2, 1], [-1, -2], [3.9, 10] |
|||
[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6] </big> |
|||
Show all output here. |
|||
;See also: |
|||
* [[Set consolidation]] |
* [[Set consolidation]] |
||
* [[Set of real numbers]] |
* [[Set of real numbers]] |
||
<br><br> |
<br><br> |
||
=={{header|11l}}== |
|||
{{trans|Python}} |
|||
<syntaxhighlight lang="11l">F consolidate(ranges) |
|||
F normalize(s) |
|||
R sorted(s.filter(bounds -> !bounds.empty).map(bounds -> sorted(bounds))) |
|||
V norm = normalize(ranges) |
|||
L(&r1) norm |
|||
V i = L.index |
|||
I !r1.empty |
|||
L(j) i + 1 .< norm.len |
|||
V& r2 = norm[j] |
|||
I !r2.empty & r1.last >= r2[0] |
|||
r1 = [r1[0], max(r1.last, r2.last)] |
|||
r2.clear() |
|||
R norm.filter(rnge -> !rnge.empty) |
|||
L(s) [[[1.1, 2.2]], |
|||
[[6.1, 7.2], [7.2, 8.3]], |
|||
[[4.0, 3.0], [2.0, 1.0]], |
|||
[[4.0, 3.0], [2.0, 1.0], [-1.0, -2.0], [3.9, 10.0]], |
|||
[[1.0, 3.0], [-6.0, -1.0], [-4.0, -5.0], [8.0, 2.0], [-6.0, -6.0]]] |
|||
print(String(s)[1 .< (len)-1]‘ => ’String(consolidate(s))[1 .< (len)-1])</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[1.1, 2.2] => [1.1, 2.2] |
|||
[6.1, 7.2], [7.2, 8.3] => [6.1, 8.3] |
|||
[4, 3], [2, 1] => [1, 2], [3, 4] |
|||
[4, 3], [2, 1], [-1, -2], [3.9, 10] => [-2, -1], [1, 2], [3, 10] |
|||
[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6] => [-6, -1], [1, 8] |
|||
</pre> |
|||
=={{header|Action!}}== |
|||
{{libheader|Action! Tool Kit}} |
|||
{{libheader|Action! Real Math}} |
|||
<syntaxhighlight lang="action!">INCLUDE "H6:REALMATH.ACT" |
|||
DEFINE PTR="CARD" |
|||
DEFINE RANGESIZE="12" |
|||
DEFINE LOW_="+0" |
|||
DEFINE HIGH_="+6" |
|||
TYPE Range=[CARD l1,l2,l3,h1,h2,h3] |
|||
PROC Inverse(Range POINTER r) |
|||
REAL tmp |
|||
RealAssign(r LOW_,tmp) |
|||
RealAssign(r HIGH_,r LOW_) |
|||
RealAssign(tmp,r HIGH_) |
|||
RETURN |
|||
PROC Normalize(Range POINTER r) |
|||
IF RealLess(r HIGH_,r LOW_) THEN |
|||
Inverse(r) |
|||
FI |
|||
RETURN |
|||
INT FUNC Compare(Range Pointer r1,r2) |
|||
IF RealLess(r1 LOW_,r2 LOW_) THEN |
|||
RETURN (-1) |
|||
ELSEIF RealLess(r2 LOW_,r1 LOW_) THEN |
|||
RETURN (1) |
|||
ELSEIF RealLess(r1 HIGH_,r2 HIGH_) THEN |
|||
RETURN (-1) |
|||
ELSEIF RealLess(r2 HIGH_,r1 HIGH_) THEN |
|||
RETURN (1) |
|||
FI |
|||
RETURN (0) |
|||
PTR FUNC GetItemAddr(PTR data INT index) |
|||
RETURN (data+index*RANGESIZE) |
|||
PROC Swap(Range POINTER r1,r2) |
|||
REAL tmp |
|||
RealAssign(r1 LOW_,tmp) |
|||
RealAssign(r2 LOW_,r1 LOW_) |
|||
RealAssign(tmp, r2 LOW_) |
|||
RealAssign(r1 HIGH_,tmp) |
|||
RealAssign(r2 HIGH_,r1 HIGH_) |
|||
RealAssign(tmp, r2 HIGH_) |
|||
RETURN |
|||
PROC Sort(PTR data INT count) |
|||
INT i,j,minpos |
|||
Range POINTER r1,r2 |
|||
FOR i=0 TO count-2 |
|||
DO |
|||
minpos=i |
|||
FOR j=i+1 TO count-1 |
|||
DO |
|||
r1=GetItemAddr(data,minpos) |
|||
r2=GetItemAddr(data,j) |
|||
IF Compare(r1,r2)>0 THEN |
|||
minpos=j |
|||
FI |
|||
OD |
|||
IF minpos#i THEN |
|||
r1=GetItemAddr(data,minpos) |
|||
r2=GetItemAddr(data,i) |
|||
Swap(r1,r2) |
|||
FI |
|||
OD |
|||
RETURN |
|||
PROC Consolidate(PTR data INT POINTER count) |
|||
INT i,j,newCount |
|||
Range POINTER r1,r2 |
|||
FOR i=0 TO count^-1 |
|||
DO |
|||
r1=GetItemAddr(data,i) |
|||
Normalize(r1) |
|||
OD |
|||
Sort(data,count^) |
|||
newCount=0 i=0 |
|||
WHILE i<count^ |
|||
DO |
|||
j=i+1 |
|||
WHILE j<count^ |
|||
DO |
|||
r1=GetItemAddr(data,i) |
|||
r2=GetItemAddr(data,j) |
|||
IF RealLess(r1 HIGH_,r2 LOW_) THEN |
|||
EXIT |
|||
ELSEIF RealLess(r1 HIGH_,r2 HIGH_) THEN |
|||
RealAssign(r2 HIGH_,r1 HIGH_) |
|||
FI |
|||
j==+1 |
|||
OD |
|||
r1=GetItemAddr(data,i) |
|||
r2=GetItemAddr(data,newCount) |
|||
RealAssign(r1 LOW_,r2 LOW_) |
|||
RealAssign(r1 HIGH_,r2 HIGH_) |
|||
newCount==+1 |
|||
i=j |
|||
OD |
|||
count^=newCount |
|||
RETURN |
|||
PROC PrintRanges(PTR data INT count) |
|||
INT i |
|||
Range POINTER r |
|||
FOR i=0 TO count-1 |
|||
DO |
|||
IF i>0 THEN Put(' ) FI |
|||
r=GetItemAddr(data,i) |
|||
Put('[) PrintR(r LOW_) |
|||
Put(',) PrintR(r HIGH_) Put(']) |
|||
OD |
|||
RETURN |
|||
PROC Append(PTR data INT POINTER count |
|||
CHAR ARRAY sLow,sHigh) |
|||
Range POINTER r |
|||
r=GetItemAddr(data,count^) |
|||
ValR(sLow,r LOW_) |
|||
ValR(sHigh,r High_) |
|||
count^=count^+1 |
|||
RETURN |
|||
INT FUNC InitData(BYTE case PTR data) |
|||
INT count |
|||
count=0 |
|||
IF case=0 THEN |
|||
Append(data,@count,"1.1","2.2") |
|||
ELSEIF case=1 THEN |
|||
Append(data,@count,"6.1","7.2") |
|||
Append(data,@count,"7.2","8.3") |
|||
ELSEIF case=2 THEN |
|||
Append(data,@count,"4","3") |
|||
Append(data,@count,"2","1") |
|||
ELSEIF case=3 THEN |
|||
Append(data,@count,"4","3") |
|||
Append(data,@count,"2","1") |
|||
Append(data,@count,"-1","-2") |
|||
Append(data,@count,"3.9","10") |
|||
ELSEIF case=4 THEN |
|||
Append(data,@count,"1","3") |
|||
Append(data,@count,"-6","-1") |
|||
Append(data,@count,"-4","-5") |
|||
Append(data,@count,"8","2") |
|||
Append(data,@count,"-6","-6") |
|||
FI |
|||
RETURN (count) |
|||
PROC Main() |
|||
BYTE ARRAY data(100) |
|||
INT count |
|||
BYTE i |
|||
Put(125) PutE() ;clear the screen |
|||
FOR i=0 TO 4 |
|||
DO |
|||
count=InitData(i,data) |
|||
PrintRanges(data,count) |
|||
Print(" -> ") |
|||
Consolidate(data,@count) |
|||
PrintRanges(data,count) |
|||
PutE() PutE() |
|||
OD |
|||
RETURN</syntaxhighlight> |
|||
{{out}} |
|||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Range_consolidation.png Screenshot from Atari 8-bit computer] |
|||
<pre> |
|||
[1.1,2.2] -> [1.1,2.2] |
|||
[6.1,7.2] [7.2,8.3] -> [6.1,8.3] |
|||
[4,3] [2,1] -> [1,2] [3,4] |
|||
[4,3] [2,1] [-1,-2] [3.9,10] -> [-2,-1] [1,2] [3,10] |
|||
[1,3] [-6,-1] [-4,-5] [8,2] [-6,-6] -> [-6,-1] [1,8] |
|||
</pre> |
|||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
< |
<syntaxhighlight lang="ada">with Ada.Text_IO; |
||
with Ada.Containers.Vectors; |
with Ada.Containers.Vectors; |
||
Line 139: | Line 377: | ||
Show (Set_4); |
Show (Set_4); |
||
Show (Set_5); |
Show (Set_5); |
||
end Range_Consolidation;</ |
end Range_Consolidation;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 148: | Line 386: | ||
( 4.0 3.0) ( 2.0 1.0) ( -1.0 -2.0) ( 3.9 10.0) ( -2.0 -1.0) ( 1.0 2.0) ( 3.0 10.0) |
( 4.0 3.0) ( 2.0 1.0) ( -1.0 -2.0) ( 3.9 10.0) ( -2.0 -1.0) ( 1.0 2.0) ( 3.0 10.0) |
||
( 1.0 3.0) ( -6.0 -1.0) ( -4.0 -5.0) ( 8.0 2.0) ( -6.0 -6.0) ( -6.0 -1.0) ( 1.0 8.0) |
( 1.0 3.0) ( -6.0 -1.0) ( -4.0 -5.0) ( 8.0 2.0) ( -6.0 -6.0) ( -6.0 -1.0) ( 1.0 8.0) |
||
</pre> |
|||
=={{header|ALGOL 68}}== |
|||
<syntaxhighlight lang="algol68"> |
|||
BEGIN # range consolidation # |
|||
MODE RANGE = STRUCT( REAL lb, ub ); |
|||
# returns a with the bounds swapped if necessary, so lb OF a <= ub OF a # |
|||
OP NORMALISE = ( RANGE a )RANGE: |
|||
( IF lb OF a < ub OF a THEN lb OF a ELSE ub OF a FI |
|||
, IF ub OF a > lb OF a THEN ub OF a ELSE lb OF a FI |
|||
) # NORMALISE # ; |
|||
# returns a with each element normalised # |
|||
OP NORMALISE = ( []RANGE a )[]RANGE: |
|||
BEGIN |
|||
[ LWB a : UPB a ]RANGE result; |
|||
FOR a pos FROM LWB a TO UPB a DO result[ a pos ] := NORMALISE a[ a pos ] OD; |
|||
result |
|||
END # NORMALISE # ; |
|||
OP < = ( RANGE a, b )BOOL: lb OF a < lb OF b; |
|||
OP > = ( RANGE a, b )BOOL: lb OF a > lb OF b; |
|||
# sorts a into order of each element's lb # |
|||
OP SORT = ( []RANGE a )[]RANGE: |
|||
BEGIN |
|||
# in-place quick sort an array of RANGEs from element lb # |
|||
# to element ub # |
|||
PROC quicksort = ( REF[]RANGE a, INT lb, ub )REF[]RANGE: |
|||
IF ub <= lb |
|||
THEN |
|||
# empty array or only 1 element # |
|||
a |
|||
ELSE |
|||
# more than one element, so must sort # |
|||
INT left := lb; |
|||
INT right := ub; |
|||
# choosing the middle element of the array as the pivot # |
|||
RANGE pivot := a[ left + ( ( right + 1 ) - left ) OVER 2 ]; |
|||
WHILE |
|||
WHILE IF left <= ub THEN a[ left ] < pivot ELSE FALSE FI DO left +:= 1 OD; |
|||
WHILE IF right >= lb THEN a[ right ] > pivot ELSE FALSE FI DO right -:= 1 OD; |
|||
left <= right |
|||
DO |
|||
RANGE t := a[ left ]; |
|||
a[ left ] := a[ right ]; |
|||
a[ right ] := t; |
|||
left +:= 1; |
|||
right -:= 1 |
|||
OD; |
|||
quicksort( a, lb, right ); |
|||
quicksort( a, left, ub ); |
|||
a |
|||
FI # quicksort # ; |
|||
quicksort( HEAP[ LWB a : UPB a ]RANGE := a, LWB a, UPB a ) |
|||
END # SORT # ; |
|||
# returns the consolidation of the ranges in a in # |
|||
OP CONSOLIDATE = ( []RANGE a in )[]RANGE: |
|||
IF UPB a in <= LWB a in |
|||
THEN a in # 0 or 1 range # |
|||
ELSE # multiple ranges # |
|||
[]RANGE a = SORT NORMALISE a in; |
|||
[ 1 : 2 * ( ( UPB a - LWB a ) + 1 ) ]RANGE result; |
|||
INT r max := 1; |
|||
result[ r max ] := a[ LWB a ]; |
|||
FOR a pos FROM LWB a + 1 TO UPB a DO |
|||
RANGE m = result[ r max ], n = a[ a pos ]; |
|||
IF ub OF m < lb OF n THEN |
|||
result[ r max +:= 1 ] := n # distinct ranges # |
|||
ELSE |
|||
result[ r max ] # overlapping ranges # |
|||
:= ( IF lb OF m < lb OF n THEN lb OF m ELSE lb OF n FI |
|||
, IF ub OF m > ub OF n THEN ub OF m ELSE ub OF n FI |
|||
) |
|||
FI |
|||
OD; |
|||
result[ : r max ] |
|||
FI # CONSOLIDATE # ; |
|||
OP FMT = ( REAL v )STRING: # prints v with at most 3 decimal places # |
|||
BEGIN |
|||
STRING result := fixed( ABS v, 0, 3 ); |
|||
IF result[ LWB result ] = "." THEN "0" +=: result FI; |
|||
WHILE result[ UPB result ] = "0" DO result := result[ : UPB result - 1 ] OD; |
|||
IF result[ UPB result ] = "." THEN result := result[ : UPB result - 1 ] FI; |
|||
IF v < 0 THEN "-" ELSE "" FI + result |
|||
END # FMT # ; |
|||
OP TOSTRING = ( RANGE a )STRING: "[ " + FMT lb OF a + ", " + FMT ub OF a + " ]"; |
|||
OP TOSTRING = ( []RANGE a )STRING: |
|||
BEGIN |
|||
STRING result := "["; |
|||
STRING prefix := " "; |
|||
FOR r pos FROM LWB a TO UPB a DO |
|||
result +:= prefix + TOSTRING a[ r pos ]; |
|||
prefix := ", " |
|||
OD; |
|||
result + " ]" |
|||
END # TOSTRING # ; |
|||
PRIO PAD = 8; # right pads s with blanks to w characters # |
|||
OP PAD = ( STRING s, INT w )STRING: |
|||
IF INT len = ( UPB s - LWB s ) + 1; |
|||
len >= w |
|||
THEN s |
|||
ELSE s + ( ( w - len ) * " " ) |
|||
FI # PAD # ; |
|||
# task test cases # |
|||
PROC test = ( []RANGE a )VOID: |
|||
BEGIN print( ( ( TOSTRING a PAD 60 ), " -> ", TOSTRING CONSOLIDATE a, newline ) ) END; |
|||
test( []RANGE( RANGE( 1.1, 2.2 ) ) ); |
|||
test( ( ( 6.1, 7.2 ), ( 7.2, 8.3 ) ) ); |
|||
test( ( ( 4, 3 ), ( 2, 1 ) ) ); |
|||
test( ( ( 4, 3 ), ( 2, 1 ), ( -1, -2 ), ( 3.9, 10 ) ) ); |
|||
test( ( ( 1, 3 ), ( -6, -1 ), ( -4, -5 ), ( 8, 2 ), ( -6, -6 ) ) ) |
|||
END |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[ [ 1.1, 2.2 ] ] -> [ [ 1.1, 2.2 ] ] |
|||
[ [ 6.1, 7.2 ], [ 7.2, 8.3 ] ] -> [ [ 6.1, 8.3 ] ] |
|||
[ [ 4, 3 ], [ 2, 1 ] ] -> [ [ 1, 2 ], [ 3, 4 ] ] |
|||
[ [ 4, 3 ], [ 2, 1 ], [ -1, -2 ], [ 3.9, 10 ] ] -> [ [ -2, -1 ], [ 1, 2 ], [ 3, 10 ] ] |
|||
[ [ 1, 3 ], [ -6, -1 ], [ -4, -5 ], [ 8, 2 ], [ -6, -6 ] ] -> [ [ -6, -1 ], [ 1, 8 ] ] |
|||
</pre> |
|||
=={{header|AutoHotkey}}== |
|||
<syntaxhighlight lang="autohotkey">RangeConsolidation(arr){ |
|||
arr1 := [], arr2 := [], result := [] |
|||
for i, obj in arr |
|||
arr1[i,1] := min(arr[i]*), arr1[i,2] := max(arr[i]*) ; sort each range individually |
|||
for i, obj in arr1 |
|||
if (obj.2 > arr2[obj.1]) |
|||
arr2[obj.1] := obj.2 ; creates helper array sorted by range |
|||
i := 1 |
|||
for start, stop in arr2 |
|||
if (i = 1) || (start > result[i-1, 2]) ; first or non overlapping range |
|||
result[i, 1] := start, result[i, 2] := stop, i++ |
|||
else ; overlapping range |
|||
result[i-1, 2] := stop > result[i-1, 2] ? stop : result[i-1, 2] |
|||
return result |
|||
}</syntaxhighlight> |
|||
Examples:<syntaxhighlight lang="autohotkey">test1 := [[1.1, 2.2]] |
|||
test2 := [[6.1, 7.2], [7.2, 8.3]] |
|||
test3 := [[4, 3], [2, 1]] |
|||
test4 := [[4, 3], [2, 1], [-1, -2], [3.9, 10]] |
|||
test5 := [[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6]] |
|||
result := "" |
|||
loop, 5 |
|||
{ |
|||
output := "" |
|||
for i, obj in RangeConsolidation(test%A_Index%) |
|||
output .= "[" format("{:g}", obj.1) ", " format("{:g}", obj.2) "], " |
|||
result .= Trim(output, ", ") "`n" |
|||
} |
|||
MsgBox % result |
|||
return</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[1.1, 2.2] |
|||
[6.1, 8.3] |
|||
[1, 2], [3, 4] |
|||
[-2, -1], [1, 2], [3, 10] |
|||
[-6, -1], [1, 8]</pre> |
|||
=={{header|C}}== |
|||
<syntaxhighlight lang="c">#include <stdio.h> |
|||
#include <stdlib.h> |
|||
typedef struct range_tag { |
|||
double low; |
|||
double high; |
|||
} range_t; |
|||
void normalize_range(range_t* range) { |
|||
if (range->high < range->low) { |
|||
double tmp = range->low; |
|||
range->low = range->high; |
|||
range->high = tmp; |
|||
} |
|||
} |
|||
int range_compare(const void* p1, const void* p2) { |
|||
const range_t* r1 = p1; |
|||
const range_t* r2 = p2; |
|||
if (r1->low < r2->low) |
|||
return -1; |
|||
if (r1->low > r2->low) |
|||
return 1; |
|||
if (r1->high < r2->high) |
|||
return -1; |
|||
if (r1->high > r2->high) |
|||
return 1; |
|||
return 0; |
|||
} |
|||
void normalize_ranges(range_t* ranges, size_t count) { |
|||
for (size_t i = 0; i < count; ++i) |
|||
normalize_range(&ranges[i]); |
|||
qsort(ranges, count, sizeof(range_t), range_compare); |
|||
} |
|||
// Consolidates an array of ranges in-place. Returns the |
|||
// number of ranges after consolidation. |
|||
size_t consolidate_ranges(range_t* ranges, size_t count) { |
|||
normalize_ranges(ranges, count); |
|||
size_t out_index = 0; |
|||
for (size_t i = 0; i < count; ) { |
|||
size_t j = i; |
|||
while (++j < count && ranges[j].low <= ranges[i].high) { |
|||
if (ranges[i].high < ranges[j].high) |
|||
ranges[i].high = ranges[j].high; |
|||
} |
|||
ranges[out_index++] = ranges[i]; |
|||
i = j; |
|||
} |
|||
return out_index; |
|||
} |
|||
void print_range(const range_t* range) { |
|||
printf("[%g, %g]", range->low, range->high); |
|||
} |
|||
void print_ranges(const range_t* ranges, size_t count) { |
|||
if (count == 0) |
|||
return; |
|||
print_range(&ranges[0]); |
|||
for (size_t i = 1; i < count; ++i) { |
|||
printf(", "); |
|||
print_range(&ranges[i]); |
|||
} |
|||
} |
|||
void test_consolidate_ranges(range_t* ranges, size_t count) { |
|||
print_ranges(ranges, count); |
|||
printf(" -> "); |
|||
count = consolidate_ranges(ranges, count); |
|||
print_ranges(ranges, count); |
|||
printf("\n"); |
|||
} |
|||
#define LENGTHOF(a) sizeof(a)/sizeof(a[0]) |
|||
int main() { |
|||
range_t test1[] = { {1.1, 2.2} }; |
|||
range_t test2[] = { {6.1, 7.2}, {7.2, 8.3} }; |
|||
range_t test3[] = { {4, 3}, {2, 1} }; |
|||
range_t test4[] = { {4, 3}, {2, 1}, {-1, -2}, {3.9, 10} }; |
|||
range_t test5[] = { {1, 3}, {-6, -1}, {-4, -5}, {8, 2}, {-6, -6} }; |
|||
test_consolidate_ranges(test1, LENGTHOF(test1)); |
|||
test_consolidate_ranges(test2, LENGTHOF(test2)); |
|||
test_consolidate_ranges(test3, LENGTHOF(test3)); |
|||
test_consolidate_ranges(test4, LENGTHOF(test4)); |
|||
test_consolidate_ranges(test5, LENGTHOF(test5)); |
|||
return 0; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[1.1, 2.2] -> [1.1, 2.2] |
|||
[6.1, 7.2], [7.2, 8.3] -> [6.1, 8.3] |
|||
[4, 3], [2, 1] -> [1, 2], [3, 4] |
|||
[4, 3], [2, 1], [-1, -2], [3.9, 10] -> [-2, -1], [1, 2], [3, 10] |
|||
[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6] -> [-6, -1], [1, 8] |
|||
</pre> |
</pre> |
||
=={{header|C sharp}}== |
=={{header|C sharp}}== |
||
{{works with|C sharp|7}} |
{{works with|C sharp|7}} |
||
< |
<syntaxhighlight lang="csharp">using static System.Math; |
||
using System.Linq; |
using System.Linq; |
||
using System; |
using System; |
||
Line 190: | Line 698: | ||
private static (double s, double e) Normalize((double s, double e) range) => |
private static (double s, double e) Normalize((double s, double e) range) => |
||
(Min(range.s, range.e), Max(range.s, range.e)); |
(Min(range.s, range.e), Max(range.s, range.e)); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 199: | Line 707: | ||
(-6, -1), (1, 8)</pre> |
(-6, -1), (1, 8)</pre> |
||
=={{header| |
=={{header|C++}}== |
||
<syntaxhighlight lang="cpp">#include <algorithm> |
|||
#include <iostream> |
|||
#include <utility> |
|||
#include <vector> |
|||
// A range is represented as std::pair<from, to> |
|||
{{trans|C#}} |
|||
template <typename iterator> |
|||
<lang dyalect>func max(x, y) { |
|||
void normalize_ranges(iterator begin, iterator end) { |
|||
if x > y { |
|||
for (iterator i = begin; i != end; ++i) { |
|||
x |
|||
if (i->second < i->first) |
|||
} else { |
|||
std::swap(i->first, i->second); |
|||
y |
|||
} |
} |
||
std::sort(begin, end); |
|||
} |
} |
||
// Merges a range of ranges in-place. Returns an iterator to the |
|||
func min(x, y) { |
|||
// end of the resulting range, similarly to std::remove. |
|||
if x < y { |
|||
template <typename iterator> |
|||
x |
|||
iterator merge_ranges(iterator begin, iterator end) { |
|||
} else { |
|||
iterator out = begin; |
|||
for (iterator i = begin; i != end; ) { |
|||
iterator j = i; |
|||
while (++j != end && j->first <= i->second) |
|||
i->second = std::max(i->second, j->second); |
|||
*out++ = *i; |
|||
i = j; |
|||
} |
} |
||
return out; |
|||
} |
} |
||
template <typename iterator> |
|||
func overlap(left, right) { |
|||
iterator consolidate_ranges(iterator begin, iterator end) { |
|||
if max(left.s, left.e) > max(right.s, right.e) { |
|||
normalize_ranges(begin, end); |
|||
max(right.s, right.e) >= min(left.s, left.e) |
|||
return merge_ranges(begin, end); |
|||
} else { |
|||
max(left.s, left.e) >= min(right.s, right.e) |
|||
} |
|||
} |
} |
||
template <typename pair> |
|||
func consolidate(left, right) { |
|||
void print_range(std::ostream& out, const pair& range) { |
|||
(s: min(min(left.s, left.e), min(right.s, right.e)), e: max(max(left.s, left.e), max(right.s, right.e))) |
|||
out << '[' << range.first << ", " << range.second << ']'; |
|||
} |
} |
||
template <typename iterator> |
|||
func normalize(range) { |
|||
void print_ranges(std::ostream& out, iterator begin, iterator end) { |
|||
(s: min(range.s, range.e), e: max(range.s, range.e)) |
|||
if (begin != end) { |
|||
print_range(out, *begin++); |
|||
for (; begin != end; ++begin) { |
|||
out << ", "; |
|||
print_range(out, *begin); |
|||
} |
|||
} |
|||
} |
} |
||
int main() { |
|||
for list in [ |
|||
std::vector<std::pair<double, double>> test_cases[] = { |
|||
[ (s: 1.1, e: 2.2) ], |
|||
{ {1.1, 2.2} }, |
|||
{ {6.1, 7.2}, {7.2, 8.3} }, |
|||
{ {4, 3}, {2, 1} }, |
|||
{ {4, 3}, {2, 1}, {-1, -2}, {3.9, 10} }, |
|||
{ {1, 3}, {-6, -1}, {-4, -5}, {8, 2}, {-6, -6} } |
|||
] { |
|||
}; |
|||
var z = list.len()-1 |
|||
for (auto&& ranges : test_cases) { |
|||
print_ranges(std::cout, std::begin(ranges), std::end(ranges)); |
|||
std::cout << " -> "; |
|||
auto i = consolidate_ranges(std::begin(ranges), std::end(ranges)); |
|||
print_ranges(std::cout, std::begin(ranges), i); |
|||
std::cout << '\n'; |
|||
} |
|||
return 0; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[1.1, 2.2] -> [1.1, 2.2] |
|||
[6.1, 7.2], [7.2, 8.3] -> [6.1, 8.3] |
|||
[4, 3], [2, 1] -> [1, 2], [3, 4] |
|||
[4, 3], [2, 1], [-1, -2], [3.9, 10] -> [-2, -1], [1, 2], [3, 10] |
|||
[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6] -> [-6, -1], [1, 8] |
|||
</pre> |
|||
=={{header|Clojure}}== |
|||
<syntaxhighlight lang="clojure">(defn normalize [r] |
|||
(let [[n1 n2] r] |
|||
[(min n1 n2) (max n1 n2)])) |
|||
(defn touch? [r1 r2] |
|||
(let [[lo1 hi1] (normalize r1) |
|||
[lo2 hi2] (normalize r2)] |
|||
(or (<= lo2 lo1 hi2) |
|||
(<= lo2 hi1 hi2)))) |
|||
(defn consolidate-touching-ranges [rs] |
|||
(let [lows (map #(apply min %) rs) |
|||
highs (map #(apply max %) rs)] |
|||
[ (apply min lows) (apply max highs) ])) |
|||
(defn consolidate-ranges [rs] |
|||
(loop [res [] |
|||
rs rs] |
|||
(if (empty? rs) |
|||
res |
|||
(let [r0 (first rs) |
|||
touching (filter #(touch? r0 %) rs) |
|||
remove-used (fn [rs used] |
|||
(remove #(contains? (set used) %) rs))] |
|||
(recur (conj res (consolidate-touching-ranges touching)) |
|||
(remove-used (rest rs) touching))))))</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
(def test-data [ [[1.1 2.2]] |
|||
[[6.1 7.2] [7.2 8.3]] |
|||
[[4 3] [2 1]] |
|||
[[4 3] [2 1] [-1 -2] [3.9 10]] |
|||
[[1 3] [-6 -1] [-4 -5] [8 2] [-6 -6]] ]) |
|||
(map consolidate-ranges test-data) |
|||
;; ==> ([[1.1 2.2]] |
|||
[[6.1 8.3]] |
|||
[[3 4] [1 2]] |
|||
[[3 10] [1 2] [-2 -1]] |
|||
[[1 8] [-6 -1] [-5 -4]])) |
|||
</pre> |
|||
=={{header|Dyalect}}== |
|||
{{trans|C#}} |
|||
<syntaxhighlight lang="dyalect">type Pt(s, e) with Lookup |
|||
func Pt.Min() => min(this.s, this.e) |
|||
func Pt.Max() => max(this.s, this.e) |
|||
func Pt.ToString() => "(\(this.s), \(this.e))" |
|||
let rng = [ |
|||
[ Pt(1.1, 2.2) ], |
|||
[ Pt(6.1, 7.2), Pt(7.2, 8.3) ], |
|||
[ Pt(4.0, 3.0), Pt(2, 1) ], |
|||
[ Pt(4.0, 3.0), Pt(2, 1), Pt(-1, 2), Pt(3.9, 10) ], |
|||
[ Pt(1.0, 3.0), Pt(-6, -1), Pt(-4, -5), Pt(8, 2), Pt(-6, -6) ] |
|||
] |
|||
func overlap(left, right) => |
|||
left.Max() > right.Max() ? right.Max() >= left.Min() |
|||
: left.Max() >= right.Min() |
|||
func consolidate(left, right) => Pt(min(left.Min(), right.Min()), max(left.Max(), right.Max())) |
|||
func normalize(range) => Pt(range.Min(), range.Max()) |
|||
for list in rng { |
|||
var z = list.Length() - 1 |
|||
while z >= 1 { |
while z >= 1 { |
||
for y in (z - 1)..0 { |
for y in (z - 1)^-1..0 when overlap(list[z], list[y]) { |
||
list[y] = consolidate(list[z], list[y]) |
|||
break list.RemoveAt(z) |
|||
list.removeAt(z) |
|||
break |
|||
} |
|||
} |
} |
||
z -= 1 |
z -= 1 |
||
} |
} |
||
for i in list.indices() { |
|||
for i in list.Indices() { |
|||
list[i] = normalize(list[i]) |
list[i] = normalize(list[i]) |
||
} |
} |
||
list.sort((x,y) => x.s - y.s) |
|||
list.Sort((x,y) => x.s - y.s) |
|||
print(list) |
print(list) |
||
}</syntaxhighlight> |
|||
} |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>[( |
<pre>[(1.1, 2.2)] |
||
[( |
[(6.1, 8.3)] |
||
[( |
[(1, 2), (3, 4)] |
||
[( |
[(-1, 2), (3, 10)] |
||
[( |
[(-6, -1), (1, 8)]</pre> |
||
=={{header|EasyLang}}== |
|||
<syntaxhighlight lang=text> |
|||
proc sort . d[][] . |
|||
n = len d[][] |
|||
for i = 1 to n - 1 |
|||
for j = i + 1 to n |
|||
if d[j][1] < d[i][1] |
|||
swap d[j][] d[i][] |
|||
. |
|||
. |
|||
. |
|||
. |
|||
func[][] consolidate a[][] . |
|||
for i to len a[][] |
|||
if a[i][1] > a[i][2] |
|||
swap a[i][1] a[i][2] |
|||
. |
|||
. |
|||
sort a[][] |
|||
r[][] &= a[1][] |
|||
b = a[1][2] |
|||
for i = 2 to len a[][] |
|||
if a[i][1] > b |
|||
r[$][2] = b |
|||
r[][] &= a[i][] |
|||
b = a[i][2] |
|||
else |
|||
b = higher b a[i][2] |
|||
. |
|||
. |
|||
r[$][2] = b |
|||
return r[][] |
|||
. |
|||
print consolidate [ [ 1.1 2.2 ] ] |
|||
print consolidate [ [ 6.1 7.2 ] [ 7.2 8.3 ] ] |
|||
print consolidate [ [ 4 3 ] [ 2 1 ] ] |
|||
print consolidate [ [ 4 3 ] [ 2 1 ] [ -1 -2 ] [ 3.9 10 ] ] |
|||
print consolidate [ [ 1 3 ] [ -6 -1 ] [ -4 -5 ] [ 8 2 ] [ -6 -6 ] ] |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[ |
|||
[ 1.10 2.20 ] |
|||
] |
|||
[ |
|||
[ 6.10 8.30 ] |
|||
] |
|||
[ |
|||
[ 1 2 ] |
|||
[ 3 4 ] |
|||
] |
|||
[ |
|||
[ -2 -1 ] |
|||
[ 1 2 ] |
|||
[ 3 10 ] |
|||
] |
|||
[ |
|||
[ -6 -1 ] |
|||
[ 1 8 ] |
|||
] |
|||
</pre> |
|||
=={{header|Factor}}== |
|||
{{works with|Factor|0.99 2021-06-02}} |
|||
<syntaxhighlight lang="factor">USING: arrays combinators formatting kernel math.combinatorics |
|||
math.order math.statistics sequences sets sorting ; |
|||
: overlaps? ( pair pair -- ? ) |
|||
2dup swap [ [ first2 between? ] curry any? ] 2bi@ or ; |
|||
: merge ( seq -- newseq ) concat minmax 2array 1array ; |
|||
: merge1 ( seq -- newseq ) |
|||
dup 2 [ first2 overlaps? ] find-combination |
|||
[ [ without ] keep merge append ] when* ; |
|||
: normalize ( seq -- newseq ) [ natural-sort ] map ; |
|||
: consolidate ( seq -- newseq ) |
|||
normalize [ merge1 ] to-fixed-point natural-sort ; |
|||
{ |
|||
{ { 1.1 2.2 } } |
|||
{ { 6.1 7.2 } { 7.2 8.3 } } |
|||
{ { 4 3 } { 2 1 } } |
|||
{ { 4 3 } { 2 1 } { -1 -2 } { 3.9 10 } } |
|||
{ { 1 3 } { -6 -1 } { -4 -5 } { 8 2 } { -6 -6 } } |
|||
} [ dup consolidate "%49u => %u\n" printf ] each</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
{ { 1.1 2.2 } } => { { 1.1 2.2 } } |
|||
{ { 6.1 7.2 } { 7.2 8.300000000000001 } } => { { 6.1 8.300000000000001 } } |
|||
{ { 4 3 } { 2 1 } } => { { 1 2 } { 3 4 } } |
|||
{ { 4 3 } { 2 1 } { -1 -2 } { 3.9 10 } } => { { -2 -1 } { 1 2 } { 3 10 } } |
|||
{ { 1 3 } { -6 -1 } { -4 -5 } { 8 2 } { -6 -6 } } => { { -6 -1 } { 1 8 } } |
|||
</pre> |
|||
=={{header|FreeBASIC}}== |
|||
{{trans|Yabasic}} |
|||
<syntaxhighlight lang="freebasic"> |
|||
Dim Shared As Integer i |
|||
Dim Shared As Single items, temp = 10^30 |
|||
Sub ordenar(tabla() As Single) |
|||
Dim As Integer t1, t2 |
|||
Dim As Boolean s |
|||
Do |
|||
s = True |
|||
For i = 1 To Ubound(tabla)-1 |
|||
If tabla(i, 1) > tabla(i+1, 1) Then |
|||
t1 = tabla(i, 1) : t2 = tabla(i, 2) |
|||
tabla(i, 1) = tabla(i + 1, 1) : tabla(i, 2) = tabla(i + 1, 2) |
|||
tabla(i + 1, 1) = t1 : tabla(i + 1, 2) = t2 |
|||
s = False |
|||
End If |
|||
Next i |
|||
Loop Until(s) |
|||
End Sub |
|||
Sub normalizar(tabla() As Single) |
|||
Dim As Integer t |
|||
For i = 1 To Ubound(tabla) |
|||
If tabla(i, 1) > tabla(i, 2) Then |
|||
t = tabla(i, 1) |
|||
tabla(i, 1) = tabla(i, 2) |
|||
tabla(i, 2) = t |
|||
End If |
|||
Next i |
|||
ordenar(tabla()) |
|||
End Sub |
|||
Sub consolidar(tabla() As Single) |
|||
normalizar(tabla()) |
|||
For i = 1 To Ubound(tabla)-1 |
|||
If tabla(i + 1, 1) <= tabla(i, 2) Then |
|||
tabla(i + 1, 1) = tabla(i, 1) |
|||
If tabla(i + 1, 2) <= tabla(i, 2) Then |
|||
tabla(i + 1, 2) = tabla(i, 2) |
|||
End If |
|||
tabla(i, 1) = temp : tabla(i, 2) = temp |
|||
End If |
|||
Next i |
|||
End Sub |
|||
Data 1, 1.1, 2.2 |
|||
Data 2, 6.1, 7.2, 7.2, 8.3 |
|||
Data 2, 4, 3, 2, 1 |
|||
Data 4, 4, 3, 2, 1, -1, -2, 3.9, 10 |
|||
Data 5, 1,3, -6,-1, -4,-5, 8,2, -6,-6 |
|||
For j As Byte = 1 To 5 |
|||
Read items |
|||
Dim As Single tabla(items, 2) |
|||
For i = 1 To items |
|||
Read tabla(i, 1), tabla(i, 2) |
|||
Next i |
|||
consolidar(tabla()) |
|||
For i = 1 To items |
|||
If tabla(i, 1) <> temp Then Print "[";tabla(i, 1); ", "; tabla(i, 2); "] "; |
|||
Next i |
|||
Print |
|||
Next j |
|||
Sleep |
|||
</syntaxhighlight> |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 344: | Line 1,135: | ||
fmt.Println(s[1 : len(s)-1]) |
fmt.Println(s[1 : len(s)-1]) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 356: | Line 1,147: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">import Data.List (intercalate, maximumBy, sort) |
||
import Data.Ord (comparing) |
import Data.Ord (comparing) |
||
------------------- RANGE CONSOLIDATION ------------------ |
|||
consolidated :: [(Float, Float)] -> [(Float, Float)] |
consolidated :: [(Float, Float)] -> [(Float, Float)] |
||
consolidated |
consolidated = foldr go [] . sort . fmap ab |
||
where |
|||
let go xy [] = [xy] |
|||
go xy [] = [xy] |
|||
go xy@(x, y) abetc@((a, b) : etc) |
|||
| y >= b = xy : etc |
|||
| y >= a = (x, b) : etc |
|||
| otherwise = xy : abetc |
|||
ab (a, b) |
|||
| a <= b = (a, b) |
|||
| otherwise = (b, a) |
|||
- |
--------------------------- TEST ------------------------- |
||
tests :: [[(Float, Float)]] |
tests :: [[(Float, Float)]] |
||
tests = |
tests = |
||
[ [] |
[ [], |
||
[(1.1, 2.2)], |
|||
[(6.1, 7.2), (7.2, 8.3)], |
|||
[(4, 3), (2, 1)], |
|||
[(4, 3), (2, 1), (-1, -2), (3.9, 10)], |
|||
[(1, 3), (-6, -1), (-4, -5), (8, 2), (-6, -6)] |
|||
] |
] |
||
Line 386: | Line 1,179: | ||
main = |
main = |
||
putStrLn $ |
putStrLn $ |
||
tabulated |
|||
tabulated "Range consolidations:" showPairs showPairs consolidated tests |
|||
"Range consolidations:" |
|||
showPairs |
|||
showPairs |
|||
consolidated |
|||
tests |
|||
-------------------- DISPLAY FORMATTING ------------------ |
|||
tabulated :: |
|||
-- DISPLAY FORMATTING ------------------------------------- |
|||
String -> |
|||
(a -> String) -> |
|||
(b -> String) -> |
|||
(a -> b) -> |
|||
[a] -> |
|||
String |
|||
tabulated s xShow fxShow f xs = |
tabulated s xShow fxShow f xs = |
||
let w = |
|||
let w = length $ maximumBy (comparing length) (xShow <$> xs) |
|||
length $ |
|||
maximumBy |
|||
in unlines $ |
|||
(comparing length) |
|||
s : fmap (((++) . rjust w ' ' . xShow) <*> ((" -> " ++) . fxShow . f)) xs |
|||
(xShow <$> xs) |
|||
rjust n c s = drop (length s) (replicate n c <> s) |
|||
in unlines $ |
|||
s : |
|||
fmap |
|||
( ((<>) . rjust w ' ' . xShow) |
|||
<*> ((" -> " <>) . fxShow . f) |
|||
) |
|||
xs |
|||
showPairs :: [(Float, Float)] -> String |
showPairs :: [(Float, Float)] -> String |
||
showPairs xs |
showPairs xs |
||
| null xs = "[]" |
| null xs = "[]" |
||
| otherwise = |
| otherwise = |
||
'[' : |
|||
intercalate |
|||
", " |
|||
(showPair <$> xs) |
|||
<> "]" |
|||
showPair :: (Float, Float) -> String |
showPair :: (Float, Float) -> String |
||
showPair (a, b) = |
showPair (a, b) = |
||
'(' : |
|||
showNum a |
|||
<> ", " |
|||
<> showNum b |
|||
<> ")" |
|||
showNum :: Float -> String |
showNum :: Float -> String |
||
showNum n |
showNum n |
||
| 0 == (n - fromIntegral (round n)) = show (round n) |
| 0 == (n - fromIntegral (round n)) = show (round n) |
||
| otherwise = show n</ |
| otherwise = show n</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>Range consolidations: |
<pre>Range consolidations: |
||
Line 421: | Line 1,243: | ||
=={{header|J}}== |
=={{header|J}}== |
||
'''Solution:''' |
'''Solution:''' |
||
< |
<syntaxhighlight lang="j">ensure2D=: ,:^:(1 = #@$) NB. if list make 1 row table |
||
normalise=: ([: /:~ /:~"1)@ensure2D NB. normalises list of ranges |
normalise=: ([: /:~ /:~"1)@ensure2D NB. normalises list of ranges |
||
merge=: ,:`(<.&{. , >.&{:)@.(>:/&{: |.) NB. merge ranges x and y |
merge=: ,:`(<.&{. , >.&{:)@.(>:/&{: |.) NB. merge ranges x and y |
||
consolidate=: (}.@] ,~ (merge {.)) ensure2D</ |
consolidate=: (}.@] ,~ (merge {.)) ensure2D</syntaxhighlight> |
||
'''Required Examples:''' |
'''Required Examples:''' |
||
< |
<syntaxhighlight lang="j"> tests=: <@".;._2 noun define |
||
1.1 2.2 |
1.1 2.2 |
||
6.1 7.2 ,: 7.2 8.3 |
6.1 7.2 ,: 7.2 8.3 |
||
Line 439: | Line 1,261: | ||
| | |3 4| 1 2| 1 8| |
| | |3 4| 1 2| 1 8| |
||
| | | | 3 10| | |
| | | | 3 10| | |
||
+-------+-------+---+-----+-----+</ |
+-------+-------+---+-----+-----+</syntaxhighlight> |
||
=={{header|Java}}== |
|||
<syntaxhighlight lang="java"> |
|||
import java.util.ArrayList; |
|||
import java.util.Arrays; |
|||
import java.util.Collections; |
|||
import java.util.Comparator; |
|||
import java.util.List; |
|||
public class RangeConsolidation { |
|||
public static void main(String[] args) { |
|||
displayRanges( Arrays.asList(new Range(1.1, 2.2))); |
|||
displayRanges( Arrays.asList(new Range(6.1, 7.2), new Range(7.2, 8.3))); |
|||
displayRanges( Arrays.asList(new Range(4, 3), new Range(2, 1))); |
|||
displayRanges( Arrays.asList(new Range(4, 3), new Range(2, 1), new Range(-1, -2), new Range(3.9, 10))); |
|||
displayRanges( Arrays.asList(new Range(1, 3), new Range(-6, -1), new Range(-4, -5), new Range(8, 2), new Range(-6, -6))); |
|||
displayRanges( Arrays.asList(new Range(1, 1), new Range(1, 1))); |
|||
displayRanges( Arrays.asList(new Range(1, 1), new Range(1, 2))); |
|||
displayRanges( Arrays.asList(new Range(1, 2), new Range(3, 4), new Range(1.5, 3.5), new Range(1.2, 2.5))); |
|||
} |
|||
private static final void displayRanges(List<Range> ranges) { |
|||
System.out.printf("ranges = %-70s, colsolidated = %s%n", ranges, Range.consolidate(ranges)); |
|||
} |
|||
private static final class RangeSorter implements Comparator<Range> { |
|||
@Override |
|||
public int compare(Range o1, Range o2) { |
|||
return (int) (o1.left - o2.left); |
|||
} |
|||
} |
|||
private static class Range { |
|||
double left; |
|||
double right; |
|||
public Range(double left, double right) { |
|||
if ( left <= right ) { |
|||
this.left = left; |
|||
this.right = right; |
|||
} |
|||
else { |
|||
this.left = right; |
|||
this.right = left; |
|||
} |
|||
} |
|||
public Range consolidate(Range range) { |
|||
// no overlap |
|||
if ( this.right < range.left ) { |
|||
return null; |
|||
} |
|||
// no overlap |
|||
if ( range.right < this.left ) { |
|||
return null; |
|||
} |
|||
// contained |
|||
if ( this.left <= range.left && this.right >= range.right ) { |
|||
return this; |
|||
} |
|||
// contained |
|||
if ( range.left <= this.left && range.right >= this.right ) { |
|||
return range; |
|||
} |
|||
// overlap |
|||
if ( this.left <= range.left && this.right <= range.right ) { |
|||
return new Range(this.left, range.right); |
|||
} |
|||
// overlap |
|||
if ( this.left >= range.left && this.right >= range.right ) { |
|||
return new Range(range.left, this.right); |
|||
} |
|||
throw new RuntimeException("ERROR: Logic invalid."); |
|||
} |
|||
@Override |
|||
public String toString() { |
|||
return "[" + left + ", " + right + "]"; |
|||
} |
|||
private static List<Range> consolidate(List<Range> ranges) { |
|||
List<Range> consolidated = new ArrayList<>(); |
|||
Collections.sort(ranges, new RangeSorter()); |
|||
for ( Range inRange : ranges ) { |
|||
Range r = null; |
|||
Range conRange = null; |
|||
for ( Range conRangeLoop : consolidated ) { |
|||
r = inRange.consolidate(conRangeLoop); |
|||
if (r != null ) { |
|||
conRange = conRangeLoop; |
|||
break; |
|||
} |
|||
} |
|||
if ( r == null ) { |
|||
consolidated.add(inRange); |
|||
} |
|||
else { |
|||
consolidated.remove(conRange); |
|||
consolidated.add(r); |
|||
} |
|||
} |
|||
Collections.sort(consolidated, new RangeSorter()); |
|||
return consolidated; |
|||
} |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
Required and other examples. |
|||
<pre> |
|||
ranges = [[1.1, 2.2]] , consolidated = [[1.1, 2.2]] |
|||
ranges = [[6.1, 7.2], [7.2, 8.3]] , consolidated = [[6.1, 8.3]] |
|||
ranges = [[1.0, 2.0], [3.0, 4.0]] , consolidated = [[1.0, 2.0], [3.0, 4.0]] |
|||
ranges = [[-2.0, -1.0], [1.0, 2.0], [3.0, 4.0], [3.9, 10.0]] , consolidated = [[-2.0, -1.0], [1.0, 2.0], [3.0, 10.0]] |
|||
ranges = [[-6.0, -1.0], [-6.0, -6.0], [-5.0, -4.0], [1.0, 3.0], [2.0, 8.0]] , consolidated = [[-6.0, -1.0], [1.0, 8.0]] |
|||
ranges = [[1.0, 1.0], [1.0, 1.0]] , consolidated = [[1.0, 1.0]] |
|||
ranges = [[1.0, 1.0], [1.0, 2.0]] , consolidated = [[1.0, 2.0]] |
|||
ranges = [[1.0, 2.0], [1.5, 3.5], [1.2, 2.5], [3.0, 4.0]] , consolidated = [[1.0, 4.0]] |
|||
</pre> |
|||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
{{Trans|Haskell}} |
{{Trans|Haskell}} |
||
{{Trans|Python}} |
{{Trans|Python}} |
||
< |
<syntaxhighlight lang="javascript">(() => { |
||
'use strict'; |
'use strict'; |
||
Line 620: | Line 1,568: | ||
// MAIN --- |
// MAIN --- |
||
return main(); |
return main(); |
||
})();</ |
})();</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>Range consolidations: |
<pre>Range consolidations: |
||
Line 628: | Line 1,576: | ||
[[4,3],[2,1],[-1,-2],[3.9,10]] -> [[-2,-1],[1,2],[3,10]] |
[[4,3],[2,1],[-1,-2],[3.9,10]] -> [[-2,-1],[1,2],[3,10]] |
||
[[1,3],[-6,-1],[-4,-5],[8,2],[-6,-6]] -> [[-6,-1],[1,8]]</pre> |
[[1,3],[-6,-1],[-4,-5],[8,2],[-6,-6]] -> [[-6,-1],[1,8]]</pre> |
||
=={{header|jq}}== |
|||
{{trans|Julia}} |
|||
{{works with|jq}} |
|||
'''Works with gojq, the Go implementation of jq''' |
|||
<syntaxhighlight lang="jq">def normalize: map(sort) | sort; |
|||
def consolidate: |
|||
normalize |
|||
| length as $length |
|||
| reduce range(0; $length) as $i (.; |
|||
.[$i] as $r1 |
|||
| if $r1 != [] |
|||
then reduce range($i+1; $length) as $j (.; |
|||
.[$j] as $r2 |
|||
| if $r2 != [] and ($r1[-1] >= $r2[0]) # intersect? |
|||
then .[$i] = [$r1[0], ([$r1[-1], $r2[-1]]|max)] |
|||
| .[$j] = [] |
|||
else . |
|||
end ) |
|||
else . |
|||
end ) |
|||
| map(select(. != [])) ; |
|||
def testranges: |
|||
[[1.1, 2.2]], |
|||
[[6.1, 7.2], [7.2, 8.3]], |
|||
[[4, 3], [2, 1]], |
|||
[[4, 3], [2, 1], [-1, -2], [3.9, 10]], |
|||
[[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6]] |
|||
| "\(.) => \(consolidate)" |
|||
; |
|||
testranges</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[[1.1,2.2]] => [[1.1,2.2]] |
|||
[[6.1,7.2],[7.2,8.3]] => [[6.1,8.3]] |
|||
[[4,3],[2,1]] => [[1,2],[3,4]] |
|||
[[4,3],[2,1],[-1,-2],[3.9,10]] => [[-2,-1],[1,2],[3,10]] |
|||
[[1,3],[-6,-1],[-4,-5],[8,2],[-6,-6]] => [[-6,-1],[-5,-4],[1,8]] |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
Line 635: | Line 1,626: | ||
of the Python code is done, rather than using a native Julia Range. |
of the Python code is done, rather than using a native Julia Range. |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="julia">normalize(s) = sort([sort(bounds) for bounds in s]) |
||
function consolidate(ranges) |
function consolidate(ranges) |
||
Line 661: | Line 1,652: | ||
testranges() |
testranges() |
||
</ |
</syntaxhighlight>{{output}} |
||
<pre> |
<pre> |
||
Array{Float64,1}[[1.1, 2.2]] => Array{Float64,1}[[1.1, 2.2]] |
Array{Float64,1}[[1.1, 2.2]] => Array{Float64,1}[[1.1, 2.2]] |
||
Line 669: | Line 1,660: | ||
Array{Float64,1}[[1.0, 3.0], [-6.0, -1.0], [-4.0, -5.0], [8.0, 2.0], [-6.0, -6.0]] => Array{Float64,1}[[-6.0, -1.0], [1.0, 8.0]] |
Array{Float64,1}[[1.0, 3.0], [-6.0, -1.0], [-4.0, -5.0], [8.0, 2.0], [-6.0, -6.0]] => Array{Float64,1}[[-6.0, -1.0], [1.0, 8.0]] |
||
</pre> |
</pre> |
||
=={{header|Kotlin}}== |
|||
<syntaxhighlight lang="kotlin">fun <T> consolidate(ranges: Iterable<ClosedRange<T>>): List<ClosedRange<T>> where T : Comparable<T> |
|||
{ |
|||
return ranges |
|||
.sortedWith(compareBy({ it.start }, { it.endInclusive })) |
|||
.asReversed() |
|||
.fold(mutableListOf<ClosedRange<T>>()) { |
|||
consolidatedRanges, range -> |
|||
if (consolidatedRanges.isEmpty()) |
|||
{ |
|||
consolidatedRanges.add(range) |
|||
} |
|||
// Keep in mind the reverse-sorting applied above: |
|||
// If the end of the current-range is higher, than it must start at a lower value, |
|||
else if (range.endInclusive >= consolidatedRanges[0].endInclusive) |
|||
{ |
|||
consolidatedRanges[0] = range |
|||
} |
|||
else if (range.endInclusive >= consolidatedRanges[0].start) |
|||
{ |
|||
consolidatedRanges[0] = range.start .. consolidatedRanges[0].endInclusive |
|||
} |
|||
else |
|||
{ |
|||
consolidatedRanges.add(0, range) |
|||
} |
|||
return@fold consolidatedRanges |
|||
} |
|||
.toList() |
|||
} |
|||
// What a bummer! Kotlin's range syntax (a..b) doesn't meet the task requirements when b < b, |
|||
// and on the other hand, the syntax for constructing lists, arrays and pairs isn't close enough |
|||
// to the range notation. Instead then, here's a *very* naive parser. Don't take it seriously. |
|||
val rangeRegex = Regex("""\[(.+),(.+)\]""") |
|||
fun parseDoubleRange(rangeStr: String): ClosedFloatingPointRange<Double> { |
|||
val parts = rangeRegex |
|||
.matchEntire(rangeStr) |
|||
?.groupValues |
|||
?.drop(1) |
|||
?.map { it.toDouble() } |
|||
?.sorted() |
|||
if (parts == null) throw IllegalArgumentException("Unable to parse range $rangeStr") |
|||
return parts[0] .. parts[1] |
|||
} |
|||
fun serializeRange(range: ClosedRange<*>) = "[${range.start}, ${range.endInclusive}]" |
|||
// See above. In practice you'd probably use consolidate directly |
|||
fun consolidateDoubleRanges(rangeStrings: Iterable<String>): List<String> |
|||
{ |
|||
return consolidate(rangeStrings.asSequence().map(::parseDoubleRange).toList()).map(::serializeRange) |
|||
} |
|||
fun main() { |
|||
val inputRanges = listOf( |
|||
listOf("[1.1, 2.2]"), |
|||
listOf("[6.1, 7.2]", "[7.2, 8.3]"), |
|||
listOf("[4, 3]", "[2, 1]"), |
|||
listOf("[4, 3]", "[2, 1]", "[-1, -2]", "[3.9, 10]"), |
|||
listOf("[1, 3]", "[-6, -1]", "[-4, -5]", "[8, 2]", "[-6, -6]") |
|||
) |
|||
inputRanges.associateBy(Any::toString, ::consolidateDoubleRanges).forEach({ println("${it.key} => ${it.value}") }) |
|||
}</syntaxhighlight> |
|||
{{Out}} |
|||
<pre> |
|||
[[1.1, 2.2]] => [[1.1, 2.2]] |
|||
[[6.1, 7.2], [7.2, 8.3]] => [[6.1, 8.3]] |
|||
[[4, 3], [2, 1]] => [[1.0, 2.0], [3.0, 4.0]] |
|||
[[4, 3], [2, 1], [-1, -2], [3.9, 10]] => [[-2.0, -1.0], [1.0, 2.0], [3.0, 10.0]] |
|||
[[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6]] => [[-6.0, -1.0], [1.0, 8.0]] |
|||
</pre> |
|||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
|||
Using the Wolfram Language's built-in Interval operations: |
|||
<syntaxhighlight lang="mathematica">data={{{1.1,2.2}}, |
|||
{{6.1,7.2},{7.2,8.3}}, |
|||
{{4,3},{2,1}}, |
|||
{{4,3},{2,1},{-1,-2},{3.9,10}}, |
|||
{{1,3},{-6,-1},{-4,-5},{8,2},{-6,-6}}}; |
|||
Column[IntervalUnion@@@Map[Interval,data,{2}]]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Interval[{1.1,2.2}] |
|||
Interval[{6.1,8.3}] |
|||
Interval[{1,2},{3,4}] |
|||
Interval[{-2,-1},{1,2},{3,10}] |
|||
Interval[{-6,-1},{1,8}]</pre> |
|||
=={{header|newLISP}}== |
|||
<syntaxhighlight lang="newlisp"> |
|||
(define (norm range) (sort range)) |
|||
(define (overlap? a b) (>= (a 1) (b 0))) |
|||
(define (combine) |
|||
(list ($args 0 0) (max ($args 1 1) ($args 0 1)))) |
|||
(define (foo ranges) |
|||
(set 'ranges (map norm ranges)) |
|||
(set 'ranges (sort ranges)) |
|||
(let (accum '() item) |
|||
(dolist (r ranges) |
|||
(set 'item (cond ((empty? accum) r) |
|||
((overlap? (accum 0) r) |
|||
(combine (pop accum) r)) |
|||
(true r))) |
|||
(push item accum)) |
|||
(reverse accum))) |
|||
(foo '((1.1 2.2))) |
|||
((1.1 2.2)) |
|||
(foo '((6.1 7.2) (7.2 8.3))) |
|||
((6.1 8.300000000000001)) |
|||
(foo '((4 3) (2 1))) |
|||
((1 2) (3 4)) |
|||
(foo '((4 3) (2 1) (-1 -2) (3.9 10))) |
|||
((-2 -1) (1 2) (3 10)) |
|||
(foo '((1 3) (-6 -1) (-4 -5) (8 2) (-6 -6))) |
|||
((-6 -1) (1 8)) |
|||
</syntaxhighlight> |
|||
=={{header|Nim}}== |
|||
<syntaxhighlight lang="nim">import algorithm, strutils |
|||
# Definition of a range of values of type T. |
|||
type Range[T] = array[2, T] |
|||
proc `<`(a, b: Range): bool {.inline.} = |
|||
## Check if range "a" is less than range "b". Needed for sorting. |
|||
if a[0] == b[0]: |
|||
a[1] < b[1] |
|||
else: |
|||
a[0] < b[0] |
|||
proc consolidate[T](rangeList: varargs[Range[T]]): seq[Range[T]] = |
|||
## Consolidate a list of ranges of type T. |
|||
# Build a sorted list of normalized ranges. |
|||
var list: seq[Range[T]] |
|||
for item in rangeList: |
|||
list.add if item[0] <= item[1]: item else: [item[1], item[0]] |
|||
list.sort() |
|||
# Build the consolidated list starting from "smallest" range. |
|||
result.add list[0] |
|||
for i in 1..list.high: |
|||
let rangeMin = result[^1] |
|||
let rangeMax = list[i] |
|||
if rangeMax[0] <= rangeMin[1]: |
|||
result[^1] = [rangeMin[0], max(rangeMin[1], rangeMax[1])] |
|||
else: |
|||
result.add rangeMax |
|||
proc `$`[T](r: Range[T]): string {.inline.} = |
|||
# Return the string representation of a range. |
|||
when T is SomeFloat: |
|||
"[$1, $2]".format(r[0].formatFloat(ffDecimal, 1), r[1].formatFloat(ffDecimal, 1)) |
|||
else: |
|||
"[$1, $2]".format(r[0], r[1]) |
|||
proc `$`[T](s: seq[Range[T]]): string {.inline.} = |
|||
## Return the string representation of a sequence of ranges. |
|||
s.join(", ") |
|||
when isMainModule: |
|||
proc test[T](rangeList: varargs[Range[T]]) = |
|||
echo ($(@rangeList)).alignLeft(52), "→ ", consolidate(rangeList) |
|||
test([1.1, 2.2]) |
|||
test([6.1, 7.2], [7.2, 8.3]) |
|||
test([4, 3], [2, 1]) |
|||
test([4.0, 3.0], [2.0, 1.0], [-1.0, -2.0], [3.9, 10.0]) |
|||
test([1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6])</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[1.1, 2.2] → [1.1, 2.2] |
|||
[6.1, 7.2], [7.2, 8.3] → [6.1, 8.3] |
|||
[4, 3], [2, 1] → [1, 2], [3, 4] |
|||
[4.0, 3.0], [2.0, 1.0], [-1.0, -2.0], [3.9, 10.0] → [-2.0, -1.0], [1.0, 2.0], [3.0, 10.0] |
|||
[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6] → [-6, -1], [1, 8]</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
Line 674: | Line 1,861: | ||
Note: the output is shown in the standard [https://perldoc.perl.org/perlop.html#Range-Operators Perl notation for Ranges]. |
Note: the output is shown in the standard [https://perldoc.perl.org/perlop.html#Range-Operators Perl notation for Ranges]. |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
Line 704: | Line 1,891: | ||
$out .= join('..', @$_). ' ' for consolidate($intervals); |
$out .= join('..', @$_). ' ' for consolidate($intervals); |
||
printf "%44s => %s\n", $in, $out; |
printf "%44s => %s\n", $in, $out; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> [1.1, 2.2] => 1.1..2.2 |
<pre> [1.1, 2.2] => 1.1..2.2 |
||
Line 712: | Line 1,899: | ||
[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6] => -6..-1 1..8</pre> |
[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6] => -6..-1 1..8</pre> |
||
=={{header| |
=={{header|Phix}}== |
||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
{{works with|Rakudo|2018.12}} |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
In Perl 6, a Range is a first class object with its own specialized notation. Perl 6 Ranges allow for exclusion of the boundary numbers. This example doesn't since it isn't a requirement in this task. Much of the logic is lifted from the [[Set_of_real_numbers#Perl_6|Set_of_real_numbers]] task with simplified logic for the much simpler requirements. |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">consolidate</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">sets</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sets</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">l</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">rs</span><span style="color: #0000FF;">,</span><span style="color: #000000;">re</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rs</span><span style="color: #0000FF;">></span><span style="color: #000000;">re</span><span style="color: #0000FF;">?{</span><span style="color: #000000;">re</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rs</span><span style="color: #0000FF;">}:{</span><span style="color: #000000;">rs</span><span style="color: #0000FF;">,</span><span style="color: #000000;">re</span><span style="color: #0000FF;">})</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">l</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">il</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ih</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">l</span> <span style="color: #008080;">to</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">jl</span><span style="color: #0000FF;">,</span><span style="color: #000000;">jh</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #004080;">bool</span> <span style="color: #000000;">overlap</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">il</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">jl</span><span style="color: #0000FF;">?</span><span style="color: #000000;">jl</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">ih</span><span style="color: #0000FF;">:</span><span style="color: #000000;">il</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">jh</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">overlap</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">il</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ih</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">il</span><span style="color: #0000FF;">,</span><span style="color: #000000;">jl</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ih</span><span style="color: #0000FF;">,</span><span style="color: #000000;">jh</span><span style="color: #0000FF;">)}</span> |
|||
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #000000;">l</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">il</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ih</span><span style="color: #0000FF;">}</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">l</span><span style="color: #0000FF;">])</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">set</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%40v => %v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">set</span><span style="color: #0000FF;">,</span><span style="color: #000000;">consolidate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">set</span><span style="color: #0000FF;">)})</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
<span style="color: #000000;">test</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">1.1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2.2</span><span style="color: #0000FF;">}})</span> |
|||
<span style="color: #000000;">test</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">6.1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7.2</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">7.2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8.3</span><span style="color: #0000FF;">}})</span> |
|||
<span style="color: #000000;">test</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}})</span> |
|||
<span style="color: #000000;">test</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">3.9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">}})</span> |
|||
<span style="color: #000000;">test</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">6</span><span style="color: #0000FF;">}})</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
|||
<pre> |
|||
{{1.1,2.2}} => {{1.1,2.2}} |
|||
{{6.1,7.2},{7.2,8.3}} => {{6.1,8.3}} |
|||
{{4,3},{2,1}} => {{1,2},{3,4}} |
|||
{{4,3},{2,1},{-1,-2},{3.9,10}} => {{-2,-1},{1,2},{3,10}} |
|||
{{1,3},{-6,-1},{-4,-5},{8,2},{-6,-6}} => {{-6,-1},{1,8}} |
|||
</pre> |
|||
=={{header|Prolog}}== |
|||
Note: the output is in standard [https://docs.perl6.org/type/Range Perl 6 notation for Ranges]. |
|||
{{works with|SWI Prolog}} |
|||
<syntaxhighlight lang="prolog">consolidate_ranges(Ranges, Consolidated):- |
|||
normalize(Ranges, Normalized), |
|||
sort(Normalized, Sorted), |
|||
merge(Sorted, Consolidated). |
|||
normalize([], []):-!. |
|||
<lang perl6># Union |
|||
normalize([r(X, Y)|Ranges], [r(Min, Max)|Normalized]):- |
|||
sub infix:<∪> (Range $a, Range $b) { Range.new($a.min,max($a.max,$b.max)) } |
|||
(X > Y -> Min = Y, Max = X; Min = X, Max = Y), |
|||
normalize(Ranges, Normalized). |
|||
merge([], []):-!. |
|||
# Intersection |
|||
merge([Range], [Range]):-!. |
|||
merge([r(Min1, Max1), r(Min2, Max2)|Rest], Merged):- |
|||
Min2 =< Max1, |
|||
!, |
|||
Max is max(Max1, Max2), |
|||
merge([r(Min1, Max)|Rest], Merged). |
|||
merge([Range|Ranges], [Range|Merged]):- |
|||
merge(Ranges, Merged). |
|||
write_range(r(Min, Max)):- |
|||
multi consolidate() { () } |
|||
writef('[%w, %w]', [Min, Max]). |
|||
write_ranges([]):-!. |
|||
multi consolidate($this is copy, **@those) { |
|||
write_ranges([Range]):- |
|||
gather { |
|||
!, |
|||
for consolidate |@those -> $that { |
|||
write_range(Range). |
|||
if $this ∩ $that { $this ∪= $that } |
|||
write_ranges([Range|Ranges]):- |
|||
else { take $that } |
|||
write_range(Range), |
|||
} |
|||
write(', '), |
|||
take $this; |
|||
write_ranges(Ranges). |
|||
} |
|||
} |
|||
test_case([r(1.1, 2.2)]). |
|||
test_case([r(6.1, 7.2), r(7.2, 8.3)]). |
|||
test_case([r(4, 3), r(2, 1)]). |
|||
test_case([r(4, 3), r(2, 1), r(-1, -2), r(3.9, 10)]). |
|||
test_case([r(1, 3), r(-6, -1), r(-4, -5), r(8, 2), r(-6, -6)]). |
|||
-> @intervals { |
|||
printf "%46s => ", @intervals.perl; |
|||
say reverse consolidate |@intervals.grep(*.elems)».sort.sort({ [.[0], .[*-1]] }).map: { Range.new(.[0], .[*-1]) } |
|||
}</lang> |
|||
{{out}} |
|||
<pre> [[1.1, 2.2],] => (1.1..2.2) |
|||
[[6.1, 7.2], [7.2, 8.3]] => (6.1..8.3) |
|||
[[4, 3], [2, 1]] => (1..2 3..4) |
|||
[[4, 3], [2, 1], [-1, -2], [3.9, 10]] => (-2..-1 1..2 3..10) |
|||
[[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6]] => (-6..-1 1..8) |
|||
</pre> |
|||
main:- |
|||
=={{header|Phix}}== |
|||
forall(test_case(Ranges), |
|||
<lang Phix>function consolidate(sequence sets) |
|||
(consolidate_ranges(Ranges, Consolidated), |
|||
for i=length(sets) to 1 by -1 do |
|||
write_ranges(Ranges), write(' -> '), |
|||
write_ranges(Consolidated), nl)).</syntaxhighlight> |
|||
atom {is,ie} = sets[i] |
|||
for j=length(sets) to i+1 by -1 do |
|||
atom {js,je} = sets[j] |
|||
bool overlap = iff(is<=js?js<=ie:is<=je) |
|||
if overlap then |
|||
sets[i] = {min(is,js),max(ie,je)} |
|||
sets[j..j] = {} |
|||
end if |
|||
end for |
|||
end for |
|||
return sort(sets) |
|||
end function |
|||
procedure test(sequence set) |
|||
printf(1,"%40v => %v\n",{set,consolidate(set)}) |
|||
end procedure |
|||
test({{1.1,2.2}}) |
|||
test({{6.1,7.2},{7.2,8.3}}) |
|||
test({{4,3},{2,1}}) |
|||
test({{4,3},{2,1},{-1,-2},{3.9,10}}) |
|||
test({{1,3},{-6,-1},{-4,-5},{8,2},{-6,-6}})</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
[1.1, 2.2] -> [1.1, 2.2] |
|||
[6.1, 7.2], [7.2, 8.3] -> [6.1, 8.3] |
|||
[4, 3], [2, 1] -> [1, 2], [3, 4] |
|||
[4, 3], [2, 1], [-1, -2], [3.9, 10] -> [-2, -1], [1, 2], [3, 10] |
|||
[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6] -> [-6, -1], [1, 8] |
|||
</pre> |
</pre> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
===Procedural=== |
===Procedural=== |
||
< |
<syntaxhighlight lang="python">def normalize(s): |
||
return sorted(sorted(bounds) for bounds in s if bounds) |
return sorted(sorted(bounds) for bounds in s if bounds) |
||
Line 812: | Line 2,024: | ||
]: |
]: |
||
print(f"{str(s)[1:-1]} => {str(consolidate(s))[1:-1]}") |
print(f"{str(s)[1:-1]} => {str(consolidate(s))[1:-1]}") |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 827: | Line 2,039: | ||
{{Trans|Haskell}} |
{{Trans|Haskell}} |
||
{{Works with|Python|3.7}} |
{{Works with|Python|3.7}} |
||
< |
<syntaxhighlight lang="python">'''Range consolidation''' |
||
from functools import reduce |
from functools import reduce |
||
Line 914: | Line 2,126: | ||
# MAIN --- |
# MAIN --- |
||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>Consolidation of numeric ranges: |
<pre>Consolidation of numeric ranges: |
||
Line 925: | Line 2,137: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
< |
<syntaxhighlight lang="racket">#lang racket |
||
;; Racket's max and min allow inexact numbers to contaminate exact numbers |
;; Racket's max and min allow inexact numbers to contaminate exact numbers |
||
Line 952: | Line 2,164: | ||
([1 3] [-6 -1] [-4 -5] [8 2] [-6 -6]))) |
([1 3] [-6 -1] [-4 -5] [8 2] [-6 -6]))) |
||
(for ([xs (in-list inputs)]) (printf "~a => ~a\n" xs (solve xs)))</ |
(for ([xs (in-list inputs)]) (printf "~a => ~a\n" xs (solve xs)))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 961: | Line 2,173: | ||
((4 3) (2 1) (-1 -2) (3.9 10)) => ((-2 -1) (1 2) (3 10)) |
((4 3) (2 1) (-1 -2) (3.9 10)) => ((-2 -1) (1 2) (3 10)) |
||
((1 3) (-6 -1) (-4 -5) (8 2) (-6 -6)) => ((-6 -1) (1 8)) |
((1 3) (-6 -1) (-4 -5) (8 2) (-6 -6)) => ((-6 -1) (1 8)) |
||
</pre> |
|||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
{{works with|Rakudo|2020.08.1}} |
|||
In Raku, a Range is a first class object with its own specialized notation. Raku Ranges allow for exclusion of the boundary numbers. This example doesn't since it isn't a requirement in this task. Much of the logic is lifted from the [[Set_of_real_numbers#Raku|Set_of_real_numbers]] task with simplified logic for the much simpler requirements. |
|||
Note: the output is in standard [https://docs.raku.org/type/Range Raku notation for Ranges]. |
|||
<syntaxhighlight lang="raku" line># Union |
|||
sub infix:<∪> (Range $a, Range $b) { Range.new($a.min,max($a.max,$b.max)) } |
|||
# Intersection |
|||
sub infix:<∩> (Range $a, Range $b) { so $a.max >= $b.min } |
|||
multi consolidate() { () } |
|||
multi consolidate($this is copy, **@those) { |
|||
gather { |
|||
for consolidate |@those -> $that { |
|||
if $this ∩ $that { $this ∪= $that } |
|||
else { take $that } |
|||
} |
|||
take $this; |
|||
} |
|||
} |
|||
for [[1.1, 2.2],], |
|||
[[6.1, 7.2], [7.2, 8.3]], |
|||
[[4, 3], [2, 1]], |
|||
[[4, 3], [2, 1], [-1, -2], [3.9, 10]], |
|||
[[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6]] |
|||
-> @intervals { |
|||
printf "%46s => ", @intervals.raku; |
|||
say reverse consolidate |@intervals.grep(*.elems)».sort.sort({ [.[0], .[*-1]] }).map: { Range.new(.[0], .[*-1]) } |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> [[1.1, 2.2],] => (1.1..2.2) |
|||
[[6.1, 7.2], [7.2, 8.3]] => (6.1..8.3) |
|||
[[4, 3], [2, 1]] => (1..2 3..4) |
|||
[[4, 3], [2, 1], [-1, -2], [3.9, 10]] => (-2..-1 1..2 3..10) |
|||
[[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6]] => (-6..-1 1..8) |
|||
</pre> |
</pre> |
||
Line 967: | Line 2,221: | ||
The actual logic for the range consolidation is marked with the comments: <big> <tt> /*■■■■►*/ </tt> </big> |
The actual logic for the range consolidation is marked with the comments: <big> <tt> /*■■■■►*/ </tt> </big> |
||
< |
<syntaxhighlight lang="rexx">/*REXX program performs range consolidation (they can be [equal] ascending/descending). */ |
||
#.= /*define the default for range sets. */ |
#.= /*define the default for range sets. */ |
||
parse arg #.1 /*obtain optional arguments from the CL*/ |
parse arg #.1 /*obtain optional arguments from the CL*/ |
||
Line 1,008: | Line 2,262: | ||
y= space(y, 0) /*elide superfluous blanks in the sets.*/ |
y= space(y, 0) /*elide superfluous blanks in the sets.*/ |
||
do k=1 while y\=='' & y\=='[]' /*process ranges while range not blank.*/ |
do k=1 while y\=='' & y\=='[]' /*process ranges while range not blank.*/ |
||
y= strip(y, 'L', ",") /*elide commas between sets of ranges. */ |
|||
parse var y '[' L "," H ']' y /*extract the "low" and "high" values.*/ |
parse var y '[' L "," H ']' y /*extract the "low" and "high" values.*/ |
||
if H<L then parse value L H with H L /*order " " " " " */ |
if H<L then parse value L H with H L /*order " " " " " */ |
||
Line 1,020: | Line 2,274: | ||
do j=1 to n-1; _= @.j |
do j=1 to n-1; _= @.j |
||
do k=j+1 to n; if word(@.k,1)>=word(_,1) then iterate; @.j=@.k; @.k=_; _=@.j |
do k=j+1 to n; if word(@.k,1)>=word(_,1) then iterate; @.j=@.k; @.k=_; _=@.j |
||
end /*k*/ |
end /*k*/ |
||
end /*j*/; return</syntaxhighlight> |
|||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
||
<pre> |
<pre> |
||
Line 1,041: | Line 2,296: | ||
original ranges: [] |
original ranges: [] |
||
consolidated ranges: [] |
consolidated ranges: [] |
||
</pre> |
|||
=={{header|RPL}}== |
|||
{{works with|RPL|HP-48R}} |
|||
« 1 OVER SIZE '''FOR''' j |
|||
j DUP2 GET V→ |
|||
'''IF''' DUP2 > '''THEN''' SWAP '''END''' |
|||
→V2 PUT |
|||
'''NEXT''' |
|||
» <span style="color:blue">RNGNORM</span>' STO |
|||
« LIST→ → len |
|||
« len 1 '''FOR''' n |
|||
1 n 1 - '''START''' |
|||
DUP2 - DUP 1 GET |
|||
SWAP V→ IFTE |
|||
'''IF''' 0 > '''THEN''' SWAP '''END''' |
|||
n ROLLD |
|||
'''NEXT''' n ROLLD |
|||
-1 '''STEP''' |
|||
len →LIST |
|||
» » '<span style="color:blue">RNGSORT</span>' STO |
|||
« <span style="color:blue">RNGNORM</span> |
|||
'''IF''' DUP SIZE 2 ≥ '''THEN''' |
|||
<span style="color:blue">RNGSORT</span> → ranges |
|||
« { } ranges 1 GET |
|||
2 ranges SIZE '''FOR''' j |
|||
ranges j GET |
|||
'''IF''' OVER 2 GET OVER 1 GET ≥ |
|||
'''THEN''' SWAP V→ ROT V→ SWAP DROP MAX →V2 |
|||
'''ELSE''' ROT ROT + SWAP END |
|||
'''NEXT''' + |
|||
» '''END''' |
|||
» '<span style="color:blue">RNGCONSO</span>' STO |
|||
{ { [1.1, 2.2] } |
|||
{ [6.1, 7.2] [7.2, 8.3] } |
|||
{ [4 3] [2 1] } |
|||
{ [4 3] [2 1] [-1, -2] [3.9 10] } |
|||
{ [1 3] [-6 -1] [-4 -5] [8 2] [-6 -6]} } |
|||
1 « <span style="color:blue">RNGCONSO</span> » DOLIST |
|||
{{out}} |
|||
<pre> |
|||
1: { { [ 1.1 2.2 ] } |
|||
{ [ 6.1 8.3 ] } |
|||
{ [ 1 2 ] [ 3 4 ] } |
|||
{ [ -2 -1 ] [ 1 2 ] [ 3 10 ] } |
|||
{ [ -6 -1 ] [ 1 8 ] } } |
|||
</pre> |
|||
=={{header|Rust}}== |
|||
Most of the implementation below belongs to the test and formatting support. |
|||
If the output might be more arbitrary, the source would be quite small. |
|||
The algorithm relies on normalizing the ranges and folding a sorted sequence of them. |
|||
<syntaxhighlight lang="rust">use std::fmt::{Display, Formatter}; |
|||
// We could use std::ops::RangeInclusive, but we would have to extend it to |
|||
// normalize self (not much trouble) and it would not have to handle pretty |
|||
// printing for it explicitly. So, let's make rather an own type. |
|||
#[derive(Clone, Debug, PartialEq, PartialOrd)] |
|||
pub struct ClosedRange<Idx> { |
|||
start: Idx, |
|||
end: Idx, |
|||
} |
|||
impl<Idx> ClosedRange<Idx> { |
|||
pub fn start(&self) -> &Idx { |
|||
&self.start |
|||
} |
|||
pub fn end(&self) -> &Idx { |
|||
&self.end |
|||
} |
|||
} |
|||
impl<Idx: PartialOrd> ClosedRange<Idx> { |
|||
pub fn new(start: Idx, end: Idx) -> Self { |
|||
if start <= end { |
|||
Self { start, end } |
|||
} else { |
|||
Self { |
|||
end: start, |
|||
start: end, |
|||
} |
|||
} |
|||
} |
|||
} |
|||
// To make test input more compact |
|||
impl<Idx: PartialOrd> From<(Idx, Idx)> for ClosedRange<Idx> { |
|||
fn from((start, end): (Idx, Idx)) -> Self { |
|||
Self::new(start, end) |
|||
} |
|||
} |
|||
// For the required print format |
|||
impl<Idx: Display> Display for ClosedRange<Idx> { |
|||
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result { |
|||
write!(f, "[{}, {}]", self.start, self.end) |
|||
} |
|||
} |
|||
fn consolidate<Idx>(a: &ClosedRange<Idx>, b: &ClosedRange<Idx>) -> Option<ClosedRange<Idx>> |
|||
where |
|||
Idx: PartialOrd + Clone, |
|||
{ |
|||
if a.start() <= b.start() { |
|||
if b.end() <= a.end() { |
|||
Some(a.clone()) |
|||
} else if a.end() < b.start() { |
|||
None |
|||
} else { |
|||
Some(ClosedRange::new(a.start().clone(), b.end().clone())) |
|||
} |
|||
} else { |
|||
consolidate(b, a) |
|||
} |
|||
} |
|||
fn consolidate_all<Idx>(mut ranges: Vec<ClosedRange<Idx>>) -> Vec<ClosedRange<Idx>> |
|||
where |
|||
Idx: PartialOrd + Clone, |
|||
{ |
|||
// Panics for incomparable elements! So no NaN for floats, for instance. |
|||
ranges.sort_by(|a, b| a.partial_cmp(b).unwrap()); |
|||
let mut ranges = ranges.into_iter(); |
|||
let mut result = Vec::new(); |
|||
if let Some(current) = ranges.next() { |
|||
let leftover = ranges.fold(current, |mut acc, next| { |
|||
match consolidate(&acc, &next) { |
|||
Some(merger) => { |
|||
acc = merger; |
|||
} |
|||
None => { |
|||
result.push(acc); |
|||
acc = next; |
|||
} |
|||
} |
|||
acc |
|||
}); |
|||
result.push(leftover); |
|||
} |
|||
result |
|||
} |
|||
#[cfg(test)] |
|||
mod tests { |
|||
use super::{consolidate_all, ClosedRange}; |
|||
use std::fmt::{Display, Formatter}; |
|||
struct IteratorToDisplay<F>(F); |
|||
impl<F, I> Display for IteratorToDisplay<F> |
|||
where |
|||
F: Fn() -> I, |
|||
I: Iterator, |
|||
I::Item: Display, |
|||
{ |
|||
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result { |
|||
let mut items = self.0(); |
|||
if let Some(item) = items.next() { |
|||
write!(f, "{}", item)?; |
|||
for item in items { |
|||
write!(f, ", {}", item)?; |
|||
} |
|||
} |
|||
Ok(()) |
|||
} |
|||
} |
|||
macro_rules! parameterized { |
|||
($($name:ident: $value:expr,)*) => { |
|||
$( |
|||
#[test] |
|||
fn $name() { |
|||
let (input, expected) = $value; |
|||
let expected: Vec<_> = expected.into_iter().map(ClosedRange::from).collect(); |
|||
let output = consolidate_all(input.into_iter().map(ClosedRange::from).collect()); |
|||
println!("{}: {}", stringify!($name), IteratorToDisplay(|| output.iter())); |
|||
assert_eq!(expected, output); |
|||
} |
|||
)* |
|||
} |
|||
} |
|||
parameterized! { |
|||
single: (vec![(1.1, 2.2)], vec![(1.1, 2.2)]), |
|||
touching: (vec![(6.1, 7.2), (7.2, 8.3)], vec![(6.1, 8.3)]), |
|||
disjoint: (vec![(4, 3), (2, 1)], vec![(1, 2), (3, 4)]), |
|||
overlap: (vec![(4.0, 3.0), (2.0, 1.0), (-1.0, -2.0), (3.9, 10.0)], vec![(-2.0, -1.0), (1.0, 2.0), (3.0, 10.0)]), |
|||
integer: (vec![(1, 3), (-6, -1), (-4, -5), (8, 2), (-6, -6)], vec![(-6, -1), (1, 8)]), |
|||
} |
|||
} |
|||
fn main() { |
|||
// To prevent dead code and to check empty input |
|||
consolidate_all(Vec::<ClosedRange<usize>>::new()); |
|||
println!("Run: cargo test -- --nocapture"); |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
running 5 tests |
|||
integer: [-6, -1], [1, 8] |
|||
disjoint: [1, 2], [3, 4] |
|||
single: [1.1, 2.2] |
|||
touching: [6.1, 8.3] |
|||
overlap: [-2, -1], [1, 2], [3, 10] |
|||
test tests::integer ... ok |
|||
test tests::disjoint ... ok |
|||
test tests::single ... ok |
|||
test tests::touching ... ok |
|||
test tests::overlap ... ok |
|||
test result: ok. 5 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out |
|||
</pre> |
|||
=={{header|SQL}}== |
|||
{{works with|ORACLE 19c}} |
|||
This is not a particularly efficient solution, but it gets the job done. |
|||
<syntaxhighlight lang="sql"> |
|||
/* |
|||
This code is an implementation of "Range consolidation" in SQL ORACLE 19c |
|||
p_list_of_sets -- input string |
|||
delimeter by default "|" |
|||
*/ |
|||
with |
|||
function range_consolidation(p_list_of_sets in varchar2) |
|||
return varchar2 is |
|||
-- |
|||
v_list_of_sets varchar2(32767) := p_list_of_sets; |
|||
v_output varchar2(32767); |
|||
v_set_1 varchar2(2000); |
|||
v_set_2 varchar2(2000); |
|||
v_pos_set_1 pls_integer; |
|||
v_pos_set_2 pls_integer; |
|||
v_set_1_min number; |
|||
v_set_1_max number; |
|||
v_set_2_min number; |
|||
v_set_2_max number; |
|||
-- |
|||
function sort_set(p_in_str varchar2) |
|||
return varchar2 is |
|||
v_out varchar2(32767) := p_in_str; |
|||
begin |
|||
-- |
|||
with out_tab as |
|||
(select to_number(regexp_substr(str, '[^,]+', 1, rownum, 'c', 0)) elem |
|||
from |
|||
(select p_in_str as str |
|||
from dual |
|||
) |
|||
connect by level <= regexp_count(str, '[^,]+') |
|||
) |
|||
select min(elem)||','||max(elem) end |
|||
into v_out |
|||
from out_tab; |
|||
-- |
|||
return v_out; |
|||
end; |
|||
-- |
|||
function sort_output(p_in_str varchar2) |
|||
return varchar2 is |
|||
v_out varchar2(32767) := p_in_str; |
|||
begin |
|||
-- |
|||
with out_tab as |
|||
(select to_number(regexp_substr(regexp_substr(str, '[^|]+', 1, rownum, 'c', 0), '[^,]+', 1, 1)) low_range |
|||
, regexp_substr(str, '[^|]+', 1, rownum, 'c', 0) range_def |
|||
from |
|||
(select p_in_str as str |
|||
from dual |
|||
) |
|||
connect by level <= regexp_count(str, '[^|]+') |
|||
) |
|||
select listagg(range_def, '|') within group(order by low_range) |
|||
into v_out |
|||
from out_tab; |
|||
-- |
|||
return v_out; |
|||
end; |
|||
-- |
|||
begin |
|||
-- |
|||
execute immediate ('alter session set NLS_NUMERIC_CHARACTERS = ''.,'''); |
|||
-- |
|||
--cleaning |
|||
v_list_of_sets := ltrim(v_list_of_sets, '['); |
|||
v_list_of_sets := rtrim(v_list_of_sets, ']'); |
|||
v_list_of_sets := replace(v_list_of_sets, ' ', ''); |
|||
--set delimeter "|" |
|||
v_list_of_sets := regexp_replace(v_list_of_sets, '\]\,\[', '|', 1, 0); |
|||
-- |
|||
<<loop_through_sets>> |
|||
while regexp_count(v_list_of_sets, '[^|]+') > 0 |
|||
loop |
|||
v_set_1 := regexp_substr(v_list_of_sets, '[^|]+', 1, 1); |
|||
v_list_of_sets := regexp_replace(v_list_of_sets, v_set_1, sort_set(v_set_1), 1, 1); |
|||
v_set_1 := sort_set(v_set_1); |
|||
v_pos_set_1 := regexp_instr(v_list_of_sets, '[^|]+', 1, 1); |
|||
-- |
|||
v_set_1_min := least(to_number(regexp_substr(v_set_1, '[^,]+', 1, 1)),to_number(regexp_substr(v_set_1, '[^,]+', 1, 2))); |
|||
v_set_1_max := greatest(to_number(regexp_substr(v_set_1, '[^,]+', 1, 1)),to_number(regexp_substr(v_set_1, '[^,]+', 1, 2))); |
|||
-- |
|||
<<loop_for>> |
|||
for i in 1..regexp_count(v_list_of_sets, '[^|]+')-1 |
|||
loop |
|||
-- |
|||
v_set_2 := regexp_substr(v_list_of_sets, '[^|]+', 1, i+1); |
|||
v_list_of_sets := regexp_replace(v_list_of_sets, v_set_2, sort_set(v_set_2), 1, 1); |
|||
v_set_2 := sort_set(v_set_2); |
|||
v_pos_set_2 := regexp_instr(v_list_of_sets, '[^|]+', 1, i+1); |
|||
v_set_2_min := least(to_number(regexp_substr(v_set_2, '[^,]+', 1, 1)),to_number(regexp_substr(v_set_2, '[^,]+', 1, 2))); |
|||
v_set_2_max := greatest(to_number(regexp_substr(v_set_2, '[^,]+', 1, 1)),to_number(regexp_substr(v_set_2, '[^,]+', 1, 2))); |
|||
-- |
|||
if greatest(v_set_1_min,v_set_2_min)-least(v_set_1_max,v_set_2_max) <= 0 then --overlapping |
|||
v_list_of_sets := regexp_replace(v_list_of_sets, v_set_1, ''||least(v_set_1_min,v_set_2_min)||','||greatest(v_set_1_max,v_set_2_max),v_pos_set_1,1); |
|||
v_list_of_sets := regexp_replace(v_list_of_sets, v_set_2, '', v_pos_set_2, 1); |
|||
continue loop_through_sets; |
|||
end if; |
|||
-- |
|||
end loop loop_for; |
|||
-- |
|||
v_output := ltrim(v_output||'|'||least(v_set_1_min,v_set_1_max)||', '||greatest(v_set_1_min,v_set_1_max),'|'); |
|||
-- |
|||
v_output := sort_output(v_output); |
|||
v_list_of_sets := regexp_replace(v_list_of_sets,v_set_1,'',1,1); |
|||
-- |
|||
end loop loop_through_sets; |
|||
-- |
|||
return '['||replace(v_output,'|','], [')||']'; |
|||
end; |
|||
--Test |
|||
select lpad('[]',50) || ' ==> ' || range_consolidation('[]') as output from dual |
|||
union all |
|||
select lpad('[],[]',50) || ' ==> ' || range_consolidation('[],[]') as output from dual |
|||
union all |
|||
select lpad('[],[1,1]',50) || ' ==> ' || range_consolidation('[],[1,1]') as output from dual |
|||
union all |
|||
select lpad('[1.3]',50) || ' ==> ' || range_consolidation('[1.3]') as output from dual |
|||
union all |
|||
select lpad('[2,2],[1]',50) || ' ==> ' || range_consolidation('[2,2],[1]') as output from dual |
|||
union all |
|||
select lpad('[4,-1,0,1,5,7,7,7],[9,6,9,6,9]',50) || ' ==> ' || range_consolidation('[4,-1,0,1,5,7,7,7],[9,6,9,6,9]') as output from dual |
|||
union all |
|||
--Test RosettaCode |
|||
select '-- Test RosettaCode' as output from dual |
|||
union all |
|||
select lpad('[1.1, 2.2]',50) || ' ==> ' || range_consolidation('[1.1, 2.2]') as output from dual |
|||
union all |
|||
select lpad('[6.1, 7.2], [7.2, 8.3]',50) || ' ==> ' || range_consolidation('[6.1, 7.2], [7.2, 8.3]') as output from dual |
|||
union all |
|||
select lpad('[4, 3], [2, 1]',50) || ' ==> ' || range_consolidation('[4, 3], [2, 1]') as output from dual |
|||
union all |
|||
select lpad('[4, 3], [2, 1], [-1, -2], [3.9, 10]',50) || ' ==> ' || range_consolidation('[4, 3], [2, 1], [-1, -2], [3.9, 10]') as output from dual |
|||
union all |
|||
select lpad('[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6]',50) || ' ==> ' || range_consolidation('[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6]') as output from dual |
|||
union all |
|||
select lpad('1,3|-6,-1|-4,-5|8,2|-6,-6',50) || ' ==> ' || range_consolidation('1,3|-6,-1|-4,-5|8,2|-6,-6') as output from dual |
|||
/ |
|||
; |
|||
/ |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[] ==> [] |
|||
[],[] ==> [] |
|||
[],[1,1] ==> [1, 1] |
|||
[1.3] ==> [1.3, 1.3] |
|||
[2,2],[1] ==> [1, 1], [2, 2] |
|||
[4,-1,0,1,5,7,7,7],[9,6,9,6,9] ==> [-1, 9] |
|||
-- Test RosettaCode |
|||
[1.1, 2.2] ==> [1.1, 2.2] |
|||
[6.1, 7.2], [7.2, 8.3] ==> [6.1, 8.3] |
|||
[4, 3], [2, 1] ==> [1, 2], [3, 4] |
|||
[4, 3], [2, 1], [-1, -2], [3.9, 10] ==> [-2, -1], [1, 2], [3, 10] |
|||
[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6] ==> [-6, -1], [1, 8] |
|||
1,3|-6,-1|-4,-5|8,2|-6,-6 ==> [-6, -1], [1, 8] |
|||
</pre> |
|||
=={{header|Wren}}== |
|||
As Wren already has a built-in Range class (which is not quite the same as what's required here), we create a Span class instead. |
|||
<syntaxhighlight lang="wren">class Span { |
|||
construct new(r) { |
|||
if (r.type != Range || !r.isInclusive) Fiber.abort("Argument must be an inclusive range.") |
|||
_low = r.from |
|||
_high = r.to |
|||
if (_low > _high) { |
|||
_low = r.to |
|||
_high = r.from |
|||
} |
|||
} |
|||
low { _low } |
|||
high { _high } |
|||
consolidate(r) { |
|||
if (r.type != Span) Fiber.abort("Argument must be a Span.") |
|||
if (_high < r.low) return [this, r] |
|||
if (r.high < _low) return [r, this] |
|||
return [Span.new(_low.min(r.low).._high.max(r.high))] |
|||
} |
|||
toString { "[%(_low), %(_high)]" } |
|||
} |
|||
var spanLists = [ |
|||
[Span.new(1.1..2.2)], |
|||
[Span.new(6.1..7.2), Span.new(7.2..8.3)], |
|||
[Span.new(4..3), Span.new(2..1)], |
|||
[Span.new(4..3), Span.new(2..1), Span.new(-1..-2), Span.new(3.9..10)], |
|||
[Span.new(1..3), Span.new(-6..-1), Span.new(-4..-5), Span.new(8..2), Span.new(-6..-6)] |
|||
] |
|||
for (spanList in spanLists) { |
|||
if (spanList.count == 1) { |
|||
System.print(spanList.toString[1..-2]) |
|||
} else if (spanList.count == 2) { |
|||
System.print(spanList[0].consolidate(spanList[1]).toString[1..-2]) |
|||
} else { |
|||
var first = 0 |
|||
while (first < spanList.count-1) { |
|||
var next = first + 1 |
|||
while (next < spanList.count) { |
|||
var res = spanList[first].consolidate(spanList[next]) |
|||
spanList[first] = res[0] |
|||
if (res.count == 2) { |
|||
spanList[next] = res[1] |
|||
next = next + 1 |
|||
} else { |
|||
spanList.removeAt(next) |
|||
} |
|||
} |
|||
first = first + 1 |
|||
} |
|||
System.print(spanList.toString[1..-2]) |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[1.1, 2.2] |
|||
[6.1, 8.3] |
|||
[1, 2], [3, 4] |
|||
[-2, -1], [1, 2], [3, 10] |
|||
[-6, -1], [1, 8] |
|||
</pre> |
</pre> |
||
=={{header|Yabasic}}== |
=={{header|Yabasic}}== |
||
< |
<syntaxhighlight lang="yabasic">sub sort(tabla()) |
||
local items, i, t1, t2, s |
local items, i, t1, t2, s |
||
Line 1,114: | Line 2,830: | ||
for i = 1 to items |
for i = 1 to items |
||
if tabla(i, 1) <> void print tabla(i, 1), "..", tabla(i, 2); |
if tabla(i, 1) <> void print tabla(i, 1), "..", tabla(i, 2); |
||
next</ |
next</syntaxhighlight> |
||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
< |
<syntaxhighlight lang="zkl">fcn consolidate(rs){ |
||
(s:=List()).append( |
(s:=List()).append( |
||
normalize(rs).reduce('wrap(ab,cd){ |
normalize(rs).reduce('wrap(ab,cd){ |
||
if(ab[1]>=cd[0]) L(ab[0],ab[1].max(cd[1])); // consolidate |
|||
else{ s.append(ab); cd } // no overlap |
|||
}) ) |
}) ) |
||
} |
} |
||
fcn normalize(s){ s.apply("sort").sort(fcn(a,b){ a[0]<b[0] }) }</ |
fcn normalize(s){ s.apply("sort").sort(fcn(a,b){ a[0]<b[0] }) }</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">foreach rs in (L( |
||
L(L(1.1, 2.2)), L(L(6.1, 7.2), L(7.2, 8.3)), L(L(4, 3), L(2, 1)), |
L(L(1.1, 2.2)), L(L(6.1, 7.2), L(7.2, 8.3)), L(L(4, 3), L(2, 1)), |
||
L(L(4.0, 3.0), L(2.0, 1.0), L(-1.0, -2.0), L(3.9, 10.0)), |
L(L(4.0, 3.0), L(2.0, 1.0), L(-1.0, -2.0), L(3.9, 10.0)), |
||
L(L(1, 3), L(-6, -1), L(-4, -5), L(8, 2), L(-6, -6)), |
L(L(1, 3), L(-6, -1), L(-4, -5), L(8, 2), L(-6, -6)), |
||
)){ println(ppp(rs),"--> ",ppp(consolidate(rs))) } |
)){ println(ppp(rs),"--> ",ppp(consolidate(rs))) } |
||
fcn ppp(ll){ ll.pump(String,fcn(list){ list.concat(", ", "[", "] ") }) }</ |
fcn ppp(ll){ ll.pump(String,fcn(list){ list.concat(", ", "[", "] ") }) }</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
Latest revision as of 13:18, 19 August 2024
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
Define a range of numbers R, with bounds b0 and b1 covering all numbers between and including both bounds.
That range can be shown as:
- [b0, b1]
- or equally as:
- [b1, b0]
Given two ranges, the act of consolidation between them compares the two ranges:
- If one range covers all of the other then the result is that encompassing range.
- If the ranges touch or intersect then the result is one new single range covering the overlapping ranges.
- Otherwise the act of consolidation is to return the two non-touching ranges.
Given N ranges where N > 2 then the result is the same as repeatedly replacing all combinations of two ranges by their consolidation until no further consolidation between range pairs is possible.
If N < 2 then range consolidation has no strict meaning and the input can be returned.
- Example 1
- Given the two ranges [1, 2.5] and [3, 4.2] then
- there is no common region between the ranges and the result is the same as the input.
- Example 2
- Given the two ranges [1, 2.5] and [1.8, 4.7] then
- there is : an overlap [2.5, 1.8] between the ranges and
- the result is the single range [1, 4.7].
- Note that order of bounds in a range is not (yet) stated.
- Example 3
- Given the two ranges [6.1, 7.2] and [7.2, 8.3] then
- they touch at 7.2 and
- the result is the single range [6.1, 8.3].
- Example 4
- Given the three ranges [1, 2] and [4, 8] and [2, 5]
- then there is no intersection of the ranges [1, 2] and [4, 8]
- but the ranges [1, 2] and [2, 5] overlap and
- consolidate to produce the range [1, 5].
- This range, in turn, overlaps the other range [4, 8], and
- so consolidates to the final output of the single range [1, 8].
- Task
Let a normalized range display show the smaller bound to the left; and show the range with the smaller lower bound to the left of other ranges when showing multiple ranges.
Output the normalized result of applying consolidation to these five sets of ranges:
[1.1, 2.2] [6.1, 7.2], [7.2, 8.3] [4, 3], [2, 1] [4, 3], [2, 1], [-1, -2], [3.9, 10] [1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6]
Show all output here.
- See also
11l
F consolidate(ranges)
F normalize(s)
R sorted(s.filter(bounds -> !bounds.empty).map(bounds -> sorted(bounds)))
V norm = normalize(ranges)
L(&r1) norm
V i = L.index
I !r1.empty
L(j) i + 1 .< norm.len
V& r2 = norm[j]
I !r2.empty & r1.last >= r2[0]
r1 = [r1[0], max(r1.last, r2.last)]
r2.clear()
R norm.filter(rnge -> !rnge.empty)
L(s) [[[1.1, 2.2]],
[[6.1, 7.2], [7.2, 8.3]],
[[4.0, 3.0], [2.0, 1.0]],
[[4.0, 3.0], [2.0, 1.0], [-1.0, -2.0], [3.9, 10.0]],
[[1.0, 3.0], [-6.0, -1.0], [-4.0, -5.0], [8.0, 2.0], [-6.0, -6.0]]]
print(String(s)[1 .< (len)-1]‘ => ’String(consolidate(s))[1 .< (len)-1])
- Output:
[1.1, 2.2] => [1.1, 2.2] [6.1, 7.2], [7.2, 8.3] => [6.1, 8.3] [4, 3], [2, 1] => [1, 2], [3, 4] [4, 3], [2, 1], [-1, -2], [3.9, 10] => [-2, -1], [1, 2], [3, 10] [1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6] => [-6, -1], [1, 8]
Action!
INCLUDE "H6:REALMATH.ACT"
DEFINE PTR="CARD"
DEFINE RANGESIZE="12"
DEFINE LOW_="+0"
DEFINE HIGH_="+6"
TYPE Range=[CARD l1,l2,l3,h1,h2,h3]
PROC Inverse(Range POINTER r)
REAL tmp
RealAssign(r LOW_,tmp)
RealAssign(r HIGH_,r LOW_)
RealAssign(tmp,r HIGH_)
RETURN
PROC Normalize(Range POINTER r)
IF RealLess(r HIGH_,r LOW_) THEN
Inverse(r)
FI
RETURN
INT FUNC Compare(Range Pointer r1,r2)
IF RealLess(r1 LOW_,r2 LOW_) THEN
RETURN (-1)
ELSEIF RealLess(r2 LOW_,r1 LOW_) THEN
RETURN (1)
ELSEIF RealLess(r1 HIGH_,r2 HIGH_) THEN
RETURN (-1)
ELSEIF RealLess(r2 HIGH_,r1 HIGH_) THEN
RETURN (1)
FI
RETURN (0)
PTR FUNC GetItemAddr(PTR data INT index)
RETURN (data+index*RANGESIZE)
PROC Swap(Range POINTER r1,r2)
REAL tmp
RealAssign(r1 LOW_,tmp)
RealAssign(r2 LOW_,r1 LOW_)
RealAssign(tmp, r2 LOW_)
RealAssign(r1 HIGH_,tmp)
RealAssign(r2 HIGH_,r1 HIGH_)
RealAssign(tmp, r2 HIGH_)
RETURN
PROC Sort(PTR data INT count)
INT i,j,minpos
Range POINTER r1,r2
FOR i=0 TO count-2
DO
minpos=i
FOR j=i+1 TO count-1
DO
r1=GetItemAddr(data,minpos)
r2=GetItemAddr(data,j)
IF Compare(r1,r2)>0 THEN
minpos=j
FI
OD
IF minpos#i THEN
r1=GetItemAddr(data,minpos)
r2=GetItemAddr(data,i)
Swap(r1,r2)
FI
OD
RETURN
PROC Consolidate(PTR data INT POINTER count)
INT i,j,newCount
Range POINTER r1,r2
FOR i=0 TO count^-1
DO
r1=GetItemAddr(data,i)
Normalize(r1)
OD
Sort(data,count^)
newCount=0 i=0
WHILE i<count^
DO
j=i+1
WHILE j<count^
DO
r1=GetItemAddr(data,i)
r2=GetItemAddr(data,j)
IF RealLess(r1 HIGH_,r2 LOW_) THEN
EXIT
ELSEIF RealLess(r1 HIGH_,r2 HIGH_) THEN
RealAssign(r2 HIGH_,r1 HIGH_)
FI
j==+1
OD
r1=GetItemAddr(data,i)
r2=GetItemAddr(data,newCount)
RealAssign(r1 LOW_,r2 LOW_)
RealAssign(r1 HIGH_,r2 HIGH_)
newCount==+1
i=j
OD
count^=newCount
RETURN
PROC PrintRanges(PTR data INT count)
INT i
Range POINTER r
FOR i=0 TO count-1
DO
IF i>0 THEN Put(' ) FI
r=GetItemAddr(data,i)
Put('[) PrintR(r LOW_)
Put(',) PrintR(r HIGH_) Put('])
OD
RETURN
PROC Append(PTR data INT POINTER count
CHAR ARRAY sLow,sHigh)
Range POINTER r
r=GetItemAddr(data,count^)
ValR(sLow,r LOW_)
ValR(sHigh,r High_)
count^=count^+1
RETURN
INT FUNC InitData(BYTE case PTR data)
INT count
count=0
IF case=0 THEN
Append(data,@count,"1.1","2.2")
ELSEIF case=1 THEN
Append(data,@count,"6.1","7.2")
Append(data,@count,"7.2","8.3")
ELSEIF case=2 THEN
Append(data,@count,"4","3")
Append(data,@count,"2","1")
ELSEIF case=3 THEN
Append(data,@count,"4","3")
Append(data,@count,"2","1")
Append(data,@count,"-1","-2")
Append(data,@count,"3.9","10")
ELSEIF case=4 THEN
Append(data,@count,"1","3")
Append(data,@count,"-6","-1")
Append(data,@count,"-4","-5")
Append(data,@count,"8","2")
Append(data,@count,"-6","-6")
FI
RETURN (count)
PROC Main()
BYTE ARRAY data(100)
INT count
BYTE i
Put(125) PutE() ;clear the screen
FOR i=0 TO 4
DO
count=InitData(i,data)
PrintRanges(data,count)
Print(" -> ")
Consolidate(data,@count)
PrintRanges(data,count)
PutE() PutE()
OD
RETURN
- Output:
Screenshot from Atari 8-bit computer
[1.1,2.2] -> [1.1,2.2] [6.1,7.2] [7.2,8.3] -> [6.1,8.3] [4,3] [2,1] -> [1,2] [3,4] [4,3] [2,1] [-1,-2] [3.9,10] -> [-2,-1] [1,2] [3,10] [1,3] [-6,-1] [-4,-5] [8,2] [-6,-6] -> [-6,-1] [1,8]
Ada
with Ada.Text_IO;
with Ada.Containers.Vectors;
procedure Range_Consolidation is
type Set_Type is record
Left, Right : Float;
end record;
package Set_Vectors is
new Ada.Containers.Vectors (Positive, Set_Type);
procedure Normalize (Set : in out Set_Vectors.Vector) is
function Less_Than (Left, Right : Set_Type) return Boolean is
begin Return Left.Left < Right.Left; end;
package Set_Sorting is
new Set_Vectors.Generic_Sorting (Less_Than);
begin
for Elem of Set loop
Elem := (Left => Float'Min (Elem.Left, Elem.Right),
Right => Float'Max (Elem.Left, Elem.Right));
end loop;
Set_Sorting.Sort (Set);
end Normalize;
procedure Consolidate (Set : in out Set_Vectors.Vector) is
use Set_Vectors;
First : Cursor := Set.First;
Last : Cursor := Next (First);
begin
while Last /= No_Element loop
if Element (First).Right < Element (Last).Left then -- non-overlap
First := Last;
Last := Next (Last);
elsif Element (First).Right >= Element (Last).Left then -- overlap
Replace_Element (Set, First, (Left => Element (First).Left,
Right => Float'Max (Element (First).Right,
Element (Last) .Right)));
Delete (Set, Last);
Last := Next (First);
end if;
end loop;
end Consolidate;
procedure Put (Set : in Set_Vectors.Vector) is
package Float_IO is
new Ada.Text_IO.Float_IO (Float);
begin
Float_IO.Default_Exp := 0;
Float_IO.Default_Aft := 1;
Float_IO.Default_Fore := 3;
for Elem of Set loop
Ada.Text_IO.Put ("(");
Float_IO.Put (Elem.Left);
Float_IO.Put (Elem.Right);
Ada.Text_IO.Put (") ");
end loop;
end Put;
procedure Show (Set : in out Set_Vectors.Vector) is
use Ada.Text_IO;
begin
Put (Set);
Normalize (Set);
Consolidate (Set);
Set_Col (70);
Put (Set);
New_Line;
end Show;
use Set_Vectors;
Set_0 : Set_Vectors.Vector := Empty_Vector;
Set_1 : Set_Vectors.Vector := Empty_Vector & (1.1, 2.2);
Set_2 : Set_Vectors.Vector := (6.1, 7.2) & (7.2, 8.3);
Set_3 : Set_Vectors.Vector := (4.0, 3.0) & (2.0, 1.0);
Set_4 : Set_Vectors.Vector := (4.0, 3.0) & (2.0, 1.0) & (-1.0, -2.0) & (3.9, 10.0);
Set_5 : Set_Vectors.Vector := (1.0, 3.0) & (-6.0, -1.0) & (-4.0, -5.0) & (8.0, 2.0) & (-6.0, -6.0);
begin
Show (Set_0);
Show (Set_1);
Show (Set_2);
Show (Set_3);
Show (Set_4);
Show (Set_5);
end Range_Consolidation;
- Output:
( 1.1 2.2) ( 1.1 2.2) ( 6.1 7.2) ( 7.2 8.3) ( 6.1 8.3) ( 4.0 3.0) ( 2.0 1.0) ( 1.0 2.0) ( 3.0 4.0) ( 4.0 3.0) ( 2.0 1.0) ( -1.0 -2.0) ( 3.9 10.0) ( -2.0 -1.0) ( 1.0 2.0) ( 3.0 10.0) ( 1.0 3.0) ( -6.0 -1.0) ( -4.0 -5.0) ( 8.0 2.0) ( -6.0 -6.0) ( -6.0 -1.0) ( 1.0 8.0)
ALGOL 68
BEGIN # range consolidation #
MODE RANGE = STRUCT( REAL lb, ub );
# returns a with the bounds swapped if necessary, so lb OF a <= ub OF a #
OP NORMALISE = ( RANGE a )RANGE:
( IF lb OF a < ub OF a THEN lb OF a ELSE ub OF a FI
, IF ub OF a > lb OF a THEN ub OF a ELSE lb OF a FI
) # NORMALISE # ;
# returns a with each element normalised #
OP NORMALISE = ( []RANGE a )[]RANGE:
BEGIN
[ LWB a : UPB a ]RANGE result;
FOR a pos FROM LWB a TO UPB a DO result[ a pos ] := NORMALISE a[ a pos ] OD;
result
END # NORMALISE # ;
OP < = ( RANGE a, b )BOOL: lb OF a < lb OF b;
OP > = ( RANGE a, b )BOOL: lb OF a > lb OF b;
# sorts a into order of each element's lb #
OP SORT = ( []RANGE a )[]RANGE:
BEGIN
# in-place quick sort an array of RANGEs from element lb #
# to element ub #
PROC quicksort = ( REF[]RANGE a, INT lb, ub )REF[]RANGE:
IF ub <= lb
THEN
# empty array or only 1 element #
a
ELSE
# more than one element, so must sort #
INT left := lb;
INT right := ub;
# choosing the middle element of the array as the pivot #
RANGE pivot := a[ left + ( ( right + 1 ) - left ) OVER 2 ];
WHILE
WHILE IF left <= ub THEN a[ left ] < pivot ELSE FALSE FI DO left +:= 1 OD;
WHILE IF right >= lb THEN a[ right ] > pivot ELSE FALSE FI DO right -:= 1 OD;
left <= right
DO
RANGE t := a[ left ];
a[ left ] := a[ right ];
a[ right ] := t;
left +:= 1;
right -:= 1
OD;
quicksort( a, lb, right );
quicksort( a, left, ub );
a
FI # quicksort # ;
quicksort( HEAP[ LWB a : UPB a ]RANGE := a, LWB a, UPB a )
END # SORT # ;
# returns the consolidation of the ranges in a in #
OP CONSOLIDATE = ( []RANGE a in )[]RANGE:
IF UPB a in <= LWB a in
THEN a in # 0 or 1 range #
ELSE # multiple ranges #
[]RANGE a = SORT NORMALISE a in;
[ 1 : 2 * ( ( UPB a - LWB a ) + 1 ) ]RANGE result;
INT r max := 1;
result[ r max ] := a[ LWB a ];
FOR a pos FROM LWB a + 1 TO UPB a DO
RANGE m = result[ r max ], n = a[ a pos ];
IF ub OF m < lb OF n THEN
result[ r max +:= 1 ] := n # distinct ranges #
ELSE
result[ r max ] # overlapping ranges #
:= ( IF lb OF m < lb OF n THEN lb OF m ELSE lb OF n FI
, IF ub OF m > ub OF n THEN ub OF m ELSE ub OF n FI
)
FI
OD;
result[ : r max ]
FI # CONSOLIDATE # ;
OP FMT = ( REAL v )STRING: # prints v with at most 3 decimal places #
BEGIN
STRING result := fixed( ABS v, 0, 3 );
IF result[ LWB result ] = "." THEN "0" +=: result FI;
WHILE result[ UPB result ] = "0" DO result := result[ : UPB result - 1 ] OD;
IF result[ UPB result ] = "." THEN result := result[ : UPB result - 1 ] FI;
IF v < 0 THEN "-" ELSE "" FI + result
END # FMT # ;
OP TOSTRING = ( RANGE a )STRING: "[ " + FMT lb OF a + ", " + FMT ub OF a + " ]";
OP TOSTRING = ( []RANGE a )STRING:
BEGIN
STRING result := "[";
STRING prefix := " ";
FOR r pos FROM LWB a TO UPB a DO
result +:= prefix + TOSTRING a[ r pos ];
prefix := ", "
OD;
result + " ]"
END # TOSTRING # ;
PRIO PAD = 8; # right pads s with blanks to w characters #
OP PAD = ( STRING s, INT w )STRING:
IF INT len = ( UPB s - LWB s ) + 1;
len >= w
THEN s
ELSE s + ( ( w - len ) * " " )
FI # PAD # ;
# task test cases #
PROC test = ( []RANGE a )VOID:
BEGIN print( ( ( TOSTRING a PAD 60 ), " -> ", TOSTRING CONSOLIDATE a, newline ) ) END;
test( []RANGE( RANGE( 1.1, 2.2 ) ) );
test( ( ( 6.1, 7.2 ), ( 7.2, 8.3 ) ) );
test( ( ( 4, 3 ), ( 2, 1 ) ) );
test( ( ( 4, 3 ), ( 2, 1 ), ( -1, -2 ), ( 3.9, 10 ) ) );
test( ( ( 1, 3 ), ( -6, -1 ), ( -4, -5 ), ( 8, 2 ), ( -6, -6 ) ) )
END
- Output:
[ [ 1.1, 2.2 ] ] -> [ [ 1.1, 2.2 ] ] [ [ 6.1, 7.2 ], [ 7.2, 8.3 ] ] -> [ [ 6.1, 8.3 ] ] [ [ 4, 3 ], [ 2, 1 ] ] -> [ [ 1, 2 ], [ 3, 4 ] ] [ [ 4, 3 ], [ 2, 1 ], [ -1, -2 ], [ 3.9, 10 ] ] -> [ [ -2, -1 ], [ 1, 2 ], [ 3, 10 ] ] [ [ 1, 3 ], [ -6, -1 ], [ -4, -5 ], [ 8, 2 ], [ -6, -6 ] ] -> [ [ -6, -1 ], [ 1, 8 ] ]
AutoHotkey
RangeConsolidation(arr){
arr1 := [], arr2 := [], result := []
for i, obj in arr
arr1[i,1] := min(arr[i]*), arr1[i,2] := max(arr[i]*) ; sort each range individually
for i, obj in arr1
if (obj.2 > arr2[obj.1])
arr2[obj.1] := obj.2 ; creates helper array sorted by range
i := 1
for start, stop in arr2
if (i = 1) || (start > result[i-1, 2]) ; first or non overlapping range
result[i, 1] := start, result[i, 2] := stop, i++
else ; overlapping range
result[i-1, 2] := stop > result[i-1, 2] ? stop : result[i-1, 2]
return result
}
Examples:
test1 := [[1.1, 2.2]]
test2 := [[6.1, 7.2], [7.2, 8.3]]
test3 := [[4, 3], [2, 1]]
test4 := [[4, 3], [2, 1], [-1, -2], [3.9, 10]]
test5 := [[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6]]
result := ""
loop, 5
{
output := ""
for i, obj in RangeConsolidation(test%A_Index%)
output .= "[" format("{:g}", obj.1) ", " format("{:g}", obj.2) "], "
result .= Trim(output, ", ") "`n"
}
MsgBox % result
return
- Output:
[1.1, 2.2] [6.1, 8.3] [1, 2], [3, 4] [-2, -1], [1, 2], [3, 10] [-6, -1], [1, 8]
C
#include <stdio.h>
#include <stdlib.h>
typedef struct range_tag {
double low;
double high;
} range_t;
void normalize_range(range_t* range) {
if (range->high < range->low) {
double tmp = range->low;
range->low = range->high;
range->high = tmp;
}
}
int range_compare(const void* p1, const void* p2) {
const range_t* r1 = p1;
const range_t* r2 = p2;
if (r1->low < r2->low)
return -1;
if (r1->low > r2->low)
return 1;
if (r1->high < r2->high)
return -1;
if (r1->high > r2->high)
return 1;
return 0;
}
void normalize_ranges(range_t* ranges, size_t count) {
for (size_t i = 0; i < count; ++i)
normalize_range(&ranges[i]);
qsort(ranges, count, sizeof(range_t), range_compare);
}
// Consolidates an array of ranges in-place. Returns the
// number of ranges after consolidation.
size_t consolidate_ranges(range_t* ranges, size_t count) {
normalize_ranges(ranges, count);
size_t out_index = 0;
for (size_t i = 0; i < count; ) {
size_t j = i;
while (++j < count && ranges[j].low <= ranges[i].high) {
if (ranges[i].high < ranges[j].high)
ranges[i].high = ranges[j].high;
}
ranges[out_index++] = ranges[i];
i = j;
}
return out_index;
}
void print_range(const range_t* range) {
printf("[%g, %g]", range->low, range->high);
}
void print_ranges(const range_t* ranges, size_t count) {
if (count == 0)
return;
print_range(&ranges[0]);
for (size_t i = 1; i < count; ++i) {
printf(", ");
print_range(&ranges[i]);
}
}
void test_consolidate_ranges(range_t* ranges, size_t count) {
print_ranges(ranges, count);
printf(" -> ");
count = consolidate_ranges(ranges, count);
print_ranges(ranges, count);
printf("\n");
}
#define LENGTHOF(a) sizeof(a)/sizeof(a[0])
int main() {
range_t test1[] = { {1.1, 2.2} };
range_t test2[] = { {6.1, 7.2}, {7.2, 8.3} };
range_t test3[] = { {4, 3}, {2, 1} };
range_t test4[] = { {4, 3}, {2, 1}, {-1, -2}, {3.9, 10} };
range_t test5[] = { {1, 3}, {-6, -1}, {-4, -5}, {8, 2}, {-6, -6} };
test_consolidate_ranges(test1, LENGTHOF(test1));
test_consolidate_ranges(test2, LENGTHOF(test2));
test_consolidate_ranges(test3, LENGTHOF(test3));
test_consolidate_ranges(test4, LENGTHOF(test4));
test_consolidate_ranges(test5, LENGTHOF(test5));
return 0;
}
- Output:
[1.1, 2.2] -> [1.1, 2.2] [6.1, 7.2], [7.2, 8.3] -> [6.1, 8.3] [4, 3], [2, 1] -> [1, 2], [3, 4] [4, 3], [2, 1], [-1, -2], [3.9, 10] -> [-2, -1], [1, 2], [3, 10] [1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6] -> [-6, -1], [1, 8]
C#
using static System.Math;
using System.Linq;
using System;
public static class RangeConsolidation
{
public static void Main() {
foreach (var list in new [] {
new[] { (1.1, 2.2) }.ToList(),
new[] { (6.1, 7.2), (7.2, 8.3) }.ToList(),
new[] { (4d, 3d), (2, 1) }.ToList(),
new[] { (4d, 3d), (2, 1), (-1, 2), (3.9, 10) }.ToList(),
new[] { (1d, 3d), (-6, -1), (-4, -5), (8, 2), (-6, -6) }.ToList()
})
{
for (int z = list.Count-1; z >= 1; z--) {
for (int y = z - 1; y >= 0; y--) {
if (Overlap(list[z], list[y])) {
list[y] = Consolidate(list[z], list[y]);
list.RemoveAt(z);
break;
}
}
}
Console.WriteLine(string.Join(", ", list.Select(Normalize).OrderBy(range => range.s)));
}
}
private static bool Overlap((double s, double e) left, (double s, double e) right) =>
Max(left.s, left.e) > Max(right.s, right.e)
? Max(right.s, right.e) >= Min(left.s, left.e)
: Max(left.s, left.e) >= Min(right.s, right.e);
private static (double s, double e) Consolidate((double s, double e) left, (double s, double e) right) =>
(Min(Min(left.s, left.e), Min(right.s, right.e)), Max(Max(left.s, left.e), Max(right.s, right.e)));
private static (double s, double e) Normalize((double s, double e) range) =>
(Min(range.s, range.e), Max(range.s, range.e));
}
- Output:
(1.1, 2.2) (6.1, 8.3) (1, 2), (3, 4) (-1, 2), (3, 10) (-6, -1), (1, 8)
C++
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
// A range is represented as std::pair<from, to>
template <typename iterator>
void normalize_ranges(iterator begin, iterator end) {
for (iterator i = begin; i != end; ++i) {
if (i->second < i->first)
std::swap(i->first, i->second);
}
std::sort(begin, end);
}
// Merges a range of ranges in-place. Returns an iterator to the
// end of the resulting range, similarly to std::remove.
template <typename iterator>
iterator merge_ranges(iterator begin, iterator end) {
iterator out = begin;
for (iterator i = begin; i != end; ) {
iterator j = i;
while (++j != end && j->first <= i->second)
i->second = std::max(i->second, j->second);
*out++ = *i;
i = j;
}
return out;
}
template <typename iterator>
iterator consolidate_ranges(iterator begin, iterator end) {
normalize_ranges(begin, end);
return merge_ranges(begin, end);
}
template <typename pair>
void print_range(std::ostream& out, const pair& range) {
out << '[' << range.first << ", " << range.second << ']';
}
template <typename iterator>
void print_ranges(std::ostream& out, iterator begin, iterator end) {
if (begin != end) {
print_range(out, *begin++);
for (; begin != end; ++begin) {
out << ", ";
print_range(out, *begin);
}
}
}
int main() {
std::vector<std::pair<double, double>> test_cases[] = {
{ {1.1, 2.2} },
{ {6.1, 7.2}, {7.2, 8.3} },
{ {4, 3}, {2, 1} },
{ {4, 3}, {2, 1}, {-1, -2}, {3.9, 10} },
{ {1, 3}, {-6, -1}, {-4, -5}, {8, 2}, {-6, -6} }
};
for (auto&& ranges : test_cases) {
print_ranges(std::cout, std::begin(ranges), std::end(ranges));
std::cout << " -> ";
auto i = consolidate_ranges(std::begin(ranges), std::end(ranges));
print_ranges(std::cout, std::begin(ranges), i);
std::cout << '\n';
}
return 0;
}
- Output:
[1.1, 2.2] -> [1.1, 2.2] [6.1, 7.2], [7.2, 8.3] -> [6.1, 8.3] [4, 3], [2, 1] -> [1, 2], [3, 4] [4, 3], [2, 1], [-1, -2], [3.9, 10] -> [-2, -1], [1, 2], [3, 10] [1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6] -> [-6, -1], [1, 8]
Clojure
(defn normalize [r]
(let [[n1 n2] r]
[(min n1 n2) (max n1 n2)]))
(defn touch? [r1 r2]
(let [[lo1 hi1] (normalize r1)
[lo2 hi2] (normalize r2)]
(or (<= lo2 lo1 hi2)
(<= lo2 hi1 hi2))))
(defn consolidate-touching-ranges [rs]
(let [lows (map #(apply min %) rs)
highs (map #(apply max %) rs)]
[ (apply min lows) (apply max highs) ]))
(defn consolidate-ranges [rs]
(loop [res []
rs rs]
(if (empty? rs)
res
(let [r0 (first rs)
touching (filter #(touch? r0 %) rs)
remove-used (fn [rs used]
(remove #(contains? (set used) %) rs))]
(recur (conj res (consolidate-touching-ranges touching))
(remove-used (rest rs) touching))))))
- Output:
(def test-data [ [[1.1 2.2]] [[6.1 7.2] [7.2 8.3]] [[4 3] [2 1]] [[4 3] [2 1] [-1 -2] [3.9 10]] [[1 3] [-6 -1] [-4 -5] [8 2] [-6 -6]] ]) (map consolidate-ranges test-data) ;; ==> ([[1.1 2.2]] [[6.1 8.3]] [[3 4] [1 2]] [[3 10] [1 2] [-2 -1]] [[1 8] [-6 -1] [-5 -4]]))
Dyalect
type Pt(s, e) with Lookup
func Pt.Min() => min(this.s, this.e)
func Pt.Max() => max(this.s, this.e)
func Pt.ToString() => "(\(this.s), \(this.e))"
let rng = [
[ Pt(1.1, 2.2) ],
[ Pt(6.1, 7.2), Pt(7.2, 8.3) ],
[ Pt(4.0, 3.0), Pt(2, 1) ],
[ Pt(4.0, 3.0), Pt(2, 1), Pt(-1, 2), Pt(3.9, 10) ],
[ Pt(1.0, 3.0), Pt(-6, -1), Pt(-4, -5), Pt(8, 2), Pt(-6, -6) ]
]
func overlap(left, right) =>
left.Max() > right.Max() ? right.Max() >= left.Min()
: left.Max() >= right.Min()
func consolidate(left, right) => Pt(min(left.Min(), right.Min()), max(left.Max(), right.Max()))
func normalize(range) => Pt(range.Min(), range.Max())
for list in rng {
var z = list.Length() - 1
while z >= 1 {
for y in (z - 1)^-1..0 when overlap(list[z], list[y]) {
list[y] = consolidate(list[z], list[y])
break list.RemoveAt(z)
}
z -= 1
}
for i in list.Indices() {
list[i] = normalize(list[i])
}
list.Sort((x,y) => x.s - y.s)
print(list)
}
- Output:
[(1.1, 2.2)] [(6.1, 8.3)] [(1, 2), (3, 4)] [(-1, 2), (3, 10)] [(-6, -1), (1, 8)]
EasyLang
proc sort . d[][] .
n = len d[][]
for i = 1 to n - 1
for j = i + 1 to n
if d[j][1] < d[i][1]
swap d[j][] d[i][]
.
.
.
.
func[][] consolidate a[][] .
for i to len a[][]
if a[i][1] > a[i][2]
swap a[i][1] a[i][2]
.
.
sort a[][]
r[][] &= a[1][]
b = a[1][2]
for i = 2 to len a[][]
if a[i][1] > b
r[$][2] = b
r[][] &= a[i][]
b = a[i][2]
else
b = higher b a[i][2]
.
.
r[$][2] = b
return r[][]
.
print consolidate [ [ 1.1 2.2 ] ]
print consolidate [ [ 6.1 7.2 ] [ 7.2 8.3 ] ]
print consolidate [ [ 4 3 ] [ 2 1 ] ]
print consolidate [ [ 4 3 ] [ 2 1 ] [ -1 -2 ] [ 3.9 10 ] ]
print consolidate [ [ 1 3 ] [ -6 -1 ] [ -4 -5 ] [ 8 2 ] [ -6 -6 ] ]
- Output:
[ [ 1.10 2.20 ] ] [ [ 6.10 8.30 ] ] [ [ 1 2 ] [ 3 4 ] ] [ [ -2 -1 ] [ 1 2 ] [ 3 10 ] ] [ [ -6 -1 ] [ 1 8 ] ]
Factor
USING: arrays combinators formatting kernel math.combinatorics
math.order math.statistics sequences sets sorting ;
: overlaps? ( pair pair -- ? )
2dup swap [ [ first2 between? ] curry any? ] 2bi@ or ;
: merge ( seq -- newseq ) concat minmax 2array 1array ;
: merge1 ( seq -- newseq )
dup 2 [ first2 overlaps? ] find-combination
[ [ without ] keep merge append ] when* ;
: normalize ( seq -- newseq ) [ natural-sort ] map ;
: consolidate ( seq -- newseq )
normalize [ merge1 ] to-fixed-point natural-sort ;
{
{ { 1.1 2.2 } }
{ { 6.1 7.2 } { 7.2 8.3 } }
{ { 4 3 } { 2 1 } }
{ { 4 3 } { 2 1 } { -1 -2 } { 3.9 10 } }
{ { 1 3 } { -6 -1 } { -4 -5 } { 8 2 } { -6 -6 } }
} [ dup consolidate "%49u => %u\n" printf ] each
- Output:
{ { 1.1 2.2 } } => { { 1.1 2.2 } } { { 6.1 7.2 } { 7.2 8.300000000000001 } } => { { 6.1 8.300000000000001 } } { { 4 3 } { 2 1 } } => { { 1 2 } { 3 4 } } { { 4 3 } { 2 1 } { -1 -2 } { 3.9 10 } } => { { -2 -1 } { 1 2 } { 3 10 } } { { 1 3 } { -6 -1 } { -4 -5 } { 8 2 } { -6 -6 } } => { { -6 -1 } { 1 8 } }
FreeBASIC
Dim Shared As Integer i
Dim Shared As Single items, temp = 10^30
Sub ordenar(tabla() As Single)
Dim As Integer t1, t2
Dim As Boolean s
Do
s = True
For i = 1 To Ubound(tabla)-1
If tabla(i, 1) > tabla(i+1, 1) Then
t1 = tabla(i, 1) : t2 = tabla(i, 2)
tabla(i, 1) = tabla(i + 1, 1) : tabla(i, 2) = tabla(i + 1, 2)
tabla(i + 1, 1) = t1 : tabla(i + 1, 2) = t2
s = False
End If
Next i
Loop Until(s)
End Sub
Sub normalizar(tabla() As Single)
Dim As Integer t
For i = 1 To Ubound(tabla)
If tabla(i, 1) > tabla(i, 2) Then
t = tabla(i, 1)
tabla(i, 1) = tabla(i, 2)
tabla(i, 2) = t
End If
Next i
ordenar(tabla())
End Sub
Sub consolidar(tabla() As Single)
normalizar(tabla())
For i = 1 To Ubound(tabla)-1
If tabla(i + 1, 1) <= tabla(i, 2) Then
tabla(i + 1, 1) = tabla(i, 1)
If tabla(i + 1, 2) <= tabla(i, 2) Then
tabla(i + 1, 2) = tabla(i, 2)
End If
tabla(i, 1) = temp : tabla(i, 2) = temp
End If
Next i
End Sub
Data 1, 1.1, 2.2
Data 2, 6.1, 7.2, 7.2, 8.3
Data 2, 4, 3, 2, 1
Data 4, 4, 3, 2, 1, -1, -2, 3.9, 10
Data 5, 1,3, -6,-1, -4,-5, 8,2, -6,-6
For j As Byte = 1 To 5
Read items
Dim As Single tabla(items, 2)
For i = 1 To items
Read tabla(i, 1), tabla(i, 2)
Next i
consolidar(tabla())
For i = 1 To items
If tabla(i, 1) <> temp Then Print "[";tabla(i, 1); ", "; tabla(i, 2); "] ";
Next i
Print
Next j
Sleep
Go
package main
import (
"fmt"
"math"
"sort"
)
type Range struct{ Lower, Upper float64 }
func (r Range) Norm() Range {
if r.Lower > r.Upper {
return Range{r.Upper, r.Lower}
}
return r
}
func (r Range) String() string {
return fmt.Sprintf("[%g, %g]", r.Lower, r.Upper)
}
func (r1 Range) Union(r2 Range) []Range {
if r1.Upper < r2.Lower {
return []Range{r1, r2}
}
r := Range{r1.Lower, math.Max(r1.Upper, r2.Upper)}
return []Range{r}
}
func consolidate(rs []Range) []Range {
for i := range rs {
rs[i] = rs[i].Norm()
}
le := len(rs)
if le < 2 {
return rs
}
sort.Slice(rs, func(i, j int) bool {
return rs[i].Lower < rs[j].Lower
})
if le == 2 {
return rs[0].Union(rs[1])
}
for i := 0; i < le-1; i++ {
for j := i + 1; j < le; j++ {
ru := rs[i].Union(rs[j])
if len(ru) == 1 {
rs[i] = ru[0]
copy(rs[j:], rs[j+1:])
rs = rs[:le-1]
le--
i--
break
}
}
}
return rs
}
func main() {
rss := [][]Range{
{{1.1, 2.2}},
{{6.1, 7.2}, {7.2, 8.3}},
{{4, 3}, {2, 1}},
{{4, 3}, {2, 1}, {-1, -2}, {3.9, 10}},
{{1, 3}, {-6, -1}, {-4, -5}, {8, 2}, {-6, -6}},
}
for _, rs := range rss {
s := fmt.Sprintf("%v", rs)
fmt.Printf("%40s => ", s[1:len(s)-1])
rs2 := consolidate(rs)
s = fmt.Sprintf("%v", rs2)
fmt.Println(s[1 : len(s)-1])
}
}
- Output:
[1.1, 2.2] => [1.1, 2.2] [6.1, 7.2] [7.2, 8.3] => [6.1, 8.3] [4, 3] [2, 1] => [1, 2] [3, 4] [4, 3] [2, 1] [-1, -2] [3.9, 10] => [-2, -1] [1, 2] [3, 10] [1, 3] [-6, -1] [-4, -5] [8, 2] [-6, -6] => [-6, -1] [1, 8]
Haskell
import Data.List (intercalate, maximumBy, sort)
import Data.Ord (comparing)
------------------- RANGE CONSOLIDATION ------------------
consolidated :: [(Float, Float)] -> [(Float, Float)]
consolidated = foldr go [] . sort . fmap ab
where
go xy [] = [xy]
go xy@(x, y) abetc@((a, b) : etc)
| y >= b = xy : etc
| y >= a = (x, b) : etc
| otherwise = xy : abetc
ab (a, b)
| a <= b = (a, b)
| otherwise = (b, a)
--------------------------- TEST -------------------------
tests :: [[(Float, Float)]]
tests =
[ [],
[(1.1, 2.2)],
[(6.1, 7.2), (7.2, 8.3)],
[(4, 3), (2, 1)],
[(4, 3), (2, 1), (-1, -2), (3.9, 10)],
[(1, 3), (-6, -1), (-4, -5), (8, 2), (-6, -6)]
]
main :: IO ()
main =
putStrLn $
tabulated
"Range consolidations:"
showPairs
showPairs
consolidated
tests
-------------------- DISPLAY FORMATTING ------------------
tabulated ::
String ->
(a -> String) ->
(b -> String) ->
(a -> b) ->
[a] ->
String
tabulated s xShow fxShow f xs =
let w =
length $
maximumBy
(comparing length)
(xShow <$> xs)
rjust n c s = drop (length s) (replicate n c <> s)
in unlines $
s :
fmap
( ((<>) . rjust w ' ' . xShow)
<*> ((" -> " <>) . fxShow . f)
)
xs
showPairs :: [(Float, Float)] -> String
showPairs xs
| null xs = "[]"
| otherwise =
'[' :
intercalate
", "
(showPair <$> xs)
<> "]"
showPair :: (Float, Float) -> String
showPair (a, b) =
'(' :
showNum a
<> ", "
<> showNum b
<> ")"
showNum :: Float -> String
showNum n
| 0 == (n - fromIntegral (round n)) = show (round n)
| otherwise = show n
- Output:
Range consolidations: [] -> [] [(1.1, 2.2)] -> [(1.1, 2.2)] [(6.1, 7.2), (7.2, 8.3)] -> [(6.1, 8.3)] [(4, 3), (2, 1)] -> [(1, 2), (3, 4)] [(4, 3), (2, 1), (-1, -2), (3.9, 10)] -> [(-2, -1), (1, 2), (3, 10)] [(1, 3), (-6, -1), (-4, -5), (8, 2), (-6, -6)] -> [(-6, -1), (1, 8)]
J
Solution:
ensure2D=: ,:^:(1 = #@$) NB. if list make 1 row table
normalise=: ([: /:~ /:~"1)@ensure2D NB. normalises list of ranges
merge=: ,:`(<.&{. , >.&{:)@.(>:/&{: |.) NB. merge ranges x and y
consolidate=: (}.@] ,~ (merge {.)) ensure2D
Required Examples:
tests=: <@".;._2 noun define
1.1 2.2
6.1 7.2 ,: 7.2 8.3
4 3 ,: 2 1
4 3 , 2 1 , _1 _2 ,: 3.9 10
1 3 , _6 _1 , _4 _5 , 8 2 ,: _6 _6
)
consolidate/@normalise&.> tests
+-------+-------+---+-----+-----+
|1.1 2.2|6.1 8.3|1 2|_2 _1|_6 _1|
| | |3 4| 1 2| 1 8|
| | | | 3 10| |
+-------+-------+---+-----+-----+
Java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class RangeConsolidation {
public static void main(String[] args) {
displayRanges( Arrays.asList(new Range(1.1, 2.2)));
displayRanges( Arrays.asList(new Range(6.1, 7.2), new Range(7.2, 8.3)));
displayRanges( Arrays.asList(new Range(4, 3), new Range(2, 1)));
displayRanges( Arrays.asList(new Range(4, 3), new Range(2, 1), new Range(-1, -2), new Range(3.9, 10)));
displayRanges( Arrays.asList(new Range(1, 3), new Range(-6, -1), new Range(-4, -5), new Range(8, 2), new Range(-6, -6)));
displayRanges( Arrays.asList(new Range(1, 1), new Range(1, 1)));
displayRanges( Arrays.asList(new Range(1, 1), new Range(1, 2)));
displayRanges( Arrays.asList(new Range(1, 2), new Range(3, 4), new Range(1.5, 3.5), new Range(1.2, 2.5)));
}
private static final void displayRanges(List<Range> ranges) {
System.out.printf("ranges = %-70s, colsolidated = %s%n", ranges, Range.consolidate(ranges));
}
private static final class RangeSorter implements Comparator<Range> {
@Override
public int compare(Range o1, Range o2) {
return (int) (o1.left - o2.left);
}
}
private static class Range {
double left;
double right;
public Range(double left, double right) {
if ( left <= right ) {
this.left = left;
this.right = right;
}
else {
this.left = right;
this.right = left;
}
}
public Range consolidate(Range range) {
// no overlap
if ( this.right < range.left ) {
return null;
}
// no overlap
if ( range.right < this.left ) {
return null;
}
// contained
if ( this.left <= range.left && this.right >= range.right ) {
return this;
}
// contained
if ( range.left <= this.left && range.right >= this.right ) {
return range;
}
// overlap
if ( this.left <= range.left && this.right <= range.right ) {
return new Range(this.left, range.right);
}
// overlap
if ( this.left >= range.left && this.right >= range.right ) {
return new Range(range.left, this.right);
}
throw new RuntimeException("ERROR: Logic invalid.");
}
@Override
public String toString() {
return "[" + left + ", " + right + "]";
}
private static List<Range> consolidate(List<Range> ranges) {
List<Range> consolidated = new ArrayList<>();
Collections.sort(ranges, new RangeSorter());
for ( Range inRange : ranges ) {
Range r = null;
Range conRange = null;
for ( Range conRangeLoop : consolidated ) {
r = inRange.consolidate(conRangeLoop);
if (r != null ) {
conRange = conRangeLoop;
break;
}
}
if ( r == null ) {
consolidated.add(inRange);
}
else {
consolidated.remove(conRange);
consolidated.add(r);
}
}
Collections.sort(consolidated, new RangeSorter());
return consolidated;
}
}
}
- Output:
Required and other examples.
ranges = [[1.1, 2.2]] , consolidated = [[1.1, 2.2]] ranges = [[6.1, 7.2], [7.2, 8.3]] , consolidated = [[6.1, 8.3]] ranges = [[1.0, 2.0], [3.0, 4.0]] , consolidated = [[1.0, 2.0], [3.0, 4.0]] ranges = [[-2.0, -1.0], [1.0, 2.0], [3.0, 4.0], [3.9, 10.0]] , consolidated = [[-2.0, -1.0], [1.0, 2.0], [3.0, 10.0]] ranges = [[-6.0, -1.0], [-6.0, -6.0], [-5.0, -4.0], [1.0, 3.0], [2.0, 8.0]] , consolidated = [[-6.0, -1.0], [1.0, 8.0]] ranges = [[1.0, 1.0], [1.0, 1.0]] , consolidated = [[1.0, 1.0]] ranges = [[1.0, 1.0], [1.0, 2.0]] , consolidated = [[1.0, 2.0]] ranges = [[1.0, 2.0], [1.5, 3.5], [1.2, 2.5], [3.0, 4.0]] , consolidated = [[1.0, 4.0]]
JavaScript
(() => {
'use strict';
const main = () => {
// consolidated :: [(Float, Float)] -> [(Float, Float)]
const consolidated = xs =>
foldl((abetc, xy) =>
0 < abetc.length ? (() => {
const
etc = abetc.slice(1),
[a, b] = abetc[0],
[x, y] = xy;
return y >= b ? (
cons(xy, etc)
) : y >= a ? (
cons([x, b], etc)
) : cons(xy, abetc);
})() : [xy],
[],
sortBy(flip(comparing(fst)),
map(([a, b]) => a < b ? (
[a, b]
) : [b, a],
xs
)
)
);
// TEST -------------------------------------------
console.log(
tabulated(
'Range consolidations:',
JSON.stringify,
JSON.stringify,
consolidated,
[
[
[1.1, 2.2]
],
[
[6.1, 7.2],
[7.2, 8.3]
],
[
[4, 3],
[2, 1]
],
[
[4, 3],
[2, 1],
[-1, -2],
[3.9, 10]
],
[
[1, 3],
[-6, -1],
[-4, -5],
[8, 2],
[-6, -6]
]
]
)
);
};
// GENERIC FUNCTIONS ----------------------------
// comparing :: (a -> b) -> (a -> a -> Ordering)
const comparing = f =>
(x, y) => {
const
a = f(x),
b = f(y);
return a < b ? -1 : (a > b ? 1 : 0);
};
// compose (<<<) :: (b -> c) -> (a -> b) -> a -> c
const compose = (f, g) => x => f(g(x));
// cons :: a -> [a] -> [a]
const cons = (x, xs) => [x].concat(xs);
// flip :: (a -> b -> c) -> b -> a -> c
const flip = f =>
1 < f.length ? (
(a, b) => f(b, a)
) : (x => y => f(y)(x));
// foldl :: (a -> b -> a) -> a -> [b] -> a
const foldl = (f, a, xs) => xs.reduce(f, a);
// fst :: (a, b) -> a
const fst = tpl => tpl[0];
// justifyRight :: Int -> Char -> String -> String
const justifyRight = (n, cFiller, s) =>
n > s.length ? (
s.padStart(n, cFiller)
) : s;
// Returns Infinity over objects without finite length.
// This enables zip and zipWith to choose the shorter
// argument when one is non-finite, like cycle, repeat etc
// length :: [a] -> Int
const length = xs =>
(Array.isArray(xs) || 'string' === typeof xs) ? (
xs.length
) : Infinity;
// map :: (a -> b) -> [a] -> [b]
const map = (f, xs) =>
(Array.isArray(xs) ? (
xs
) : xs.split('')).map(f);
// maximumBy :: (a -> a -> Ordering) -> [a] -> a
const maximumBy = (f, xs) =>
0 < xs.length ? (
xs.slice(1)
.reduce((a, x) => 0 < f(x, a) ? x : a, xs[0])
) : undefined;
// sortBy :: (a -> a -> Ordering) -> [a] -> [a]
const sortBy = (f, xs) =>
xs.slice()
.sort(f);
// tabulated :: String -> (a -> String) ->
// (b -> String) ->
// (a -> b) -> [a] -> String
const tabulated = (s, xShow, fxShow, f, xs) => {
// Heading -> x display function ->
// fx display function ->
// f -> values -> tabular string
const
ys = map(xShow, xs),
w = maximumBy(comparing(x => x.length), ys).length,
rows = zipWith(
(a, b) => justifyRight(w, ' ', a) + ' -> ' + b,
ys,
map(compose(fxShow, f), xs)
);
return s + '\n' + unlines(rows);
};
// take :: Int -> [a] -> [a]
// take :: Int -> String -> String
const take = (n, xs) =>
'GeneratorFunction' !== xs.constructor.constructor.name ? (
xs.slice(0, n)
) : [].concat.apply([], Array.from({
length: n
}, () => {
const x = xs.next();
return x.done ? [] : [x.value];
}));
// unlines :: [String] -> String
const unlines = xs => xs.join('\n');
// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
const zipWith = (f, xs, ys) => {
const
lng = Math.min(length(xs), length(ys)),
as = take(lng, xs),
bs = take(lng, ys);
return Array.from({
length: lng
}, (_, i) => f(as[i], bs[i], i));
};
// MAIN ---
return main();
})();
- Output:
Range consolidations: [[1.1,2.2]] -> [[1.1,2.2]] [[6.1,7.2],[7.2,8.3]] -> [[6.1,8.3]] [[4,3],[2,1]] -> [[1,2],[3,4]] [[4,3],[2,1],[-1,-2],[3.9,10]] -> [[-2,-1],[1,2],[3,10]] [[1,3],[-6,-1],[-4,-5],[8,2],[-6,-6]] -> [[-6,-1],[1,8]]
jq
Works with gojq, the Go implementation of jq
def normalize: map(sort) | sort;
def consolidate:
normalize
| length as $length
| reduce range(0; $length) as $i (.;
.[$i] as $r1
| if $r1 != []
then reduce range($i+1; $length) as $j (.;
.[$j] as $r2
| if $r2 != [] and ($r1[-1] >= $r2[0]) # intersect?
then .[$i] = [$r1[0], ([$r1[-1], $r2[-1]]|max)]
| .[$j] = []
else .
end )
else .
end )
| map(select(. != [])) ;
def testranges:
[[1.1, 2.2]],
[[6.1, 7.2], [7.2, 8.3]],
[[4, 3], [2, 1]],
[[4, 3], [2, 1], [-1, -2], [3.9, 10]],
[[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6]]
| "\(.) => \(consolidate)"
;
testranges
- Output:
[[1.1,2.2]] => [[1.1,2.2]] [[6.1,7.2],[7.2,8.3]] => [[6.1,8.3]] [[4,3],[2,1]] => [[1,2],[3,4]] [[4,3],[2,1],[-1,-2],[3.9,10]] => [[-2,-1],[1,2],[3,10]] [[1,3],[-6,-1],[-4,-5],[8,2],[-6,-6]] => [[-6,-1],[-5,-4],[1,8]]
Julia
In Julia, a Range is a type of iterator, generally one over a specified interval. The task as specified is orthogonal to the iteration purpose of a Julia Range, since the task is about merging sets of numbers, not iterations. Therefore, a translation of the Python code is done, rather than using a native Julia Range.
normalize(s) = sort([sort(bounds) for bounds in s])
function consolidate(ranges)
norm = normalize(ranges)
for (i, r1) in enumerate(norm)
if !isempty(r1)
for r2 in norm[i+1:end]
if !isempty(r2) && r1[end] >= r2[1] # intersect?
r1 .= [r1[1], max(r1[end], r2[end])]
empty!(r2)
end
end
end
end
[r for r in norm if !isempty(r)]
end
function testranges()
for s in [[[1.1, 2.2]], [[6.1, 7.2], [7.2, 8.3]], [[4, 3], [2, 1]],
[[4, 3], [2, 1], [-1, -2], [3.9, 10]],
[[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6]]]
println("$s => $(consolidate(s))")
end
end
testranges()
- Output:
Array{Float64,1}[[1.1, 2.2]] => Array{Float64,1}[[1.1, 2.2]] Array{Float64,1}[[6.1, 7.2], [7.2, 8.3]] => Array{Float64,1}[[6.1, 8.3]] Array{Float64,1}[[4.0, 3.0], [2.0, 1.0]] => Array{Float64,1}[[1.0, 2.0], [3.0, 4.0]] Array{Float64,1}[[4.0, 3.0], [2.0, 1.0], [-1.0, -2.0], [3.9, 10.0]] => Array{Float64,1}[[-2.0, -1.0], [1.0, 2.0], [3.0, 10.0]] Array{Float64,1}[[1.0, 3.0], [-6.0, -1.0], [-4.0, -5.0], [8.0, 2.0], [-6.0, -6.0]] => Array{Float64,1}[[-6.0, -1.0], [1.0, 8.0]]
Kotlin
fun <T> consolidate(ranges: Iterable<ClosedRange<T>>): List<ClosedRange<T>> where T : Comparable<T>
{
return ranges
.sortedWith(compareBy({ it.start }, { it.endInclusive }))
.asReversed()
.fold(mutableListOf<ClosedRange<T>>()) {
consolidatedRanges, range ->
if (consolidatedRanges.isEmpty())
{
consolidatedRanges.add(range)
}
// Keep in mind the reverse-sorting applied above:
// If the end of the current-range is higher, than it must start at a lower value,
else if (range.endInclusive >= consolidatedRanges[0].endInclusive)
{
consolidatedRanges[0] = range
}
else if (range.endInclusive >= consolidatedRanges[0].start)
{
consolidatedRanges[0] = range.start .. consolidatedRanges[0].endInclusive
}
else
{
consolidatedRanges.add(0, range)
}
return@fold consolidatedRanges
}
.toList()
}
// What a bummer! Kotlin's range syntax (a..b) doesn't meet the task requirements when b < b,
// and on the other hand, the syntax for constructing lists, arrays and pairs isn't close enough
// to the range notation. Instead then, here's a *very* naive parser. Don't take it seriously.
val rangeRegex = Regex("""\[(.+),(.+)\]""")
fun parseDoubleRange(rangeStr: String): ClosedFloatingPointRange<Double> {
val parts = rangeRegex
.matchEntire(rangeStr)
?.groupValues
?.drop(1)
?.map { it.toDouble() }
?.sorted()
if (parts == null) throw IllegalArgumentException("Unable to parse range $rangeStr")
return parts[0] .. parts[1]
}
fun serializeRange(range: ClosedRange<*>) = "[${range.start}, ${range.endInclusive}]"
// See above. In practice you'd probably use consolidate directly
fun consolidateDoubleRanges(rangeStrings: Iterable<String>): List<String>
{
return consolidate(rangeStrings.asSequence().map(::parseDoubleRange).toList()).map(::serializeRange)
}
fun main() {
val inputRanges = listOf(
listOf("[1.1, 2.2]"),
listOf("[6.1, 7.2]", "[7.2, 8.3]"),
listOf("[4, 3]", "[2, 1]"),
listOf("[4, 3]", "[2, 1]", "[-1, -2]", "[3.9, 10]"),
listOf("[1, 3]", "[-6, -1]", "[-4, -5]", "[8, 2]", "[-6, -6]")
)
inputRanges.associateBy(Any::toString, ::consolidateDoubleRanges).forEach({ println("${it.key} => ${it.value}") })
}
- Output:
[[1.1, 2.2]] => [[1.1, 2.2]] [[6.1, 7.2], [7.2, 8.3]] => [[6.1, 8.3]] [[4, 3], [2, 1]] => [[1.0, 2.0], [3.0, 4.0]] [[4, 3], [2, 1], [-1, -2], [3.9, 10]] => [[-2.0, -1.0], [1.0, 2.0], [3.0, 10.0]] [[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6]] => [[-6.0, -1.0], [1.0, 8.0]]
Mathematica /Wolfram Language
Using the Wolfram Language's built-in Interval operations:
data={{{1.1,2.2}},
{{6.1,7.2},{7.2,8.3}},
{{4,3},{2,1}},
{{4,3},{2,1},{-1,-2},{3.9,10}},
{{1,3},{-6,-1},{-4,-5},{8,2},{-6,-6}}};
Column[IntervalUnion@@@Map[Interval,data,{2}]]
- Output:
Interval[{1.1,2.2}] Interval[{6.1,8.3}] Interval[{1,2},{3,4}] Interval[{-2,-1},{1,2},{3,10}] Interval[{-6,-1},{1,8}]
newLISP
(define (norm range) (sort range))
(define (overlap? a b) (>= (a 1) (b 0)))
(define (combine)
(list ($args 0 0) (max ($args 1 1) ($args 0 1))))
(define (foo ranges)
(set 'ranges (map norm ranges))
(set 'ranges (sort ranges))
(let (accum '() item)
(dolist (r ranges)
(set 'item (cond ((empty? accum) r)
((overlap? (accum 0) r)
(combine (pop accum) r))
(true r)))
(push item accum))
(reverse accum)))
(foo '((1.1 2.2)))
((1.1 2.2))
(foo '((6.1 7.2) (7.2 8.3)))
((6.1 8.300000000000001))
(foo '((4 3) (2 1)))
((1 2) (3 4))
(foo '((4 3) (2 1) (-1 -2) (3.9 10)))
((-2 -1) (1 2) (3 10))
(foo '((1 3) (-6 -1) (-4 -5) (8 2) (-6 -6)))
((-6 -1) (1 8))
Nim
import algorithm, strutils
# Definition of a range of values of type T.
type Range[T] = array[2, T]
proc `<`(a, b: Range): bool {.inline.} =
## Check if range "a" is less than range "b". Needed for sorting.
if a[0] == b[0]:
a[1] < b[1]
else:
a[0] < b[0]
proc consolidate[T](rangeList: varargs[Range[T]]): seq[Range[T]] =
## Consolidate a list of ranges of type T.
# Build a sorted list of normalized ranges.
var list: seq[Range[T]]
for item in rangeList:
list.add if item[0] <= item[1]: item else: [item[1], item[0]]
list.sort()
# Build the consolidated list starting from "smallest" range.
result.add list[0]
for i in 1..list.high:
let rangeMin = result[^1]
let rangeMax = list[i]
if rangeMax[0] <= rangeMin[1]:
result[^1] = [rangeMin[0], max(rangeMin[1], rangeMax[1])]
else:
result.add rangeMax
proc `$`[T](r: Range[T]): string {.inline.} =
# Return the string representation of a range.
when T is SomeFloat:
"[$1, $2]".format(r[0].formatFloat(ffDecimal, 1), r[1].formatFloat(ffDecimal, 1))
else:
"[$1, $2]".format(r[0], r[1])
proc `$`[T](s: seq[Range[T]]): string {.inline.} =
## Return the string representation of a sequence of ranges.
s.join(", ")
when isMainModule:
proc test[T](rangeList: varargs[Range[T]]) =
echo ($(@rangeList)).alignLeft(52), "→ ", consolidate(rangeList)
test([1.1, 2.2])
test([6.1, 7.2], [7.2, 8.3])
test([4, 3], [2, 1])
test([4.0, 3.0], [2.0, 1.0], [-1.0, -2.0], [3.9, 10.0])
test([1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6])
- Output:
[1.1, 2.2] → [1.1, 2.2] [6.1, 7.2], [7.2, 8.3] → [6.1, 8.3] [4, 3], [2, 1] → [1, 2], [3, 4] [4.0, 3.0], [2.0, 1.0], [-1.0, -2.0], [3.9, 10.0] → [-2.0, -1.0], [1.0, 2.0], [3.0, 10.0] [1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6] → [-6, -1], [1, 8]
Perl
Note: the output is shown in the standard Perl notation for Ranges.
use strict;
use warnings;
use List::Util qw(min max);
sub consolidate {
our @arr; local *arr = shift;
my @sorted = sort { @$a[0] <=> @$b[0] } map { [sort { $a <=> $b } @$_] } @arr;
my @merge = shift @sorted;
for my $i (@sorted) {
if ($merge[-1][1] >= @$i[0]) {
$merge[-1][0] = min($merge[-1][0], @$i[0]);
$merge[-1][1] = max($merge[-1][1], @$i[1]);
} else {
push @merge, $i;
}
}
return @merge;
}
for my $intervals (
[[1.1, 2.2],],
[[6.1, 7.2], [7.2, 8.3]],
[[4, 3], [2, 1]],
[[4, 3], [2, 1], [-1, -2], [3.9, 10]],
[[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6]]) {
my($in,$out);
$in = join ', ', map { '[' . join(', ', @$_) . ']' } @$intervals;
$out .= join('..', @$_). ' ' for consolidate($intervals);
printf "%44s => %s\n", $in, $out;
}
- Output:
[1.1, 2.2] => 1.1..2.2 [6.1, 7.2], [7.2, 8.3] => 6.1..8.3 [4, 3], [2, 1] => 1..2 3..4 [4, 3], [2, 1], [-1, -2], [3.9, 10] => -2..-1 1..2 3..10 [1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6] => -6..-1 1..8
Phix
with javascript_semantics function consolidate(sequence sets) integer l = length(sets) sequence res = repeat(0,l) for i=1 to l do atom {rs,re} = sets[i] res[i] = iff(rs>re?{re,rs}:{rs,re}) end for for i=l to 1 by -1 do atom {il,ih} = res[i] for j=l to i+1 by -1 do atom {jl,jh} = res[j] bool overlap = iff(il<=jl?jl<=ih:il<=jh) if overlap then {il,ih} = {min(il,jl),max(ih,jh)} res[j] = res[l] l -= 1 end if end for res[i] = {il,ih} end for res = sort(res[1..l]) return res end function procedure test(sequence set) printf(1,"%40v => %v\n",{set,consolidate(set)}) end procedure test({{1.1,2.2}}) test({{6.1,7.2},{7.2,8.3}}) test({{4,3},{2,1}}) test({{4,3},{2,1},{-1,-2},{3.9,10}}) test({{1,3},{-6,-1},{-4,-5},{8,2},{-6,-6}})
- Output:
{{1.1,2.2}} => {{1.1,2.2}} {{6.1,7.2},{7.2,8.3}} => {{6.1,8.3}} {{4,3},{2,1}} => {{1,2},{3,4}} {{4,3},{2,1},{-1,-2},{3.9,10}} => {{-2,-1},{1,2},{3,10}} {{1,3},{-6,-1},{-4,-5},{8,2},{-6,-6}} => {{-6,-1},{1,8}}
Prolog
consolidate_ranges(Ranges, Consolidated):-
normalize(Ranges, Normalized),
sort(Normalized, Sorted),
merge(Sorted, Consolidated).
normalize([], []):-!.
normalize([r(X, Y)|Ranges], [r(Min, Max)|Normalized]):-
(X > Y -> Min = Y, Max = X; Min = X, Max = Y),
normalize(Ranges, Normalized).
merge([], []):-!.
merge([Range], [Range]):-!.
merge([r(Min1, Max1), r(Min2, Max2)|Rest], Merged):-
Min2 =< Max1,
!,
Max is max(Max1, Max2),
merge([r(Min1, Max)|Rest], Merged).
merge([Range|Ranges], [Range|Merged]):-
merge(Ranges, Merged).
write_range(r(Min, Max)):-
writef('[%w, %w]', [Min, Max]).
write_ranges([]):-!.
write_ranges([Range]):-
!,
write_range(Range).
write_ranges([Range|Ranges]):-
write_range(Range),
write(', '),
write_ranges(Ranges).
test_case([r(1.1, 2.2)]).
test_case([r(6.1, 7.2), r(7.2, 8.3)]).
test_case([r(4, 3), r(2, 1)]).
test_case([r(4, 3), r(2, 1), r(-1, -2), r(3.9, 10)]).
test_case([r(1, 3), r(-6, -1), r(-4, -5), r(8, 2), r(-6, -6)]).
main:-
forall(test_case(Ranges),
(consolidate_ranges(Ranges, Consolidated),
write_ranges(Ranges), write(' -> '),
write_ranges(Consolidated), nl)).
- Output:
[1.1, 2.2] -> [1.1, 2.2] [6.1, 7.2], [7.2, 8.3] -> [6.1, 8.3] [4, 3], [2, 1] -> [1, 2], [3, 4] [4, 3], [2, 1], [-1, -2], [3.9, 10] -> [-2, -1], [1, 2], [3, 10] [1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6] -> [-6, -1], [1, 8]
Python
Procedural
def normalize(s):
return sorted(sorted(bounds) for bounds in s if bounds)
def consolidate(ranges):
norm = normalize(ranges)
for i, r1 in enumerate(norm):
if r1:
for r2 in norm[i+1:]:
if r2 and r1[-1] >= r2[0]: # intersect?
r1[:] = [r1[0], max(r1[-1], r2[-1])]
r2.clear()
return [rnge for rnge in norm if rnge]
if __name__ == '__main__':
for s in [
[[1.1, 2.2]],
[[6.1, 7.2], [7.2, 8.3]],
[[4, 3], [2, 1]],
[[4, 3], [2, 1], [-1, -2], [3.9, 10]],
[[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6]],
]:
print(f"{str(s)[1:-1]} => {str(consolidate(s))[1:-1]}")
- Output:
[1.1, 2.2] => [1.1, 2.2] [6.1, 7.2], [7.2, 8.3] => [6.1, 8.3] [4, 3], [2, 1] => [1, 2], [3, 4] [4, 3], [2, 1], [-1, -2], [3.9, 10] => [-2, -1], [1, 2], [3, 10] [1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6] => [-6, -1], [1, 8]
Functional
Defining consolidation as a fold over a list of tuples:
'''Range consolidation'''
from functools import reduce
# consolidated :: [(Float, Float)] -> [(Float, Float)]
def consolidated(xs):
'''A consolidated list of
[(Float, Float)] ranges.'''
def go(abetc, xy):
'''A copy of the accumulator abetc,
with its head range ab either:
1. replaced by or
2. merged with
the next range xy, or
with xy simply prepended.'''
if abetc:
a, b = abetc[0]
etc = abetc[1:]
x, y = xy
return [xy] + etc if y >= b else ( # ab replaced.
[(x, b)] + etc if y >= a else ( # xy + ab merged.
[xy] + abetc # xy simply prepended.
)
)
else:
return [xy]
def tupleSort(ab):
a, b = ab
return ab if a <= b else (b, a)
return reduce(
go,
sorted(map(tupleSort, xs), reverse=True),
[]
)
# TEST ----------------------------------------------------
# main :: IO ()
def main():
'''Tests'''
print(
tabulated('Consolidation of numeric ranges:')(str)(str)(
consolidated
)([
[(1.1, 2.2)],
[(6.1, 7.2), (7.2, 8.3)],
[(4, 3), (2, 1)],
[(4, 3), (2, 1), (-1, -2), (3.9, 10)],
[(1, 3), (-6, -1), (-4, -5), (8, 2), (-6, -6)]
])
)
# GENERIC FUNCTIONS FOR DISPLAY ---------------------------
# compose (<<<) :: (b -> c) -> (a -> b) -> a -> c
def compose(g):
'''Right to left function composition.'''
return lambda f: lambda x: g(f(x))
# tabulated :: String -> (a -> String) ->
# (b -> String) ->
# (a -> b) -> [a] -> String
def tabulated(s):
'''Heading -> x display function -> fx display function ->
f -> value list -> tabular string.'''
def go(xShow, fxShow, f, xs):
w = max(map(compose(len)(xShow), xs))
return s + '\n' + '\n'.join([
xShow(x).rjust(w, ' ') + ' -> ' + fxShow(f(x)) for x in xs
])
return lambda xShow: lambda fxShow: (
lambda f: lambda xs: go(
xShow, fxShow, f, xs
)
)
# MAIN ---
if __name__ == '__main__':
main()
- Output:
Consolidation of numeric ranges: [(1.1, 2.2)] -> [(1.1, 2.2)] [(6.1, 7.2), (7.2, 8.3)] -> [(6.1, 8.3)] [(4, 3), (2, 1)] -> [(1, 2), (3, 4)] [(4, 3), (2, 1), (-1, -2), (3.9, 10)] -> [(-2, -1), (1, 2), (3, 10)] [(1, 3), (-6, -1), (-4, -5), (8, 2), (-6, -6)] -> [(-6, -1), (1, 8)]
Racket
#lang racket
;; Racket's max and min allow inexact numbers to contaminate exact numbers
;; Use argmax and argmin instead, as they don't have this problem
(define (max . xs) (argmax identity xs))
(define (min . xs) (argmin identity xs))
;; a bag is a list of disjoint intervals
(define ((irrelevant? x y) item) (or (< (second item) x) (> (first item) y)))
(define (insert bag x y)
(define-values (irrelevant relevant) (partition (irrelevant? x y) bag))
(cons (list (apply min x (map first relevant))
(apply max y (map second relevant))) irrelevant))
(define (solve xs)
(sort (for/fold ([bag '()]) ([x (in-list xs)])
(insert bag (apply min x) (apply max x))) < #:key first))
(define inputs '(([1.1 2.2])
([6.1 7.2] [7.2 8.3])
([4 3] [2 1])
([4 3] [2 1] [-1 -2] [3.9 10])
([1 3] [-6 -1] [-4 -5] [8 2] [-6 -6])))
(for ([xs (in-list inputs)]) (printf "~a => ~a\n" xs (solve xs)))
- Output:
((1.1 2.2)) => ((1.1 2.2)) ((6.1 7.2) (7.2 8.3)) => ((6.1 8.3)) ((4 3) (2 1)) => ((1 2) (3 4)) ((4 3) (2 1) (-1 -2) (3.9 10)) => ((-2 -1) (1 2) (3 10)) ((1 3) (-6 -1) (-4 -5) (8 2) (-6 -6)) => ((-6 -1) (1 8))
Raku
(formerly Perl 6)
In Raku, a Range is a first class object with its own specialized notation. Raku Ranges allow for exclusion of the boundary numbers. This example doesn't since it isn't a requirement in this task. Much of the logic is lifted from the Set_of_real_numbers task with simplified logic for the much simpler requirements.
Note: the output is in standard Raku notation for Ranges.
# Union
sub infix:<∪> (Range $a, Range $b) { Range.new($a.min,max($a.max,$b.max)) }
# Intersection
sub infix:<∩> (Range $a, Range $b) { so $a.max >= $b.min }
multi consolidate() { () }
multi consolidate($this is copy, **@those) {
gather {
for consolidate |@those -> $that {
if $this ∩ $that { $this ∪= $that }
else { take $that }
}
take $this;
}
}
for [[1.1, 2.2],],
[[6.1, 7.2], [7.2, 8.3]],
[[4, 3], [2, 1]],
[[4, 3], [2, 1], [-1, -2], [3.9, 10]],
[[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6]]
-> @intervals {
printf "%46s => ", @intervals.raku;
say reverse consolidate |@intervals.grep(*.elems)».sort.sort({ [.[0], .[*-1]] }).map: { Range.new(.[0], .[*-1]) }
}
- Output:
[[1.1, 2.2],] => (1.1..2.2) [[6.1, 7.2], [7.2, 8.3]] => (6.1..8.3) [[4, 3], [2, 1]] => (1..2 3..4) [[4, 3], [2, 1], [-1, -2], [3.9, 10]] => (-2..-1 1..2 3..10) [[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6]] => (-6..-1 1..8)
REXX
Most of the REXX code was testing (and rebuilding) the syntax (insuring blanks after commas), and handling of a null set.
The actual logic for the range consolidation is marked with the comments: /*■■■■►*/
/*REXX program performs range consolidation (they can be [equal] ascending/descending). */
#.= /*define the default for range sets. */
parse arg #.1 /*obtain optional arguments from the CL*/
if #.1='' then do /*Not specified? Then use the defaults*/
#.1= '[1.1, 2.2]'
#.2= '[6.1, 7.2], [7.2, 8.3]'
#.3= '[4, 3], [2, 1]'
#.4= '[4, 3], [2, 1], [-1, -2], [3.9, 10]'
#.5= '[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6]'
#.6= '[]'
end
do j=1 while #.j\==''; $= #.j /*process each of the range sets. */
say copies('═', 75) /*display a fence between range sets. */
say ' original ranges:' $ /*display the original range set. */
$= order($) /*order low and high ranges; normalize.*/
call xSort words($) /*sort the ranges using a simple sort. */
$= merge($) /*consolidate the ranges. */
say ' consolidated ranges:' $ /*display the consolidated range set. */
end /*j*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
merge: procedure expose @.; parse arg y
if words(y)<2 then signal build /*Null or only 1 range? Skip merging. */
do j=1 to @.0-1; if @.j=='' then iterate /*skip deleted ranges.*/
do k=j+1 to @.0; if @.k=='' then iterate /* " " " */
parse var @.j a b; parse var @.k aa bb /*extract low and high*/
/*■■■■►*/ if a<=aa & b>=bb then do; @.k=; iterate; end /*within a range*/
/*■■■■►*/ if a<=aa & b>=aa then do; @.j= a bb; @.k=; iterate; end /*abutted ranges*/
end /*k*/
end /*j*/
build: z=
do r=1 for @.0; z= z translate(@.r, ',', " "); end /*r*/ /*add comma*/
f=; do s=1 for words(z); f= f '['word(z, s)"], "; end /*s*/ /*add [ ], */
if f=='' then return '[]' /*null set.*/
return space( changestr(',', strip( space(f), 'T', ","), ", ") ) /*add blank*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
order: procedure expose @.; parse arg y,,z; @.= /*obtain arguments from the invocation.*/
y= space(y, 0) /*elide superfluous blanks in the sets.*/
do k=1 while y\=='' & y\=='[]' /*process ranges while range not blank.*/
y= strip(y, 'L', ",") /*elide commas between sets of ranges. */
parse var y '[' L "," H ']' y /*extract the "low" and "high" values.*/
if H<L then parse value L H with H L /*order " " " " " */
L= L / 1; H= H / 1 /*normalize the L and the H values.*/
@.k= L H; z= z L','H /*re─build the set w/o and with commas.*/
end /*k*/ /* [↓] at this point, K is one to big.*/
@.0= k - 1 /*keep track of the number of ranges. */
return strip(z) /*elide the extra leading blank in set.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
xSort: procedure expose @.; parse arg n /*a simple sort for small set of ranges*/
do j=1 to n-1; _= @.j
do k=j+1 to n; if word(@.k,1)>=word(_,1) then iterate; @.j=@.k; @.k=_; _=@.j
end /*k*/
end /*j*/; return
- output when using the default inputs:
═══════════════════════════════════════════════════════════════════════════ original ranges: [1.1, 2.2] consolidated ranges: [1.1, 2.2] ═══════════════════════════════════════════════════════════════════════════ original ranges: [6.1, 7.2], [7.2, 8.3] consolidated ranges: [6.1, 8.3] ═══════════════════════════════════════════════════════════════════════════ original ranges: [4, 3], [2, 1] consolidated ranges: [1, 2], [3, 4] ═══════════════════════════════════════════════════════════════════════════ original ranges: [4, 3], [2, 1], [-1, -2], [3.9, 10] consolidated ranges: [-2, -1], [1, 2], [3, 10] ═══════════════════════════════════════════════════════════════════════════ original ranges: [1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6] consolidated ranges: [-6, -1], [1, 8] ═══════════════════════════════════════════════════════════════════════════ original ranges: [] consolidated ranges: []
RPL
« 1 OVER SIZE FOR j j DUP2 GET V→ IF DUP2 > THEN SWAP END →V2 PUT NEXT » RNGNORM' STO « LIST→ → len « len 1 FOR n 1 n 1 - START DUP2 - DUP 1 GET SWAP V→ IFTE IF 0 > THEN SWAP END n ROLLD NEXT n ROLLD -1 STEP len →LIST » » 'RNGSORT' STO « RNGNORM IF DUP SIZE 2 ≥ THEN RNGSORT → ranges « { } ranges 1 GET 2 ranges SIZE FOR j ranges j GET IF OVER 2 GET OVER 1 GET ≥ THEN SWAP V→ ROT V→ SWAP DROP MAX →V2 ELSE ROT ROT + SWAP END NEXT + » END » 'RNGCONSO' STO
{ { [1.1, 2.2] }
{ [6.1, 7.2] [7.2, 8.3] }
{ [4 3] [2 1] }
{ [4 3] [2 1] [-1, -2] [3.9 10] }
{ [1 3] [-6 -1] [-4 -5] [8 2] [-6 -6]} }
1 « RNGCONSO » DOLIST
- Output:
1: { { [ 1.1 2.2 ] } { [ 6.1 8.3 ] } { [ 1 2 ] [ 3 4 ] } { [ -2 -1 ] [ 1 2 ] [ 3 10 ] } { [ -6 -1 ] [ 1 8 ] } }
Rust
Most of the implementation below belongs to the test and formatting support. If the output might be more arbitrary, the source would be quite small. The algorithm relies on normalizing the ranges and folding a sorted sequence of them.
use std::fmt::{Display, Formatter};
// We could use std::ops::RangeInclusive, but we would have to extend it to
// normalize self (not much trouble) and it would not have to handle pretty
// printing for it explicitly. So, let's make rather an own type.
#[derive(Clone, Debug, PartialEq, PartialOrd)]
pub struct ClosedRange<Idx> {
start: Idx,
end: Idx,
}
impl<Idx> ClosedRange<Idx> {
pub fn start(&self) -> &Idx {
&self.start
}
pub fn end(&self) -> &Idx {
&self.end
}
}
impl<Idx: PartialOrd> ClosedRange<Idx> {
pub fn new(start: Idx, end: Idx) -> Self {
if start <= end {
Self { start, end }
} else {
Self {
end: start,
start: end,
}
}
}
}
// To make test input more compact
impl<Idx: PartialOrd> From<(Idx, Idx)> for ClosedRange<Idx> {
fn from((start, end): (Idx, Idx)) -> Self {
Self::new(start, end)
}
}
// For the required print format
impl<Idx: Display> Display for ClosedRange<Idx> {
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
write!(f, "[{}, {}]", self.start, self.end)
}
}
fn consolidate<Idx>(a: &ClosedRange<Idx>, b: &ClosedRange<Idx>) -> Option<ClosedRange<Idx>>
where
Idx: PartialOrd + Clone,
{
if a.start() <= b.start() {
if b.end() <= a.end() {
Some(a.clone())
} else if a.end() < b.start() {
None
} else {
Some(ClosedRange::new(a.start().clone(), b.end().clone()))
}
} else {
consolidate(b, a)
}
}
fn consolidate_all<Idx>(mut ranges: Vec<ClosedRange<Idx>>) -> Vec<ClosedRange<Idx>>
where
Idx: PartialOrd + Clone,
{
// Panics for incomparable elements! So no NaN for floats, for instance.
ranges.sort_by(|a, b| a.partial_cmp(b).unwrap());
let mut ranges = ranges.into_iter();
let mut result = Vec::new();
if let Some(current) = ranges.next() {
let leftover = ranges.fold(current, |mut acc, next| {
match consolidate(&acc, &next) {
Some(merger) => {
acc = merger;
}
None => {
result.push(acc);
acc = next;
}
}
acc
});
result.push(leftover);
}
result
}
#[cfg(test)]
mod tests {
use super::{consolidate_all, ClosedRange};
use std::fmt::{Display, Formatter};
struct IteratorToDisplay<F>(F);
impl<F, I> Display for IteratorToDisplay<F>
where
F: Fn() -> I,
I: Iterator,
I::Item: Display,
{
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
let mut items = self.0();
if let Some(item) = items.next() {
write!(f, "{}", item)?;
for item in items {
write!(f, ", {}", item)?;
}
}
Ok(())
}
}
macro_rules! parameterized {
($($name:ident: $value:expr,)*) => {
$(
#[test]
fn $name() {
let (input, expected) = $value;
let expected: Vec<_> = expected.into_iter().map(ClosedRange::from).collect();
let output = consolidate_all(input.into_iter().map(ClosedRange::from).collect());
println!("{}: {}", stringify!($name), IteratorToDisplay(|| output.iter()));
assert_eq!(expected, output);
}
)*
}
}
parameterized! {
single: (vec![(1.1, 2.2)], vec![(1.1, 2.2)]),
touching: (vec![(6.1, 7.2), (7.2, 8.3)], vec![(6.1, 8.3)]),
disjoint: (vec![(4, 3), (2, 1)], vec![(1, 2), (3, 4)]),
overlap: (vec![(4.0, 3.0), (2.0, 1.0), (-1.0, -2.0), (3.9, 10.0)], vec![(-2.0, -1.0), (1.0, 2.0), (3.0, 10.0)]),
integer: (vec![(1, 3), (-6, -1), (-4, -5), (8, 2), (-6, -6)], vec![(-6, -1), (1, 8)]),
}
}
fn main() {
// To prevent dead code and to check empty input
consolidate_all(Vec::<ClosedRange<usize>>::new());
println!("Run: cargo test -- --nocapture");
}
- Output:
running 5 tests integer: [-6, -1], [1, 8] disjoint: [1, 2], [3, 4] single: [1.1, 2.2] touching: [6.1, 8.3] overlap: [-2, -1], [1, 2], [3, 10] test tests::integer ... ok test tests::disjoint ... ok test tests::single ... ok test tests::touching ... ok test tests::overlap ... ok test result: ok. 5 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
SQL
This is not a particularly efficient solution, but it gets the job done.
/*
This code is an implementation of "Range consolidation" in SQL ORACLE 19c
p_list_of_sets -- input string
delimeter by default "|"
*/
with
function range_consolidation(p_list_of_sets in varchar2)
return varchar2 is
--
v_list_of_sets varchar2(32767) := p_list_of_sets;
v_output varchar2(32767);
v_set_1 varchar2(2000);
v_set_2 varchar2(2000);
v_pos_set_1 pls_integer;
v_pos_set_2 pls_integer;
v_set_1_min number;
v_set_1_max number;
v_set_2_min number;
v_set_2_max number;
--
function sort_set(p_in_str varchar2)
return varchar2 is
v_out varchar2(32767) := p_in_str;
begin
--
with out_tab as
(select to_number(regexp_substr(str, '[^,]+', 1, rownum, 'c', 0)) elem
from
(select p_in_str as str
from dual
)
connect by level <= regexp_count(str, '[^,]+')
)
select min(elem)||','||max(elem) end
into v_out
from out_tab;
--
return v_out;
end;
--
function sort_output(p_in_str varchar2)
return varchar2 is
v_out varchar2(32767) := p_in_str;
begin
--
with out_tab as
(select to_number(regexp_substr(regexp_substr(str, '[^|]+', 1, rownum, 'c', 0), '[^,]+', 1, 1)) low_range
, regexp_substr(str, '[^|]+', 1, rownum, 'c', 0) range_def
from
(select p_in_str as str
from dual
)
connect by level <= regexp_count(str, '[^|]+')
)
select listagg(range_def, '|') within group(order by low_range)
into v_out
from out_tab;
--
return v_out;
end;
--
begin
--
execute immediate ('alter session set NLS_NUMERIC_CHARACTERS = ''.,''');
--
--cleaning
v_list_of_sets := ltrim(v_list_of_sets, '[');
v_list_of_sets := rtrim(v_list_of_sets, ']');
v_list_of_sets := replace(v_list_of_sets, ' ', '');
--set delimeter "|"
v_list_of_sets := regexp_replace(v_list_of_sets, '\]\,\[', '|', 1, 0);
--
<<loop_through_sets>>
while regexp_count(v_list_of_sets, '[^|]+') > 0
loop
v_set_1 := regexp_substr(v_list_of_sets, '[^|]+', 1, 1);
v_list_of_sets := regexp_replace(v_list_of_sets, v_set_1, sort_set(v_set_1), 1, 1);
v_set_1 := sort_set(v_set_1);
v_pos_set_1 := regexp_instr(v_list_of_sets, '[^|]+', 1, 1);
--
v_set_1_min := least(to_number(regexp_substr(v_set_1, '[^,]+', 1, 1)),to_number(regexp_substr(v_set_1, '[^,]+', 1, 2)));
v_set_1_max := greatest(to_number(regexp_substr(v_set_1, '[^,]+', 1, 1)),to_number(regexp_substr(v_set_1, '[^,]+', 1, 2)));
--
<<loop_for>>
for i in 1..regexp_count(v_list_of_sets, '[^|]+')-1
loop
--
v_set_2 := regexp_substr(v_list_of_sets, '[^|]+', 1, i+1);
v_list_of_sets := regexp_replace(v_list_of_sets, v_set_2, sort_set(v_set_2), 1, 1);
v_set_2 := sort_set(v_set_2);
v_pos_set_2 := regexp_instr(v_list_of_sets, '[^|]+', 1, i+1);
v_set_2_min := least(to_number(regexp_substr(v_set_2, '[^,]+', 1, 1)),to_number(regexp_substr(v_set_2, '[^,]+', 1, 2)));
v_set_2_max := greatest(to_number(regexp_substr(v_set_2, '[^,]+', 1, 1)),to_number(regexp_substr(v_set_2, '[^,]+', 1, 2)));
--
if greatest(v_set_1_min,v_set_2_min)-least(v_set_1_max,v_set_2_max) <= 0 then --overlapping
v_list_of_sets := regexp_replace(v_list_of_sets, v_set_1, ''||least(v_set_1_min,v_set_2_min)||','||greatest(v_set_1_max,v_set_2_max),v_pos_set_1,1);
v_list_of_sets := regexp_replace(v_list_of_sets, v_set_2, '', v_pos_set_2, 1);
continue loop_through_sets;
end if;
--
end loop loop_for;
--
v_output := ltrim(v_output||'|'||least(v_set_1_min,v_set_1_max)||', '||greatest(v_set_1_min,v_set_1_max),'|');
--
v_output := sort_output(v_output);
v_list_of_sets := regexp_replace(v_list_of_sets,v_set_1,'',1,1);
--
end loop loop_through_sets;
--
return '['||replace(v_output,'|','], [')||']';
end;
--Test
select lpad('[]',50) || ' ==> ' || range_consolidation('[]') as output from dual
union all
select lpad('[],[]',50) || ' ==> ' || range_consolidation('[],[]') as output from dual
union all
select lpad('[],[1,1]',50) || ' ==> ' || range_consolidation('[],[1,1]') as output from dual
union all
select lpad('[1.3]',50) || ' ==> ' || range_consolidation('[1.3]') as output from dual
union all
select lpad('[2,2],[1]',50) || ' ==> ' || range_consolidation('[2,2],[1]') as output from dual
union all
select lpad('[4,-1,0,1,5,7,7,7],[9,6,9,6,9]',50) || ' ==> ' || range_consolidation('[4,-1,0,1,5,7,7,7],[9,6,9,6,9]') as output from dual
union all
--Test RosettaCode
select '-- Test RosettaCode' as output from dual
union all
select lpad('[1.1, 2.2]',50) || ' ==> ' || range_consolidation('[1.1, 2.2]') as output from dual
union all
select lpad('[6.1, 7.2], [7.2, 8.3]',50) || ' ==> ' || range_consolidation('[6.1, 7.2], [7.2, 8.3]') as output from dual
union all
select lpad('[4, 3], [2, 1]',50) || ' ==> ' || range_consolidation('[4, 3], [2, 1]') as output from dual
union all
select lpad('[4, 3], [2, 1], [-1, -2], [3.9, 10]',50) || ' ==> ' || range_consolidation('[4, 3], [2, 1], [-1, -2], [3.9, 10]') as output from dual
union all
select lpad('[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6]',50) || ' ==> ' || range_consolidation('[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6]') as output from dual
union all
select lpad('1,3|-6,-1|-4,-5|8,2|-6,-6',50) || ' ==> ' || range_consolidation('1,3|-6,-1|-4,-5|8,2|-6,-6') as output from dual
/
;
/
- Output:
[] ==> [] [],[] ==> [] [],[1,1] ==> [1, 1] [1.3] ==> [1.3, 1.3] [2,2],[1] ==> [1, 1], [2, 2] [4,-1,0,1,5,7,7,7],[9,6,9,6,9] ==> [-1, 9] -- Test RosettaCode [1.1, 2.2] ==> [1.1, 2.2] [6.1, 7.2], [7.2, 8.3] ==> [6.1, 8.3] [4, 3], [2, 1] ==> [1, 2], [3, 4] [4, 3], [2, 1], [-1, -2], [3.9, 10] ==> [-2, -1], [1, 2], [3, 10] [1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6] ==> [-6, -1], [1, 8] 1,3|-6,-1|-4,-5|8,2|-6,-6 ==> [-6, -1], [1, 8]
Wren
As Wren already has a built-in Range class (which is not quite the same as what's required here), we create a Span class instead.
class Span {
construct new(r) {
if (r.type != Range || !r.isInclusive) Fiber.abort("Argument must be an inclusive range.")
_low = r.from
_high = r.to
if (_low > _high) {
_low = r.to
_high = r.from
}
}
low { _low }
high { _high }
consolidate(r) {
if (r.type != Span) Fiber.abort("Argument must be a Span.")
if (_high < r.low) return [this, r]
if (r.high < _low) return [r, this]
return [Span.new(_low.min(r.low).._high.max(r.high))]
}
toString { "[%(_low), %(_high)]" }
}
var spanLists = [
[Span.new(1.1..2.2)],
[Span.new(6.1..7.2), Span.new(7.2..8.3)],
[Span.new(4..3), Span.new(2..1)],
[Span.new(4..3), Span.new(2..1), Span.new(-1..-2), Span.new(3.9..10)],
[Span.new(1..3), Span.new(-6..-1), Span.new(-4..-5), Span.new(8..2), Span.new(-6..-6)]
]
for (spanList in spanLists) {
if (spanList.count == 1) {
System.print(spanList.toString[1..-2])
} else if (spanList.count == 2) {
System.print(spanList[0].consolidate(spanList[1]).toString[1..-2])
} else {
var first = 0
while (first < spanList.count-1) {
var next = first + 1
while (next < spanList.count) {
var res = spanList[first].consolidate(spanList[next])
spanList[first] = res[0]
if (res.count == 2) {
spanList[next] = res[1]
next = next + 1
} else {
spanList.removeAt(next)
}
}
first = first + 1
}
System.print(spanList.toString[1..-2])
}
}
- Output:
[1.1, 2.2] [6.1, 8.3] [1, 2], [3, 4] [-2, -1], [1, 2], [3, 10] [-6, -1], [1, 8]
Yabasic
sub sort(tabla())
local items, i, t1, t2, s
items = arraysize(tabla(), 1)
repeat
s = true
for i = 1 to items-1
if tabla(i, 1) > tabla(i+1, 1) then
t1 = tabla(i, 1) : t2 = tabla(i, 2)
tabla(i, 1) = tabla(i + 1, 1) : tabla(i, 2) = tabla(i + 1, 2)
tabla(i + 1, 1) = t1 : tabla(i + 1, 2) = t2
s = false
end if
next
until(s)
end sub
sub normalize(tabla())
local items, i, t
items = arraysize(tabla(), 1)
for i = 1 to items
if tabla(i, 1) > tabla(i, 2) then
t = tabla(i, 1)
tabla(i, 1) = tabla(i, 2)
tabla(i, 2) = t
end if
next
sort(tabla())
end sub
sub consolidate(tabla())
local items, i
normalize(tabla())
items = arraysize(tabla(), 1)
for i = 1 to items - 1
if tabla(i + 1, 1) <= tabla(i, 2) then
tabla(i + 1, 1) = tabla(i, 1)
if tabla(i + 1, 2) <= tabla(i, 2) then
tabla(i + 1, 2) = tabla(i, 2)
end if
tabla(i, 1) = void : tabla(i, 2) = void
end if
next
end sub
// data 1, 1.1, 2.2
// data 2, 6.1, 7.2, 7.2, 8.3
// data 2, 4, 3, 2, 1
// data 4, 4, 3, 2, 1, -1, -2, 3.9, 10
data 5, 1,3, -6,-1, -4,-5, 8,2, -6,-6
void = 10^30
read items
dim tabla(items, 2)
for i = 1 to items
read tabla(i, 1), tabla(i, 2)
next
consolidate(tabla())
for i = 1 to items
if tabla(i, 1) <> void print tabla(i, 1), "..", tabla(i, 2);
next
zkl
fcn consolidate(rs){
(s:=List()).append(
normalize(rs).reduce('wrap(ab,cd){
if(ab[1]>=cd[0]) L(ab[0],ab[1].max(cd[1])); // consolidate
else{ s.append(ab); cd } // no overlap
}) )
}
fcn normalize(s){ s.apply("sort").sort(fcn(a,b){ a[0]<b[0] }) }
foreach rs in (L(
L(L(1.1, 2.2)), L(L(6.1, 7.2), L(7.2, 8.3)), L(L(4, 3), L(2, 1)),
L(L(4.0, 3.0), L(2.0, 1.0), L(-1.0, -2.0), L(3.9, 10.0)),
L(L(1, 3), L(-6, -1), L(-4, -5), L(8, 2), L(-6, -6)),
)){ println(ppp(rs),"--> ",ppp(consolidate(rs))) }
fcn ppp(ll){ ll.pump(String,fcn(list){ list.concat(", ", "[", "] ") }) }
- Output:
[1.1, 2.2] --> [1.1, 2.2] [6.1, 7.2] [7.2, 8.3] --> [6.1, 8.3] [4, 3] [2, 1] --> [1, 2] [3, 4] [4, 3] [2, 1] [-1, -2] [3.9, 10] --> [-2, -1] [1, 2] [3, 10] [1, 3] [-6, -1] [-4, -5] [8, 2] [-6, -6] --> [-6, -1] [1, 8]