Teaching Kids Programming – Linear Equation with Two Unknowns (Chicken and Rabbit Problem)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Linear Equation with Two Unknowns can be used to solve Chicken and Rabit Problem (R for rabbits, and C for chicken)

For heads:
For legs:

Let’s plug into the second equation, and we get:

so
so

When is odd – we don’t have a solution to this problem because C will not be a whole integer and there is no such thing as half chicken!

This actually makes sense because is always even (H is non-negative integers), and L can’t be odd – legs will always be a even number.

Chick and Rabbit in Math/Python

We can translate this into Python code – we can return None instead of asserting or throw an Argument-Error-Exception.

1
2
3
4
5
6
7

def solveRabbitAndChicken(H, L):
   assert L & 1 == 0  # L needs to be odd
   C = (4*H-L)//2
   assert C >= 0 # can't be negative
   R = H - C
   assert R >= 0 # can't be negative
   return (C, R)

def solveRabbitAndChicken(H, L):
   assert L & 1 == 0  # L needs to be odd
   C = (4*H-L)//2
   assert C >= 0 # can't be negative
   R = H - C
   assert R >= 0 # can't be negative
   return (C, R)

The time and space complexity is O(1) constant as the algorithm just solves the linear equation with 2 unknowns based on the math.

Chick and Rabbit in Bruteforce Algorithm/Python

We can bruteforce all possibilities with the rabbit number (and automatically compute the number of chicken):

1
2
3
4
5

def solveRabbitAndChicken(H, L):
    for R in range(H+1):
        C = H - R
        if 2*C+4*R == L:
            return (C, R)

def solveRabbitAndChicken(H, L):
    for R in range(H+1):
        C = H - R
        if 2*C+4*R == L:
            return (C, R)

We can also bruteforce the Chicken and obtain the number of rabbits via math equation :

1
2
3
4
5

def solveRabbitAndChicken(H, L):
    for C in range(H+1):
        R = H - C
        if 2*C+4*R == L:
            return (C, R)

def solveRabbitAndChicken(H, L):
    for C in range(H+1):
        R = H - C
        if 2*C+4*R == L:
            return (C, R)

The time complexity is O(H) as we need to try in worst case H+1 possibilities. Another more naive brute-force algorithm in O(N^2) will be trying all pairs of (chicken, rabbit) and check if solution (C, R) meets two conditions aka Heads and Legs:

1
2
3
4
5

def solveRabbitAndChicken(H, L):
    for C in range(H+1):
        for R in range(H+1):
            if 2*C+4*R == L and R+C == H:
                return (C, R)

def solveRabbitAndChicken(H, L):
    for C in range(H+1):
        for R in range(H+1):
            if 2*C+4*R == L and R+C == H:
                return (C, R)

See also: Python Function to Solve the Chicken and Rabbit Math Problem

–EOF (The Ultimate Computing & Technology Blog) —