SO challenge 16 code

challenge16.py

import json
from uuid import uuid4

class Node:
    def __init__(self, coins, target, prev, coin):
        self.previous_node = prev
        self.target = target
        self.count = target+1
        self.id = uuid4()
        self.coin = coin
        if target > 0:
            done = []
            for index, coin in enumerate(coins):
                if coin not in done:
                    new_coins = coins[:index] + coins[index+1:]
                    next_node = Node(new_coins, target-coin, self, coin)
                    done.append(coin)
                
        elif target == 0:
            prev.set_count(1)

    def set_count(self, last_count):
        if self.count > last_count:
            self.count = last_count
        if self.previous_node is not None:
            self.previous_node.set_count(self.count+1)
        
def main():
    filename = 'challenge16.txt'
    with open(filename, 'r') as challenge_file:
        arr = json.load(challenge_file)
        for row in arr:
            [d, c, t, e] = row
            denominate(d, c, t, e)

def denominate(denominations, counts, target, expected_num_coins):
    result = -1
    num_coins = target + 1
    if len(denominations) == 1 and target % denominations[0] == 0:
        num_coins = target // denominations[0]
        if num_coins <= counts[0]:
            result = 0

    if result == -1:
        
        all_coins = [v for vs in [[x]*y for (x,y) in zip(denominations, counts)] for v in vs]

        coin_tree = Node(all_coins, target, None, None)

        num_coins = coin_tree.count    
    
    if num_coins > target:
        result = -1

    #if expected_num_coins != num_coins and expected_num_coins != result:
    #print('input: ', denominations, counts, target, '| results:', result, num_coins, '| pass:', expected_num_coins == num_coins or expected_num_coins == result)
    if result == -1:
        num_coins = -1
    return num_coins

if __name__ == '__main__':
    main()

challenge16.txt

[
  [[1],[100],73, 73],
  [[1,5],[3,2],14, -1],
  [[1,5,10],[10,2,1],23, 6],
  [[2,4],[10,10],7, -1],
  [[3,7],[10,10],24, 4],
  [[1,3,4],[5,5,1],6, 2],
  [[1,5,10],[2,1,1],18, -1],
  [[1,7,10],[10,1,1],14, 5],
  [[4,5,9],[5,5,5],18, 2],
  [[6,9,20],[5,5,5],43, -1],
  [[5,10],[0,10],50, 5],
  [[1,2,5],[0,0,10],10, 2],
  [[7],[3],21, 3],
  [[7],[2],21, -1],
  [[1,3,5],[1,1,1],8, 2],
  [[1,2,5,10],[1,1,1,1],18, 4],
  [[2,3,7],[10,10,1],14, 4],
  [[1,4,6,9],[2,2,2,2],18, 2],
  [[5,11,17],[10,10,10],34, 2],
  [[1,8,15],[100,1,1],23, 2],
  [[1,2],[10,5],7, 3],
  [[1,3],[5,2],8, 4],
  [[2,5],[5,2],12, 3],
  [[1,4,6],[5,1,1],10, 2],
  [[1,3,9],[3,1,1],13, 4],
  [[2,7,10],[5,1,1],17, 2],
  [[1,2,5,10],[3,2,1,1],18, 4],
  [[1,3,5],[2,2,1],11, 3],
  [[1,2,5],[10,1,1],8, 3],
  [[1,2,5,10],[10,2,1,1],19, 4],
  [[3,4,7],[5,2,1],15, 3],
  [[2,5,10],[3,2,1],20, 3],
  [[1,2,3],[5,5,5],9, 3],
  [[1,3,4,5],[2,2,1,1],12, 3],
  [[2,3,5,8],[3,2,2,1],18, 4],
  [[1,5,6],[5,2,1],14, 5],
  [[1,2,4],[3,3,1],9, 4],
  [[1,3,7],[2,2,1],10, 2],
  [[2,4,6],[2,2,1],12, 3],
  [[1,2,5],[1,1,1],7, 2],
  [[3,5,8],[2,1,1],13, 2],
  [[1,2,6],[3,1,1],8, 2],
  [[2,3,5],[5,2,2],14, 4],
  [[1,4,7],[3,1,1],12, 3],
  [[1,3,6,9],[2,2,1,1],15, 2],
  [[2,5,7],[1,1,1],10, -1],
  [[1,2,5,10],[2,2,1,1],19, 4],
  [[1,3,5,8],[3,2,2,1],17, 4],
  [[2,4,6,9],[2,2,1,1],18, 4],
  [[1,2,3,7],[3,2,1,1],13, 4],
  [[1,3,5],[5,3,2],16, 4],
  [[2,5,10],[2,1,1],17, 3],
  [[1,4,6],[3,1,1],11, 3],
  [[1,2,5],[10,1,1],14, 9],
  [[3,7,11],[2,1,1],18, 2],
  [[1,2,3,4],[2,2,2,1],9, 3],
  [[1,5,10,20],[5,2,1,1],23, 4],
  [[2,3,5,7],[2,2,1,1],15, 3],
  [[1,4,5,6],[3,1,1,1],13, 5],
  [[1,2,3,6],[2,2,1,1],10, 3],
  [[1,3,5,9],[3,2,1,1],16, 4],
  [[2,4,7,10],[2,1,1,1],18, 4],
  [[1,2,5,8],[5,2,1,1],19, 6],
  [[1,3,6,7],[2,2,1,1],14, 3],
  [[1,2,4,5],[3,2,1,1],12, 4],
  [[3,5,7,9],[2,1,1,1],15, 3],
  [[1,2,3,5],[4,2,1,1],11, 4],
  [[1,4,6,8],[2,2,1,1],16, 4],
  [[2,3,5,9],[3,2,1,1],14, 2],
  [[1,2,5,6],[3,2,1,1],13, 3],
  [[1,3,4,7],[2,2,1,1],12, 3],
  [[2,4,6,8],[2,2,1,1],14, 2],
  [[1,2,3,7],[3,2,1,1],13, 4],
  [[1,3,5,7],[2,2,1,1],12, 2],
  [[2,4,5,9],[3,2,1,1],15, 3],
  [[1,2,4,6],[2,2,1,1],11, 3],
  [[1,3,5,8],[3,2,1,1],14, 3],
  [[2,3,6,7],[2,2,1,1],13, 2],
  [[1,2,5,10],[4,2,1,1],17, 3],
  [[1,3,6,9],[3,2,1,1],15, 2],
  [[2,5,7,10],[2,1,1,1],16, 4],
  [[1,2,3,4],[5,2,1,1],12, 5],
  [[1,3,5,6],[3,2,1,1],14, 3],
  [[2,4,6,9],[2,2,1,1],15, 2],
  [[1,2,3,7],[3,2,1,1],12, 3],
  [[1,4,5,8],[2,2,1,1],14, 3],
  [[2,3,5,7],[2,2,1,1],13, 3],
  [[1,2,4,6],[3,2,1,1],15, 5],
  [[1,3,5,9],[2,2,1,1],14, 2],
  [[2,5,7,10],[2,1,1,1],17, 2],
  [[1,2,3,6],[3,2,1,1],13, 4],
  [[1,3,4,7],[2,2,1,1],12, 3],
  [[2,4,6,8],[2,2,1,1],14, 2],
  [[1,2,5,8],[3,2,1,1],15, 3],
  [[1,3,6,9],[3,2,1,1],16, 3],
  [[2,3,5,9],[2,2,1,1],15, 3],
  [[1,2,3,4],[4,2,1,1],11, 4],
  [[1,3,5,7],[2,2,1,1],13, 3],
  [[2,4,6,9],[2,2,1,1],14, 3],
  [[1,2,5,6],[3,2,1,1],12, 3]
]