Shortest Path to accomplish given scenario

Question

I was asked in an interview to code the following scenario

A tv has 0-450 channels but the remote buttons 2,5,8,9 have malfunctioned so write a program to get input from the user and traverse that channel through the shortest path

EXAMPLE:

47 -> no need to traverse button 4,7 is available

45 -> 44+1 output from which channel to traverse and how many traversal required to reach 45.

55 -> 55 can be reached from 47 only coz 54 has 5. |||ly (50-55) has 5 in it so again 48 and 49 has 8 and 9 respectively.

I've tried my logic but not even able to code in such a way it is best shortest path for all input PLEASE help me with the logic or show me the program.

Answer 1

Think in another way. A valid solution can only be formed by valid digits.

---

1. Build a valid button set by remove malfunctioned buttons from all possible buttons

   0,1,3,4,6,7

2. Find first invalid digit of the channel number from left to right. If found, go to step 3. Otherwise, no need to traverse button.

3. Generate two numbers nearest to the channel number on both side with valid button set only.

   For example: channel number = 189

   Blind all digits on the right of first invalid digit -> 18x

   Upper bound: Look for a slightly bigger digit of 8 from valid set, but not found. In such case, we look for a bigger valid digit of 1, we get 3. Then pad smallest valid digit for the rest. We get 300.

   Lower bound: Look for a slightly smaller digit of 8 from valid set, we get 7. Then pad largest valid digit for the rest. We get 177.

4. Consider boundary case if lower or upper bound cannot be formed (channel number 450 should get 0 as valid solution) and out of upper limit

5. Compare the two numbers with the channel number and obtain the closest one.

6. Format and Output

---

Time complexity: O(log(n)) for all cases

Answer 2

This is working as expected, I believe.
It can be further optimized, but is the best I can do right now.

The formatting is necessary because of the corner cases when user types 8 or 9 or 89..99, in those cases, there is a change in the decimal places and that's the only way I found to fix it.

class RemoteControl
{        
    public char[] brokenButtons = new char[4] {'2','5','8','9'};
    public char[] availableButtons = new char[6] { '0', '1', '3', '4', '6', '7'};        
    public char[] allButtons = new char[10] {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};

    private char[] HighestPriorChannel(char[] inputChannel)
    {
        char[] channel = inputChannel.ToArray();            

        int pos;
        bool changed, isMarked = false;
        for (int i = channel.Length - 1; i >= 0; i--)
        {
            changed = false;
            pos = Array.IndexOf<char>(allButtons, channel[i]);
            if (isMarked) pos--;

            while (pos >= 0)
            {
                channel[i] = allButtons[pos];
                pos--;
                if (!brokenButtons.Contains(channel[i])) break;
                else changed = true;
            }

            if (isMarked || changed)
            {
                for (int j = i + 1; j < channel.Length; j++)
                    channel[j] = availableButtons.Last();
            }
            isMarked = brokenButtons.Contains(channel[i]);
        }            

        return channel;
    }

    private char[] LowestNextChannel(char[] inputChannel)
    {
        char[] channel = inputChannel.ToArray();         
        int pos;
        bool changed, isMarked = false;
        for (int i = channel.Length - 1; i >= 0; i--)
        {
            changed = false;
            pos = Array.IndexOf<char>(allButtons, channel[i]);
            if (isMarked) pos++;

            while(pos < allButtons.Length)
            {
                channel[i] = allButtons[pos];
                pos++;
                if (!brokenButtons.Contains(channel[i])) break;
                else changed = true;
            }

            if (isMarked || changed)
            {
                for (int j = i + 1; j < channel.Length; j++)
                    channel[j] = availableButtons.First();
            }
            isMarked = brokenButtons.Contains(channel[i]);
        }            
        return channel;
    }

    private int FindNearestChannel(char[] channel)
    {
        char[] prior = HighestPriorChannel(channel);
        char[] next = LowestNextChannel(channel);

        int intChannel = Convert.ToInt32(new string(channel));
        int intPrior = Convert.ToInt32(new string(prior));
        int intNext = Convert.ToInt32(new string(next));

        bool nextInRange = IsChannelInRange(intNext);
        bool priorInRange = IsChannelInRange(intPrior);

        if (nextInRange && priorInRange)
        {
            if ((intChannel - intPrior) > (intNext - intChannel))
            {
                return intNext;
            }
            else
            {
                return intPrior;
            }
        }
        else if (nextInRange)
        {
            return intNext;
        }
        else
        {
            return intPrior;
        }

    }

