CODEWITHSUNDEEP
pythonpython-2.7
paddu
paddu

Reputation: 713

Recursion logic to calculate coin change/football score

I am trying to understand the question posted in stackflow.

I was trying to use the recursion logic given as one of the answers to calculate NFL score

score = 10
points = [7, 3, 2]
names = {7: "touchdown", 3: "field goals", 2 : "safeties"}

def count_combs(left, i, comb, add):
    if add: comb.append(add)
    if left == 0 or (i+1) == len(points):

        if (i+1) == len(points) and left > 0:
            comb.append( (left, points[i]) )
            i += 1
        while i < len(points):
            comb.append( (0, points[i]) )
            i += 1
        print " ".join("%d %s" % (n,names[c]) for (n,c) in comb)
        return 1
    cur = points[i]
    return sum(count_combs(left-x*cur, i+1, comb[:], (x,cur)) for x in range(0, int(left/cur)+1))

print count_combs(score, 0, [], None)

The value coming out is incorrect.

0 touchdown 0 field goals 10 safeties

It must be 5 safeties not 10.

Upvotes: 1

Views: 757

Answers (1)

Blckknght
Blckknght

Reputation: 104722

The code incorrectly assumes that the last value of points is always going to be 1. That was probably a good assumption when dealing with money since there's almost always going to be a coin of denomination 1, but it's not right for your football version of the code.

The error is in this in the block:

     if (i+1) == len(points) and left > 0:
        comb.append( (left, points[i]) )
        i += 1

A more correct implementation of that block needs to do two things differently. First, it needs to make sure that left is divisible by points[i], since otherwise you can't get the desired score with the kind of points left. It also needs to use left/points[i] in the append call, since it can't rely on the last value being 1.

Here's a fixed version of the code, with comments on the new stuff:

def count_combs(left, i, comb, add):
    if add: comb.append(add)
    if left == 0 or (i+1) == len(points):
        if (i+1) == len(points) and left > 0:
            if left % points[i]: # can't get the exact score with this kind of points
                return 0         # so give up on this recursive branch
            comb.append( (left/points[i], points[i]) ) # fix the amount here
            i += 1
        while i < len(points):
            comb.append( (0, points[i]) )
            i += 1
        print " ".join("%d %s" % (n,names[c]) for (n,c) in comb)
        return 1
    cur = points[i]
    return sum(count_combs(left-x*cur, i+1, comb[:], (x,cur)) for x in range(0, int(left/cur)+1))

Upvotes: 3

Related Questions