Wednesday, 3 July 2013

Disks In a pile

Problem Statement

Vijay is playing a very interesting game. He has N disks ( each of equal radius). 
Every disk has a distinct number out of 1 to N associated with it. Disks are placed one over other in a single pile.

Vijay wants to sort this pile of disk in increasing order from top to bottom. But he has a very very special method of doing this. In a single step he can only choose one disk out of the pile and he can only put it at the top. 

Vijay wants to sort his pile of disks in minimum number of possible steps. So help Vijay in doing so. So don't have to show the actual steps just answer the minimum number of possible steps to sort the pile so that that Vijay  can check whether he is doing his work right or wrong.

Input/Output Specs

Input Specification:

Your input will be an integer type array of size N containing integers from 1 to N in any random order which shows the position of disk from top to bottom. 

Output: 

Your output will be an integer type value that returns Minimum number of steps (as specified above) required to sort disk in a pile. 


For above example answer would be 2 steps. [ Minimum number of steps ]

using System;
public class DiskPile
{
  public static int MimimumNumber(int[] input)
  {
     return DiskPlace.FindMinimum(input);
  }
}

class MinimumMove
{
    int[] work = null;
    int [] ordered = null;
    public int minimumPossibleCount = 0;

    public MinimumMove(int count)
    {
        work = new int[count];
        ordered = new int[count];
    }

    public void Populatedisk(int[] values)
    {
        work = values;
        Console.WriteLine("Disk Values");
        PrintArray();
    }

    public void FindMinimum()
    {
        SortArray(work) ;
        foreach (int val in ordered)
        {
            int maxvalue = val;
            int index = FindLastIndex(work,maxvalue);
            Loop(maxvalue, index);
        }
    }

    private int FindLastIndex(int[] work,int maxvalue)
    {
        int index=0;
        for(int i=work.Length-1;i>=0;i--)
        {
            if(work[i]==maxvalue)
            {
                index= i;
                break;
            }
        }
        return index; 
    }
 
    private void SortArray(int[] work)
    {
        Array.Copy(work,ordered,work.Length);
        Array.Sort(ordered);
        Array.Reverse(ordered);
    }
 
    private void TopPlace(int fromindex)
    {
        for (int top = fromindex; top > 0; top--)
        {
        swap(top, top - 1);
        }
    }

    private void swap(int fromindex, int toindex)
    {
        int temp = work[fromindex];
        work[fromindex] = work[toindex];
        work[toindex] = temp;
    }
 
    public void Loop(int valueint index)
    {
        if(index>0)
        for (int ind = index-1; ind >= 0; ind--)
        {
            if (value < work[ind])
            {
                TopPlace(index);
                Console.WriteLine();
                Console.WriteLine("Place {0} in Top =>",value);
                PrintArray();
                minimumPossibleCount++;
                break;
            }
        }
    }
 
    private void PrintArray()
    {
        foreach (int disk in work)
        {
            Console.Write("[{0}]",disk);
        }
        Console.WriteLine("");
    }

}

public class DiskPlace
{
    public static int FindMinimum(int[] args)
    {
        try
        {
         
            int count = args.Length;
            int[] arr = new int[count];
            MinimumMove possible = new MinimumMove(count);
            possible.Populatedisk(args);
            possible.FindMinimum();
            return possible.minimumPossibleCount;
     
        }
        catch (Exception ex)
        {
            Console.WriteLine(ex.Message);
            return 0;
        }
    }
}

No comments:

Post a Comment