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

Shortest Prime Path
Two numbers a and b are said to be “primaly” connected (a --> b) iif:
a<b and a+b is a prime number.
A prime path between two numbers a and b is the path of primaly connected numbers from a to b.
Given two numbers a and b (1<=a<b<=15000), write an algorithm to find the shortest prime path between a and b.
Input will be given as a file names primepath_input.txt containing a pair of numbers per line representing a and b. End of file will be represented by 0 0. Example:
1 10
10854 10891
4 5
1 15000
0 0
Output should be a file named primepath_output.txt with one result per line for each corresponding line in the input file (except for the 0 0 input). The code should either return one shortest path between a and b when it exists, or “no solution” in case there isn’t a prime path between a and b:
Shortest prime path from 1 to 10: 1 10
Shortest prime path from 10854 to 10891: 10854 10859 10868 10869 10882 10891
Shortest prime path from 4 to 5: no solution
Shortest prime path from 1 to 15000: 1 2 17 15000
There may be multiple shortest paths between a and b. Your code only has to output one of them.

AnswerPre-build the graph for all the 15000 x 15000 pairs (takes some time but it will pay off later). Be careful with the primality check, better to use Sieve of Eratosthenes. After that it is just a matter of running a BSF in the pre-built graph:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
namespace PrimePath
{
    class Program
    {
        static int MAX_N = 15000;
        static int[,] graph = new int[MAX_N + 1, MAX_N + 1];
        static void Main(string[] args)
        {
            FileInfo fi_input = new FileInfo("primepath_input.txt");
            StreamReader sr_input = fi_input.OpenText();
            FileInfo fi_output = new FileInfo("primepath_output.txt");
            StreamWriter sr_output = fi_output.CreateText();
            Console.Write("Creating graph...");
            CreateGraph();
            Console.WriteLine("done.");
            while (!sr_input.EndOfStream)
            {
                string line = sr_input.ReadLine();
                string[] parts = line.Split(' ');
                int start = Convert.ToInt32(parts[0]);
                int end = Convert.ToInt32(parts[1]);
                if (start == 0 && end == 0)
                {
                    break;
                }
                string result = FindPath(start, end);
                Console.WriteLine(result);
                sr_output.WriteLine(result);
            }
            sr_input.Close();
            sr_output.Close();
        }
        static void CreateGraph()
        {
            int[] primes = new int[2 * MAX_N + 1];
            //Primes
            for (int i = 0; i <= 2 * MAX_N; i++)
            {
                primes[i] = 1;
            }
            primes[0] = primes[1] = 0;
            for (int i = 2; i <= 2 * MAX_N; i++)
            {
                for (int j = 2; j <= 2 * MAX_N; j++)
                {
                    if (i * j <= 2 * MAX_N)
                    {
                        primes[i * j] = 0;
                    }
                    else
                    {
                        break;
                    }
                }
            }
            //Graph
            for (int i = 1; i <= MAX_N; i++)
            {
                for (int j = 1; j <= MAX_N; j++)
                {
                    graph[i, j] = 0;
                }
            }
            for (int i = 1; i <= MAX_N; i++)
            {
                for (int j = i + 1; j <= MAX_N; j++)
                {
                    if (i != j && primes[i + j] == 1)
                    {
                        graph[i, j] = 1;
                    }
                }
            }
        }
        static string FindPath(int start, int end)
        {
            int[] used = new int[MAX_N + 1];
            int[,] queue = new int[MAX_N, 2];
            int head = 0;
            int tail = 0;
            bool found = false;
            string retVal = "";
            for (int i = 0; i <= MAX_N; i++)
            {
                used[i] = 0;
            }
            queue[tail, 0] = start;
            queue[tail, 1] = -1;
            used[start] = 1;
            tail++;
            while (head < tail)
            {
                int current = queue[head, 0];
                int from = queue[head, 1];
                head++;
                if (current == end)
                {
                    retVal = "Shortest prime path from " + start.ToString() + " to " + end.ToString() + ": ";
                    string path = "";
                    GetPath(queue, queue[head-1, 1], queue[head-1, 0], ref path);
                    retVal += path;
                    found = true;
                    break;
                }
                else
                {
                    for (int i = 1; i <= MAX_N; i++)
                    {
                        if (graph[current, i] == 1 && used[i] == 0)
                        {
                            queue[tail, 0] = i;
                            queue[tail, 1] = head - 1;
                            tail++;
                            used[i] = 1;
                        }
                    }
                }
            }
            if (!found)
            {
                retVal = "Shortest prime path from " + start.ToString() + " to " + end.ToString() + ": no solution";
            }
            return retVal;
        }
        static void GetPath(int[,] queue, int from, int to, ref string path)
        {
            if (from != -1)
            {
                path = to.ToString() + " " + path;
                GetPath(queue, queue[from, 1], queue[from, 0], ref path);
            }
            else
            {
                path = to.ToString() + " " + path;
            }
        }
    }
}