1

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.

1 Answer 1

3

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))
1
  • yes, this thing with 1 is commonly overlooked. I also deal with it in this answer, though in scheme. (FYI.)
    – Will Ness
    Oct 17, 2019 at 23:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.