Converting a Python script to Objective-C

Question

I recently asked this question to create a function for optimal word-wrapping and got the response I was looking for in this Python script. Unfortunately, I don't speak Python. :D Can someone help me convert this to Objective-C?

_

Code. I took the liberty of modifying the DP always to return exactly n lines, at the     cost of increasing the running time from O(#words ** 2) to O(#words ** 2 * n).

def minragged(text, n=3):
    """
    >>> minragged('Just testing to see how this works.')
    ['Just testing', 'to see how', 'this works.']
    >>> minragged('Just testing to see how this works.', 10)
    ['', '', 'Just', 'testing', 'to', 'see', 'how', 'this', 'works.', '']
    """
    words = text.split()
    cumwordwidth = [0]
    # cumwordwidth[-1] is the last element
    for word in words:
        cumwordwidth.append(cumwordwidth[-1] + len(word))
    totalwidth = cumwordwidth[-1] + len(words) - 1  # len(words) - 1 spaces
    linewidth = float(totalwidth - (n - 1)) / float(n)  # n - 1 line breaks
    def cost(i, j):
        """
        cost of a line words[i], ..., words[j - 1] (words[i:j])
        """
        actuallinewidth = max(j - i - 1, 0) + (cumwordwidth[j] - cumwordwidth[i])
        return (linewidth - float(actuallinewidth)) ** 2
    # best[l][k][0] is the min total cost for words 0, ..., k - 1 on l lines
    # best[l][k][1] is a minimizing index for the start of the last line
    best = [[(0.0, None)] + [(float('inf'), None)] * len(words)]
    # xrange(upper) is the interval 0, 1, ..., upper - 1
    for l in xrange(1, n + 1):
        best.append([])
        for j in xrange(len(words) + 1):
            best[l].append(min((best[l - 1][k][0] + cost(k, j), k) for k in xrange(j + 1)))
    lines = []
    b = len(words)
    # xrange(upper, 0, -1) is the interval upper, upper - 1, ..., 1
    for l in xrange(n, 0, -1):
        a = best[l][b][1]
        lines.append(' '.join(words[a:b]))
        b = a
    lines.reverse()
    return lines

if __name__ == '__main__':
    import doctest
    doctest.testmod()

You took all the indentations away. Indenting is part of python's syntax: instead of enclosing blocks with braces, you indent them. — salezica
– salezica, Commented Feb 22, 2011 at 7:21
Please edit your question and format the code properly (or ask whoever wrote it to give you an indented version). It is impossible to read python code without indentation. That's like stripping all { and } from C code. — ThiefMaster
– ThiefMaster, Commented Feb 22, 2011 at 7:21
Yikes! Didn't realize. The original code is posted here: stackoverflow.com/questions/5059956/… — Brian A Bird
– Brian A Bird, Commented Feb 22, 2011 at 7:35
I just copied and pasted this code into terminal to check if it was working and it is. So the indentation must be correct. — Brian A Bird
– Brian A Bird, Commented Feb 22, 2011 at 16:32

Community · Accepted Answer · 2017-05-23 10:33:08Z

Here's the function translated to Objective-C. It's been updated to compile but only barely tested for correctness (on the example given in your previous question: [... minragged:@"Just testing to see how this works." lineCount:3]). Nothing regarding efficiency or Objective-C idioms has been taken in to account.

@interface NSMutableArray (reverse)
/* Could also return self, but this makes it explicit that array is reversed in-place
   rather than returning a reversed copy.
 */
-(void)reverse;
@end

@implementation NSMutableArray (reverse)
-(void)reverse {
    int i,j;
    for (i=0,j=[self count]-1; i<j; ++i,--j) {
        [self exchangeObjectAtIndex:i withObjectAtIndex:j];
    }
}
@end




-(NSArray*)minragged:(NSString*)text lineCount:(int)n {
    int width = 0;
    NSArray *words = [text componentsSeparatedByCharactersInSet:[NSCharacterSet whitespaceAndNewlineCharacterSet]];
    NSMutableArray *cumWordWidth = [NSMutableArray arrayWithObject:[NSNumber numberWithInt:width]];
    for (NSString *word in words) {
        width += [word length];
        [cumWordWidth addObject:[NSNumber numberWithInt:width]];
    }
    int totalWidth = width + [words count] - 1,
        lineWidth = (double)(totalWidth - (n - 1)) / (double)(n),
        actualLineWidth,
        i, j, k, min_k;
    double cost, min_cost;

    // best[i][k][0] is the min total cost for words 0, ..., k - 1 on i lines
    // best[i][k][1] is a minimizing index for the start of the last line
    NSMutableArray *best = [NSMutableArray arrayWithCapacity:n],
                   *best_i_prev = [NSMutableArray arrayWithCapacity:([words count]+1)],
                   *best_i;

    [best_i_prev addObject:[NSArray arrayWithObjects:[NSNumber numberWithDouble:0.0],[NSNull null],nil]];
    for (i=0; i < [words count]; ++i) {
        [best_i_prev addObject:[NSArray arrayWithObjects:(NSNumber*)kCFNumberPositiveInfinity,[NSNull null],nil]];
    }
    [best addObject:best_i_prev];

    for (i=1; i <= n; ++i) {
        best_i=[NSMutableArray arrayWithCapacity:[words count]];
        for (j=0; j <= [words count]; ++j) {
            min_k=0;
            min_cost = [(NSNumber*)kCFNumberPositiveInfinity doubleValue];
            for (k=0; k < j; ++k) {
                actualLineWidth = j - k - 1;
                if (actualLineWidth < 0) {
                    actualLineWidth = 0;
                }
                actualLineWidth += [[cumWordWidth objectAtIndex:j] intValue]
                                   - [[cumWordWidth objectAtIndex:k] intValue];
                cost = (lineWidth - (double)(actualLineWidth));
                cost *= cost;
                cost += [[[best_i_prev objectAtIndex:k] objectAtIndex:0] doubleValue];
                if (cost < min_cost) {
                    min_cost = cost;
                    min_k = k;
                }
            }
            [best_i addObject:[NSArray arrayWithObjects:[NSNumber numberWithDouble:min_cost], 
                                                        [NSNumber numberWithInt:min_k],
                                                        nil]];
        }
        [best addObject:best_i];
        best_i_prev = best_i;
    }

    NSMutableArray *lines = [NSMutableArray arrayWithCapacity:n];
    NSRange range;
    int end;
    end = [words count];
    for (i=n; i > 0; --i) {
        range.location = [[[[best objectAtIndex:i] objectAtIndex:end] objectAtIndex:1] intValue];
        range.length = end-range.location;
        [lines addObject:[[words subarrayWithRange:range] componentsJoinedByString:@" "]];
        end = range.location;
    }
    [lines reverse];
    return lines;
}

You may wish to create an autorelease pool to clear out the objects created in -minragged:lineCount: so as not to exhaust memory. If you do, make sure to retain lines before draining the pool, and autoreleasing it afterwards.

It doesn't work yet, but it's definitely getting closer. I made a few edits so that it runs without errors (the returned response, isn't correct however). Hopefully someone will approve my edits.
@Brian: updated to compile and (hopefully) for correctness, though I only had one sample to test and was too lazy (my operating word for this answer) to create others. I would have approved your edits, but SO didn't list any pending.

Collectives™ on Stack Overflow

Converting a Python script to Objective-C

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related