Skip to content

Instantly share code, notes, and snippets.

@fjahr fjahr/pb.py
Last active Apr 20, 2018

Embed
What would you like to do?
Minimize Change Output for Bitcoin transactions, naive implementation
"""
Suppose you are given a list of possible Bitcoin that you control (inputs). You
need to pay someone exactly 0.71 BTC. How would you select exactly 2 inputs in
such a way as to minimize the change output if you could ignore fees? Write a
python function that selects the two inputs.
"""
from itertools import permutations
TEST_INPUTS = [0.21, 0.59, 1.34, 3.45, 0.3, 0.84, 0.53, 0.62, 0.70, 0.21, 0.44,
0.28, 0.39, 200.9, 4.34]
PAYMENT = 0.71
def run(inputs, payment):
"""
Runs the program and prints result to std out.
"""
filtered_inputs = filter_larger_than_payment(inputs, payment)
best_combo = find_best_combo(filtered_inputs, payment)
print(best_combo)
def filter_larger_than_payment(inputs, payment):
"""
Filters inputs that are larger than the payment since they can not be
relevant for the solution.
"""
return [input for input in inputs if input < payment]
def find_best_combo(inputs, payment):
"""
Finds the smallest combination of inputs that are combined still larger
than the payment.
"""
best_combo = (payment, payment)
for combo in permutations(inputs, 2):
(val1, val2) = combo
if val1 + val2 == payment:
best_combo = combo
break
elif val1 + val2 < payment:
continue
elif val1 + val2 < best_combo[0] + best_combo[1]:
best_combo = combo
return best_combo
run(TEST_INPUTS, PAYMENT)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.