Skip to content

Instantly share code, notes, and snippets.

@dieter-medium
Last active April 6, 2022 18:41
Show Gist options
  • Save dieter-medium/ad9f47a4e7e8ef4127461771a421e614 to your computer and use it in GitHub Desktop.
Save dieter-medium/ad9f47a4e7e8ef4127461771a421e614 to your computer and use it in GitHub Desktop.
Display the source blob
Display the rendered blob
Raw
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
class SparseMatrix
def initialize
@data = {}
end
def set(row_idx, col_idx, value)
data[key(row_idx, col_idx)] = value
end
def get(row_idx, col_idx)
data[key(row_idx, col_idx)]
end
private
attr_reader :data
def key(row_idx, col_idx)
"#{row_idx}-#{col_idx}"
end
end
class Minima
attr_accessor :start_index, :value
def initialize(value: 10**20)
@start_index = 0
@value = value
end
end
class Minimas
def initialize(count_nodes:)
@data = [Minima.new(value: 0)] + Array.new(count_nodes){ Minima.new }
end
def update_minima(cost, start_node_idx, end_node_idx)
return if @data[end_node_idx + 1].value <= cost
@data[end_node_idx + 1].value = cost
@data[end_node_idx].start_index = start_node_idx
end
def start_nodes
@data.map(&:start_index)
end
def [](idx)
@data[idx].value
end
private
attr_reader :data
end
class Dynamic
attr_reader :word_lengths, :max_line_length, :space_length, :word_lengths_count, :line_spaces
def initialize(words:, max_line_length:)
@word_lengths = words.map(&:length)
@word_lengths_count = @word_lengths.size
@max_line_length = max_line_length
@space_length = 1
end
def breaks
@line_spaces = precalculated_possible_line_spaces
@minimas = Minimas.new(count_nodes: word_lengths_count)
(0...word_lengths_count).each do |end_word_idx|
process_possible_lines_ending_with(end_word_idx)
end
@minimas.start_nodes
end
private
def process_possible_lines_ending_with(end_word_idx)
start_word_idx = end_word_idx
while start_word_idx >= 0
process_possible_line(start_word_idx, end_word_idx)
start_word_idx -= 1
end
end
def process_possible_line(start_word_idx, end_word_idx)
cost = penality_for_line(start_word_idx, end_word_idx)
@minimas.update_minima(cost, start_word_idx, end_word_idx)
end
def penality_for_line(start_word_idx, end_word_idx)
return 10 ** 10 if line_spaces.get(start_word_idx, end_word_idx) < 0
@minimas[start_word_idx] + line_spaces.get(start_word_idx, end_word_idx) ** 2
end
def precalculated_possible_line_spaces
word_lengths.each_with_index.each_with_object(SparseMatrix.new) do |(start_word_length, start_word_idx), line_space|
remaining_space_in_line = max_line_length - start_word_length
line_space.set start_word_idx, start_word_idx, remaining_space_in_line
((start_word_idx + 1)...word_lengths_count).each do |end_word_idx|
remaining_space_in_line = line_space.get(start_word_idx, end_word_idx - 1) - word_lengths[end_word_idx] - space_length
line_space.set start_word_idx, end_word_idx, remaining_space_in_line
end
end
end
end
Display the source blob
Display the rendered blob
Raw
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
class GreetyBreaks
attr_reader :word_lengths, :max_line_length, :space_length
def initialize(words:, max_line_length:)
@word_lengths = words.map(&:length)
@max_line_length = max_line_length
@space_length = 1
end
def breaks
current_length = -space_length
word_lengths.each_with_index.each_with_object([]) do |(word_length, idx), breaks|
if word_length + current_length >= max_line_length
breaks.push idx
current_length = -space_length
end
current_length += space_length + word_length
end
end
end
Display the source blob
Display the rendered blob
Raw
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
Display the source blob
Display the rendered blob
Raw
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
Display the source blob
Display the rendered blob
Raw
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
Display the source blob
Display the rendered blob
Raw
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
class Minima
attr_accessor :start_index, :value
def initialize(value: 10 ** 20)
@start_index = 0
@value = value
end
end
class Minimas
def initialize(count_nodes:)
@data = [Minima.new(value: 0)] + Array.new(count_nodes) { Minima.new }
end
def update_minima(cost, start_node_idx, end_node_idx)
return if @data[end_node_idx].value <= cost
@data[end_node_idx].value = cost
@data[end_node_idx].start_index = start_node_idx
end
def start_nodes
@data.map(&:start_index)
end
def [](idx)
@data[idx].value
end
private
attr_reader :data
end
class ShortestPath
attr_reader :word_lengths, :max_line_length, :space_length, :word_lengths_count, :line_spaces
def initialize(words:, max_line_length:)
@word_lengths = words.map(&:length)
@word_lengths_count = @word_lengths.size
@max_line_length = max_line_length
@space_length = 1
end
def breaks
pre_calculate_word_offsets
@minimas = Minimas.new(count_nodes: word_lengths_count)
(0...word_lengths_count).each do |start_word_idx|
process_possible_lines(start_word_idx, start_word_idx + 1)
end
@minimas.start_nodes
end
private
def pre_calculate_word_offsets
@offsets = [0]
word_lengths.each do |word_length|
@offsets.append(@offsets[-1] + word_length)
end
end
def process_possible_lines(start_word_idx, first_end_node_idx)
end_node_idx = first_end_node_idx
while end_node_idx <= word_lengths_count
break unless process_possible_line(end_node_idx, start_word_idx)
end_node_idx += 1
end
end
def process_possible_line(end_node_idx, start_word_idx)
current_line_length = calculate_current_line_length(end_node_idx, start_word_idx)
no_space_left_in_line = current_line_length > max_line_length
return false if no_space_left_in_line
penality = (max_line_length - current_line_length) ** 2
cost = @minimas[start_word_idx] + penality
@minimas.update_minima(cost, start_word_idx, end_node_idx)
true
end
def calculate_current_line_length(end_node_idx, start_word_idx)
spaces = end_node_idx - start_word_idx - 1
@offsets[end_node_idx] - @offsets[start_word_idx] + spaces
end
end
class Minima
attr_accessor :start_index, :value
def initialize
@start_index = 0
@value = 10 ** 20
end
end
class SMAWK
attr_reader :minima_provider, :minimas, :cnt_elements
def initialize(minima_provider, cnt_elements)
@minima_provider = minima_provider
@minimas = Array.new(cnt_elements + 1) { Minima.new }
@cnt_elements = cnt_elements
@minimas[0].value = 0
end
def cost(start_idx, end_idx)
minima_provider.call(minimas[start_idx].value, start_idx, end_idx)
end
def start_index(end_index)
minimas[end_index].start_index
end
def calc
backward_facing_cursor = cnt_elements + 1
forward_facing_cursor = 0
offset = 0
loop do
rth_column = [backward_facing_cursor, 2 ** (forward_facing_cursor + 1)].min
edge_between_head_and_tail = 2 ** forward_facing_cursor + offset
calc_sub_matrix(offset...edge_between_head_and_tail, edge_between_head_and_tail...(rth_column + offset))
right_most_col_of_sub_matrix = minimas[rth_column - 1 + offset]
minimum_right_most_col_of_sub_matrix = right_most_col_of_sub_matrix.value
exited_by_break = ((2 ** forward_facing_cursor)...(rth_column - 1)).each do |start_word_idx|
current_score = cost(start_word_idx + offset, rth_column - 1 + offset)
if current_score <= minimum_right_most_col_of_sub_matrix
backward_facing_cursor -= start_word_idx
forward_facing_cursor = 0
offset += start_word_idx
break true
end
false
end
next if exited_by_break == true
break if rth_column == backward_facing_cursor
forward_facing_cursor += 1
end
end
def calc_sub_matrix(rows, columns)
rows = rows.to_a
columns = columns.to_a
rows = evaluate_sub_matrix_rows(columns, rows)
handle_leftover_columns(columns, rows)
calculate_sub_matrix_minima(columns, rows)
end
private
def calculate_sub_matrix_minima(columns, rows)
current_row = current_column = 0
while current_column < columns.size
start_row_index = if current_column + 1 < columns.size
minimas[columns[current_column + 1]].start_index
else
rows[-1]
end
current_column_cost = cost(rows[current_row], columns[current_column])
if current_column_cost < minimas[columns[current_column]].value
minimas[columns[current_column]].value = current_column_cost
minimas[columns[current_column]].start_index = rows[current_row]
end
if rows[current_row] < start_row_index
current_row += 1
else
current_column += 2
end
end
end
def handle_leftover_columns(columns, rows)
return if columns.empty?
every_second_column = columns.each_slice(2).map { |v| v[1] }.to_a.compact
new_sub_matrix = every_second_column
calc_sub_matrix(rows, new_sub_matrix)
end
def evaluate_sub_matrix_rows(columns, rows)
[].tap do |stack|
current_row = 0
while current_row < rows.size
if stack.size.positive?
current_column_cost = columns[stack.size - 1]
if cost(stack[-1], current_column_cost) < cost(rows[current_row], current_column_cost)
stack.append(rows[current_row]) if stack.size < columns.size
current_row += 1
else
stack.pop
end
else
stack.append(rows[current_row])
current_row += 1
end
end
end
end
end
class LineBreaks
NEAR_INFINITY = 10 ** 10
attr_reader :word_offsets, :max_line_length, :space_length, :word_offsets_count, :line_spaces
def initialize(words:, max_line_length:)
@word_offsets = (0...(words.size-1)).each.reduce([0]){|res, index| res.push(words[index].length + res[-1])}
@word_offsets_count = @word_offsets.size
@max_line_length = max_line_length
@space_length = 1
@smawk = SMAWK.new(lambda { |current_minima, start_idx, end_idx|
cost(current_minima, start_idx, end_idx)
}, words.size - 1 )
end
def concave_modified_infinity(current_line_width, max_line_length)
concave_modifier = current_line_width - max_line_length
NEAR_INFINITY * concave_modifier
end
def cost(current_minima, start_idx, end_idx)
white_spaces = end_idx - start_idx - 1
start_word = word_offsets[start_idx]
end_word = word_offsets[end_idx]
current_line_width = end_word - start_word + white_spaces
return concave_modified_infinity(current_line_width, max_line_length) if current_line_width > max_line_length
current_minima + (max_line_length - current_line_width) ** 2
end
def breaks
@smawk.calc
(0...word_offsets_count).map { |idx| @smawk.start_index(idx) }
end
end
Display the source blob
Display the rendered blob
Raw
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
Display the source blob
Display the rendered blob
Raw
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
@dieter-medium
Copy link
Author

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment