TopologicalGenus | Topcoder Archive

Problem Statement

You are given a description of a three-dimensional solid shape as a String[] shape. The shape is made up of one or more unit cubes which are glued together along touching faces. Whether there is a cube at coordinate (x,y,z) is specified by the xth character of the yth space-separated token of the zth String. A cube is represented by an 'X', while '.' indicates no cube.

Your goal is to determine the "genus" of this shape.

What do we mean by "genus"? It's a term from the mathematics of topology, which considers two solid shapes equivalent if they can be smoothly deformed into each other. It turns out that all solid shapes are topologically equivalent to a sphere with a certain number of handles (like coffee cup handles) coming off of it. The number of those handles cannot change through deformation, and it is known as the "genus" of the shape.

A smooth deformation can involve bending, stretching, and squishing an object, but no breaking or joining of any connections can occur. If you picture the shape as a balloon with a flexible plastic surface, filled with air, then you can imagine the kinds of deformations that are possible. You can bend the plastic surface however you wish, but you can't glue two separate sections together, and you can't cut a hole in it.

Check the notes and the examples for additional clarification.

Definition

Class:: TopologicalGenus
Method:: getGenus
Parameters:: String[]
Returns:: int
Method signature:: int getGenus(String[] shape)
(be sure your method is public)

Notes

Less formally, you can think of the "genus" as the number of holes in the shape. A sphere has genus 0, while a doughnut-shaped torus, with one hole, has genus 1.
Two cubes are considered connected together only if they touch at a face. If it helps to visualize tricky cases like examples 3 and 4, imagine that we've shaved 5% off every exposed face of every cube in the shape.
There will be no hollow areas inside the shape. See the last constraint.

Constraints

shape will contain between 1 and 50 elements, inclusive.
Each element of shape will contain between 1 and 50 characters, inclusive.
Each element of shape will consist of one or more nonempty tokens separated by a single space.
Each token in shape will contain only '.' or 'X'.
Each element of shape will have the same number of tokens.
Each token in shape will have the same length.
There will be at least one 'X' in shape.
Any two 'X's in shape will be connected by an orthogonal path of 'X's.
Any '.' in shape will be connected to the outside of the shape by an orthogonal or diagonal path of '.'s.

Examples

```
{"X"}
```
```
Returns: 0
```
A solid cube is easily deformed into a sphere.

{"XXX X.X XXX",
 "XXX X.X XXX",
 "XXX X.X XXX"}

Returns: 1

A thick torus.

{"..XXX.. XXXXXXX ..XXX..",
 "..XXX.. X.XXX.X ..XXX..",
 "..XXX.. XXXXXXX ..XXX.."}

Returns: 2

A 3x3x3 cube with two handles coming off of it.

```
{"XXX XXX XX.",
 "XXX X.X XXX",
 "XXX XXX XXX"}
```
```
Returns: 0
```
Since cubes are joined only along faces, there is no hollow area inside this shape. This shape is similar to a sphere with a hole drilled to its center; the empty space can be filled in through deformation.
```
{"XXX XXX XX.",
 "XXX X.X XXX",
 ".XX XXX XXX"}
```
```
Returns: 1
```
However, a sphere with a hole drilled all the way through it cannot be filled in.
```
{"XXX XXX XXX",
 "X.X ... XXX",
 "XXX XXX XXX"}
```
```
Returns: 2
```
To understand why the genus is 2, divide the shape into three parts: {"AAA AAA AAA", "B.C ... AAA", "AAA AAA AAA"} The 'A's can be deformed into a sphere. The two handles come from 'B' and 'C'.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.