SHARE
TWEET

Task10ShortestSequenceOfOperations

g-stoyanov Jun 2nd, 2013 74 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 Task10ShortestSequenceOfOperations
  15. {
  16.     using System;
  17.     using System.Collections.Generic;
  18.     using System.Linq;
  19.  
  20.     public class Task10ShortestSequenceOfOperations
  21.     {
  22.         /// <summary>
  23.         /// Test method CalcShortestSequence.
  24.         /// </summary>
  25.         public static void Main()
  26.         {
  27.             List<int> shortestSequence = CalcShortestSequence(5, 16);
  28.             Console.WriteLine(string.Join(" -> ", shortestSequence.OrderBy(i => i)));
  29.             Console.WriteLine();
  30.  
  31.             shortestSequence = CalcShortestSequence(0, 39);
  32.             Console.WriteLine(string.Join(" -> ", shortestSequence.OrderBy(i => i)));
  33.             Console.WriteLine();
  34.  
  35.             shortestSequence = CalcShortestSequence(-1, 34);
  36.             Console.WriteLine(string.Join(" -> ", shortestSequence.OrderBy(i => i)));
  37.             Console.WriteLine();
  38.  
  39.             shortestSequence = CalcShortestSequence(-21, 1);
  40.             Console.WriteLine(string.Join(" -> ", shortestSequence.OrderBy(i => i)));
  41.             Console.WriteLine();
  42.  
  43.             shortestSequence = CalcShortestSequence(-18, 2);
  44.             Console.WriteLine(string.Join(" -> ", shortestSequence.OrderBy(i => i)));
  45.             Console.WriteLine();
  46.  
  47.             shortestSequence = CalcShortestSequence(-21, -13);
  48.             Console.WriteLine(string.Join(" -> ", shortestSequence.OrderBy(i => i)));
  49.             Console.WriteLine();
  50.  
  51.             shortestSequence = CalcShortestSequence(-20, -15);
  52.             Console.WriteLine(string.Join(" -> ", shortestSequence.OrderBy(i => i)));
  53.             Console.WriteLine();
  54.  
  55.             shortestSequence = CalcShortestSequence(-22, -12);
  56.             Console.WriteLine(string.Join(" -> ", shortestSequence.OrderBy(i => i)));
  57.             Console.WriteLine();
  58.         }
  59.  
  60.         /// <summary>
  61.         /// Find the shortest sequence of operations
  62.         /// from the list above that starts from fromN and finishes in toM.
  63.         /// </summary>
  64.         /// <param name="fromN">Start number.</param>
  65.         /// <param name="toM">End number.</param>
  66.         /// <returns>List with shortest sequence.</returns>
  67.         public static List<int> CalcShortestSequence(int fromN, int toM)
  68.         {
  69.             Queue<int> workContainer = new Queue<int>();
  70.             List<int> result = new List<int>();
  71.  
  72.             workContainer.Enqueue(toM);
  73.             result.Add(toM);
  74.             while (workContainer.Peek() != fromN)
  75.             {
  76.                 if (OperationOne(workContainer, result, fromN))
  77.                 {
  78.                     continue;
  79.                 }
  80.  
  81.                 if (OperationTwo(workContainer, result, fromN))
  82.                 {
  83.                     continue;
  84.                 }
  85.  
  86.                 if (OperationThree(workContainer, result, fromN))
  87.                 {
  88.                     continue;
  89.                 }
  90.             }
  91.  
  92.             return result;
  93.         }
  94.  
  95.         /// <summary>
  96.         /// Support method to calculate first operation - /2.
  97.         /// </summary>
  98.         /// <param name="inputData">Input data.</param>
  99.         /// <param name="bound">Start number.</param>
  100.         /// <param name="result">Modified inputData.</param>
  101.         /// <returns>Boolean value indicates successful operation.</returns>
  102.         public static bool OperationOne(Queue<int> workContainer, List<int> result, int bound)
  103.         {
  104.             bool isSuccessful = false;
  105.             int currentValue = workContainer.Peek();
  106.             if (currentValue != 2 && currentValue > 0 && currentValue / 2 >= bound && currentValue % 2 == 0)
  107.             {
  108.                 currentValue = workContainer.Dequeue() / 2;
  109.                 SaveOperation(workContainer, result, currentValue, ref isSuccessful);
  110.             }
  111.  
  112.             return isSuccessful;
  113.         }
  114.  
  115.         /// <summary>
  116.         /// Support method to calculate second operation - -2.
  117.         /// </summary>
  118.         /// <param name="inputData">Input data.</param>
  119.         /// <param name="bound">Start number.</param>
  120.         /// <param name="result">Modified inputData.</param>
  121.         /// <returns>Boolean value indicates successful operation.</returns>
  122.         public static bool OperationTwo(Queue<int> workContainer, List<int> result, int bound)
  123.         {
  124.             bool isSuccessful = false;
  125.             int currentValue = workContainer.Peek();
  126.             if ((currentValue - 2 >= bound && ((currentValue <= 0 && bound % 2 == currentValue % 2) || (currentValue > 0 && currentValue - 2 < 0))) ||
  127.                 (currentValue > 0 && currentValue - 2 >= bound && currentValue % 2 == 0))
  128.             {
  129.                 currentValue = workContainer.Dequeue() - 2;
  130.                 SaveOperation(workContainer, result, currentValue, ref isSuccessful);
  131.             }
  132.  
  133.             return isSuccessful;
  134.         }
  135.  
  136.         /// <summary>
  137.         /// Support method to calculate third operation - -1.
  138.         /// </summary>
  139.         /// <param name="inputData">Input data.</param>
  140.         /// <param name="bound">Start number.</param>
  141.         /// <param name="result">Modified inputData.</param>
  142.         /// <returns>Boolean value indicates successful operation.</returns>
  143.         public static bool OperationThree(Queue<int> workContainer, List<int> result, int bound)
  144.         {
  145.             bool isSuccessful = false;
  146.             int currentValue = workContainer.Peek();
  147.  
  148.             if ((currentValue <= 0 && bound % 2 != currentValue % 2) ||
  149.                 (currentValue > 0 && currentValue - 1 >= bound && !(currentValue < 0 && bound % 2 != 0)))
  150.             {
  151.                 currentValue = workContainer.Dequeue() - 1;
  152.                 SaveOperation(workContainer, result, currentValue, ref isSuccessful);
  153.             }
  154.  
  155.             return isSuccessful;
  156.         }
  157.  
  158.         /// <summary>
  159.         /// Support method to save data after operation.
  160.         /// </summary>
  161.         /// <param name="firstHolder">First data holder</param>
  162.         /// <param name="secondHolder">Second data holder</param>
  163.         /// <param name="data">Given data</param>
  164.         /// <param name="isSuccessful">Result of operation</param>
  165.         public static void SaveOperation(Queue<int> firstHolder, List<int> secondHolder, int data, ref bool isSuccessful)
  166.         {
  167.             secondHolder.Add(data);
  168.             firstHolder.Enqueue(data);
  169.             isSuccessful = true;
  170.         }
  171.     }
  172. }
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