Program.cs

/*

BULK - The Bulk!
ACM uses a new special technology of building its transceiver stations. 
This technology is called Modular Cuboid Architecture (MCA) and is covered by a patent of Lego company. 
All parts of the transceiver are shipped in unit blocks that have the form of cubes of exactly the same size. 
The cubes can be then connected to each other. 
The MCA is modular architecture, that means we can select preferred transceiver configuration and buy only those components we need.

The cubes must be always connected "face-to-face", i.e. the whole side of one cube is connected to the whole side of another cube. 
One cube can be thus connected to at most six other units. 
The resulting equipment, consisting of unit cubes is called The Bulk in the communication technology slang.

Sometimes, an old and unneeded bulk is condemned, put into a storage place, and replaced with a new one. 
It was recently found that ACM has many of such old bulks that just occupy space and are no longer needed. 
The director has decided that all such bulks must be disassembled to single pieces to save some space. 
Unfortunately, there is no documentation for the old bulks and nobody knows the exact number of pieces that form them. 
You are to write a computer program that takes the bulk description and computes the number of unit cubes.

Each bulk is described by its faces (sides). 
A special X-ray based machine was constructed that is able to localise all faces of the bulk in the space, even the inner faces, 
because the bulk can be partially hollow (it can contain empty spaces inside). 
But any bulk must be connected (i.e. it cannot drop into two pieces) and composed of whole unit cubes.

 

Input
There is a single positive integer T on the first line of input (equal to about 1000). It stands for the number of bulks to follow. 
Each bulk description begins with a line containing single positive integer F, 6 <= F <= 250, stating the number of faces. 
Then there are F lines, each containing one face description. 
All faces of the bulk are always listed, in any order. 
Any face may be divided into several distinct parts and described like if it was more faces. 
Faces do not overlap. 
Every face has one inner side and one outer side. No side can be "partially inner and partially outer".

Each face is described on a single line. The line begins with an integer number P stating the number of points that determine the face, 4 <= P <= 200. 
Then there are 3 x P numbers, coordinates of the points. 
Each point is described by three coordinates X,Y,Z (0 <= X,Y,Z <= 1000) separated by spaces. 
The points are separated from each other and from the number P by two space characters. These additional spaces were added to make the input more human readable. 
The face can be constructed by connecting the points in the specified order, plus connecting the last point with the first one.

The face is always composed of "unit squares", that means every edge runs either in X, Y or Z-axis direction. 
If we take any two neighbouring points X1,Y1,Z1 and X2,Y2,Z2, then the points will always differ in exactly one of the three coordinates. 
I.e. it is either X1 <> X2, or Y1 <> Y2, or Z1 <> Z2, other two coordinates are the same. 
Every face lies in an orthogonal plane, i.e. exactly one coordinate is always the same for all points of the face. The face outline will never touch nor cross itself.

 

Output
Your program must print a single line for every test case. The line must contain the sentence The bulk is composed of V units., where V is the volume of the bulk.
*/


