| 1 | |
|---|
| 2 | def tokenizer(denominations,amount): |
|---|
| 3 | denominations.sort() |
|---|
| 4 | tokens = [] |
|---|
| 5 | i = 0 |
|---|
| 6 | max_i = len(denominations) |
|---|
| 7 | while sum(tokens)<amount: |
|---|
| 8 | if i>=max_i: |
|---|
| 9 | i = max_i -1 |
|---|
| 10 | d = denominations[i] |
|---|
| 11 | rest = amount - sum(tokens) |
|---|
| 12 | if d == 1: |
|---|
| 13 | tokens.append(1) |
|---|
| 14 | i +=1 |
|---|
| 15 | elif d <= rest-d + denominations[i-1]+1: |
|---|
| 16 | tokens.append(d) |
|---|
| 17 | i +=1 |
|---|
| 18 | elif d > rest -d + denominations[i-1]+1: |
|---|
| 19 | i -= 1 |
|---|
| 20 | return tokens |
|---|
| 21 | |
|---|
| 22 | def prepare_for_exchange(denominations,oldcoins,newcoins): |
|---|
| 23 | """returns ([value to keep,..],[value for paying,...],[value for blank,...]), |
|---|
| 24 | assumes that all newcoins are exchanged anyhow""" |
|---|
| 25 | |
|---|
| 26 | oldcoins = list(oldcoins) |
|---|
| 27 | oldcoins.sort() |
|---|
| 28 | oldcoins.reverse() |
|---|
| 29 | |
|---|
| 30 | newcoins = list(newcoins) |
|---|
| 31 | newcoins.sort() |
|---|
| 32 | newcoins.reverse() |
|---|
| 33 | |
|---|
| 34 | amountold = sum([int(o) for o in oldcoins]) |
|---|
| 35 | amountnew = sum([int(n) for n in newcoins]) |
|---|
| 36 | amount = amountold + amountnew |
|---|
| 37 | |
|---|
| 38 | targettokens = tokenizer(denominations,amount) |
|---|
| 39 | targettokens.sort() |
|---|
| 40 | targettokens.reverse() |
|---|
| 41 | keepold = [] |
|---|
| 42 | makenew = [] |
|---|
| 43 | for tt in targettokens: |
|---|
| 44 | try: |
|---|
| 45 | keepold.append(oldcoins.pop(oldcoins.index(tt))) |
|---|
| 46 | except ValueError: |
|---|
| 47 | makenew.append(tt) |
|---|
| 48 | |
|---|
| 49 | return (keepold,oldcoins,makenew) |
|---|
| 50 | |
|---|
| 51 | |
|---|
| 52 | def testspend(tokens,amount): |
|---|
| 53 | picked = [] |
|---|
| 54 | tokens.sort() |
|---|
| 55 | tokens.reverse() |
|---|
| 56 | for token in tokens: |
|---|
| 57 | rest = amount - sum(picked) |
|---|
| 58 | if rest > 0 and token <= rest: |
|---|
| 59 | picked.append(token) |
|---|
| 60 | return picked |
|---|
| 61 | |
|---|
| 62 | |
|---|
| 63 | def test_tokenizer(): |
|---|
| 64 | problems = 0 |
|---|
| 65 | for denominations in dl: |
|---|
| 66 | print 'DENOMINATIONS %s' % denominations |
|---|
| 67 | print |
|---|
| 68 | for i in range(1,max(denominations)*3): |
|---|
| 69 | print 'Tokenize %i, ' % i, |
|---|
| 70 | tokens = tokenizer(denominations,i) |
|---|
| 71 | print 'tokens %s (%s)' % (tokens,sum(tokens)) |
|---|
| 72 | if sum(tokens) != i: |
|---|
| 73 | print 'fuckup' |
|---|
| 74 | break; |
|---|
| 75 | for j in range(1,i+1): |
|---|
| 76 | picked = testspend(tokens,j) |
|---|
| 77 | if sum(picked) != j: |
|---|
| 78 | problems += 1 |
|---|
| 79 | print 'testing: %s, picked %s, sum %s, worked: %s' % (j,picked,sum(picked),sum(picked)==j) |
|---|
| 80 | print |
|---|
| 81 | print |
|---|
| 82 | print 'Problems: %s' % problems |
|---|
| 83 | |
|---|
| 84 | amount = 137 |
|---|
| 85 | print tokenizer(dl[0],amount) |
|---|
| 86 | |
|---|
| 87 | def test_prepare_for_exchange(): |
|---|
| 88 | denominations = dl[0] |
|---|
| 89 | startvalue = max(denominations) |
|---|
| 90 | for i in range(1,startvalue * 2 +1): |
|---|
| 91 | print '#'*20,' i: %s ' % i, '#' * 20 |
|---|
| 92 | start = tokenizer(denominations,i) |
|---|
| 93 | for j in range(1,i*3 +1): |
|---|
| 94 | print 'j: %s - ' % j, |
|---|
| 95 | newcoins = tokenizer(denominations,j) |
|---|
| 96 | keepold,paywith,makenew = prepare_for_exchange(denominations,start,newcoins) |
|---|
| 97 | sumkeep = sum(keepold) |
|---|
| 98 | sumnew = sum(makenew) |
|---|
| 99 | total = sumkeep + sumnew |
|---|
| 100 | print "keep: %s, tomake: %s, paywith: %s, %s, sum: %s" % (keepold,makenew,paywith,newcoins,total) |
|---|
| 101 | |
|---|
| 102 | if __name__ == '__main__': |
|---|
| 103 | |
|---|
| 104 | dl = [[1,2,5,10,20,50,100],[1,3,9,27],[1,3,5,7,11,13,17,19,23],[1,17,33]] |
|---|
| 105 | #test_tokenizer() |
|---|
| 106 | #test_prepare_for_exchange() |
|---|
| 107 | print "keep: %s, paywith: %s, makenew: %s" %prepare_for_exchange(dl[0],[10],[5,2]) |
|---|
| 108 | |
|---|
| 109 | |
|---|
| 110 | |
|---|
