Back to Basics: Brute Force in Powershell

Thursday, September 29, 2011 at 9:30AM
Shaun Hess in Back to Basics, Powershell, Powershell, Programming, Programming, Windows IT

Most of you have heard some variation of this problem:

A farmer has pigs and chickens. When the farmer walks out in the yard he sees 20 heads and 56 legs. How many pigs and chickens does the farmer have?

Based on the information given we can determine a few basic truths:

1.  20 heads. I think we can assume we have no decapitated pigs or chickens so the number of pigs + number of chickens is equal to 20.
2. 56 legs. 4*number of pigs + 2*number of chickens is equal to 56.

So how are we going to solve this in a programmatic way? Lets try a brute force algorithm. That's just another way to say we are going to enumerate and check over and over until we hit a solution. Remember this code is for learning and doesn't follow best practices.

function solve {            
 param(            
 [int]$numLegs,            
 [int]$numHeads            
 )            
             
 foreach ($numChicks in (0..$numHeads + 1)) {            
  $numPigs = $numHeads - $numChicks            
  $totLegs = 4*$numPigs + 2*$numChicks            
  if ($totLegs -eq $numLegs) {            
   return $numPigs, $numChicks            
  }            
 }            
 return            
}            
            
function barnYard {            
 $heads = Read-Host "Enter the number of heads"            
 $legs = Read-Host "Enter the number of legs"            
 $pigs, $chickens = solve -numLegs $legs -numHeads $heads            
 if ($pigs -eq $null) {            
  Write-Host "No pigs"            
 } else {            
  Write-Host "Number of pigs", $pigs            
  Write-Host "Number of chickens", $chickens            
 }            
}

Above is two functions, solve and barnYard. In programming this is called "decomposition". Basically we want to isolate components and break up the code so we can have separation and reuse. Functions also allow us to capture common patterns of computation and refer to it by name. But you already knew that. So lets throw these two functions in a file called farmyard.ps1 and source it.

PS H:\Development\Powershell> . .\farmyard.ps1

Now we can call the functions within the file and solve our farmyard mystery:

PS H:\Development\Powershell> barnYard            
Enter the number of heads: 20            
Enter the number of legs: 56            
Number of pigs 8            
Number of chickens 12

I'll leave you with a few words from Wikipedia on the subject:

Brute-force search is typically used when the problem size is limited, or when there are problem-specific heuristics that can be used to reduce the set of candidate solutions to a manageable size. The method is also used when the simplicity of implementation is more important than speed. This is the case, for example, in critical applications where any errors in the algorithm would have very serious consequences; or when using a computer to prove a mathematical theorem. Brute-force search is also useful as "baseline" method when benchmarking other algorithms or metaheuristics. Indeed, brute-force search can be viewed as the simplest metaheuristic.

Article originally appeared on shaunhess.com (http://www.shaunhess.com/).