using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace BULK {

    public class Point {
        public int X { get; set; }
        public int Y { get; set; }
        public int Z { get; set; }

        internal string ToObjVertex(int comment) {
            return $"v {X:F1} {Y:F1} {Z:F1} #{comment}";
        }

        public bool Equals3D(Point p) {
            return this.X == p.X && this.Y == p.Y && this.Z == p.Z;
        }
    }
    public class Face {

        public enum FaceOrientationEnum {
            Unknown = 0,
            Front = 1,
            Top = 2,
            Right = 3
        }



        /*
         * 
         * P0------P1
         * |       |
         * |       |
         * |       |
         * P3------P2
         */


        public Point P0 { get; set; }
        public Point P1 { get; set; }
        public Point P2 { get; set; }
        public Point P3 { get; set; }

        public int Contribution { get; set; }


        public string Name { get; set; }
        public List<Point> Vertex { get; set; } = new List<Point>();
        public FaceOrientationEnum FaceOrientation { get; set; }

        public long Area { get; set; }

        public void CalculatePPoints() {
            var minX = this.Vertex.Min(i => i.X);
            var maxX = this.Vertex.Max(i => i.X);
            var minY = this.Vertex.Min(i => i.Y);
            var maxY = this.Vertex.Max(i => i.Y);

            this.P0 = this.Vertex.First(i => i.X == minX && i.Y == maxY);
            this.P1 = this.Vertex.First(i => i.X == maxX && i.Y == maxY);
            this.P2 = this.Vertex.First(i => i.X == maxX && i.Y == minY);
            this.P3 = this.Vertex.First(i => i.X == minX && i.Y == minY);
        }

        public void Simplify() {
            // there no check for the last point to the first one. 
            // I don't think there is a need for this check since it is stated that all faces are squares.
            var pointsToRemove = new List<int>();

            // 0 = unknown
            // 1 = x
            // 2 = y
            // 3 = z
            var lastMoveOnAxis = 0;

            for (int i = 0; i < this.Vertex.Count - 1; i++) {
                var currentMove = 0;
                var p0 = this.Vertex[i + 0];
                var p1 = this.Vertex[i + 1];

                if (p0.X != p1.X)
                    currentMove = 1;
                else if (p0.Y != p1.Y)
                    currentMove = 2;
                else if (p0.Z != p1.Z)
                    currentMove = 3;
                else
                    currentMove = 0;

                if (currentMove == lastMoveOnAxis)
                    pointsToRemove.Add(i);

                lastMoveOnAxis = currentMove;

            }

            foreach (var i in pointsToRemove) {
                this.Vertex.RemoveAt(i);
            }

        }
        public void Identify() {
            // front = z is the same
            // top   = y is the same
            // right = x is the same

            if (Vertex[0].Z == Vertex[1].Z && Vertex[1].Z == Vertex[2].Z)
                this.FaceOrientation = FaceOrientationEnum.Front;
            else if (Vertex[0].Y == Vertex[1].Y && Vertex[1].Y == Vertex[2].Y)
                this.FaceOrientation = FaceOrientationEnum.Top;
            else if (Vertex[0].X == Vertex[1].X && Vertex[1].X == Vertex[2].X)
                this.FaceOrientation = FaceOrientationEnum.Right;
            else
                this.FaceOrientation = FaceOrientationEnum.Unknown;
        }

        public bool IsConnectedToFace(Face f) {
            var rVal = false;
            var nConnectedPoints = 0;

            foreach (var p0 in this.Vertex) {
                foreach (var p1 in f.Vertex) {
                    if (p0.Equals3D(p1))
                        nConnectedPoints++;

                }
            }

            rVal = nConnectedPoints > 1;
            return rVal;
        }

        internal long CalculateArea() {
            this.Area = (this.P1.X - this.P0.X) * (this.P1.Y - this.P2.Y);
            return this.Area;
        }
    }

    public class Bulk {
        public string Name { get; set; }
        public List<Face> FaceList { get; set; } = new List<Face>();

        public List<Tuple<Face, List<Face>>> ConnectedFaces { get; set; } = new List<Tuple<Face, List<Face>>>();

        public void IdentifyFaceOrientationAndSimplify() {
            foreach (var face in FaceList) {
                face.Identify();
                face.Simplify();
            }
        }

        public void MarkConnectedFaces() {

            foreach (var face in FaceList) {
                var connections = new Tuple<Face, List<Face>>(face, new List<Face>());

                foreach (var possibleConnection in FaceList) {

                    if (face == possibleConnection)
                        continue; // ignore itself

                    if (face.IsConnectedToFace(possibleConnection))
                        connections.Item2.Add(possibleConnection);

                }

                this.ConnectedFaces.Add(connections);
            }

        }

        public void MarkOneConnectedFace(List<Face> faceList) {

            foreach (var face in faceList) {
                var connections = new Tuple<Face, List<Face>>(face, new List<Face>());

                foreach (var possibleConnection in FaceList) {

                    if (face == possibleConnection)
                        continue; // ignore itself

                    if (face.FaceOrientation == possibleConnection.FaceOrientation) // faces with same face orientation don't need to be checked
                        continue;

                    if (face.IsConnectedToFace(possibleConnection)) { // there is need for just one connected face since i'll need just the height
                        connections.Item2.Add(possibleConnection);
                        break;
                    }

                }

                this.ConnectedFaces.Add(connections);
            }

        }

        public void Calculate() {
            var faces = this.GetFacesByOrientation(Face.FaceOrientationEnum.Front);
            faces = faces.OrderByDescending(i => i.Vertex.First().Z).ToList();

            faces.All(face => {
                face.CalculatePPoints();
                face.CalculateArea();
                return true;
            });


            for (int i = 0; i < faces.Count; i++) {

                var face = faces[i];
                var contribution = face.Contribution; 

                if (0 == i) // first face contribute
                    contribution = +1;
                else if (0 == contribution) { // defaults to don't contribuite (last face?)
                    contribution = -1;
                }

                face.Contribution = contribution;

                var coveredFace = FindNextCoveredFace(faces, i);
                if (null != coveredFace)
                    coveredFace.Contribution = contribution * -1; 


            }

            var volume = faces.Aggregate(0L, (acc, f) => {
                return acc + (f.Area * f.P0.Z * f.Contribution);
            });

            Console.WriteLine("The bulk is composed of {0} units.", volume);

        }

        private Face FindNextCoveredFace(List<Face> faces, int i) {

            var topFace = faces[i];
            for (int j = i+1; j < faces.Count; j++) {
                var face = faces[j];

                if ((face.P0.X >= topFace.P0.X) && (face.P0.X <= topFace.P1.X) &&
                    (face.P0.Y <= topFace.P0.Y) && (face.P0.Y >= topFace.P3.Y)) {
                    return faces[j];
                }

            }

            return null;
        }

        private List<Face> GetFacesByOrientation(Face.FaceOrientationEnum faceOrientation) {

            var faces = this.FaceList
                .Where(i => i.FaceOrientation == faceOrientation)
                .ToList();


            return faces;
        }
    }

    class Program {

        static void Main(string[] args) {
            var numberOfBulks = 0;
            var streamReader = new StreamReader("..\\..\\..\\input.txt");

            numberOfBulks = int.Parse(streamReader.ReadLine());

            for (int i = 0; i < numberOfBulks; i++) {
                var bulk = ParseBulk(streamReader, $"bulk{i}");
                CreateObj(bulk);
                CreateDebugObj(bulk);

                bulk.IdentifyFaceOrientationAndSimplify();
                bulk.MarkConnectedFaces();
                //bulk.Calculate();
            }

        }

        private static void CreateObj(Bulk bulk) {
            // viewer https://3dviewer.net/
            using var streamWriter = new StreamWriter($"..\\..\\..\\bulk-{bulk.Name}.obj");
            var vertexCounter = 1;
            var vertexList = new List<Point>();
            var vertexWriter = new StringWriter();
            var faceWriter = new StringWriter();

            foreach (var face in bulk.FaceList) {
                faceWriter.Write($"f ");

                for (int i = 0; i < face.Vertex.Count; i++) {
                    var point = face.Vertex[i];
                    vertexList.Add(point); var vertexIndex = vertexCounter++;
                    vertexWriter.WriteLine(point.ToObjVertex(i+1));
                    faceWriter.Write($"{vertexIndex}// ");

                }
                faceWriter.Write("\n");
            }


            streamWriter.WriteLine("g bulk");
            streamWriter.WriteLine(vertexWriter);
            streamWriter.WriteLine(faceWriter);


        }

        private static void CreateDebugObj(Bulk bulk) {
            // viewer https://3dviewer.net/

            using var streamWriter = new StreamWriter($"..\\..\\..\\bulk-{bulk.Name}-debug.obj");
            var vertexCounter = 1;
            var faceCounter = 0;
            var vertexList = new List<Point>();
            var vertexWriter = new StringWriter();
            var faceWriter = new StringWriter();

            foreach (var face in bulk.FaceList) {
                faceWriter.WriteLine($"g face{faceCounter++}");
                faceWriter.Write($"f ");

                for (int i = 0; i < face.Vertex.Count; i++) {
                    var point = face.Vertex[i];
                    vertexList.Add(point); var vertexIndex = vertexCounter++;
                    vertexWriter.WriteLine(point.ToObjVertex(i+1));
                    faceWriter.Write($"{vertexIndex}// ");

                }
                faceWriter.Write("\n");
            }

            streamWriter.WriteLine(vertexWriter);
            streamWriter.WriteLine(faceWriter);
        }

        private static Bulk ParseBulk(StreamReader reader, string bulkName) {
            var bulk = new Bulk() { Name = bulkName };
            var numeberOfFaces = int.Parse(reader.ReadLine());

            for (int i = 0; i < numeberOfFaces; i++) {
                var face = new Face() { Name = $"face{i}" }; bulk.FaceList.Add(face);
                var line = reader.ReadLine();
                var lineParts = line.Split(' ').Where(i => i != string.Empty).ToArray();

                var numberOfPoints = int.Parse(lineParts[0]);

                for (int j = 0; j < numberOfPoints; j++) {
                    var point = new Point(); face.Vertex.Add(point);
                    point.X = int.Parse(lineParts[(j * 3) + 0 + 1]);
                    point.Y = int.Parse(lineParts[(j * 3) + 1 + 1]);
                    point.Z = int.Parse(lineParts[(j * 3) + 2 + 1]);

                }

            }
            return bulk;
        }
    }
}