Range consolidation

From Rosetta Code
Revision as of 04:12, 4 February 2019 by Hout (talk | contribs) (→‎Functional: Edited lambda, updated output)
Range consolidation is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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

Works with: Rakudo version 2018.12

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) }

  1. 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)

  1. 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]]
   )
   
  1. 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]