Class: WordWrapper::MinimumRaggedness

Inherits:
WordWrapper show all
Defined in:
lib/minimum_raggedness.rb

Constant Summary

Constants inherited from WordWrapper

Infinity, OneSpaceWidth, Width

Instance Attribute Summary collapse

Attributes inherited from WordWrapper

#output, #width, #words

Instance Method Summary collapse

Methods inherited from WordWrapper

#illegal_words, #initialize, #line_cost, #total_cost

Constructor Details

This class inherits a constructor from WordWrapper

Instance Attribute Details

#splits ⇒ Object

Returns the value of attribute splits.



3
4
5
 
# File 'lib/minimum_raggedness.rb', line 3

def splits
  @splits
end

Instance Method Details

#compute_wrapping ⇒ Object 



87
88
89
90
 
# File 'lib/minimum_raggedness.rb', line 87

def compute_wrapping
  @words = @input.split
  @cost, @splits = optimal_cost(@words.dup, @words.length)
end

#cost ⇒ Object 



70
71
72
73
 
# File 'lib/minimum_raggedness.rb', line 70

def cost
  compute_wrapping unless @cost
  @cost
end

#cost_between(words, i, j) ⇒ Integer

Return the c

Parameters:

  • words (Array<String]) —

    in the text

  • i (Integer) —

    left bound of words to check between

  • j (Integer) —

    right bound of words to check between

Returns:

  • (Integer) —

    cost of a line containing the words from i to j



10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
# File 'lib/minimum_raggedness.rb', line 10

def cost_between(words, i, j)
  @c ||= {}
  @c[[i,j]] ||=
    begin
      # Special case for single words that are longer than @width.
      # Mark their cost as 0 so they get their own line without
      # messing up the algorithm
      if j == i and words[j-1].length >= @width
        cost = 0
      else
        cost = @width -
          ((j - i) * OneSpaceWidth ) -
          words[i-1..j-1].inject(0){ |acc, w| acc + w.length } # 0 indexed
        cost = cost >= 0 ? cost**2 : Infinity
      end
    end
end

#optimal_cost(words, j) ⇒ Array<Integer, Array<String>>

Use dynamic programming to computer the optimal cost of this text. Recursively calls itself, keeping track of costs found as well as the array of splits required to give that cost (so we can actually generate the optimal text at the end).

The evaluation looks like this (o is shorthand for optimal_cost):

        -- o(1, j)                                   if c(1,j) < Inf
o(j) = -
        -- min[ 1 <= k < j ] ( o(k) + c(k+1, j) )    if c(1,j) == Inf

Parameters:

  • words (Array<String>) —

    to split

  • j (Intger) —

    index to compute cost up through, goes from 1..length of words as we recursively compute costs.

Returns:

  • (Array<Integer, Array<String>>) —

    (cost, [chain of splits that gives cost])



44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
 
# File 'lib/minimum_raggedness.rb', line 44

def optimal_cost(words, j)
  @o ||= {}
  @o[j] ||=
    begin
      ks = []
      cost = cost_between words, 1, j
      if cost == Infinity and j > 1
        ks = (1..j-1)
        candidates = {}
        ks.collect do |k|
        o = optimal_cost words, k
        c = cost_between words, k + 1, j
        # store both the chain of the child call and k
        candidates[c + o[0]] = [o[1], k]
      end
        if candidates.any?
          cost = candidates.keys.min
          # ks is the chain of splits for this line of recursion
          ks = candidates[cost][0] + [candidates[cost][1]]
        end
      end
      # cost of this line, chain of splits that result in this cost
      [cost,ks]
    end
end

#solution? ⇒ Boolean

Returns:

  • (Boolean) 


92
93
94
 
# File 'lib/minimum_raggedness.rb', line 92

def solution?
  cost != Infinity
end

#wrap ⇒ Object 



75
76
77
78
79
80
81
82
83
84
85
 
# File 'lib/minimum_raggedness.rb', line 75

def wrap
  compute_wrapping unless @splits
  prev = 0
  ans = ""
  @splits.each do |s|
    ans << @words[prev..s-1].join(" ") << "\n"
    prev = s
  end
  ans << @words[prev..@words.length].join(" ") << "\n"
  ans
end