Minimum time needed to print a string-CodePudding

How can I solve the following problem in C#/Java and time complexity?

There is a circular printer wheel with the letters A through Z in sequence. It wraps so A and Z are adjacent. The printer has a pointer that is initially pointing to 'A'. Moving from any character to any adjacent character takes 1 second . It can move in either direction . Given a string of letters, what is the minimum time needed to print the string?

Example : s = "BZA" time taken is 3 seconds , since we start from A and to reach B time is 1 sec. Then from B to Z is 2 seconds (B-> A -> Z) . Then Z -> A is again 1 sec , so totally it is 3 seconds.

I tried to assign each character in a dictionary by giving a number like A points to 1 and Z points to 26 but I couldnt proceed further since by using this logic time to travel from B -> Z which is 25 seconds which is incorrect.

CodePudding user response：

The dictionary approach is a good start: you need for all your letters to have an associated number, eg. starting with 1 for A, 26 for Z. Now you can do a simple subtraction to figure out the direct route (ignoring passing over 1 or 26).

If you have the direct distance, the indirect distance would be the exact opposite. You don't need to bother with complex math, just subtract the direct distance from your total.

example code:

int maxNumber = 26;
int firstNumber = myDictionary['A'];
int secondNumber = myDictionary['Q'];

int direct = Math.abs(secondNumber - firstNumber);

if (direct <= (int)(maxNumber/2))
    return direct;
return maxIdx - direct;

CodePudding user response：

Not sure if there is a better approach, but I think you should measure the distance between the letters considering the wrap around the Z => A.

This is an attempt to solve the problem, albeit I have not extensively tested it but it seems to work at the moment.

void Main()
{
    Console.WriteLine(LetterMinDistance('A', 'Y'));

    Console.WriteLine(LetterMinDistance('R', 'A'));

    Console.WriteLine(LetterMinDistance('C', 'C'));

    Console.WriteLine(LetterMinDistance('L', 'K'));

}

int LetterMinDistance(char source, char dest)
{
    const string alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
                             
    int idx1 = alphabet.IndexOf(source);
    int idx2 = alphabet.IndexOf(dest);
    
    int forward = idx2 - idx1;
    int backward = alphabet.Length - (idx2   idx1);
    
    return Math.Min(Math.Abs(forward),Math.Abs(backward));
}

CodePudding user response：

You could write a method to determine the minimum distance between two characters:

static int Distance(char start, char end)
{
    if (start < end)
        return Math.Min(end - start, 26 - end   start);
    else
        return Math.Min(start - end, 26 - start   end);
}

Then compute total distance for a string:

static int TotalDistance(string s)
{
    int total = 0;

    for (int i = 0; i < s.Length - 1;   i)
        total  = Distance(s[i], s[i   1]);

    return total;
}

So:

Console.WriteLine(TotalDistance("BZA")); // Prints 3