Last active
August 25, 2023 10:43
-
-
Save yoones/c67c9b92651785bb355c3b0570d75eec to your computer and use it in GitHub Desktop.
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
#!/usr/bin/env ruby | |
# https://twitter.com/smlpth/status/1693574834179961234 | |
# "I have an array of amounts on one hand and a target amount on the other. I need to find a combination of amounts in the array that sums to the target. If multiple combinations work, take the one containing the most recent amounts." | |
require 'logger' | |
logger = Logger.new(STDOUT) | |
logger.level = :debug # set it to info to only see matches | |
# logger.level = :info | |
target_amount = 80 | |
amounts = [ | |
100, | |
20, | |
50, | |
40, | |
10, | |
60, | |
25, | |
70 | |
].delete_if { |i| i > target_amount } | |
max_idx = amounts.count - 1 | |
class Node | |
attr_accessor :value, :total, :idx | |
attr_accessor :parent_node, :children | |
def initialize(parent_node:, value:, idx:) | |
@parent_node = parent_node | |
@value = value | |
@idx = idx | |
@children = [] | |
end | |
def total | |
return @total if defined?(@total) | |
parent_total = parent_node.nil? ? 0 : parent_node.total | |
@total = parent_total + value | |
end | |
def to_s | |
return idx.to_s if parent_node.nil? | |
[parent_node.to_s, idx.to_s].join("->") | |
end | |
end | |
root = Node.new(parent_node: nil, value: amounts[0], idx: 0) | |
match = nil | |
incomplete_nodes = [root] | |
logger.debug "amounts = #{amounts}" | |
round = 1 | |
while incomplete_nodes.any? | |
logger.debug "* round ##{round} (incomplete_nodes.count = #{incomplete_nodes.count})" | |
next_round = [] | |
incomplete_nodes.each do |node| | |
logger.debug " node.idx = #{node.idx} (value: #{node.value})" | |
unless node.idx == max_idx | |
((node.idx + 1)..max_idx).to_a.each do |child_idx| | |
child_node = Node.new(parent_node: node, value: amounts[child_idx], idx: child_idx) | |
logger.debug " child_idx = #{child_idx}/#{max_idx} (value: #{child_node.value}) total=#{child_node.total}" | |
node.children << child_node | |
if child_node.total == target_amount | |
# I chose to keep the best match, but we can keep track of several ones if we need to perform post-filtering. | |
# I'm thinking of something like a Sudoku: one cell (C1) might accept multiple good answers, | |
# but other cells, with their own constraints, might later narrow down the list of good answers for C1. | |
match = child_node if match.nil? || match.idx > child_node.idx | |
logger.info "FOUND at #{child_node.to_s}" | |
# From now on, no need to look further down the tree for a match, | |
# we only need to look for a potential match with more "recent" amounts (idx closer to zero) | |
max_idx = child_node.idx | |
else | |
next_round << child_node | |
end | |
end | |
end | |
end | |
incomplete_nodes = next_round | |
round += 1 | |
end | |
if match.nil? | |
logger.info "No match found." | |
else | |
logger.info "Best match: #{match.to_s}" | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment