Jump to content

Need help with Breadth First Search C#

straight_stewie

EDIT:: A short while after posting this, I spilled a drink on my keyboard. While my keyboard was spazzing out, it managed to highlight and delete a significant portion of this program, and then save it! How lucky is it that I posted it here?
 

So for fun, I'm trying to find the largest sum of any path in a pyramid. What I have done is generate an int[,] of the graph, and also an int[,][] adjacency list where the index of the list of adjacent nodes is the same as the index of the current node in the graph. The graph has multiple levels (0-14). For the first iteration, I need to find the sums between level 0 and 1. Then I need to replace level 1 with the sums. After the first iteration, an extra step is added: I need to find the sums between level 1 and level 2, remove the lowest sum (from each individual comparison), and replace level 2 with the sums. Rinse and repeat until the end of the pyramid is found. 

For the life of me I cannot figure out how to do this...

Here's my program so far, all it does is read a text file, generate the graph, and generate an adjacency list. Also included is the text file of the graph.
 

        static void Main(string[] args)
        {
            string path = @"F:\ProjectEuler\REALMASTER\MasterSolution\MasterSolution\Pyramid.txt";
            int[,] myPyramid = GetPyramid(File.ReadAllLines(path), 15);
            int[,][] listMe = AdjacencyList(myPyramid, 15);

            // PYRAMID SEARCH HERE!!!!!!!!!

        }

        private static int[,] GetPyramid(string[] referenceMe, int dimension) // Takes a string[] and a square dimensions and returns an int[,].
        {
            int[,] myPyramid = new int[dimension, dimension];
            int rowIndex = 0;
            int colIndex = 0;
            string temp = "";

            foreach (string reference in referenceMe)                         //This loop takes a weird string array and properly puts it in a 2d array.
            {
                char[] charContain = reference.ToCharArray();

                for (int i = 0; i < charContain.Length; i++)
                {
                    if (charContain[i] != ' ')
                        temp += charContain[i];

                    else
                    {
                        myPyramid[rowIndex, colIndex] = Convert.ToInt32(temp);
                        colIndex++;
                        temp = "";
                    }
                }

                colIndex = 0;
                rowIndex++;
            }

            for (int i = 0; i < 14; i++)  // This loop delimits the end of all rows except the last one with "10000", useful later.
                myPyramid[i, 14] = 10000;

            return myPyramid;
        }

        private static int[,][] AdjacencyList(int[,] graph, int depth)        //Generates an adjacency list of type int[,][].
        {
            int stopMe = depth - 1;
            int[,][] adjacencyList = new int[depth, depth][];
            int rowIndex = 0;
            int colIndex = 0;

            foreach (int mine in graph) 
            {
                if (mine == 10000)  // If we hit the row delimiter, move to the next row and reset the column.
                {
                    rowIndex++;
                    colIndex = 0;
                }

                if (rowIndex == stopMe) // If we have reached the last row, stop.
                    break;

                else if (mine != 0 && mine != 10000) // Add an array of integers where they are the nodes connected to the same indices on the graph.
                {
                    adjacencyList[rowIndex, colIndex] = new int[] { graph[rowIndex + 1, colIndex], graph[rowIndex + 1, colIndex + 1] };
                    colIndex++;
                }
            }

            return adjacencyList;
        }

 

Pyramid.txt

ENCRYPTION IS NOT A CRIME

Link to comment
Share on other sites

Link to post
Share on other sites

I honestly have no idea. What are you trying to achieve?

Judge a product on its own merits AND the company that made it.

How to setup MSI Afterburner OSD | How to make your AMD Radeon GPU more efficient with Radeon Chill | (Probably) Why LMG Merch shipping to the EU is expensive

Oneplus 6 (Early 2023 to present) | HP Envy 15" x360 R7 5700U (Mid 2021 to present) | Steam Deck (Late 2022 to present)

 

Mid 2023 AlTech Desktop Refresh - AMD R7 5800X (Mid 2023), XFX Radeon RX 6700XT MBA (Mid 2021), MSI X370 Gaming Pro Carbon (Early 2018), 32GB DDR4-3200 (16GB x2) (Mid 2022

Noctua NH-D15 (Early 2021), Corsair MP510 1.92TB NVMe SSD (Mid 2020), beQuiet Pure Wings 2 140mm x2 & 120mm x1 (Mid 2023),

Link to comment
Share on other sites

Link to post
Share on other sites

5 hours ago, straight_stewie said:

EDIT:: A short while after posting this, I spilled a drink on my keyboard. While my keyboard was spazzing out, it managed to highlight and delete a significant portion of this program, and then save it! How lucky is it that I posted it here?

That's why source control exists...

The single biggest problem in communication is the illusion that it has taken place.

Link to comment
Share on other sites

Link to post
Share on other sites

1 minute ago, Nuluvius said:

That's why source control exists...

And Git/GitHub.............

 

And OneDrive........... (where all my projects and files are saved online)

Judge a product on its own merits AND the company that made it.

How to setup MSI Afterburner OSD | How to make your AMD Radeon GPU more efficient with Radeon Chill | (Probably) Why LMG Merch shipping to the EU is expensive

Oneplus 6 (Early 2023 to present) | HP Envy 15" x360 R7 5700U (Mid 2021 to present) | Steam Deck (Late 2022 to present)

 

Mid 2023 AlTech Desktop Refresh - AMD R7 5800X (Mid 2023), XFX Radeon RX 6700XT MBA (Mid 2021), MSI X370 Gaming Pro Carbon (Early 2018), 32GB DDR4-3200 (16GB x2) (Mid 2022

Noctua NH-D15 (Early 2021), Corsair MP510 1.92TB NVMe SSD (Mid 2020), beQuiet Pure Wings 2 140mm x2 & 120mm x1 (Mid 2023),

Link to comment
Share on other sites

Link to post
Share on other sites

Just now, AluminiumTech said:

And Git/GitHub.............

 

And OneDrive........... (where all my projects and files are saved online)

I currently prefer Bitbucket for personal use.

The single biggest problem in communication is the illusion that it has taken place.

Link to comment
Share on other sites

Link to post
Share on other sites

3 minutes ago, Nuluvius said:

I currently prefer Bitbucket for personal use.

IDK what that is so yeah...............

Judge a product on its own merits AND the company that made it.

How to setup MSI Afterburner OSD | How to make your AMD Radeon GPU more efficient with Radeon Chill | (Probably) Why LMG Merch shipping to the EU is expensive

Oneplus 6 (Early 2023 to present) | HP Envy 15" x360 R7 5700U (Mid 2021 to present) | Steam Deck (Late 2022 to present)

 

Mid 2023 AlTech Desktop Refresh - AMD R7 5800X (Mid 2023), XFX Radeon RX 6700XT MBA (Mid 2021), MSI X370 Gaming Pro Carbon (Early 2018), 32GB DDR4-3200 (16GB x2) (Mid 2022

Noctua NH-D15 (Early 2021), Corsair MP510 1.92TB NVMe SSD (Mid 2020), beQuiet Pure Wings 2 140mm x2 & 120mm x1 (Mid 2023),

Link to comment
Share on other sites

Link to post
Share on other sites

1 minute ago, AluminiumTech said:

IDK what that is so yeah...............

Link.

The single biggest problem in communication is the illusion that it has taken place.

Link to comment
Share on other sites

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×