Problem:
You are given a collection of unit cubes whose vertex coordinates are integers. Two cubes with a shared face are glued together. A connected mass of cubes forms a "blob". Your task is to count the number of blobs and find the total surface area of all blobs.
Note: A blob may have internal "bubbles." Its total surface area includes internal wall area of bubbles, as well as area contribution from trapped blobs inside bubbles.
Each unit cube has vertex coordinates (x,y,z), (x+1,y,z), ..., (x+1,y+1,z+1). (x,y,z) is called the minimal vertex of a given cube, and is used to specify the cube.
At first the problem seemed very challenging, but by noting that a "blob" is created only when the vertex of one cube (x, y, z) is one unit away from another cube on strictly on one axis (ex. (x + 1, y, z), (x, y + 1, x), or (x, y, z + 1), the problem became very straight-forward.
Here is the python solution below:
def Blob(vertices):
surfaceArea = len(vertices)*6
numberOfObjects = len(vertices)
for vertex in vertices:
isConnected = False
for k in range(3):
x = vertex[:]
x[k] += 1
if x in vertices:
surfaceArea = surfaceArea - 2
isConnected = True
if isConnected:
numberOfObjects -= 1
return (surfaceArea, numberOfObjects)
I later decided to make the problem more complex, by dealing with the vertices with decimals and attempting to produce a somewhat elegant algorithm (It's not though :( ). Here's my explanation:
Keep in mind, as in the last problem, all vertices will be unique. Basically, a blob, in the decimal case, occurs when the distance between two vertices is greater than 0 and less than √(2). Generally, if we think of the vertex of the original unit cube to be (x1, y1, z1), and the vertex of the unit cube that intersects the original cube as (x1 + x2, y1 + y2, z1 + z2) we can compute their difference of coordinates to be (x2, y2, z2). Because we are dealing with a unit cube (all sides of length 1) the lengths of all sides of the volume produced by the unit cubes can be computed as (1 - x2, 1 - y2, 1 - z2). The surface area to be removed from the collective surface area of a blob(s) will be 2 * (1 - x2) * (1 - y2) + 2 * (1 - x2) * (1 - z2) + 2 * (1 - y2) * (1 - z2).
The python program follows:
def BlobDecimal(vertices):
surfaceArea = len(vertices)*6
numberOfObjects = len(vertices)
i = 0
for vertex_out in vertices:
isConnected = False
for vertex_in in vertices:
distsqr = 0
for k in range(3):
distsqr += (vertex_in[k] - vertex_out[k])**2
if (distsqr > 0 and distsqr < 2 and all(vertex_out[l] <= vertex_in[l] for l in range(len(vertex_in)))):
diff_vert = (1 - (vertex_in[0] - vertex_out[0]), 1 - (vertex_in[1] - vertex_out[1]),
1- (vertex_in[2] - vertex_out[2]))
diff_surface_area = 2*diff_vert[0]*diff_vert[1] + 2*diff_vert[0]*diff_vert[2] +
2*diff_vert[1]*diff_vert[2]
surfaceArea -= diff_surface_area
isConnected = True
if isConnected:
numberOfObjects -= 1
return (surfaceArea, numberOfObjects)
