NMShortestReach

using System;
using System.Text;
using System.Collections.Generic;

namespace _10_Shortest_reach
{
    public class CustomLinkedList<T> where T : IComparable
    {
        private T[] values;
        private int[] parents;
        private SortedSet<T> sortedValues; // this member is used only to increase the searching speed from O(n) to O(ln n)
        public int Count { get; private set; }

        public CustomLinkedList()
        {
            this.values = new T[4];
            this.parents = new int[4];
            this.sortedValues = new SortedSet<T>();
            this.Count = 0;
        }

        public T this[int index]
        {
            get
            {
                if (index < 0 || index >= this.Count)
                {
                    throw new IndexOutOfRangeException();
                }

                return this.values[index];
            }
        }

        /// <summary>
        /// Returns the index of the parent element (i.e. upper level of the tree)
        /// </summary>
        public int GetParent(int index)
        {
            if (index < 0 || index >= this.Count)
            {
                throw new IndexOutOfRangeException();
            }

            return this.parents[index];
        }

        /// <summary>
        /// Adds new value to the queue
        /// </summary>
        /// <param name="parent">index of the parent element (i.e. upper level of the tree)</param>
        public void Add(T value, int parent = -1)
        {
            if (this.Count == this.values.Length)
            {
                T[] newValues = new T[this.values.Length * 2];
                this.values.CopyTo(newValues, 0);
                this.values = newValues;

                int[] newParents = new int[this.parents.Length * 2];
                this.parents.CopyTo(newParents, 0);
                this.parents = newParents;
            }

            this.values[this.Count] = value;
            this.parents[this.Count] = parent;
            this.sortedValues.Add(value); // it will add sucessfully only unique values
            this.Count++;
        }

        public bool Contains(T value)
        {
            // return (Array.IndexOf<T>(this.values, value) >= 0); // O(n) that results to O(n^2) for the application, very slow for numbers above 50000
            return (this.sortedValues.Contains(value)); // O(ln n), better
        }
    }

    static class ShortestReach
    {
        static private CustomLinkedList<int> list = new CustomLinkedList<int>();

        static void Main()
        {
            Console.Write("Start number N: ");
            int start = int.Parse(Console.ReadLine());

            Console.Write("End number M: ");
            int end = int.Parse(Console.ReadLine());

            if (start <= 0 || end < start)
            {
                throw new ArgumentOutOfRangeException("start N should be positive and less than end M");
            }

            list.Add(start);
            int current = list.Count-1;

            while (current < list.Count)
            {
                if (list[current] == end) // solution has been found
                {
                    Console.WriteLine(Environment.NewLine + "Total objects created: " + list.Count);
                    Console.WriteLine(Environment.NewLine + "Solution: " + ShowResult(current));

                    Console.WriteLine("Press Enter to finish");
                    Console.ReadLine();
                    return;
                }

                // for each new member checks if it is within range and it not exists already
                if (list[current] + 1 <= end && !list.Contains(list[current] + 1))
                {
                    list.Add(list[current] + 1, current);
                }

                if (list[current] + 2 <= end && !list.Contains(list[current] + 2))
                {
                    list.Add(list[current] + 2, current);
                }

                if (list[current] * 2 <= end && !list.Contains(list[current] * 2))
                {
                    list.Add(list[current] * 2, current);
                }

                current++;
            }

            // this should not be reached as there is always a solution
            throw new ApplicationException("No solution");
        }

        /// <summary>
        /// Returns the list of all values of the soluton from start to end
        /// Actually it reveses the saved order from last to first using parents
        /// </summary>
        /// <param name="last">Last value</param>
        /// <returns>string of solution path (for example "1 -> 5 -> 7 -> 8 -> 16")</returns>
        static string ShowResult(int last)
        {
            StringBuilder output = new StringBuilder(list[last].ToString());
            while (list.GetParent(last) >= 0)
            {
                last = list.GetParent(last);
                output.Insert(0, list[last] + " -> ");
            }

            return output.ToString();
        }
    }
}