SHARE
TWEET

ShortestPathFinder

g-stoyanov Jun 2nd, 2013 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  * Task 10*
  3.  * We are given numbers N and M and the following operations:
  4.  * N = N+1
  5.  * N = N+2
  6.  * N = N*2
  7.  * Write a program that finds the shortest sequence of operations
  8.  * from the list above that starts from N and finishes in M.
  9.  * Hint: use a queue.
  10.  * Example: N = 5, M = 16
  11.  * Sequence: 5 ---> 6 ---> 8 ---> 16
  12.  */
  13.  
  14. namespace Task10Version2ShortestSequenceOfOperation.Common
  15. {
  16.     using System;
  17.     using System.Collections.Generic;
  18.     using System.Linq;
  19.  
  20.     public class ShortestPathFinder
  21.     {
  22.         private readonly Queue<TreeNode<int>> holder = new Queue<TreeNode<int>>();
  23.         private readonly List<TreeNode<int>> results = new List<TreeNode<int>>();
  24.         private readonly List<string> pathsWithoutDublicates = new List<string>();
  25.  
  26.         /// <summary>
  27.         /// Initializes a new instance of the <see cref="ShortestPathFinder" /> class.
  28.         /// </summary>
  29.         /// <param name="start">The start of path.</param>
  30.         /// <param name="stop">The stop of path.</param>
  31.         public ShortestPathFinder(int start, int stop)
  32.         {
  33.             TreeNode<int> root = new TreeNode<int>(start);
  34.             this.CreateTree(start, stop, root, this.holder, -1, this.results);
  35.         }
  36.  
  37.         /// <summary>
  38.         /// Printing all shortest paths.
  39.         /// </summary>
  40.         public void PrintShortestPaths()
  41.         {
  42.             this.ProcessPaths();
  43.             foreach (var path in this.pathsWithoutDublicates)
  44.             {
  45.                 Console.WriteLine(path);
  46.                 Console.WriteLine();
  47.             }
  48.         }
  49.  
  50.         /// <summary>
  51.         /// Recursive function to fill paths tree.
  52.         /// </summary>
  53.         private void CreateTree(int start, int stop, TreeNode<int> currentNode, Queue<TreeNode<int>> holder, int treeLevelOfStop, List<TreeNode<int>> results)
  54.         {
  55.             if (treeLevelOfStop == -1 || currentNode.NodeTreeLevel < treeLevelOfStop)
  56.             {
  57.                 TreeNode<int> firstChildToAdd = new TreeNode<int>(currentNode.Value * 2);
  58.                 TreeNode<int> secondChildToAdd = new TreeNode<int>(currentNode.Value + 2);
  59.                 TreeNode<int> thirdChildToAdd = new TreeNode<int>(currentNode.Value + 1);
  60.  
  61.                 if (firstChildToAdd.Value == stop ||
  62.                     secondChildToAdd.Value == stop ||
  63.                     thirdChildToAdd.Value == stop)
  64.                 {
  65.                     treeLevelOfStop = currentNode.NodeTreeLevel + 1;
  66.                 }
  67.  
  68.                 if (currentNode.Value > 0 &&
  69.                     firstChildToAdd.Value > start && firstChildToAdd.Value <= stop)
  70.                 {
  71.                     currentNode.AddChild(firstChildToAdd);
  72.                 }
  73.  
  74.                 if (secondChildToAdd.Value > start && secondChildToAdd.Value <= stop)
  75.                 {
  76.                     currentNode.AddChild(secondChildToAdd);
  77.                 }
  78.  
  79.                 if (thirdChildToAdd.Value > start && thirdChildToAdd.Value <= stop)
  80.                 {
  81.                     currentNode.AddChild(thirdChildToAdd);
  82.                 }
  83.  
  84.                 for (int i = 0; i < currentNode.CountChildren(); i++)
  85.                 {
  86.                     TreeNode<int> child = currentNode.GetChild(i);
  87.                     if (child.Value == stop)
  88.                     {
  89.                         results.Add(child);
  90.                     }
  91.  
  92.                     holder.Enqueue(child);
  93.                 }
  94.  
  95.                 currentNode = holder.Dequeue();
  96.  
  97.                 this.CreateTree(start, stop, currentNode, holder, treeLevelOfStop, results);
  98.             }
  99.         }
  100.  
  101.         /// <summary>
  102.         /// Make paths from result and remove dublicates
  103.         /// </summary>
  104.         private void ProcessPaths()
  105.         {
  106.             for (int i = 0; i < this.results.Count; i++)
  107.             {
  108.                 TreeNode<int> result = this.results[i];
  109.                 Stack<int> path = new Stack<int>();
  110.                 while (result != null)
  111.                 {
  112.                     path.Push(result.Value);
  113.                     result = result.Parent;
  114.                 }
  115.  
  116.                 string finalPath = string.Join(" -> ", path);
  117.                 if (!this.pathsWithoutDublicates.Contains(finalPath))
  118.                 {
  119.                     this.pathsWithoutDublicates.Add(finalPath);
  120.                 }
  121.             }
  122.         }
  123.     }
  124. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top