sentence-screen-fitting

Sentence Screen Fitting

Problem Statement

• On the OpCode Slack

Given a rows x cols screen and a sentence represented by a list of non-empty words, find how many times the given sentence can be fitted on the screen. Note: A word cannot be split into two lines. The order of words in the sentence must remain unchanged. Two consecutive words in a line must be separated by a single space. Total words in the sentence won’t exceed 100. Length of each word is greater than 0 and won’t exceed 10. 1 ≤ rows, cols ≤ 20,000.

Example 2: Input: rows = 3, cols = 6, sentence = [“a”, “bcd”, “e”] Output: 2 Explanation: a-bcd- e-a— bcd-e- The character ‘-’ signifies an empty space on the screen.

Examples

rows	columns	sentence	output
2	8	hello world	1
3	6	a bcd e	2
4	5	I had apple pi	1

Helpful Utilities

I havent done of these in javascript in a while. Also, I’m doing a talk on javascript generators soon and you know I’m going to want to use them here, so lets do it.

Since we’re going to be using cycles of our sentences here, a method that can cycle forever would be useful

const cycle = function * (collection) {
    while(true) {
        for(const x of collection)
            yield x
    }
}

<<cycle>>
const letters = `abcdefg`

const it = cycle(letters)[Symbol.iterator]()
for(let i=0; i < 25; i+=1, it.next()) {}
return it.next().value

e

This is cool, but we to actually need to know what cycle we’re in too

const cycleCount = function * (collection) {
    let cycles = 0
    while(true) {
        for(const x of collection)
            yield cycles
        cycles += 1
    }
}

<<cycleCount>>
const letters = `abcdefg`

const it = cycleCount(letters)[Symbol.iterator]()
for(let i=0; i < 25; i+=1, it.next()) {}
return it.next().value

3

And we can combine these by zipping, which is handy

const zip = function * (...collections) {
    if(!collections.length)
        return
    const iterators = collections.map(x => x[Symbol.iterator]())
    while(true) {
        const nexts = iterators.map(i => i.next())
        if(nexts.some(x => x.done))
            return
        yield nexts.map(x => x.value)
    }
}

<<cycle>>

<<cycleCount>>

<<zip>>

const letters = `abcdefg`

const it = zip(cycle(letters), cycleCount(letters))[Symbol.iterator]()
for(let i=0; i < 25; i+=1, it.next()) {}
return it.next().value

[ ‘e’, 3 ]

Cool!

Putting it all together

So now the plan can become to create an iterator for our words, and then move through it one word at a time, eating up the space remaining on each column and then outputting the final cycle.

<<cycle>>

<<cycleCount>>

<<zip>>

const countCyclesForFitting = (rows, columns, words) => {
    const it = zip(cycle(words), cycleCount(words))[Symbol.iterator]()
    let {value: [currentWord, cycleNum]} = it.next()
    for(let r=0; r<rows; r++) {
        let spaceLeftInRow = columns
        while(spaceLeftInRow >= currentWord.length) {
            spaceLeftInRow -= (currentWord.length + 1) //+1 for the space that follows
            {[currentWord, cycleNum] = it.next().value} //putting this in a block since otherwise omitting the semi-colon above breaks things
        }
    }
    return cycleNum
}

return examples.map((example) => {
    const [rows, columns, phrase, expected] = example
    return [...example, countCyclesForFitting(rows, columns, phrase.split(` `))]
})

2	8	hello world	1	1
3	6	a bcd e	2	2
4	5	I had apple pi	1	1

In the above table the second to last column is the expected amount of cycles, the last is the one we got.

Looks like we got it! Woo.

Alternate approach idea:

It occurs to me that each line can only start with so many words (length(sentence) with max 100 to be exact) and given a line starts with a certain word the next sentence must begin at a known location. As we calculate things, we can simply cache for each word how many lines it occupies and what word the next line must start with. That would simplify the speed at runtime by an amount that should be sufficient for any modern day hardware, a further step can be taken by detecting once a cycle is complete and extrapolating from ther ein constant time.