6
\$\begingroup\$

I recently solved Advent of Code 2019 Day 6 in C#.

Part 1:

You've landed at the Universal Orbit Map facility on Mercury. Because navigation in space often involves transferring between orbits, the orbit maps here are useful for finding efficient routes between, for example, you and Santa. You download a map of the local orbits (your puzzle input).

Except for the universal Center of Mass (COM), every object in space is in orbit around exactly one other object. An orbit looks roughly like this:

                  \
                   \
                    |
                    |
AAA--> o            o <--BBB
                    |
                    |
                   /
                  /

In this diagram, the object BBB is in orbit around AAA. The path that BBB takes around AAA (drawn with lines) is only partly shown. In the map data, this orbital relationship is written AAA)BBB, which means "BBB is in orbit around AAA".

Before you use your map data to plot a course, you need to make sure it wasn't corrupted during the download. To verify maps, the Universal Orbit Map facility uses orbit count checksums - the total number of direct orbits (like the one shown above) and indirect orbits.

Whenever A orbits B and B orbits C, then A indirectly orbits C. This chain can be any number of objects long: if A orbits B, B orbits C, and C orbits D, then A indirectly orbits D.

For example, suppose you have the following map:

COM)B
B)C
C)D
D)E
E)F
B)G
G)H
D)I
E)J
J)K
K)L

Visually, the above map of orbits looks like this:

        G - H       J - K - L
       /           /
COM - B - C - D - E - F
               \
                I

In this visual representation, when two objects are connected by a line, the one on the right directly orbits the one on the left.

Here, we can count the total number of orbits as follows:

D directly orbits C and indirectly orbits B and COM, a total of 3 orbits. L directly orbits K and indirectly orbits J, E, D, C, B, and COM, a total of 7 orbits. COM orbits nothing. The total number of direct and indirect orbits in this example is 42.

What is the total number of direct and indirect orbits in your map data?

Part 2:

Now, you just need to figure out how many orbital transfers you (YOU) need to take to get to Santa (SAN).

You start at the object YOU are orbiting; your destination is the object SAN is orbiting. An orbital transfer lets you move from any object to an object orbiting or orbited by that object.

For example, suppose you have the following map:

COM)B
B)C
C)D
D)E
E)F
B)G
G)H
D)I
E)J
J)K
K)L
K)YOU
I)SAN

Visually, the above map of orbits looks like this:

                          YOU
                         /
        G - H       J - K - L
       /           /
COM - B - C - D - E - F
               \
                I - SAN

In this example, YOU are in orbit around K, and SAN is in orbit around I. To move from K to I, a minimum of 4 orbital transfers are required:

K to J
J to E
E to D
D to I

Afterward, the map of orbits looks like this:

        G - H       J - K - L
       /           /
COM - B - C - D - E - F
               \
                I - SAN
                 \
                  YOU

What is the minimum number of orbital transfers required to move from the object YOU are orbiting to the object SAN is orbiting? (Between the objects they are orbiting - not between YOU and SAN.)

I am fairly new to C# and coming from a C++ background and would like to learn how to improve writing more idiomatic and readable code. My approach to the problem is as follows:

First I have been pasting the input to a text file each day and reading the input from File. In this case, I tokenize the inputs into a List<Tuple<string, string>> which I can then pass to my OrbitalMapCalculator. My OrbitalMapCalculator then creates a list of every single body that already has a count of how many direct and indirect orbits it has. Because each body keeps its own count of orbits, an orbiting body can simply increment the number of orbits of the body it orbits.

For part one I then simply add the total orbits of all bodies.

For part two I find the distance from "YOU" to center and from "SAN" to center. I then find the first common orbit. From there I find the two distances and add them together.

Here is the tokenizer:

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

namespace AdventofCode2019
{
    class ProcessInput
    {
        internal List<Tuple<string, string>> GenerateOrbitalPairs(string textFile)
        {
            List<Tuple<string, string>> orbitalTokens = new List<Tuple<string, string>>();

            if (File.Exists(textFile))
            {
                string[] tokenPairs = File.ReadAllLines(textFile);
                foreach (string pair in tokenPairs)
                {
                    string[] splitPair = pair.Split(')');
                    orbitalTokens.Add(new Tuple<string, string>(splitPair[0], splitPair[1]));
                }
            }

            return orbitalTokens;
        }
    }
}

The bulk of the work is done in the OrbitalMapCalculator:

using System;
using System.Collections.Generic;

namespace AdventofCode2019
{
    internal class OrbitalMapCalculator
    {
        private class Node
        {
            public Node orbitingNode;
            public int numberOfOrbits;
            public string ID;

            public Node(string id)
            {
                orbitingNode = null;
                numberOfOrbits = 0;
                ID = id;
            }

