Skip to content

Instantly share code, notes, and snippets.

@maxArturo

maxArturo/Readme.md

Last active August 29, 2015 14:12
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save maxArturo/eb6e7cfd054151121b73 to your computer and use it in GitHub Desktop.
Save maxArturo/eb6e7cfd054151121b73 to your computer and use it in GitHub Desktop.
Download ZIP
Text Justify(Hard?)
Raw
Readme.md

Following with the "I'm sure there's some sort of implementation of this algorithm in MS Office" trend, here's a text justifying one - again from leetcode.

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

For example,

words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.

Return the formatted lines as:

[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Note: Each word is guaranteed not to exceed L in length.

Raw
solution.rb
# encoding: UTF-8
require 'minitest/autorun'
#https://oj.leetcode.com/problems/text-justification/
def text_justify(word_array, justify_length)
return -1 unless
word_array && word_array.count > 0 &&
justify_length > 0
running_count, result, line_array = 0, [], []
while word_array.any? do
if running_count + word_array.first.length +
(line_array.any? ? line_array.length : 0) > justify_length
result.push line_justify(line_array, line_array.count == 1,
justify_length)
running_count = word_array.first.length
line_array = [word_array.shift]
else
running_count += word_array.first.length
line_array.push word_array.shift
end
end
result.push line_justify(line_array, line_array.count == 1,
justify_length)
result
end
def line_justify(line_array, left_justify, total_length)
word_length = line_array.inject(0){|sum, n| sum += n.length}
space_length = total_length - word_length
if left_justify
line_array.join + (" " * space_length)
else
mod_spaces = space_length % (line_array.length - 1)
even_spaces = space_length / (line_array.length - 1)
line_array.inject do |memo, n|
additional_space = mod_spaces > 0 ? 1 : 0
mod_spaces -= 1
memo + (" ") * even_spaces + (" " * additional_space) + n
end
end
end
describe "answer validation" do
it "returns correct answers" do
input = ["This", "is", "an", "example", "of",
"text", "justification."]
answer = [
"This is an", "example of text", "justification. "]
assert_equal answer, text_justify(input, 16)
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment