Skip to content

Instantly share code, notes, and snippets.

@jenny-codes
Created October 26, 2024 17:09
Show Gist options
  • Save jenny-codes/380a17ce0ceef4fd8dac51cb25f4dbf9 to your computer and use it in GitHub Desktop.
Save jenny-codes/380a17ce0ceef4fd8dac51cb25f4dbf9 to your computer and use it in GitHub Desktop.
dynamic_programming_recipe
# The recipe for doing dynamic programming
def dynamic_programming(table, recipe, data)
if !table[recipe[:key][data]].nil?
table[recipe[:key][data]]
elsif recipe[:cond].call(data)
table[recipe[:key][data]] = recipe[:then].call(data)
else
table[recipe[:key][data]] = recipe[:after].call(
recipe[:before].call(data).map { |d| dynamic_programming(table, recipe, d) }
)
end
end
def divide_and_conquer(value, steps)
if steps[:cond].call(value)
steps[:then].call(value)
else
steps[:after].call(
step[:before]
.call(value)
.map { |sub_value| divide_and_conquer(sub_value, steps) }
)
end
end
# ==========================
# Problem: Jump game
# Description: https://leetcode.com/problems/jump-game/
def can_jump_v1(nums)
return true if nums.count == 1
farest = 0
nums.each_with_index do |n, idx|
# next farest = n if idx == 0
farest = [(idx + n), farest].max
return true if farest >= nums.count - 1
return false if farest <= idx
end
end
def can_jump_v2(nums)
dp = []
reachable?(dp, nums)
end
def reachable?(dp, nums)
last = nums.count - 1
return dp[last] unless dp[last].nil?
return dp[last] = true if last == 0
dp[last] = nums[0..-2].each_with_index
.select { |n, idx| n >= last - idx }
.any? { |_n, idx| reachable?(dp, nums[0..idx]) }
end
def can_jump_v3(nums)
steps = {
key: ->(data) { data.count - 1 },
cond: ->(data) { data.count == 1 },
then: ->(_data) { true },
before: ->(data) { data[0..-2].each_with_index.select { |n, idx| n >= last - idx } },
after: ->(list) { list.include?(true) }
}
dynamic_programming([], steps, nums)
end
# ==========================
# Problem: Unique paths
# Description: https://leetcode.com/problems/unique-paths/
# v4: Solve with generalized formula
def uniq_paths_v4(m, n)
dp = {}
m.times do |x|
n.times do |y|
value = x == 0 || y == 0 ? 1 : dp[[x, y - 1]] + dp[[x - 1, y]]
dp[[x, y]] = value
end
end
dp[[m - 1, n - 1]]
end
# v3: Solve with generalized formula
def uniq_paths_v3(m, n)
recipe = {
key: ->(data) { data },
cond: ->(data) { data.first == 1 || data.last == 1 },
then: ->(_data) { 1 },
before: ->(data) { [[data.first - 1, data.last], [data.first, data.last - 1]] },
after: ->(pair) { pair.first + pair.last }
}
dynamic_programming({}, recipe, [m, n])
end
# v2: Solve with dynamic programming
def uniq_paths_v2(m, n)
recurse_v2(Array.new(m) { Array.new(n) }, m - 1, n - 1)
end
def recurse_v2(dp, m, n)
return dp[m][n] if dp[m][n]
return dp[m][n] = 1 if m.zero? || n.zero?
dp[m][n] = recurse_v2(dp, m, n - 1) + recurse_v2(dp, m - 1, n)
end
# v1: Solve with recursion
def uniq_paths_v1(m, n)
return 1 if (m == 1) || (n == 1)
uniq_paths_v1(m, n - 1) + uniq_paths_v1(m - 1, n)
end
# ===============================================================
# Test
require 'minitest/autorun'
class UniqPathsTest < Minitest::Test
def test_only_horizontal
assert uniq_paths_v1(1, 3) == 1
assert uniq_paths_v2(1, 3) == 1
assert uniq_paths_v3(1, 3) == 1
assert uniq_paths_v4(1, 3) == 1
end
def test_only_vertical
assert uniq_paths_v1(3, 1) == 1
assert uniq_paths_v2(3, 1) == 1
assert uniq_paths_v3(3, 1) == 1
assert uniq_paths_v4(3, 1) == 1
end
def test_two_dimentional_grid
assert_equal 3, uniq_paths_v1(3, 2)
assert_equal 3, uniq_paths_v2(3, 2)
assert_equal 3, uniq_paths_v3(3, 2)
assert_equal 3, uniq_paths_v4(3, 2)
end
def test_even_bigger_grid
assert_equal 28, uniq_paths_v1(3, 7)
assert_equal 28, uniq_paths_v2(3, 7)
assert_equal 28, uniq_paths_v3(3, 7)
assert_equal 28, uniq_paths_v4(3, 7)
end
end
class JumpGameTest < Minitest::Test
def test_one
assert can_jump_v1([0])
assert can_jump_v1([1])
assert can_jump_v2([0])
assert can_jump_v2([1])
end
def test_two
refute can_jump_v1([0, 2])
assert can_jump_v1([1, 0])
refute can_jump_v2([0, 2])
assert can_jump_v2([1, 0])
end
def test_three
assert can_jump_v1([1, 2, 3])
assert can_jump_v2([1, 2, 3])
end
def test_four
refute can_jump_v1([1, 0, 2])
refute can_jump_v2([1, 0, 2])
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment