Advertisement
sashomaga

Shortest sequence of operations -> queue of nodes

Jun 2nd, 2013
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 3.61 KB | None | 0 0
  1. /* We are given numbers N and M and the following operations:
  2. N = N+1
  3. N = N+2
  4. N = N*2
  5. Write a program that finds the shortest sequence of operations from the list above that starts from N and finishes in M. Hint: use a queue.
  6. Example: N = 5, M = 16
  7. Sequence: 5 -> 7 -> 8 -> 16 */
  8.  
  9. class Node<T>
  10.     {
  11.         internal T Value { get; set; }
  12.  
  13.         private Node<T> parent;
  14.         internal Node<T> Parent
  15.         {
  16.             get { return parent; }
  17.             set { parent = value; }
  18.         }
  19.  
  20.         public Node()
  21.         {
  22.         }
  23.         public Node(T value)
  24.         {
  25.             this.Value = value;
  26.         }
  27.     }
  28.  
  29. class Program
  30.     {
  31.         static int m = 1225;
  32.         static int n = 5;
  33.  
  34.         private static int GetM()
  35.         {
  36.             Console.Write("Input M: ");
  37.             return int.Parse(Console.ReadLine());
  38.         }
  39.  
  40.         private static int GetN()
  41.         {
  42.             Console.Write("Input N: ");
  43.             return int.Parse(Console.ReadLine());
  44.         }
  45.  
  46.         private static Node<int> FindElement(Node<int> element)
  47.         {
  48.             Queue<Node<int>> elementsQueue = new Queue<Node<int>>();
  49.             elementsQueue.Enqueue(element);
  50.  
  51.             while (elementsQueue.Count > 0)
  52.             {
  53.                 Node<int> currentElement = elementsQueue.Dequeue();
  54.  
  55.                 if (currentElement.Value == m)
  56.                 {
  57.                     return currentElement;
  58.                 }
  59.                 else if (currentElement.Value < m)
  60.                 {
  61.                     Node<int> nextElement = new Node<int>(currentElement.Value + 1);
  62.                     nextElement.Parent = currentElement;
  63.                     elementsQueue.Enqueue(nextElement);
  64.  
  65.                     nextElement = new Node<int>(currentElement.Value + 2);
  66.                     nextElement.Parent = currentElement;
  67.                     elementsQueue.Enqueue(nextElement);
  68.  
  69.                     nextElement = new Node<int>(currentElement.Value * 2);
  70.                     nextElement.Parent = currentElement;
  71.                     elementsQueue.Enqueue(nextElement);
  72.                 }
  73.             }
  74.             throw new ArgumentException("The searched element can not be reached.");
  75.         }
  76.  
  77.         private static Node<int> PrintChain(int n, Node<int> searchedElement)
  78.         {
  79.             Stack<int> result = new Stack<int>();
  80.             while (searchedElement.Parent != null)
  81.             {
  82.                 result.Push(searchedElement.Value);
  83.                 searchedElement = searchedElement.Parent;
  84.             }
  85.  
  86.             result.Push(n);
  87.  
  88.             while (result.Count > 0)
  89.             {
  90.                 if (result.Count != 1)
  91.                 {
  92.                     Console.Write("{0} -> ", result.Pop());
  93.                 }
  94.                 else
  95.                 {
  96.                     Console.WriteLine("{0}", result.Pop());
  97.                 }
  98.             }
  99.             return searchedElement;
  100.         }
  101.  
  102.         static void Main(string[] args)
  103.         {
  104.             //n = GetN();
  105.             //m = GetM();
  106.  
  107.             bool elementReached = false;
  108.  
  109.             Node<int> root = new Node<int>(n);
  110.  
  111.             Node<int> searchedElement = new Node<int>();
  112.             try
  113.             {
  114.                 searchedElement = FindElement(root);
  115.                 elementReached = true;
  116.             }
  117.             catch (ArgumentException e)
  118.             {
  119.                 Console.WriteLine(e.Message);
  120.             }
  121.  
  122.             if (elementReached)
  123.             {
  124.                 searchedElement = PrintChain(n, searchedElement);
  125.             }
  126.         }
  127.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement