smart_word_wrap.rb

#!/usr/bin/ruby

# Author: Daniel "Trizen" Șuteu
# License: GPLv3
# Date: 15th October 2013
# https://trizenx.blogspot.com
# https://trizenx.blogspot.com/2013/11/smart-word-wrap.html

# Smart word wrap algorithm
# See: https://en.wikipedia.org/wiki/Word_wrap#Minimum_raggedness

class SmartWordWrap
    @width = 0;
    def prepare_words(array)
        if !@preprocessed && array.any? { |w| w.size > @width }
            @preprocessed = true
            new_array = []
            array.each do |value|
                if value.size > @width
                    new_array.concat(value.scan(/.{1,#{@width}}/m))
                else
                    new_array << value
                end
            end
            array = new_array
        end
        cache_key = array.hash
        return @prepare_cache[cache_key] if @prepare_cache&.key?(cache_key)
        root = []
        len = 0
        i = -1
        limit = array.size-1
        while ((i+=1) <= limit)
            len += (word_len = array[i].size)
            if len > @width
                if word_len > @width
                    len -= word_len
                    value = array[i]
                    array.delete_at(i)
                    array.insert(i, *(value.scan(/.{1,#{@width}}/m)))
                    limit = array.size-1
                    i -= 1; next
                end
                break
            end
            root << [array[0..i].join(' '), prepare_words(array[i+1 .. limit])]
            break if ((len += 1) >= @width)
        end
        @prepare_cache[cache_key] = root
        root
    end

    def combine(root, path)
        cache_key = [root, path].hash
        return @combine_cache[cache_key] if @combine_cache&.key?(cache_key)
        row = []
        key = path.shift
        path.each do |value|
            root << key
            if value.empty?
                row = [root + []]
            else
                value.each do |item|
                    row += combine(root, item)
                end
            end
            root.pop
        end
        path.unshift(key)
        @combine_cache[cache_key] = row
        row
    end

    def find_best(arrays)
        best = { score: Float::INFINITY, value: [] }
        arrays.each { |array|
            score = 0;
            array.each { |line| score += (@width - line.size)**2 }
            if score < best[:score]
                best[:score] = score
                best[:value] = array
            end
        }
        best[:value]
    end

    def smart_wrap(text, width)
        @width = width;
        words = text.is_a?(Enumerable) ? text : text.split(' ')
        @preprocessed = false
        @prepare_cache = {}
        @combine_cache = {}
        n = words.size
        if n > 0
            prepared_words = []
            words.each do |w|
                if w.size > @width
                    prepared_words.concat(w.scan(/.{1,#{@width}}/m))
                else
                    prepared_words << w
                end
            end
            words = prepared_words
            @preprocessed = true
            n = words.size
            dp = Array.new(n + 1, Float::INFINITY)
            nxt = Array.new(n + 1, 0)
            dp[n] = 0
            (n - 1).downto(0) do |i|
                current_len = 0
                (i...n).each do |j|
                    current_len += words[j].size + (j > i ? 1 : 0)
                    break if current_len > width
                    cost = (@width - current_len) ** 2
                    total_cost = cost + dp[j + 1]
                    if total_cost < dp[i]
                        dp[i] = total_cost
                        nxt[i] = j + 1
                    end
                end
            end
            build_cache = lambda do |idx|
                return [] if idx >= n
                next_idx = nxt[idx]
                curr_slice = words[idx...next_idx]
                line_str = curr_slice.join(' ')
                child_structure = build_cache.call(next_idx)
                structure = [[line_str, child_structure]]
                @prepare_cache[words[idx...n].hash] = structure
                structure
            end
            build_cache.call(0)
        end
        lines = [];
        self.prepare_words(words).each { |path| lines += combine([], path) }
        best = self.find_best(lines)
        best == nil and return nil
        return best.join("\n")
    end
end

text = "Hello, World! Hello, World!, Hello, World!, Hello, World!" * 5
obj = SmartWordWrap.new
puts obj.smart_wrap(text, 25)