将短信分成30个字符大小的短信。

Question

问题陈述如下 -

There is a text messaging service.It provides with an API to send SMSes to a user, 
but they can be at most 30 characters long. 
Also it doesn't guarantee the order in which the messages will be received.


You have to build a function which splits the text in chunks so that it can 
be sent in multiple messages. Each chunk has to be :
- upto 30 characters long
- no word should be split in the middle
- each chunk has to have its order suffixed in the form of '(k/n)' 
  e.g. "this is the first chunk (1/2)", "this is the second chunk (2/2)"
- if the text provided to the function is within 30 characters limit, 
  no ordering should be suffixed

Input/Output Format 
Each test case consists of a single line of words. Words are space 
separated. Any other character other than space is considered part of 
the word. For each test case, output the minimum number of chunks C 
required to fit the entire SMS. 

Restrictions
1 <=C<= 99; Input will be such that C remain in this mentioned limit 
if your algorithm is optimal. No word will have a length that does 
not fit in a single chunk (even after considering the suffix).

Sample Input: 
The best lies are always mixed with a little truth 
There is no creature on earth half so terrifying as a truly just man!!!!!
You know nothing, Jon Snow 

Sample Output 
3
3
1

Explanation: 
In first case, we will have to split as below 

The best lies are always (1/3)
mixed with a little (2/3)
truth (3/3)

First line is fully utilised with 30 characters in it. 
Second line has 25 characters but if we try to fit last word in this line, 
it becomes 31 characters. 'mixed with a little truth (2/2) 
Hence we must split into 3 parts as above.

我的方法是先找到大致块数，然后再进行扩展，但效果不佳。我在想，是否可以通过数学方法来计算需要多少块，还是必须先建立块并查看，但那么在不知道"k/n"的'n'的情况下如何建立块呢？

- discoverAnkit

---

@SomeDude，它说如果你的算法是最优的，这让我怀疑会有一个测试样例需要考虑后缀的可变长度。 - Andrew Morton

@SomeDude 这种方法会给出一个有效的分区，但问题要求得到最小数量的块。 - user58697

@AndrewMorton 我认为后缀部分应该始终占用固定的空间 => 1个空格字符，1个'('字符，2个数字（如果块数大于10，则为99），1个')'字符 => 后缀总共5个字符。这是恒定的 - 在剩余的25个字符中，您需要适合有效的单词。极端情况是，如果只有一个块并且有一个单词被省略了，请查看它是否可以适合后缀空间，即5个字符。 - SomeDude

@SomeDude，恐怕您错过了重要的部分：(k/n)是那30个字符的一部分。 - user58697

@SomeDude 当后缀从“(9/99)”变成“(10/99)”时，长度会改变，两者都与“(9/9)”的长度不同。 - Andrew Morton

Answer 1

你需要知道n才能知道每个块可以放多少单词，因为这取决于n。

即使n以99进制表示，只占一个字符，你仍然需要逐个检查每个单词的长度。

我怀疑最佳的单词分配方式不是简单地将单词（和空格）放入行中，直到下一个项目无法放入为止：在较早的某些位置上进行一些更小的块可能会更好地实现打包。但是，这不是cutting stock problem，因为必须保留顺序。

通过简单的方法，我指的是假设单词的数量少于十个块，并且如果不是这样，则基于单词数量少于100个块重新开始，例如在VB.NET中：

Imports System.Text
Imports System.Text.RegularExpressions

