utxo_smallest_change.py

# You possess bitcoins in the form of UTXOs sorted by date and you need to send your friend X bitcoins.
# Find a date range whose outputs that will result in the least amount of change.
# Ideal solution will use Python whose function find_range(utxos, x) will give back the start and end dates.
# Each utxo has value and date (in unix time)


class UTXO(object):
    def __init__(self, value, date):
        self.value = value
        self.date = date    # unix time


def sort_utxos(utxos):
    # Sort utxos by date asc
    return sorted(utxos, key=lambda x: x.date)


def find_range(utxos, x):
    # Find date range of utxos which will result in smallest change
    sorted_utxos = sort_utxos(utxos)

    smallest_change = float('inf')
    best_start_date = -1
    best_end_date = -1

    for i in range(0, len(sorted_utxos)):
        start_utxo = sorted_utxos[i]

        total = 0

        for j in range(i, len(sorted_utxos)):
            end_utxo = sorted_utxos[j]
            total += end_utxo.value

            if(total >= x):
                change = total - x

                if(change < smallest_change):
                    smallest_change = change
                    best_start_date = start_utxo.date
                    best_end_date = end_utxo.date

                break

    return (best_start_date, best_end_date)


utxos = [UTXO(1, 0), UTXO(2, 1), UTXO(3, 2),
         UTXO(4, 3), UTXO(5, 5), UTXO(6, 4)]
print find_range(utxos, 8)