Circles dividing the plane
Ruby - 312 306 285 273 269 259 characters
This answer has been superseded by my other approach which uses considerably less characters and runs in O(n log n)
.
Okay, let's go. For starters, I just wanted a working implementation, so this is not algorithmically optimised yet. I sort the circles from largest to smallest, and build a tree (circles included in other circles are children of those larger ones). Both operations take O(n^2)
at worst and O(n log n)
at best. Then I iterate through the tree to count areas. If the children of a circle fill up its entire diameter, there are two new areas, otherwise there is just one. This iteration take O(n)
. So I have overall complexity O(n^2)
and qualify for neither reward nor penalty.
This code expects the input without the number of circles to be stored in a variable s
:
t=[]
s.lines.map{|x|x,r=x.split.map &:to_i;{d:2*r,l:x-r,c:[]}}.sort_by!{|c|-c[:d]}.map{|c|i=-1;n=t
while o=n[i+=1]
if 0>d=c[:l]-o[:l]
break
elsif o[:d]>d
n=o[:c]
i=-1
end
end
n[i,0]=c}
a=1
t.map &(b=->n{d=0
n[:c].each{|c|d+=c[:d]}.map &b
a+=d==n[:d]?2:1})
p a
Ungolfed version (expects input in variable string
):
list = []
string.split("\n").map { |x|
m = x.split
x,radius = m.map &:to_i
list<<{x:x, d:2*radius, l:x-radius, r:x+radius, children:[]}
}
list.sort_by! { |circle| -circle[:d] }
tree = []
list.map { |circle|
i = -1
node = tree
while c=node[i+=1]
if circle[:x]<c[:l]
break
elsif circle[:x]<c[:r]
node = c[:children]
i = -1
end
end
node[i,0] = circle
}
areas = 1
tree.map &(count = -> node {
d = 0
i = -1
while c=node[:children][i+=1]
count.call c
d += c[:d]
end
areas += d == node[:d] ? 2 : 1
})
p areas
Ruby, 203 183 173 133 - 100 = 33 characters
So here is a different approach. This time, I sort the circles by their left-most point. Circles touching at their left-most point are sorted from largest to smallest. This takes O(n log n)
(well, Ruby uses quick sort, so actually O(n^2)
but implementing merge/heap sort is probably beyond the scope of this challenge). Then I iterate over this list, remembering all left-most and right-most positions of the circles I have visited. This allows me to detect if a series of circles connects all the way across an enclosing larger circle. In this case, there are two subareas, otherwise just one. This iteration takes only O(n)
giving a total complexity of O(n log n)
which qualifies for the 100 character reward.
This snippet expects the input to be supplied via a file in the command-line arguments without the number of circles:
l,r={},{}
a=1
$<.map{|x|c,q=x.split.map &:to_r;[c-q,-2*q]}.sort.map{|x,y|a+=r[y=x-y]&&l[x]?2:1
l[y]=1 if l[x]&&!r[y]
l[x]=r[y]=1}
p a
Ungolfed version (expects input in a variable string
):
list = []
string.split("\n").map { |x|
m = x.split
x,radius = m.map &:to_r
list<<{x:x, d:2*radius, l:x-radius, r:x+radius}
}
list.sort_by! { |circle| circle[:l] + 1/circle[:d] }
l,r={},{}
areas = 1
list.map { |circle|
x,y=circle[:l],circle[:r]
if l[x] && r[y]
areas += 2
else
areas += 1
l[y]=1 if l[x]
end
r[y]=1
l[x]=1
}
p areas
Mathematica, 125 122 - 150 = -28 chars
I don't know the complexity of the built-in function ConnectedComponents
.
1+{-1,2,1}.Length/@{VertexList@#,EdgeList@#,ConnectedComponents@#}&@Graph[(+##)<->(#-#2)&@@@Rest@ImportString[#,"Table"]]&
Usage:
1+{-1,2,1}.Length/@{VertexList@#,EdgeList@#,ConnectedComponents@#}&@Graph[(+##)<->(#-#2)&@@@Rest@ImportString[#,"Table"]]&[
"9
38 14
-60 40
73 19
0 100
98 2
-15 5
39 15
-38 62
94 2"]
11