    private void GoBackward(int desiredChannel, int nearestChannel)
    {
        int times = 0;
        while (desiredChannel != nearestChannel)
        {
            nearestChannel--;
            times++;

        }
        Console.WriteLine("Press button (-) {0} times", times);
    }

    private void GoForward(int desiredChannel, int nearestChannel)
    {
        int times = 0;
        while(desiredChannel != nearestChannel){
            nearestChannel++;
            times++;

        }
        Console.WriteLine("Press button (+) {0} times", times);
    }

    public void FindChannel(string channel)
    {
        if (channel.Intersect(brokenButtons).Count() > 0)
        {                
            int nearestChannel = FindNearestChannel(channel.ToArray());

            Console.WriteLine("Turn Channel {0}", nearestChannel);

            int asInt = Convert.ToInt32(channel);
            if (asInt > nearestChannel)
                GoForward(asInt, nearestChannel);
            else
                GoBackward(asInt, nearestChannel);
        }
        else
        {
            Console.WriteLine("Turn Channel {0}", channel);
            Console.WriteLine("Done.");
        }
    }        

    private bool IsChannelInRange(int channel)
    {
        return (channel < 451) && (channel >= 0);
    }

    public bool IsValidInput(string input)
    {            
        int asInt = 0;
        return Int32.TryParse(input, out asInt) && IsChannelInRange(asInt);
    }        
}
class Program
{
    static void Main(string[] args)
    {
        RemoteControl rm = new RemoteControl();
        string input = "";
        bool turnOff = false;
        do
        {
            Console.Clear();
            Console.WriteLine("Enter a valid channel or \"off\" to turn off");
            input = Console.ReadLine();
            turnOff = input.ToLower() == "off";
        }
        while (!(turnOff || rm.IsValidInput(input)));

        if (!turnOff)
        {                
            rm.FindChannel(input.PadLeft(3,'0'));
            Console.ReadLine();
        }
    }
}

Answer 3

*Updated and checked for errors, final solution could be something like this:

    public static void Traverse(int channelToAccess, int maxChannels, params char[] brokenButtons)
    {      
        int result = -1;      // closest channel num

        for (int i = 1; result == -1 && i > 0 && i < maxChannels; i++)
        {
            if (!(channelToAccess + i).ToString().Any(brokenButtons.Contains)) { result = channelToAccess + i; break; }
            if (!(channelToAccess - i).ToString().Any(brokenButtons.Contains)) { result = channelToAccess - i; break; }
        }
       int difference = result - channelToAccess;
       Console.WriteLine("To open channel {0} you should turn channel {1} and press {2} button {3} times", channelToAccess, result, difference > 0 ? "-" : "+", Math.Abs(difference));
    }

Example of usage : Traverse(255, 450, '2', '5', '8', '9');

Output: To open channel 255 you should turn channel 300 and press button '-' 45 times

Answer 4

For a TV remote we can make some assumptions:

• It does not add up so we have to use +1 or -1 button starting with the nearest channel
• When reaching the upper bound +1 will go to the lowest number, -1 acts in the other direction the same way.

Starting with these assumptions to find the channel with the least steps in either direction:

public int NearestChannel(int channel)
{
   var forward = StepsForward(channel);
   var backward = StepsBackward(channel);

   if (forward < backward)
   {
      return channel - forward;
   }
   else
   {
      return channel + backward;
   }
}

The StepsForward and StepsBackward methods are simply counting until we reach an valid result. The only thing to be aware of are the upper and lower bounds (0 and 450 in your example):

public int StepsForward(int channel)
{
   int steps = 0;

   while (!IsValid(channel))
   {
      channel--;
      if (channel < 0)
      {
         channel = 450;
      }
      steps++;
   }

   return steps;
}

public int StepsBackward(int channel)
{
   int steps = 0;

   while (!IsValid(channel))
   {
      channel++;
      if (channel > 450)
      {
         channel = 0;
      }
      steps++;
   }

   return steps;
}

Validation is then merely looking if the number to test containes any invalid digits:

public bool IsValid(int number)
{
   var numberAsString = number.ToString();
   foreach (var digit in numberAsString)
   {
      switch (digit)
      {
         case '2':
         case '5':
         case '8':
         case '9':
            return false;
      }
   }

   return true;
}