CODEWITHSUNDEEP
algorithmrecursionword-wrapmemoization
Miss Rainbowdash
Miss Rainbowdash

Reputation: 205

Is it possible to develop a recursive word wrap algorithm?

I want to develop a recursive word wrap algorithm that takes a specified string and wrap length (the maximum number of characters on one line) to return a wrapped output at the input length. I don't want it to break apart words. So for example, This is the first paragraph that you need to input with length 20 returns as:

This is the first
paragraph that you
need to input

I already have a dynamic programming (bottom-up) solution implemented, but I was wondering if it's possible to write an algorithm to do this using just recursion (top-down) instead? I'd also like to memoize it if I can. Please don't give me any runnable code... I"m just wondering about ideas/pseudocode.

Upvotes: 2

Views: 2077

Answers (3)

Amit Soni
Amit Soni

Reputation: 1

The below code will help you to get the optimal cost for that problem.

#include<bits/stdc++.h>
using namespace std;

// method to get the optimal cost
int findOptimalCost(int *arr, int s, int e,int lineLength,map<pair<int,int>,int>dp) {

if(s>=e)    // return 0 for the last line because we are not calculating the last line space
    return 0;

if(dp.find({s,e}) != dp.end()) {  // return cost if we already calculate
    return dp[{s,e}];
}

int minCost = INT_MAX;
for(int i=s;i<=e;i++) {
    int sum = 0,space=i-s;
    for(int j =s; j<=i; j++) 
        sum += arr[j];  // add the word length 
    sum += space;  // add the space for words (if 2 word then we will count 1 space ) 
    int cost;
    if(sum<=lineLength) 
        cost = (lineLength-sum)*(lineLength-sum) + findOptimalCost(arr,s+1+space,e,lineLength,dp);  // calculate the cost for perticular line and call for rest line
        if(minCost > cost) {
            minCost = cost; // update the minCost variable if the latest cost is less then the previous calculated cost
        }
    }
return dp[{s,e}] = minCost; // store the minimum cost for particular line and return
}

int main()
{
//code
    int len = 4; // total word in the list
    int arr[] = {3,2,2,5};  // let us assume the length of word
    
    int lineLength = 6; // size of max line length
    
    
    map<pair<int,int>,int> dp;
    cout<<findOptimalCost(arr,0,len-1,lineLength,dp)<<endl;
    
return 0;
}

Upvotes: 0

Ankit kaushik
Ankit kaushik

Reputation: 1063

import java.lang.Math;

public int RCS(int[] l , int n , int m , int index) {

    // first base condition - if index gets beyond the array 'l' , then return 0;
    if (index > n - 1) return 0;

    // second base condition - if index is the last word i.e there is only one word left in the
    // array to be inserted in the line then return the cost if added in that line.
    if (index == n - 1) return (m - l[n - 1]) * (m - l[n - 1]) * (m - l[n - 1]);

    // make a global cost variable to be returned
    int cost = Integer.MAX_VALUE;

    // Here , we try to select words from the array and apply RCS on the rest of the array.
    // From index to last element , we iteratvely select first , or first two and so on.
    for (int i = index ; i < n ; i++) {
        int current_space_sum = 0 ;
        // we add the length of the selected word. We have selected words in array from index to i.
        for (int k = index ; k <= i ; k++) {
            current_space_sum = current_space_sum + l[k] ;
        }
        // Adding the space between the words choses. If 2 words are chosen , there is one space and so on
        current_space_sum = current_space_sum + i - index;
        // If the length of the chosen words is greater than the line can accept , no need of looking beyond.
        if (current_space_sum > m) break;
        // Iteratively find the minimum cost
        cost =  Math.min(cost , (m - current_space_sum) * (m - current_space_sum) * (m - current_space_sum) + RCS(l , n , m , i + 1));
    }
    return cost;
}



public static void main(String[] args) {
    WordWrap w = new WordWrap();
    int[] l = {3, 2 , 2 , 5};
    int n = l.length;
    int m = 6;
    int result = w.RCS(l , n , m , 0);

    System.out.println(result);
}

Upvotes: 0

BrettFromLA
BrettFromLA

Reputation: 916

Something like the pseudocode below should work. (I'm sure we'll get comments if I made a mistake!)

function Wrap(the_text,line_len)

if length(the_text) > line_len then
    text_bit = the first few words of the_text, keeping their length shorter than line_len
    remove text_bit from the beginning of the_text
    return text_bit + linefeed + Wrap(the_text, line_len)
else
    return the_text
end if

end function

Upvotes: 2

Related Questions