Ruby Recursive Algorithm Issue

Question

Working on the algorithm:

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 1:

Input:
rows = 2, cols = 8, sentence = ["hello", "world"]

Output: 
1

Explanation:
hello---
world---

The character '-' signifies an empty space on the screen.
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.
Example 3:

Input:
rows = 4, cols = 5, sentence = ["I", "had", "apple", "pie"]

Output: 
1

Explanation:
I-had
apple
pie-I
had--

The character '-' signifies an empty space on the screen.

Here's my code:

def words_typing(sentence, rows, cols)
   count_words(sentence, rows, cols, cols, 0, 0)
end

def count_words(sentence, rows, cols, remaining_space, row_num, word_idx)
    return 0 if row_num == rows #keep going until out of rows, ends the recursion
    word_idx = 0 if word_idx == sentence.length  #reset the word back to the first

    if remaining_space >= sentence[word_idx].length
        if remaining_space == sentence[word_idx].length
            return 1 + count_words(sentence, rows, cols, remaining_space - sentence[word_idx].length, row_num, word_idx + 1 )
        else #greater than 1
            return 1 + count_words(sentence, rows, cols, remaining_space - sentence[word_idx].length - 1, row_num, word_idx + 1 )
        end
    else #move to a new line, reset remaining space
        return count_words(sentence, rows, cols, cols, row_num+1, word_idx)
    end 
end

The code works as follows. word_idx is the index of a word in the sentence array. Remaining space is initially the number of columns. Whenever there's enough space for a word to be put down, I return 1 + the function call on the same row with the next word and the space remaining. If the remaining space >= 1 + word length, then I'll account for having a space between two consecutive words (which is why I have the extra conditional).

If word_idx gets longer than the sentence array, it resets back to zero as it should. The recursive function will keep going until row_num is now greater than the number of rows that are provided to us in the problem.

This code, however, doesn't work. My outputs are usually greater than the correct answer, but conceptually all seems okay with me. Anyone see something wrong with my approach?

Answer 1

As you problem has been identified I would like to suggest another way to write the method.

def sentences_per_page(rows, cols, sentence)
  nbr_sentences = 0
  last_word_index = sentence.size-1
  loopy = sentence.each_with_index.cycle
  word, idx = loopy.next
  rows.times do
    cols_left = cols
    while cols_left >= word.size
      cols_left -= (word.size + 1)
      nbr_sentences += 1 if idx == last_word_index
      word, idx = loopy.next
    end
  end
  nbr_sentences
end

rows = 4
cols = 5
sentence = ["I", "had", "apple", "pie"]
puts                    "    rows      sentences"
(1..12).each { |n| puts "     %d           %d" %
  [n, sentences_per_page(n, cols, sentence)] }
rows      sentences
  1           0
  2           0
  3           1
  4           1
  5           1
  6           2
  7           2
  8           2
  9           3
 10           3
 11           3
 12           4

I've used the method Array#cycle. For sentence as defined above,

loopy = sentence.each_with_index.cycle
  #=> #<Enumerator: #<Enumerator: ["I", "had", "apple", "pie"]:each_with_index>:cycle> 
loopy.first 10
  #=> [["I", 0], ["had", 1], ["apple", 2], ["pie", 3],
  #    ["I", 0], ["had", 1], ["apple", 2], ["pie", 3],
  #    ["I", 0], ["had", 1]]  

Answer 2

It's because you are counting words not sentences.

def words_typing(sentence, rows, cols)
   count_words(sentence, rows, cols, cols, 0, 0, 0)
end

def count_words(sentence, rows, cols, remaining_space, row_num, word_idx, number_of_sentences)
    nos = number_of_sentences
    return nos if row_num == rows #keep going until out of rows, ends the recursion

    if word_idx == sentence.length  #reset the word back to the first
    word_idx = 0 
    nos = number_of_sentences+1
    end
    if remaining_space >= sentence[word_idx].length

        if remaining_space == sentence[word_idx].length

            return count_words(sentence, rows, cols, remaining_space - sentence[word_idx].length, row_num, word_idx + 1, nos )
        else #greater than 1

            return count_words(sentence, rows, cols, remaining_space - sentence[word_idx].length - 1, row_num, word_idx + 1 , nos)
        end
    else #move to a new line, reset remaining space

        return count_words(sentence, rows, cols, cols, row_num+1, word_idx, nos)
    end 
end


rows = 3
 cols = 6
 sentence = ["a", "bcd", "e"]
words_typing(sentence, rows, cols)
rows = 4; cols = 5; sentence = ["I", "had", "apple", "pie"]
words_typing(sentence, rows, cols)

I've introduced a new variable/argument (the last) that holds number of sentences (at start 0). When word_idx == sentence.length it means that new sentence fitted in the remaining space, hence nos = number_of_sentences+1.
At the end we return nos (number of sentences).