Advent of Code - Day 6, 2024: BFS and FSM

Solution to the "Pipe" problem, http://acm.tju.edu.cn/toj/showp1005.html, in C#. This was a complicated problem to solve, mainly because the calculations around the bending points, as well as the floating point errors in the calculation. It becomes important to break the problem down into as many small classes and functions as possible. The corner cases are the killers here. The approach is to realize that you only need to try 10K different lights thru a pipe of no more than 40 segments (400K computations per input). The hairy code is the one inside the Pipe.cs class to deal with the bending points. It worked for the input given, but I’m not 100% sure it will work for all the inputs since I only had this input to play with:

InputHandler.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
namespace Pipe
{
    class InputHandler
    {
        private FileInfo fi = null;
        private StreamReader sr = null;
        private InputHandler() { }
        public InputHandler(string fileName)
        {
            this.fi = new FileInfo(fileName);
            this.sr = this.fi.OpenText();
        }
        public Point[] ReadNextInput()
        {
            if(this.sr != null)
            {
                Point[] points = null;
                int nPoints = Int32.Parse(this.sr.ReadLine());
                if (nPoints == 0)
                {
                    return null;
                }
                points = new Point[nPoints];
                for (int i = 0; i < nPoints; i++)
                {
                    string[] lineParts = this.sr.ReadLine().Split(' ');
                    points[i] = new Point(float.Parse(lineParts[0]),
                                        float.Parse(lineParts[1]));
                }
                return points;
            }
            else
            {
                return null;
            }
        }
        ~InputHandler()
        {
            if (this.sr != null)
            {
                this.sr.Close();
            }
        }
    }
}
Line.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Pipe
{
    class Line
    {
        public float angle = -1;
        public float constant = -1;
        public bool isVertical = false;
        public float xConstant = -1;
       
        private Line() { }
        public Line(Point p1,
                    Point p2)
        {
            if (p2.x == p1.x)
            {
                this.isVertical = true;
                this.xConstant = p1.x;
            }
            else
            {
                float denominator = p2.x - p1.x;
                this.angle = (p2.y - p1.y) / denominator;
                this.constant = (p1.y * p2.x - p2.y * p1.x) / denominator;
            }
        }
        public Point PointOfIntersectionGivenX(float x)
        {
            float y = this.angle * x + this.constant;
            return new Point(x, y);
        }
    }
}
Pipe.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Pipe
{
    class Pipe
    {
        private Segment[] segments = null;
        private Pipe() { }
        public Pipe(Point[] points)
        {
            if (points == null)
            {
                throw new Exception("Points cannot be null, failed to initilize the pipe");
            }
            int nSegments = 2 * (points.Length - 1);
            if(nSegments > 0)
            {
                segments = new Segment[nSegments];
                int iSegment = 0;
                Point startOfSegment;
                Point endOfSegment;
                for (int i = 0; i < points.Length - 1; i++)
                {
                    startOfSegment = new Point(points[i]);
                    endOfSegment = new Point(points[i + 1]);
                    this.segments[iSegment++] = new Segment(startOfSegment,
                                                            endOfSegment);
                    startOfSegment = new Point(points[i].x,
                                               points[i].y - 1);
                    endOfSegment = new Point(points[i + 1].x,
                                             points[i + 1].y - 1);
                    this.segments[iSegment++] = new Segment(startOfSegment,
                                                            endOfSegment);
                }
            }
        }
        public void Process()
        {
            if (this.segments == null)
            {
                Console.WriteLine("Through all the pipe.");
                return;
            }
            float lineStartX;
            float lineStartY;
            float lineEndX;
            float lineEndY;
            float maxX = float.MinValue;
            bool foundLightThatGoesAcross = false;
            for (float deltaLineStart = 0.00f; deltaLineStart <= 1.00; deltaLineStart += 0.01f)
            {
                for (float deltaLineEnd = 0.00f; deltaLineEnd <= 1.00; deltaLineEnd += 0.01f)
                {
                    lineStartX = this.segments[0].startOfSegment.x;
                    lineStartY = this.segments[0].startOfSegment.y - 1 + deltaLineStart;
                    lineEndX = this.segments[0].endOfSegment.x;
                    lineEndY = this.segments[0].endOfSegment.y - 1 + deltaLineEnd;
                    Point startPoint = new Point(lineStartX,
                                                 lineStartY);
                    Point endPoint = new Point(lineEndX,
                                               lineEndY);
                    Line light = new Line(startPoint,
                                          endPoint);
                    bool foundAtLeastOneIntersection = false;
                    for (int iSegment = 0; iSegment < this.segments.Length; iSegment++)
                    {
                        Point intersectionPoint = this.segments[iSegment].IntersectionWithLine(light);
                        if (intersectionPoint != null)
                        {
                            //Intersection might be a bending point - begin{
                            bool bendingPointBuLightGoesThru = false;
                            if (
                                 (Util.IsEqualTo(intersectionPoint.x, segments[iSegment].startOfSegment.x) && Util.IsEqualTo(intersectionPoint.y, segments[iSegment].startOfSegment.y)) ||
                                 (Util.IsEqualTo(intersectionPoint.x, segments[iSegment].endOfSegment.x) && Util.IsEqualTo(intersectionPoint.y, segments[iSegment].endOfSegment.y))
                               )
                            {
                                int previousSegmentIndex = -1;
                                int nextSegmentIndex = -1;
                                if (Util.IsEqualTo(intersectionPoint.x, segments[iSegment].startOfSegment.x) && Util.IsEqualTo(intersectionPoint.y, segments[iSegment].startOfSegment.y))
                                {
                                    nextSegmentIndex = iSegment;
                                    previousSegmentIndex = iSegment - 2;
                                }
                                else
                                {
                                    nextSegmentIndex = iSegment + 2;
                                    previousSegmentIndex = iSegment;
                                }
                                if (nextSegmentIndex >= 0 &&
                                    nextSegmentIndex < segments.Length &&
                                    previousSegmentIndex >= 0 &&
                                    previousSegmentIndex < segments.Length) //This means that we're inside the pipe, within the inner segments
                                {
                                    if (Util.IsGreaterThan(light.angle, 0f) &&
                                        Util.IsGreaterThanOrEqualTo(this.segments[nextSegmentIndex].segmentLine.angle, light.angle))
                                    {
                                        //Angles in the same upwards direction, let the light go thru
                                        bendingPointBuLightGoesThru = true;
                                    }
                                    else if (Util.IsLessThan(light.angle, 0f) &&
                                             Util.IsLessThanOrEqualTo(this.segments[nextSegmentIndex].segmentLine.angle, light.angle))
                                    {
                                        //Angles in the same downwards direction, let the light go thru
                                        bendingPointBuLightGoesThru = true;
                                    }
                                    else if (Util.IsEqualTo(light.angle, 0f)) //Light is a horizontal line
                                    {
                                        if (Util.IsEqualTo(this.segments[nextSegmentIndex].segmentLine.angle, light.angle))
                                        {
                                            //Segment is a horizontal line, let the light go thru
                                            bendingPointBuLightGoesThru = true;
                                        }
                                        else if (Util.IsLessThanOrEqualTo(this.segments[previousSegmentIndex].segmentLine.angle * this.segments[nextSegmentIndex].segmentLine.angle, 0f))
                                        {
                                            //Adjacent segments have opposite direction, let the light go thru
                                            bendingPointBuLightGoesThru = true;
                                        }
                                        else
                                        {
                                            //Adjacent segments have same direction, block the light
                                            bendingPointBuLightGoesThru = false;
                                        }
                                    }
                                    else
                                    {
                                        //Light and segments collide, block the light
                                        bendingPointBuLightGoesThru = false;
                                    }
                                }
                                else
                                {
                                    //In this case it is a bending point but we're in one of the extreme points of the pipe
                                    //In which case the light should go thru
                                    bendingPointBuLightGoesThru = true;
                                }
                            }
                            //Intersection might be a bending point - end}
                            if (!bendingPointBuLightGoesThru)
                            {
                                foundAtLeastOneIntersection = true;
                                if (intersectionPoint.x > maxX)
                                {
                                    maxX = intersectionPoint.x;
                                }
                                break;
                            }
                        }
                    }
                    if (!foundAtLeastOneIntersection)
                    {
                        foundLightThatGoesAcross = true;
                        break;
                    }
                }
                if (foundLightThatGoesAcross)
                {
                    break;
                }
            }
            if (foundLightThatGoesAcross)
            {
                Console.WriteLine("Through all the pipe.");
            }
            else
            {
                Console.WriteLine("{0}", maxX.ToString("F"));
            }
        }
    }
}
Point.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Pipe
{
    class Point
    {
        public float x;
        public float y;
        private Point() { }
        public Point(float x,
                     float y)
        {
            this.x = x;
            this.y = y;
        }
        public Point(Point p)
        {
            this.x = p.x;
            this.y = p.y;
        }
    }
}
Program.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Pipe
{
    class Program
    {
        static void Main(string[] args)
        {
            if (args.Length == 0)
            {
                Usage();
                return;
            }
            string fileName = args[0];
            InputHandler inputHandler = new InputHandler(fileName);
            Point[] points = inputHandler.ReadNextInput();
            while (points != null)
            {
                Pipe pipe = new Pipe(points);
                pipe.Process();
                points = inputHandler.ReadNextInput();
            }
        }
        static void Usage()
        {
            Console.WriteLine("Usage: Pipe.exe <input file>");
            Console.WriteLine("For more info visit http://acm.tju.edu.cn/toj/showp1005.html");
        }
    }
}
Segment.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Pipe
{
    class Segment
    {
        public Line segmentLine;
        public Point startOfSegment;
        public Point endOfSegment;
        private Segment() { }
        public Segment(Point p1,
                       Point p2)
        {
            this.startOfSegment = new Point(p1);
            this.endOfSegment = new Point(p2);
            this.segmentLine = new Line(this.startOfSegment,
                                        this.endOfSegment);
        }
        public Point IntersectionWithLine(Line line)
        {
            //If both are vertical lines, they don't intersect
            if (line.isVertical &&
                this.segmentLine.isVertical)
            {
                return null;
            }
            //If the line is vertical, all we have to do is check that the x is between the segment boundaries
            //Then get the point of intersection
            if (line.isVertical)
            {
                if (Util.IsGreaterThanOrEqualTo(line.xConstant, this.startOfSegment.x) &&
                    Util.IsLessThanOrEqualTo(line.xConstant, this.endOfSegment.x))
                {
                    return this.segmentLine.PointOfIntersectionGivenX(line.xConstant);
                }
                else
                {
                    return null;
                }
            }
            //If the segment is vertical:
            //1. Find the intersection between the lines
            //2. If the point from (1) is within the segment boudaries, we have a valid intersection
            if (this.segmentLine.isVertical)
            {
                Point pointOfIntersection = line.PointOfIntersectionGivenX(this.segmentLine.xConstant);
                if (Util.IsGreaterThanOrEqualTo(pointOfIntersection.y, this.startOfSegment.y) &&
                    Util.IsLessThanOrEqualTo(pointOfIntersection.y, this.endOfSegment.y))
                {
                    return pointOfIntersection;
                }
                else
                {
                    return null;
                }
            }
            //At this point, find the intersection between the lines, check to see if it falls within the segment boundaries
            float denominator = this.segmentLine.angle - line.angle;
            float intersectionX = (line.constant - this.segmentLine.constant) / denominator;
            float intersectionY = (this.segmentLine.angle * line.constant - line.angle * this.segmentLine.constant) / denominator;
            if (Util.IsGreaterThanOrEqualTo(intersectionX, this.startOfSegment.x) &&
                Util.IsLessThanOrEqualTo(intersectionX, this.endOfSegment.x) &&
                Util.IsGreaterThanOrEqualTo(intersectionY, Math.Min(this.startOfSegment.y, this.endOfSegment.y)) &&
                Util.IsLessThanOrEqualTo(intersectionY, Math.Max(this.startOfSegment.y, this.endOfSegment.y)))
            {
                return new Point(intersectionX,
                                 intersectionY);
            }
            return null;
        }
    }
}
Util.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Pipe
{
    class Util
    {
        private const float ZERO = 0.001f;
        static public bool IsGreaterThan(float f1,
                                         float f2)
        {
            float delta = f1 - f2;
            return delta > ZERO;
        }
        static public bool IsLessThan(float f1,
                                      float f2)
        {
            float delta = f2 - f1;
            return delta > ZERO;
        }
        static public bool IsEqualTo(float f1,
                                     float f2)
        {
            float delta = Math.Abs(f1 - f2);
            return delta <= ZERO;
        }
        static public bool IsGreaterThanOrEqualTo(float f1,
                                         float f2)
        {
            return IsGreaterThan(f1, f2) || IsEqualTo(f1, f2);
        }
        static public bool IsLessThanOrEqualTo(float f1,
                                     float f2)
        {
            return IsLessThan(f1, f2) || IsEqualTo(f1, f2);
        }
    }
}