Range modifications: Difference between revisions
(Emphasis) |
|||
| Line 12: | Line 12: | ||
contain the integers 13 14 22 100999999 101000000 and 101000001.<br> |
contain the integers 13 14 22 100999999 101000000 and 101000001.<br> |
||
Empty ranges are removed. An empty sequence has an empty string representation. |
Empty ranges are removed. An empty sequence has an empty string representation. |
||
Note: There are NO internal spaces in the sequence format. |
|||
;Task: |
;Task: |
||
Revision as of 05:24, 24 October 2020
The increasing range of all integers from a lower to an upper bound, including
each boundary, is shown by the lower-boundary separated from the
higher-boundary by a single dash. So 64-1234 is the range of all integers
from 64 to 1234, (including both 64 and 1234). 10-10 is the range covering
the single integer 10.
A sequence of ranges is shown by successive integer ranges that do not overlap,
and which have increasing lower bounds. Each range is separated by a single
comma. So 13-14,22-22,100999999-101000001 is a sequence of ranges that
contain the integers 13 14 22 100999999 101000000 and 101000001.
Empty ranges are removed. An empty sequence has an empty string representation.
Note: There are NO internal spaces in the sequence format.
- Task
Given an initial sequence of ranges write programs to add or remove an integer
from the sequence and display the resultant sequence.
Note:
- The initial sequence may be empty.
- Adding an int that is already covered should not change the sequence.
- removing an int that is not in the sequence should not change the sequence.
- The add and remove operations should print their result in the standard form mentioned.
- Solutions must work by modifying range boundaries, splitting and joining, as well as creating and deleting ranges.
Do not use algorithms that create and modify arrays of all the integer values within ranges.
Show the results, (including intermediate results), of performing the following steps
- Ex0
Start with ""
add 77
add 79
add 78
remove 77
remove 78
remove 79
- Ex1
Start with "1-3,5-5"
add 1
remove 4
add 7
add 8
add 6
remove 7
- Ex2
Start with "1-5,10-25,27-30"
add 26
add 9
add 7
remove 26
remove 9
remove 7
Go
<lang go>package main
import (
"fmt" "strings"
)
type rng struct{ from, to int }
type fn func(rngs *[]rng, n int)
func (r rng) String() string { return fmt.Sprintf("%d-%d", r.from, r.to) }
func rangesAdd(rngs []rng, n int) []rng {
if len(rngs) == 0 {
rngs = append(rngs, rng{n, n})
return rngs
}
for i, r := range rngs {
if n < r.from-1 {
rngs = append(rngs, rng{})
copy(rngs[i+1:], rngs[i:])
rngs[i] = rng{n, n}
return rngs
} else if n == r.from-1 {
rngs[i] = rng{n, r.to}
return rngs
} else if n <= r.to {
return rngs
} else if n == r.to+1 {
rngs[i] = rng{r.from, n}
if i < len(rngs)-1 && (n == rngs[i+1].from || n+1 == rngs[i+1].from) {
rngs[i] = rng{r.from, rngs[i+1].to}
copy(rngs[i+1:], rngs[i+2:])
rngs[len(rngs)-1] = rng{}
rngs = rngs[:len(rngs)-1]
}
return rngs
} else if i == len(rngs)-1 {
rngs = append(rngs, rng{n, n})
return rngs
}
}
return rngs
}
func rangesRemove(rngs []rng, n int) []rng {
if len(rngs) == 0 {
return rngs
}
for i, r := range rngs {
if n <= r.from-1 {
return rngs
} else if n == r.from && n == r.to {
copy(rngs[i:], rngs[i+1:])
rngs[len(rngs)-1] = rng{}
rngs = rngs[:len(rngs)-1]
return rngs
} else if n == r.from {
rngs[i] = rng{n + 1, r.to}
return rngs
} else if n < r.to {
rngs[i] = rng{r.from, n - 1}
rngs = append(rngs, rng{})
copy(rngs[i+2:], rngs[i+1:])
rngs[i+1] = rng{n + 1, r.to}
return rngs
} else if n == r.to {
rngs[i] = rng{r.from, n - 1}
return rngs
}
}
return rngs
}
func standard(rngs []rng) string {
if len(rngs) == 0 {
return ""
}
var sb strings.Builder
for _, r := range rngs {
sb.WriteString(fmt.Sprintf("%s,", r))
}
s := sb.String()
return s[:len(s)-1]
}
func main() {
const add = 0
const remove = 1
fns := []fn{
func(prngs *[]rng, n int) {
*prngs = rangesAdd(*prngs, n)
fmt.Printf(" add %2d => %s\n", n, standard(*prngs))
},
func(prngs *[]rng, n int) {
*prngs = rangesRemove(*prngs, n)
fmt.Printf(" remove %2d => %s\n", n, standard(*prngs))
},
}
var rngs []rng
ops := [][2]int{{add, 77}, {add, 79}, {add, 78}, {remove, 77}, {remove, 78}, {remove, 79}}
fmt.Printf("Start: %q\n", standard(rngs))
for _, op := range ops {
fns[op[0]](&rngs, op[1])
}
rngs = []rng{{1, 3}, {5, 5}}
ops = [][2]int{{add, 1}, {remove, 4}, {add, 7}, {add, 8}, {add, 6}, {remove, 7}}
fmt.Printf("\nStart: %q\n", standard(rngs))
for _, op := range ops {
fns[op[0]](&rngs, op[1])
}
rngs = []rng{{1, 5}, {10, 25}, {27, 30}}
ops = [][2]int{{add, 26}, {add, 9}, {add, 7}, {remove, 26}, {remove, 9}, {remove, 7}}
fmt.Printf("\nStart: %q\n", standard(rngs))
for _, op := range ops {
fns[op[0]](&rngs, op[1])
}
}</lang>
- Output:
Start: ""
add 77 => 77-77
add 79 => 77-77,79-79
add 78 => 77-79
remove 77 => 78-79
remove 78 => 79-79
remove 79 =>
Start: "1-3,5-5"
add 1 => 1-3,5-5
remove 4 => 1-3,5-5
add 7 => 1-3,5-5,7-7
add 8 => 1-3,5-5,7-8
add 6 => 1-3,5-8
remove 7 => 1-3,5-6,8-8
Start: "1-5,10-25,27-30"
add 26 => 1-5,10-30
add 9 => 1-5,9-30
add 7 => 1-5,7-7,9-30
remove 26 => 1-5,7-7,9-25,27-30
remove 9 => 1-5,7-7,10-25,27-30
remove 7 => 1-5,10-25,27-30
Julia
Julia has iterator classes called a type of Range, such as integer UnitRanges, that are like the "10-10" of the task but are stated as 10:10, with a colon not a minus sign. This implementation uses Julia's UnitRange class internally. <lang julia>import Base.string, Base.parse, Base.print
const RangeSequence = Array{UnitRange, 1}
function combine!(seq::RangeSequence, r2)
if isempty(seq)
push!(seq, r2)
else
r1 = seq[end]
if r1.start > r2.start
r1, r2 = r2, r1
end
if r2.stop > r1.stop
if r2.start <= r1.stop + 1
seq[end] = r1.start:r2.stop
else
push!(seq, r2)
end
end
end
return seq
end
function parse(::Type{RangeSequence}, s)
seq = UnitRange[]
entries = split(s, r"\s*,\s*")
for e in entries
startstop = split(e, r"\:|\-")
if length(startstop) == 2
start = tryparse(Int, startstop[1])
stop = tryparse(Int, startstop[2])
if start != nothing && stop != nothing
combine!(seq, start:stop)
end
elseif (n = tryparse(Int, startstop[1])) != nothing
combine!(seq, n:n)
end
end
return seq
end
function insertinteger!(seq, n::Integer)
isempty(seq) && return push!(seq, n:n)
pos = findlast(x -> x.start <= n, seq)
if pos == nothing
if seq[1].start - n > 1
pushfirst!(seq, n:n)
else
r = popfirst!(seq)
pushfirst!(seq, UnitRange(n:r.stop))
end
else
newseq = vcat(combine!(seq[1:pos], n:n), seq[pos+1:end])
empty!(seq)
append!(seq, newseq)
end
return seq
end
reduce(rangeseq) = begin seq = UnitRange[]; for r in rangeseq combine!(seq, r) end; seq end
function removeinteger!(seq, n::Integer)
pos = findlast(x -> x.start <= n, seq)
if pos != nothing
r1, r2 = seq[pos].start, seq[pos].stop
if r1 == r2 == n
deleteat!(seq, pos:pos)
elseif r2 == n
seq[pos] = r1:r2-1
elseif r1 == n
seq[pos] = r1+1:r2
elseif r1 < n < r2
seq[pos] = n+1:r2
insert!(seq, pos, r1:n-1)
end
end
return seq
end
function string(r::UnitRange, weird=true)
r1, r2 = r.start, r.stop weird && return "$r1-$r2" return r1 == r2 ? "$r1" : abs(r1 - r2) > 1 ? "$r1-$r2" : "$r1, $r2"
end
print(io::IO, seq::RangeSequence) = print(io, join(map(string, reduce(seq)), ", "))
const seq = parse(RangeSequence, "")
println("Start: \"\"")
insertinteger!(seq, 77)
println(" added 77 => ", seq)
insertinteger!(seq, 79)
println(" added 79 => ", seq)
insertinteger!(seq, 78)
println(" added 78 => ", seq)
removeinteger!(seq, 77)
println(" removed 77 => ", seq)
removeinteger!(seq, 78)
println(" removed 78 => ", seq)
removeinteger!(seq, 79)
println(" removed 79 => ", seq, "\n")
const seq2 = parse(RangeSequence, "1-3, 5-5") println("Start: $seq2") insertinteger!(seq2, 1) println(" added 1 => ", seq2) removeinteger!(seq2, 4) println(" removed 4 => ", seq2) insertinteger!(seq2, 7) println(" added 7 => ", seq2) insertinteger!(seq2, 8) println(" added 8 => ", seq2) insertinteger!(seq2, 6) println(" added 6 => ", seq2) removeinteger!(seq2, 7) println(" removed 7 => ", seq2, "\n")
const seq3 = parse(RangeSequence, "1-5, 10-25, 27-30") println("Start: $seq3") insertinteger!(seq3, 26) println(" added 26 => ", seq3) insertinteger!(seq3, 9) println(" added 9 => ", seq3) insertinteger!(seq3, 7) println(" added 7 => ", seq3) removeinteger!(seq3, 26) println(" removed 26 => ", seq3) removeinteger!(seq3, 9) println(" removed 9 => ", seq3) removeinteger!(seq3, 7) println(" removed 7 => ", seq3)
</lang>
- Output:
Start: ""
added 77 => 77-77
added 79 => 77-77, 79-79
added 78 => 77-79
removed 77 => 78-79
removed 78 => 79-79
removed 79 =>
Start: 1-3, 5-5
added 1 => 1-3, 5-5
removed 4 => 1-3, 5-5
added 7 => 1-3, 5-5, 7-7
added 8 => 1-3, 5-5, 7-8
added 6 => 1-3, 5-8
removed 7 => 1-3, 5-6, 8-8
Start: 1-5, 10-25, 27-30
added 26 => 1-5, 10-30
added 9 => 1-5, 9-30
added 7 => 1-5, 7-7, 9-30
removed 26 => 1-5, 7-7, 9-25, 27-30
removed 9 => 1-5, 7-7, 10-25, 27-30
removed 7 => 1-5, 10-25, 27-30
Phix
<lang Phix>requires("0.8.2") -- (uses latest apply() functionality)
function add(sequence ranges, integer v) -- -- eg {} + 9 --> Template:9,9 -- [1] -- Template:3,5 + 9 --> {{3,5},{9,9}} -- [1] -- Template:3,5 + 4 --> as-is -- [2] -- Template:3,5 + 2 --> Template:2,5 -- [3] -- {{3,5},{7,9}} + 6 --> Template:3,9 -- [4] -- {{3,5},{8,9}} + 6 --> {{3,6},{8,9}} -- [5] -- {{3,5},{8,9}} + 7 --> {{3,5},{7,9}} -- [3] -- Template:3,5 + 6 --> Template:3,6 -- [6] -- Template:3,5 + 1 --> {{1,1},{3,5}} -- [7] --
integer l = length(ranges)
for i=1 to l+1 do
if i>l then ranges &= Template:V,v exit -- [1]
end if
integer {lo,hi} = ranges[i], nl
if v>=lo and v<=hi then exit -- [2]
elsif v=lo-1 then ranges[i][1] = v exit -- [3]
elsif v=hi+1 then
if i<l then
{nl,hi} = ranges[i+1]
if nl=v+1 then
ranges[i..i+1] = Template:Lo,hi exit -- [4]
else
ranges[i][2] = v exit -- [5]
end if
else
ranges[i][2] = v exit -- [6]
end if
elsif v<lo then ranges[i..i-1] = Template:V,v exit -- [7]
end if
end for
return ranges
end function
function del(sequence ranges, integer v) -- -- eg Template:1,2 - 1 --> Template:2,2 -- [1] -- Template:2,2 - 2 --> {} -- [2] -- Template:1,2 - 2 --> Template:1,1 -- [3] -- Template:1,3 - 2 --> {{1,1},{3,3}} -- [4] -- Template:2,3 - 1 --> as-is -- [5] --
for i=1 to length(ranges) do
integer {lo,hi} = ranges[i]
if v>=lo and v<=hi then
if v=lo then
if v<hi then ranges[i][1] = lo+1 -- [1]
else ranges[i..i] = {} end if -- [2]
elsif v==hi then ranges[i][2] = hi-1 -- [3]
else ranges[i..i] = {{lo,v-1},{v+1,hi}} -- [4]
end if exit
elsif v<hi then exit end if -- [5]
end for
return ranges
end function
constant tests = split(""" Start with ""
add 77 add 79 add 78 remove 77 remove 78 remove 79
Start with "1-3,5-5"
add 1 remove 4 add 7 add 8 add 6 remove 7
Start with "1-5,10-25,27-30"
add 26 add 9 add 7 remove 26 remove 9 remove 7
""","\n",no_empty:=true)
string range = "" sequence ranges -- range internal form for i=1 to length(tests) do
string ti = tests[i]
if match("Start with",ti) then
Template:Range = scanf(ti,"Start with \"%s\"")
printf(1,"\nNew start range: \"%s\"\n",{range})
ranges = split(range,",")
ranges = vslice(apply(true,scanf,{ranges,{"%d-%d"}}),1)
else
Template:String op, integer v = scanf(trim(ti),"%s %d")
integer rid = routine_id(substitute(op,"remove","del"))
ranges = rid(ranges,v)
range = join(apply(true,sprintf,{{"%d-%d"},ranges}),",")
printf(1," %9s %2d -> \"%s\"\n",{op,v,range})
end if
end for</lang>
- Output:
(Note that all double-quotes in the output were deliberately added in the last two printf() statements, mainly to prove there are no unnecessary spaces, etc, and obviously would be trivial to remove.)
New start range: ""
add 77 -> "77-77"
add 79 -> "77-77,79-79"
add 78 -> "77-79"
remove 77 -> "78-79"
remove 78 -> "79-79"
remove 79 -> ""
New start range: "1-3,5-5"
add 1 -> "1-3,5-5"
remove 4 -> "1-3,5-5"
add 7 -> "1-3,5-5,7-7"
add 8 -> "1-3,5-5,7-8"
add 6 -> "1-3,5-8"
remove 7 -> "1-3,5-6,8-8"
New start range: "1-5,10-25,27-30"
add 26 -> "1-5,10-30"
add 9 -> "1-5,9-30"
add 7 -> "1-5,7-7,9-30"
remove 26 -> "1-5,7-7,9-25,27-30"
remove 9 -> "1-5,7-7,10-25,27-30"
remove 7 -> "1-5,10-25,27-30"
Python
<lang python>class Sequence():
def __init__(self, sequence_string):
self.ranges = self.to_ranges(sequence_string)
assert self.ranges == sorted(self.ranges), "Sequence order error"
def to_ranges(self, txt):
return [[int(x) for x in r.strip().split('-')]
for r in txt.strip().split(',') if r]
def remove(self, rem):
ranges = self.ranges
for i, r in enumerate(ranges):
if r[0] <= rem <= r[1]:
if r[0] == rem: # range min
if r[1] > rem:
r[0] += 1
else:
del ranges[i]
elif r[1] == rem: # range max
if r[0] < rem:
r[1] -= 1
else:
del ranges[i]
else: # inside, range extremes.
r[1], splitrange = rem - 1, [rem + 1, r[1]]
ranges.insert(i + 1, splitrange)
break
if r[0] > rem: # Not in sorted list
break
return self
def add(self, add):
ranges = self.ranges
for i, r in enumerate(ranges):
if r[0] <= add <= r[1]: # already included
break
elif r[0] - 1 == add: # rough extend to here
r[0] = add
break
elif r[1] + 1 == add: # rough extend to here
r[1] = add
break
elif r[0] > add: # rough insert here
ranges.insert(i, [add, add])
break
else:
ranges.append([add, add])
return self
return self.consolidate()
def consolidate(self):
"Combine overlapping ranges"
ranges = self.ranges
for this, that in zip(ranges, ranges[1:]):
if this[1] + 1 >= that[0]: # Ranges interract
if this[1] >= that[1]: # this covers that
this[:], that[:] = [], this
else: # that extends this
this[:], that[:] = [], [this[0], that[1]]
ranges[:] = [r for r in ranges if r]
return self
def __repr__(self):
rr = self.ranges
return ",".join(f"{r[0]}-{r[1]}" for r in rr)
def demo(opp_txt):
by_line = opp_txt.strip().split('\n')
start = by_line.pop(0)
ex = Sequence(start.strip().split()[-1][1:-1]) # Sequence("1-3,5-5")
lines = [line.strip().split() for line in by_line]
opps = [((ex.add if word[0] == "add" else ex.remove), int(word[1]))
for word in lines]
print(f"Start: \"{ex}\"")
for op, val in opps:
print(f" {op.__name__:>6} {val:2} => {op(val)}")
print()
if __name__ == '__main__':
demo("""
Start with ""
add 77
add 79
add 78
remove 77
remove 78
remove 79
""")
demo("""
Start with "1-3,5-5"
add 1
remove 4
add 7
add 8
add 6
remove 7
""")
demo("""
Start with "1-5,10-25,27-30"
add 26
add 9
add 7
remove 26
remove 9
remove 7
""")
</lang>
- Output:
Start: ""
add 77 => 77-77
add 79 => 77-77,79-79
add 78 => 77-79
remove 77 => 78-79
remove 78 => 79-79
remove 79 =>
Start: "1-3,5-5"
add 1 => 1-3,5-5
remove 4 => 1-3,5-5
add 7 => 1-3,5-5,7-7
add 8 => 1-3,5-5,7-8
add 6 => 1-3,5-8
remove 7 => 1-3,5-6,8-8
Start: "1-5,10-25,27-30"
add 26 => 1-5,10-30
add 9 => 1-5,9-30
add 7 => 1-5,7-7,9-30
remove 26 => 1-5,7-7,9-25,27-30
remove 9 => 1-5,7-7,10-25,27-30
remove 7 => 1-5,10-25,27-30
Wren
<lang ecmascript>import "/fmt" for Fmt
var rangesAdd = Fn.new { |ranges, n|
if (ranges.count == 0) {
ranges.add(n..n)
return
}
for (i in 0...ranges.count) {
var r = ranges[i]
if (n < r.from - 1) {
ranges.insert(i, n..n)
return
} else if (n == r.from-1) {
ranges[i] = n..r.to
return
} else if (n <= r.to) {
return
} else if (n == r.to+1) {
ranges[i] = r.from..n
if (i < ranges.count - 1 && (n == ranges[i+1].from || n + 1 == ranges[i+1].from)) {
ranges[i] = r.from..ranges[i+1].to
ranges.removeAt(i+1)
}
return
} else if (i == ranges.count - 1) {
ranges.add(n..n)
return
}
}
}
var rangesRemove = Fn.new { |ranges, n|
if (ranges.count == 0) return
for (i in 0...ranges.count) {
var r = ranges[i]
if (n <= r.from - 1) {
return
} else if (n == r.from && n == r.to) {
ranges.removeAt(i)
return
} else if (n == r.from) {
ranges[i] = n+1..r.to
return
} else if (n < r.to) {
ranges[i] = r.from..n-1
ranges.insert(i+1, n+1..r.to)
return
} else if (n == r.to) {
ranges[i] = r.from..n-1
return
}
}
}
var standard = Fn.new { |ranges| Fmt.v("s", 0, ranges, 0, ",", "").replace("..", "-") }
var add = 0 var remove = 1 var fns = [
Fn.new { |ranges, n|
rangesAdd.call(ranges, n)
Fmt.print(" add $2d => $n", n, standard.call(ranges))
},
Fn.new { |ranges, n|
rangesRemove.call(ranges, n)
Fmt.print(" remove $2d => $n", n, standard.call(ranges))
}
]
var ranges = [] var ops = [ [add, 77], [add, 79], [add, 78], [remove, 77], [remove, 78], [remove, 79] ] Fmt.print("Start: $q", standard.call(ranges)) for (op in ops) fns[op[0]].call(ranges, op[1])
ranges = [1..3, 5..5] ops = [ [add, 1], [remove, 4], [add, 7], [add, 8], [add, 6], [remove, 7] ] Fmt.print("\nStart: $q", standard.call(ranges)) for (op in ops) fns[op[0]].call(ranges, op[1])
ranges = [1..5, 10..25, 27..30] ops = [ [add, 26], [add, 9], [add, 7], [remove, 26], [remove, 9], [remove, 7] ] Fmt.print("\nStart: $q", standard.call(ranges)) for (op in ops) fns[op[0]].call(ranges, op[1]) </lang>
- Output:
Start: ""
add 77 => 77-77
add 79 => 77-77,79-79
add 78 => 77-79
remove 77 => 78-79
remove 78 => 79-79
remove 79 =>
Start: "1-3,5-5"
add 1 => 1-3,5-5
remove 4 => 1-3,5-5
add 7 => 1-3,5-5,7-7
add 8 => 1-3,5-5,7-8
add 6 => 1-3,5-8
remove 7 => 1-3,5-6,8-8
Start: "1-5,10-25,27-30"
add 26 => 1-5,10-30
add 9 => 1-5,9-30
add 7 => 1-5,7-7,9-30
remove 26 => 1-5,7-7,9-25,27-30
remove 9 => 1-5,7-7,10-25,27-30
remove 7 => 1-5,10-25,27-30