Chunk SMS into SMSes of size 30 characters

Question

The problem statement is as follows -

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.

My approach -> was more around finding the approximate number of chunks first and then expanding on it but that didn't work. I was wondering is it even possible to first calculate how many chunks will be required mathematically or do we actually have to build chunks and see but then how do we build chunks without knowing 'n' of 'k/n'?

Answer 1

You have to know n to be able to know how many words can be put in each chunk because that depends on n.

Even if n is expressed in base 99 so that it only takes one character, you still need to examine the length of every word individually.

I have a suspicion that the optimal distribution of words between chunks is not the simple method of putting words (and spaces) into lines until the next item won't fit: it could be better to make some smaller chunks somewhere earlier to enable better packing later. However, this is not the cutting stock problem because the order must be preserved.

By the simple method, I mean packing the words in assuming there are less than ten chunks, and if not then start again based on there being less than 100 chunks, for example in 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

That happens to generate 99 chunks. The question doesn't ask for the output of the actual chunks - that part of the example code is there to have a look in case it is obvious where a different alogorithm could do better.