Range consolidation
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 element 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 normalised 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 output here.
Go
<lang 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{
Template: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])
}
}</lang>
- 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]
Perl 6
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 allow for excluded boundaries since that wasn't a requirement in this task. Much of the logic is lifted from Set_of_real_numbers with simplified logic for the much simpler requirements.
Note: the output is in standard Perl 6 notation for Ranges.
<lang perl6># Union sub infix:<∪> (Range $a, Range $b) { Range.new($a.min,$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.perl;
say reverse consolidate |@intervals».sort.sort({ [.[0], .[1]] }).map: { Range.new(.[0], .[1]) }
}</lang>
- 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
<lang python>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]}")
</lang>
- 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: <lang python>from functools import (reduce)
- consolidated :: [(Float, Float)] -> [(Float, Float)]
def consolidated(xs):
ys = sorted(map(tupleSort, xs), reverse=True)
return reduce(
lambda a, x: [(x[0], max(x[1], a[0][1]))] + a[1:] if (
x[1] >= a[0][0]
) else [x] + a,
ys[1:],
[ys[0]]
)
- tupleSort :: (a, a) -> (a, a)
def tupleSort(ab): a, b = ab return ab if a <= b else (b, a)
if __name__ == '__main__':
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)]
]
for x in tests:
print (
str(x) + '\n\t-> ' + str(consolidated(x)) + '\n'
)</lang>
- 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)]
zkl
<lang 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] }) }</lang> <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(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(", ", "[", "] ") }) }</lang>
- 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]