Module Module1

    Function NumberLength(n As Integer) As Integer
        Return If(n < 10, 1, 2)
    End Function

    Sub Main()
        Dim msg = "Escobazos tu dios pisan amor sus el las grupos se y no de los pulso mudas muerte mi inocentes vilo los las bajaba viciosa tierra de amor horizonte la se deja de tierra heridas ni los la es los recodos horizonte diminutas la de es nube talco hombrecillo de piel los se escobazos nadadora de bajo consume las se con ni las en por que donde tierra es sillas el de de que latido viva lo a grupos torre escaleras desnudo dolor me a la la quedo que sepultura signos criaturas de desnudo subía la húmedo desnuda latido nube quedo de la el nadadora el cielo dolor arroyo escobazos quedo donde de amor venas el viva poniendo desangradas torre que resonancia los fría ansioso el de subía el tierra todo se ansioso manteles por amor amor con de el quemadas resonancia con mujer el y que luna los bajaba quedo los yo a alegrísima de ilesa huido el mi que los se bajo la hombrecillo luna en de vilo es de el aire despenada que latido aire para sus horizonte todo muelles heridas viva hule tierra para huido de las a los llenando los que por húmedo tránsito tierra la la aire olvidando recodos de de la ligeros los término por luna bajaba tierra llenando del al que bajo de que de a pupila mueven que grupos se tránsito los ciudades de de nino mármol vuelve lenguas se los pisotean la vengo con faraón tránsito ballenas la se los tierra del escaleras de tierra nunca lenta se musgos que desgarrados la de desgarrados la imperturbable la resonancia y duro subía tierra me mi de talco escaleras el duro los desangradas sus buscando desangradas de pies algodón golondrina por que las no larga con diana que el en imperturbable de los luna al la huevos muertos las los las larga para borrachos de el aire los la bajo tierra fría talco los los comida en llanura en en los todo que en olvidando es de el de tu la de los muerte los las de que húmedo llenando de los pasan los hombrecillo se duro lenta ballenas ninos hule la con a la tierra por gustada es y se tierra amor las recientes manteles tierra de para signos el es un diana es del dios es imperturbable de consume de muelles luna para al nube tierra bajo apariencia encuentro es diminutas"
        Dim nPart = 1
        Dim nPartsTotal = 1 'assume 9 or less parts
        Dim nPartsTotalLength = 1
        Dim maxPartLength = 30

        If msg.Length <= maxPartLength Then
            Console.WriteLine("1")
            Console.ReadLine()
            Exit Sub
        End If

        Dim words = Regex.Split(msg, "( )")

        Dim suffixLength = 5 ' up to 9 parts

        Dim pos = 0
        Dim nWord = 0

        Dim thisPart As New StringBuilder
        Dim partText As New List(Of String)

        While nWord < words.Count()
            suffixLength = 3 + NumberLength(nPart) + nPartsTotalLength
            If pos + suffixLength + words(nWord).Length <= maxPartLength Then
                pos += words(nWord).Length
                nWord += 1
                thisPart.Append(words(nWord - 1))
            Else
                partText.Add(thisPart.ToString())
                pos = 0
                nPart += 1
                nPartsTotal += 1
                thisPart.Clear()

                If nPartsTotal > 9 AndAlso nPartsTotalLength = 1 Then
                    ' start again knowing that there are more than 9 parts required
                    nPartsTotalLength = 2
                    nPart = 1
                    nPartsTotal = 1
                    nWord = 0
                    partText.Clear()
                End If
            End If

        End While

        If thisPart.Length > 0 Then
            partText.Add(thisPart.ToString())
        End If

        Console.WriteLine(nPartsTotal)
        Console.WriteLine(New String("|"c, maxPartLength)) ' show max length

        For i = 1 To partText.Count()
            Console.WriteLine($"{partText(i - 1)}({i}/{nPartsTotal})")
        Next

        Console.ReadLine()

    End Sub

End Module

那会生成99个块。问题并未要求实际块的输出 - 例子代码中的这部分是为了查看是否明显地可以使用不同的算法来改进。

- Andrew Morton

Answer 2

这个问题其实很简单。我一开始试图先找出块的数量，结果弄错了。Andrew的解决方案是正确的。

附上我的JavaScript代码（仅供参考）

function splitSMSIn10Chunks(string){
    let parts = string.split(' ');
    let suffix = '(x/y)';
    let chunks = 0;
    let currentChunk = '';
    for(let i=0;i<parts.length;i++){ 

        if((currentChunk.length+1+parts[i].length+suffix.length)<=30){
            currentChunk = currentChunk + parts[i] + " ";
        }else{            
            currentChunk = currentChunk + suffix;
            currentChunk = parts[i]+" " ;
            chunks++;
        }        
        if(i==parts.length-1){
            //Last chunk
            currentChunk = currentChunk + suffix;
            chunks++;
        }
        if(chunks==10) return -1;
    }
    return chunks;
};

function splitSMSIn99Chunks(string){

    let parts = string.split(' ');
    let suffix = '(x/yy)';
    let chunks = 0;
    let currentChunk = '';
    for(let i=0;i<parts.length;i++){  

        if((currentChunk.length+1+parts[i].length+suffix.length)<=30){
            currentChunk = currentChunk + parts[i] + " ";
        }else{            
            currentChunk = currentChunk + suffix;
            currentChunk = parts[i]+" " ;
            chunks++;
            if(chunks==9){
                suffix = '(xx/yy)';
            }
        }        

        if(i==parts.length-1){
            //Last chunk
            currentChunk = currentChunk + suffix;
            chunks++;
            console.log(currentChunk);
        }
    }
    return chunks;
};

let sms = "The best lies are always mixed with a little truth The best lies are always mixed with a little truth The best lies are always mixed with a little truth The best lies are always mixed with a little truth";

let chunksRequired = splitSMSIn10Chunks(sms);
if(chunksRequired==-1){
    console.log(splitSMSIn99Chunks(sms));
}else{
    console.log(chunksRequired);
}

可以用一个函数完成，但为了保持简单易读，我创建了两个单独的函数。

- discoverAnkit