Monday, January 23, 2012

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!

No comments: