ルビー再帰アルゴリズム問題

Question

次のように

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 

コードは動作します：

は

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. 

ここに私のコードです。 word_idxは、文の配列内の単語のインデックスです。残りのスペースは、最初は列の数です。単語が置かれるのに十分なスペースがあるときは、次の単語とスペースが残っている同じ行の関数呼び出しを返します。残りのスペース> = 1 +単語の長さの場合、2つの連続した単語の間にスペースがあることを考慮します（これが理由で余分な条件付きです）。

word_idxが文の配列よりも長くなると、必要に応じて0にリセットされます。再帰関数は、row_numが問題で私たちに提供されている行の数より大きくなるまで継続します。

ただし、このコードは機能しません。私のアウトプットは正解よりも大きいのですが、概念的には私にとっては大丈夫です。誰か私のアプローチに何か間違っているのを見ますか？

Answer 1

これは、文章ではなく単語を数えているためです。

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) 

文の数（開始点0）を保持する新しい変数/引数（最後）を導入しました。 word_idx == sentence.lengthの場合は、残りのスペースに新しい文が当てはまることを意味します。したがって、nos = number_of_sentences+1です。
最後にnos（文章数）を返します。

Answer 2

問題が確認されているので、このメソッドを記述する別の方法を提案したいと思います。

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 

私はArray#cycleメソッドを使用しました。上記のようにsentenceについては、

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]]