            public Node(Node orbiting, string id)
            {
                orbitingNode = orbiting;
                numberOfOrbits = orbiting.numberOfOrbits + 1;
                ID = id;
            }
        }

        private List<Node> orbitalMap = new List<Node>();

        public void ReadTokens(List<Tuple<string, string>> orbitalPairs)
        {
            string centerOfMass = "COM";
            Node centerNode = new Node(centerOfMass);
            orbitalMap.Add(centerNode);
            Queue<string> centerNames = new Queue<string>();
            centerNames.Enqueue(centerOfMass);

            while (centerNames.Count > 0)
            {
                centerOfMass = centerNames.Dequeue();

                foreach (Node node in orbitalMap)
                {
                    if (node.ID == centerOfMass)
                    {
                        centerNode = node;
                        break;
                    }
                }

                foreach (Tuple<string, string> pair in orbitalPairs)
                {
                    if (centerOfMass == pair.Item1)
                    {
                        orbitalMap.Add(new Node(centerNode, pair.Item2));
                        centerNames.Enqueue(pair.Item2);
                    }
                }
            }
        }

        public int CountOrbits()
        {
            int orbits = 0;
            foreach (Node node in orbitalMap)
            {
                orbits += node.numberOfOrbits;
            }
            return orbits;
        }

        public int DistanceToSanta()
        {
            string yourID = "YOU";
            string santasID = "SAN";
            Node you = null;
            Node santa = null;

            foreach (Node node in orbitalMap)
            {
                if (node.ID == yourID)
                {
                    you = node;
                }
                if (node.ID == santasID)
                {
                    santa = node;
                }
            }

            List<Node> youToCenter = new List<Node>();
            List<Node> santaToCenter = new List<Node>();
            AddNodesTilCenter(you, youToCenter);
            AddNodesTilCenter(santa, santaToCenter);
            Node pivotNode = FindPivotNode(youToCenter, santaToCenter);

            int youToPivot = you.numberOfOrbits - pivotNode.numberOfOrbits - 1;
            int santaToPivot = santa.numberOfOrbits - pivotNode.numberOfOrbits - 1;

            return youToPivot + santaToPivot;
        }

        private void AddNodesTilCenter(Node sentinal, List<Node> nodes)
        {
            while (sentinal.orbitingNode != null)
            {
                nodes.Add(sentinal);
                sentinal = sentinal.orbitingNode;
            }
        }

        private Node FindPivotNode(List<Node> lhs, List<Node> rhs)
        {
            foreach (Node leftNode in lhs)
            {
                foreach (Node rightNode in rhs)
                {
                    if (leftNode.ID == rightNode.ID)
                    {
                        return leftNode;
                    }
                }
            }
            return null;
        }
    }
}

And finally the Program.cs:

using System;
using System.Collections.Generic;

namespace AdventofCode2019
{
    class Program
    {
        static void Main(string[] args)
        {
            string inputFile =
                 @"C:\AdventOfCode\AdventofCode2019\AdventofCode2019\Day6Input.txt";
            ProcessInput processor = new ProcessInput();
            OrbitalMapCalculator calculator = new OrbitalMapCalculator();
            List<Tuple<string, string>> orbitalPairs = processor.GenerateOrbitalPairs(inputFile);
            calculator.ReadTokens(orbitalPairs);

            // Part One only
            int answer = calculator.CountOrbits();

            // Part Two Only
            int answer = calculator.DistanceToSanta();

            Console.WriteLine(answer);
            Console.ReadKey();
        }
    }
}
Improve this question
\$\endgroup\$

1 Answer 1

Reset to default
5
\$\begingroup\$

Thank you for well-formed question :)

I will write my review only regarding ProcessInput class for now, as overall review needs more time then I have at the moment ...

  1. Personally I don't like the method name GenerateOrbitalPairs as you do not generate anything, but rather read or parse. So i think ReadOrbitalpairs or ParseOrbitalPairs would be better.

  2. I think that you should not return empty List if file was not found. Empty list is expected result for empty file ! But for missed file I would say that Exception is expected. System.IO.FileNotFoundException which is raised by File.ReadAllLines in this case is fine.

  3. Tuple is not the best option for public method to return, because it's not clear what it contains for another person (in this case for me) ... When I first saw this method I needed go inside it, read all inner code in order to understand what it does return. Method signature should be clear, so I would create a separate class like OrbitPair { public string OrbitFrom; public string OrbitTo; }

    Or at least used named Tuples

  4. Use LINQ instead of for each loop. Usually it makes code clearer and shorter. That is what your code could look like

    internal List<(string OrbitFrom, string OrbitTo)> GenerateOrbitalPairs(string textFile)
{
    return File.ReadAllLines(textFile).Select(s => (OrbitFrom: s.Split(')')[0], OrbitTo: s.Split(')')[1])).ToList();
}
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.