Ruby-rekursiven Algorithmus Ausgabe

Question

Arbeiten auf dem Algorithmus:

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. 

Hier ist mein 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 

Der Code funktioniert wie folgt. word_idx ist der Index eines Wortes im Satz-Array. Der verbleibende Platz ist anfangs die Anzahl der Spalten. Immer wenn genügend Platz für ein Wort vorhanden ist, gebe ich 1 + den Funktionsaufruf in der gleichen Zeile mit dem nächsten Wort und dem verbleibenden Platz zurück. Wenn der verbleibende Abstand> = 1 + Wortlänge ist, werde ich dafür verantwortlich sein, zwischen zwei aufeinander folgenden Wörtern ein Leerzeichen zu haben (weshalb ich die zusätzliche Bedingung habe).

Wenn word_idx länger als das Satzarray wird, wird es wie erwartet auf Null zurückgesetzt. Die rekursive Funktion wird fortgesetzt, bis row_num jetzt größer als die Anzahl der Zeilen ist, die uns im Problem zur Verfügung gestellt werden.

Dieser Code funktioniert jedoch nicht. Meine Ausgaben sind normalerweise größer als die richtige Antwort, aber konzeptionell scheint alles in Ordnung zu sein. Jeder sieht etwas falsch mit meinem Ansatz?

Answer 1

Es ist, weil Sie Wörter nicht Sätze zählen.

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) 

Ich habe eine neue Variable/Argument (die letzte) eingeführt, die die Anzahl der Sätze enthält (bei Start 0). Bei word_idx == sentence.length bedeutet dies, dass ein neuer Satz in den verbleibenden Platz passt, daher nos = number_of_sentences+1.
Am Ende geben wir nos (Anzahl der Sätze) zurück.

Answer 2

Da Sie das Problem identifiziert haben, möchte ich eine andere Möglichkeit vorschlagen, die Methode zu schreiben.

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 

Ich habe die Methode Array#cycle verwendet. Für sentence wie oben definiert,

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