Unexpected result in a simple example

Question

   def solve(numLegs, numHeads):
        for numSpiders in range(0, numHeads + 1):
         for numChicks in range(0, numHeads - numSpiders + 1):
          numPigs = numHeads - numChicks - numSpiders
          totLegs = 4*numPigs + 2*numChicks + 6*numSpiders 
          if totLegs == numLegs:
           return [numPigs, numChicks, numSpiders]
        return [None, None, None]

    def barnYard(heads, legs):
        pigs, chickens, spiders = solve(legs, heads)
        if pigs == None:
         print "There is no solution."
        else:
         print 'Number of pigs: ', pigs
         print 'Number of Chickens: ', chickens
         print 'Number of Spider: ', spiders

    barnYard(20,56) # 8 pigs - 12 chickens
    barnYard(21,62) # 10 pig - 11 chickens

20 heads and 56 legs returns 8 pigs and 12 chickens, so I made it 21 and 62 to add a spider, but it still returns pigs and chickens, whats wrong in the code?

Thanks!

Answer 1

There is absolutely nothing wrong with your code. That's a completely valid result. With 10 pigs and 11 chickens, you get 10+11=21 heads, and 10*4 + 11*2 = 62 legs.

So it returns a correct result.

Now if you change that to 10 heads and 62 legs, and also change the code to have 8 legs for a spider as they tend to do, then you get the result 3 pigs, 1 chicken and 6 spiders.

Your code simply tries spiders last, so you wont get any spiders unless it has to be spiders.

Answer 2

A linear system with 2 equations and 3 variables is under-determined -- there may be multiple solutions for any given set of parameters; and this is indeed the case for the code you're showing. Nothing wrong with the code, if what you want is to get the solution (if any) with as few spiders as possible.

If you want to get the solution (if any) with as many spiders as possible, try "many spiders" first, for example change the outer loop, which is now

    for numSpiders in range(0, numHeads + 1):

i.e., first tries to get a solution with no spiders at all, then if that fails tries with one, and so forth, to be instead:

    for numSpiders in reversed(range(0, numHeads + 1)):

which goes the other way round (that's what the reversed is for) and will try numHeads spiders first, then numHeads-1, and so forth.

(Your equations are actually Diophantine ones, i.e., strictly integer-based, which has important implications when compared to ordinary linear equations which admit fractional solutions, but your issue here is not tied to Diophantine-equation problems, just to the bit about underdetermined linear systems).

Answer 3

Your code is correct - in the first iteration of the outermost for loop, numChicks is 0. Since solve returns as soon as it finds a valid match, another possible valid match won't be attempted.

You could change the return statement into a yield statement and iterate over solve's results to get all possible combinations.

For instance:

def solve(numLegs, numHeads):
     for numBees in range(0, numHeads + 1):
             for numChicks in range(0, numHeads - numBees + 1):
                     numPigs = numHeads - numChicks - numBees
                     totLegs = 4*numPigs + 2*numChicks + 6*numBees 
                     if totLegs == numLegs:
                             yield [numPigs, numChicks, numBees]

def barnYard(heads, legs):
    for pigs, chickens, bees in solve(legs, heads):
             print 'Number of pigs: ', pigs
             print 'Number of chickens: ', chickens
             print 'Number of bees: ', bees

barnYard(20,56)

will output:

Number of pigs:  8
Number of chickens:  12
Number of bees:  0

Number of pigs:  6
Number of chickens:  13
Number of bees:  1

Number of pigs:  4
Number of chickens:  14
Number of bees:  2

Number of pigs:  2
Number of chickens:  15
Number of bees:  3

Number of pigs:  0
Number of chickens:  16
Number of bees:  4