Calculating the correct length of string per line with Page X/Y

Question

I got asked a question and now I am kicking myself for not being able to come up with the exact/correct result.

Imagine we have a function that splits a string into multiple lines but each line has to have x number of characters before we "split" to the new line:

private string[] GetPagedMessages(string input, int maxCharsPerLine) { ... }

For each line, we need to incorporate, at the end of the line "x/y" which is basically 1/4, 2/4 etc... Now, the paging mechanism must also be part of the length restriction per line.

I have been overworked and overthinking and tripping up on things and this seems pretty straight forward but for the life of me, I cannot figure it out! What am I not "getting"?

What am I interested in? The calculation and some part of the logic but mainly the calculation of how many lines are required to split the input based on the max chars per line which also needs to include the x/y.

Remember: we can have more than a single digit for the x/y (i.e: not just 1/4 but also 10/17 or 99/200)

Samples:

input = "This is a long message"

maxCharsPerLine = 10

output:

This i 1/4 // << Max 10 chars
s a lo 2/4 // << Max 10 chars
ng mes 3/4 // << Max 10 chars
sage 4/4 // << Max 10 chars

Overall the logic is simple but its just the calculation that is throwing me off.

Answer 1

A naive approach is to start counting the line lengths minus the "pager"'s size, until the line count changes in size ("1/9" is shorter than "1/10", which is shorter than "11/20", and so on):

private static int[] GetLineLengths(string input, int maxCharsPerLine)
{
    /* The "pager" (x/y) is at least 4 characters (including the preceding space) and at most ... 8?
    * 7/9     (4)
    * 1/10    (5)
    * 42/69   (6)
    * 3/123   (6)
    * 42/420  (7)
    * 999/999 (8)
    */

    int charsRemaining = input.Length;

    var lineLengths = new List<int>();

    // Start with " 1/2", (1 + 1 + 2) = 4 length
    var highestLineNumberLength = 1;

    var lineNumber = 0;
    do
    {
        lineNumber++;

        var currentLineNumberLength = lineNumber.ToString().Length; // 1 = 1, 99 = 2, ...
        if (currentLineNumberLength > highestLineNumberLength)
        {
            // Pager size changed, reset
            highestLineNumberLength = currentLineNumberLength;
            lineLengths.Clear();
            lineNumber = 0;
            charsRemaining = input.Length;
            continue;
        }

        var pagerSize = currentLineNumberLength + highestLineNumberLength + 2;
        var lineLength = maxCharsPerLine - pagerSize;

        if (lineLength <= 0)
        {
            throw new ArgumentException($"Can't split input of size {input.Length} into chunks of size {maxCharsPerLine}");
        }

        lineLengths.Add(lineLength);

        charsRemaining -= lineLength;

    }
    while (charsRemaining > 0);

    return lineLengths.ToArray();
}

Usage:

private static string[] GetPagedMessages(string input, int maxCharsPerLine)
{
    if (input.Length <= maxCharsPerLine)
    {
        // Assumption: no pager required for a message that takes one line
        return new[] { input };
    }

    var lineLengths = GetLineLengths(input, maxCharsPerLine);

    var result = new string[lineLengths.Length];

    // Cut the input and append the pager
    var previousIndex = 0;
    for (var i = 0; i < lineLengths.Length; i++)
    {
        var lineLength = Math.Min(lineLengths[i], input.Length - previousIndex); // To cater for final line being shorter
        result[i] = input.Substring(previousIndex, lineLength) + " " + (i + 1) + "/" + lineLengths.Length;
        previousIndex += lineLength;
    }

    return result;
}

Prints, for example:

This  1/20
is a  2/20
long  3/20
strin 4/20
g tha 5/20
t wil 6/20
l spa 7/20
n mor 8/20
e tha 9/20
n te 10/20
n li 11/20
nes  12/20
beca 13/20
use  14/20
of i 15/20
ts e 16/20
norm 17/20
ous  18/20
leng 19/20
th 20/20

Answer 2

The idea: First, find how many digits is the number of lines:

(n = input.Length, maxCharsPerLine = 10)
if n <= 9*(10-4)  ==> 1 digit
if n <= 9*(10-5) + 90*(10-6)  ==> 2 digits
if n <= 9*(10-6) + 90*(10-7) + 900*(10-8)  ==> 3 digits
if n <= 9*(10-7) + 90*(10-8) + 900*(10-9) + 9000*(10-10)  ==> No solution

Then, subtract the spare number of lines. The solution:

    private static int GetNumberOfLines(string input, int maxCharsPerLine)
    {
        int n = input.Length;
        int x = maxCharsPerLine;

        for (int i = 4; i < x; i++)
        {
            int j, sum = 0, d = 9, numberOfLines = 0;

            for (j = i; j <= i + i - 4; j++)
            {
                if (x - j <= 0)
                    return -1;   // No solution

                sum += d * (x - j);
                numberOfLines += d;
                d *= 10;
            }
            if (n <= sum)
                return numberOfLines - (sum - n) / (x - j + 1);
        }
        return -2;   // Invalid
    }

Usage:

    private static string[] GetPagedMessages(string input, int maxCharsPerLine)
    {
        int numberOfLines = GetNumberOfLines(input, maxCharsPerLine);
        if (numberOfLines < 0)
            return null;

        string[] result = new string[numberOfLines];

        int spaceLeftForLine = maxCharsPerLine - numberOfLines.ToString().Length - 2;  // Remove the chars of " x/y" except the incremental 'x'
        int inputPosition = 0;
        for (int line = 1; line < numberOfLines; line++)
        {
            int charsInLine = spaceLeftForLine - line.ToString().Length;
            result[line - 1] = input.Substring(inputPosition, charsInLine) + $" {line}/{numberOfLines}";
            inputPosition += charsInLine;
        }
        result[numberOfLines-1] = input.Substring(inputPosition) + $" {numberOfLines}/{numberOfLines}";
        return result;
    }