Created
July 11, 2016 08:36
-
-
Save gambala/01eae89eda2cb228c586eabe94eeeca5 to your computer and use it in GitHub Desktop.
Let's find minimal path in pyramid from top to bottom
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Pyramid | |
attr_accessor :layers_number | |
attr_accessor :layers | |
def initialize(layers_number, layers = []) | |
@layers_number = layers_number | |
@layers = layers | |
end | |
def populate_with_random_weights | |
(1..layers_number).each do |i| | |
layers << Array.new(i) { rand(1..9) } | |
end | |
end | |
def print | |
layers.each_with_index do |layer, layer_number| | |
puts layer_indentation(layer_number) + layer_weights(layer) | |
end | |
end | |
def weight(layer_number, cell_number) | |
layers[layer_number - 1][cell_number - 1] | |
end | |
private | |
def layer_indentation(layer_number) | |
' ' * (layers_number - layer_number) | |
end | |
def layer_weights(layer_weights) | |
layer_weights.join(' ') | |
end | |
end | |
class PyramidResolver | |
attr_accessor :pyramid | |
def initialize(pyramid) | |
@pyramid = pyramid | |
end | |
def print_minimal_path | |
puts minimal_path[:direction] | |
puts "Your path's length will be #{minimal_path[:length]}" | |
end | |
private | |
def minimal_path | |
@minimal_path ||= minimal_path_from(1, 1) | |
end | |
def minimal_path_from(layer_number, cell_number) | |
path = path_ahead(layer_number, cell_number) | |
path[:weight] = pyramid.weight(layer_number, cell_number) | |
path[:length] += path[:weight] | |
if layer_first?(layer_number) | |
path[:direction] = "start with #{path[:weight]} -> #{path[:direction]}" | |
end | |
path | |
end | |
def layer_last?(layer_number) | |
layer_number == pyramid.layers_number | |
end | |
def layer_first?(layer_number) | |
layer_number == 1 | |
end | |
def path_ahead(layer_number, cell_number) | |
return { length: 0, direction: 'finish!' } if layer_last?(layer_number) | |
path_ahead_between minimal_path_from(layer_number + 1, cell_number), | |
minimal_path_from(layer_number + 1, cell_number + 1) | |
end | |
def path_ahead_between(left, right) | |
case left[:length] <=> right[:length] | |
when -1 | |
{ length: left[:length], | |
direction: "go left to #{left[:weight]} -> #{left[:direction]}" } | |
when 0 | |
{ length: left[:length], | |
direction: "go left or right to #{left[:weight]} -> #{left[:direction]}" } | |
when 1 | |
{ length: right[:length], | |
direction: "go right to #{right[:weight]} -> #{right[:direction]}" } | |
end | |
end | |
end | |
pyramid = Pyramid.new(4) | |
pyramid.populate_with_random_weights | |
puts "Let's find minimal path in pyramid:" | |
pyramid.print | |
pyramid_resolver = PyramidResolver.new(pyramid) | |
pyramid_resolver.print_minimal_path | |
puts '' | |
pyramid = Pyramid.new(4, [[9], | |
[2, 2], | |
[9, 9, 4], | |
[6, 8, 9, 3]]) | |
puts "Let's find minimal path in pyramid:" | |
pyramid.print | |
pyramid_resolver = PyramidResolver.new(pyramid) | |
pyramid_resolver.print_minimal_path |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment