Understanding an example

Question

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

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

I'm learning Python and came across this example, can someone please explain in plain english (or pseudo-code) what this is doing line by line.

Many thanks

Answer 1

It is iterating through every possible combination of pigs and chickens (with the specified number of heads) until it finds one that has the correct number of legs, and then returns the numbers of pigs and chickens. If it gets through each combination without finding a valid answer, it returns [None, None] to indicate failure.

Answer 2

Essentially, solve is iterating through every possible combination of chickens and pigs, and when it finds a match, returning it.)

NumChickens + NumPigs must equal NumHeads, so it checks every NumChickens from 0 to NumHeads (that's what for range(0,NumHeads+1) does), and sets NumPigs to be NumHeads-NumChickens.

From there, its just a matter of multiplying out the number of feet, and seeing if they match.

Answer 3

solve is computing how many chicks (1 head, 2 legs) and how many pigs (1 head, 4 legs) it takes to total up to the given numbers of heads and legs.

It uses a "brute force", that is, maximally simple, approach:

• it tries even possible number of chicks from none at all to as many as was specified as number of heads (that's the role of the loop for numChicks in range(0, numHeads + 1):, since range gives integers from the starting value included to the ending value excluded);
• for each given numChicks it computes how many pigs there would be to give the requested number of heads, by the statement numPigs = numHeads - numChicks
• then it computes how many total legs those chicks and pigs would have, by totLegs = 4*numPigs + 2*numChicks
• then it checks if the totLegs equal the requested number: if so, it returns a list with two items, the numbers of chicks and pigs that solve the problem
• lastly, if it "falls of the bottom" of the for loop without having returned a value yet, it knows there's no solution, and signifies that by returning a list each of whose two items is None.

barnYard just delegates the solution to solve, and prints it out in a nice readable way, either as "no solution" or as nicely decorated numbers of chicks and pigs.

Now, to keep progressing, ask yourself if solve could be written more efficiently. Clearly there is no solution if the number of legs is less than twice the number of heads, or more than four times the number of heads, or odd -- maybe solve could test for those case and return [None, None] immediately. Could you code that...?

It may not be obvious, but every other combination of numbers of heads and legs has a solution -- and there IS a way to find it just by arithmetic, without looping. Think about it, maybe with the help of elementary middle-school algebra...

Answer 4

Basically, it's trying to figure out the answer to the problem, "How many chickens and pigs are there in a barnyard if there are X heads and Y legs in the barnyard?" The for numChicks in range(0, numHeads + 1):code creates a variables numChicks, and cycles through it from numChicks = 0 to numChicks = numHeads. (Note: the range function doesn't include the highest value).

For each number of numChicks, it checks to see if that numChicks and corresponding numPigs values comes up with the correct value of numLegs. numHeads will always be correct since numChicks + numPigs = numHeads, but numLegs varies based on the distribution -- hence the loop. If at any point the solution is found (when totLegs == numLegs), then that value is returned. If the entire loop gets done and no solution was found, then the list [None, None] is returned, meaning that there's no solution for this input.

Answer 5

Alex Martelli alludes to an algebraic solution which I'll include here for completeness. It can be worked out with the use of simultaneous equations. Being a simple mathematical solution, it's possibly faster, at least for large numbers of legs and heads :-)

Let:

• H be the number of heads;
• L be the number of legs;
• C be the number of chicks; and
• P be the number of pigs.

Given C and P, we can calculate the other two variables with:

H =  C +  P (1)
L = 2C + 4P (2)

I'll detail every step in the calculations below. The mathematically inclined can no doubt point out that steps could be combined but I'd prefer to be explicit. From (1), we can calculate:

   H = C + P
=> 0 = C + P - H       [subtract H from both sides]
=> 0 = H - C - P       [multiply both sides by -1]
=> P = H - C           [add P to both sides] (3)

and substitute that into (2):

    L = 2C + 4P
=>  L = 2C + 4(H - C)   [substitute H-C for P]
=>  L = 2C + 4H - 4C    [expand 4(H-C) to 4H-4C]
=>  L = 4H - 2C         [combine 2C-4C into -2C]
=>  0 = 4H - 2C - L     [subtract L from both sides]
=> 2C = 4H - L          [add 2C to both sides]
=>  C = 2H - L/2        [divide both sides by 2] (4)

Now you have two formulae, one that can calculate the number of chicks from head and legs (4), the other which can calculate number of pigs from chicks and heads (3).

So here's the Python code to do it, with appropriate checks to ensure you don't allow some of the more bizarre mathematical solutions, like 2 heads and 7 legs giving us a pig and a half along with half a chick, or 1 head and 12 legs giving 5 pigs and -4 chicks :-)

def solve (numLegs, numHeads):
    # Use the formulae (these make integers).
    chicks = numHeads * 2 - int (numLegs / 2)
    pigs = numHeads - chicks

    # Don't allow negative number of animals.
    if chicks < 0 or pigs < 0:
        return [None, None]

    # Don't allow fractional animals.
    if chicks * 2 + pigs * 4 != numLegs:
        return [None, None]
    if chicks + pigs != numHeads:
        return [None, None]

    return [pigs, chicks]

Of course, if you pass in fractional numbers of head or legs, all bets are off. Here's a complete test program so you can try out various values to ensure both methods return the same values:

import sys

def usage (reason):
    print "Error: %s"%(reason)
    print "Usage: solve <numHeads> <numLegs>"
    sys.exit (1);

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

def solve2 (numLegs, numHeads):
    chicks = numHeads * 2 - int (numLegs / 2)
    pigs = numHeads - chicks
    if chicks < 0 or pigs < 0:           return [None, None]
    if chicks * 2 + pigs * 4 != numLegs: return [None, None]
    if chicks + pigs != numHeads:        return [None, None]
    return [pigs, chicks]

if len (sys.argv) != 3:
    usage ("Wrong number of parameters (%d)"%(len (sys.argv)))

try:    heads = int (sys.argv[1])
except: usage ("Invalid <numHeads> of '%s'"%(sys.argv[1]))

try:    legs = int (sys.argv[2])
except: usage ("Invalid <numLegs> of '%s'"%(sys.argv[2]))

print "[pigs, chicks]:"
print "  ", solve1 (legs, heads)
print "  ", solve2 (legs, heads)