PowerShell - Project Euler Problem 102

I am always pleased when I can use PowerShell to solve a Project Euler problem. This one was straightforward. You are supplied with a text file containing 1000 random triangular coordinates and you need to determine how many of the triangles contain the origin (0,0). There are multiple ways to attack this, I went for he easier approach: if the area of the supplied triangle is equal to the 3 triangles created using the origin, then we know that the triangle contains the origin. I used Heron's Formula to calculate the area.

Following is the code used to find the answer.

<# Get side lengths 
$LengthAB = Length of AB = SquareRoot of (Ax - Bx)^2 + (Ay - By)^2
$LengthAC = Length of AC = SquareRoot of (Ax - Cx)^2 + (Ay - Cy)^2
$LengthBC = Length of BC = SquareRoot of (Bx - Cx)^2 + (By - Cy)^2

$s = .5($LengthAB +$LengthAC +$LengthAC)
$Area = SQRT($s($s-$LengthAB)($s-$LengthAC)($s-$LengthBC) #>      

function Get-LengthOfSide {     
param([Array]$X,[Array]$Y)     
  
return [Math]::sqrt( [Math]::pow(($X[0]-$Y[0]),2) + [Math]::pow(($X[1]-$Y[1]),2))     
}     

function Get-AreaOfTriangle {     
param([Array]$X,[Array]$Y, [Array]$Z)     
  
$LengthAB = Get-LengthOfSide -X $X -Y $Y     
$LengthAC = Get-LengthOfSide -X $X -Y $Z     
$LengthBC = Get-LengthOfSide -X $Y -Y $Z     
$s = .5*($LengthAB+$LengthAC+$LengthBC)     
$Area = [Math]::sqrt( $s*($s-$LengthAB)*($s-$LengthAC)*($s-$LengthBC) )     
return $Area     
}     

$path = 'C:\Users\stah06\Documents\triangles.txt'     
$uri = 'http://projecteuler.net/project/triangles.txt'     

# Using Invoke-WebRequest (PowerShell V3)     
#Invoke-WebRequest -Uri $uri -OutFile $path     

# Using System.Net.WebClient (PowerShell V2)     
$web = New-Object System.Net.WebClient     
$web.DownloadFile($uri, $path)     

$match = 0     
Get-Content $path |      
foreach {     
$A = $_.split(",")[0],$_.split(",")[1]     
$B = $_.split(",")[2],$_.split(",")[3]     
$C = $_.split(",")[4],$_.split(",")[5]     
$D = 0,0     

$TriangleABC = Get-AreaOfTriangle -X $A -Y $B -Z $C     
$TriangleABD = Get-AreaOfTriangle -X $A -Y $B -Z $D     
$TriangleACD = Get-AreaOfTriangle -X $A -Y $C -Z $D     
$TriangleBCD = Get-AreaOfTriangle -X $B -Y $C -Z $D     
  
$SumofTriangles = $TriangleABD +$TriangleACD + $TriangleBCD     
      
if ( [math]::abs($TriangleABC -$SumofTriangles) -lt .5) {      
 #"{0} {1}" -f $TriangleABC, $SumofTriangles     
 $match++     
}     
}     

$match      

Enjoy!

Project Euler 112

A brute force attack on Project Euler #112. I suspect there is a more efficient algorithm for this (not using string conversions), but this works.

function Test-Bouncy {          
  param([int]$num)          
  $up=$down=$false          
  $numArray = $num.ToString().ToCharArray()          
  $length = $numArray.Length          
  for($i=1; $i -lt $length; $i++) {          
      if ($numArray[$i-1] -lt $numArray[$i]) {          
          $up = $true          
      }          
      elseif ($numArray[$i-1] -gt $numArray[$i]) {          
          $down = $true          
      }          
      if ($up -and $down) {          
          return $true          
      }          
  }          
  return $false            
}          
        
$isBouncy = $ratio = 0          
$x = 1          
while ($ratio -lt .99) {          
  if(Test-Bouncy $x) {          
      $isBouncy++          
      $ratio = $isBouncy/$x                  
  }          
  $x++          
}          
        
"{0}`t{1}" -f ($x-1),$ratio

Enjoy!

Project Euler and PowerShell - Problem 42

Here is a PowerShell solution to Project Euler - Problem 42.

# Download the text file and create the array            
$web = New-Object System.Net.WebClient           
$url = "http://projecteuler.net/project/words.txt"           
$words = $web.DownloadString($url).replace("""","").split(",")           
          
# Generate a list of Triangular numbers           
[int[]]$triNums = @()           
for($r=1;$r -lt 500; $r++) {           
   $triNums += $r*($r+1)/2           
}           
          
# Create a hashtable for numeric lookup           
$lookup = @{}           
$i=1           
65..90 | Foreach {$lookup.add([Char]$_,$i++)}           
          
# Get the numeric value of a word           
function Get-WordValue($word) {           
$letters = $word.ToCharArray()           
$sum = 0           
foreach ($letter in $letters) {           
 $sum += $lookup[[char]$letter]           
}           
return $sum           
}           
          
# Count the Triangular words           
$Count = 0           
foreach ($word in $words) {           
if($triNums -contains (Get-WordValue $word)) {           
 #"{0}`t{1}" -f (Get-WordValue $word), $word           
       $Count++           
}            
}           
$count

Get-LatticePoints

I am so close to reaching the second level in Project Euler (need 50, I am at 48). Most of the problems that I have solved have been via Python, however, I am occasionally able to use PowerShell. A few of the problems ask to find lattice points within a circle.

What is a lattice point? - Think of a lattice point as an intersection on a grid. So if you had a circle with radius 1, there would be 5 lattice points: (-1,0), (0,1), (0,-1), (1,0) and (0,0).
Following is a PowerShell function that will get the number of lattice points for a given radius:

function Get-LatticePoints ([int]$radius)       
{       
    $count = 0       
    $x = -$radius       
    while ($x -le $radius)       
    {       
        $y = -$radius       
        While ($y -le $radius)        
        {       
            if($x*$x + $y*$y -le $radius*$radius)       
            {       
                $count++       
            }       
            $y++       
        }       
        $x++       
    }       
    return $count       
}       
       
for($i=1;$i -le 100;$i+=1) {       
   "Index: {0}`tLatticePoints: {1}" -f $i, (Get-LatticePoints $i)       
}

I forsee using this function in a couple of the Euler problems.

Enjoy!

Project Euler and PowerShell - Problem 19

Eleven down, 14 more to go before I reach level 1 (tetrahedron) on Project Euler. This one was easy if you know what PowerShell can do with dates!

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

$startDate = Get-Date "01/01/1901"
$endDate = Get-Date "12/31/2000"
$cnt = 0
for($date=$startDate; $date -lt $endDate; $date = $date.AddMonths(1))
{
    if ($date.DayOfWeek -eq 'Sunday')
    {
        $cnt++
    }    
}    
$cnt

Project Euler and PowerShell - Problem 14

The following iterative sequence is defined for the set of positive integers:

n -> n/2 (n is even)
n -> 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

$limit=1000000;$max=$longest=0
for($x=3;$x -lt $limit;$x+=2)
{
    $number = $x
    $count = 1
    while ($number -ne 1)
    {  
        if($number%2 -eq 0){$number /=2}
        else{$number= 3*$number +1}
        $count++
    }
  
    if($count -gt $max)
    {
        $max = $count
        $longest=$x
        "{0}`t{1}" -f $x,$max
    }  
}

I may be able to get this to run a little faster by storing the sequence count.

Project Euler and PowerShell - Problem 36

This one looked fun!

The decimal number, 585 = 1001001001 (binary), is palindromic in both bases.
Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.
(Please note that the palindromic number, in either base, may not include leading zeros.)

Here is my (non-optimized) solution.

# Sum all numbers less then 1,000,000 that are
# palindromic in base 10 and base 2
function Reverse-Parameter {
    param ([string]$number)
     for ($i = $number.length - 1; $i -ge 0; $i--)
    {
        $b = $b + ($number.substring($i,1))
    }
    [decimal]$b
}

$max = 1000000;$sum = 0
for ($i=0;$i -lt $max;$i++)
{   
    $k = Reverse-Parameter $i
    if($i -eq $k)
    {
        $bi = [Convert]::ToString($i,2)
        $rbi = Reverse-Parameter $bi
        if($bi -eq $rbi)
        {
            $sum = $sum + $i
            "{0}`t{1}`t`t{2}" -f $i,$bi,$sum
        }
    }   
}

Project Euler and PowerShell - Problem 10

Continuing on with Project Euler, I am momentarily skipping problems 8 (getting that big string into a numeric array still eludes me!) and 9 to quickly do problem 10.

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.

This is another brute force attack. I am sure there is a more efficient algorithm, but the following gets it done.

function isPrime
{
    param ($number)
    $isPrime = $true
    if($number -lt 2) { $isPrime = $False}
    if($number -gt 2 -and $number%2 -eq 0) {$isPrime = $False}
    for($i=3;$i -le [math]::Sqrt($number);$i+=2)
    {
        if($number % $i -eq 0) { $isPrime = $False}
    }   
    $isPrime
}   

$limit=2000000
$sum=2
for($i=3; $i -lt $limit;$i+=2)
{
    if( isPrime $i)
    {
        $sum+=$i
        "{0}`t{1}" -f $i, $sum
    }
}

While this generates the correct answer, it is painfully slow. I will be revisiting this one in an attempt to optimize it.

Project Euler and PowerShell - Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6^th prime is 13.

What is the 10001^st prime number?

function isPrime
{
  param ($number)
  $isPrime = $true
  if($number -lt 2) { $isPrime = $False}
  if($number -gt 2 -and $number%2 -eq 0) {$isPrime = $False}
  for($i=3;$i -le [math]::Sqrt($number);$i+=2)
  {
      if($number % $i -eq 0) { $isPrime = $False}
  } 
  $isPrime
} 

$i = $j = 0
do {
  if(isPrime $i){$j++;$i}
  $i++
} until ($j -eq 10001)

Project Euler and PowerShell - Problem 6

This was an easy one!
The sum of the squares of the first ten natural numbers is,

1² + 2² + ... + 10² = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + ... + 10)² = 55² = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

$sumSquares = $squareSums = $difference = 0
for ($i=1;$i -le 100;$i++)
{
   $sumSquares += [Math]::Pow($i,2)
   $squareSums += $i
}
$difference = [math]::Pow($squareSums,2) - $sumSquares
$difference

Project Euler and PowerShell - Problem 5

Moving on...

Problem 5: 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest number that is divisible with no remainder evenly divisible by all of the numbers from 1 to 20?

function modFunction ($mod)
{
   $number = 1
   $start = $mod
   do {
       if($number%$mod -eq 0)
       {
           $mod--
       }
       else
       {
           $number++;
           $mod=$start
       }       
   }
   until ($mod -eq 1)   
   $number
}

modFunction 20

While short, this is clearly a brute force approach. Anyone have a more efficient algorithm?

Project Euler and PowerShell - Problem 4

Problem 4: A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91X99. Find the largest palindrome made from the product of two 3-digit numbers.

function Reverse-Integer
{
 param([string]$str)
 for ($i = $str.ToString().Length - 1; $i -ge 0; $i--)
 {
     $c = $c + ($str.ToString().Substring($i,1))
 }
 [int]$c
}

$big = 0
for($x=100;$x -le 999;$x++)
{
 for($y=100;$y -le 999;$y++)
 {
     $xy = $x*$y
     $yx = Reverse-Integer $xy
     if ($yx -eq $xy)
     {
         if ($xy -gt $big) {$big=$xy}  
     }  
 }
}
$big

This one takes a long time to run. If anyone has any ideas on how to refactor this, please share!

Project Euler and PowerShell - Problem 3

Problem 3 -The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?

function isPrime
{
   param ($number)
   $isPrime = $true
   if($number -lt 2) { $isPrime = $False}
   if($number -gt 2 -and $number%2 -eq 0) {$isPrime = $False}
   for($i=3;$i -le [math]::Sqrt($number);$i+=2)
   {
       if($number % $i -eq 0) { $isPrime = $False}
   }   
   $isPrime
}   

$value=600851475143
$sqrValue =[Math]::Sqrt($value)

for($i=3;$i -le $sqrValue; $i+=2)
{
     if($value%$i -eq 0 -and (isPrime $i))
     {
           $maxPrime = $i
     }
}

$maxPrime

Project Euler and PowerShell - Problem 2

This is a continuation of my efforts to use PowerShell to solve some of the problems at Project Euler.

Problem 2: Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

function Get-SumFib ($n)
{
 $current = $previous = 1 
 while ($current -lt $n)
 {
     if($current%2 -eq 0)
     {
         $sum= $sum + $current
     }
  
     $current,$previous = ($current + $previous),$current}
 $sum 
}
Get-Fib 4000000

Project Euler and PowerShell - Problem 1

Was looking at Pete on Software the other day and saw a reference to Project Euler. What a cool site! Basically, the intent of this site is to use computational/programming skills to solve increasing complex mathematical problems. This seemed like an interesting way to test my PowerShell skills. The next few blog posts will be my attempts at solving a few of these.

- Spoiler Alert -

If you have any interest in solving any of these problems at Project Euler, quit reading this post and immediately pull up your programming editor of choice and have at it.

Problem 1: If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

$result = 0
for($i = 0; $i -lt 1000;$i++)
{
  if ($i % 3 -eq 0 -or $i % 5 -eq 0)
  {
      $result += $i;
  }  
}
$result