Skip to content

Instantly share code, notes, and snippets.

@gambala
Created July 11, 2016 08:36
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 gambala/01eae89eda2cb228c586eabe94eeeca5 to your computer and use it in GitHub Desktop.
Save gambala/01eae89eda2cb228c586eabe94eeeca5 to your computer and use it in GitHub Desktop.
Let's find minimal path in pyramid from top to bottom
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