Created
October 26, 2024 17:09
-
-
Save jenny-codes/380a17ce0ceef4fd8dac51cb25f4dbf9 to your computer and use it in GitHub Desktop.
dynamic_programming_recipe
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
# 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