PowerShell - gregorymorrison/euler1 GitHub Wiki

Windows PowerShell, introduced in 2006, is Microsoft's attempt at a useful shell. It borrows Unix's function chaining using pipes 😃 and Unix's sigils and comparison operators ☹️ . It's object-oriented, and comes with drivers that let you interact directly with things like the file system, the registry, databases, etc.

So, what does it look like? Here is Euler1 in an idiomatic PowerShell style. Here, the (..) range operator creates an array. This is piped to a filter that uses an anonymous function - each element of the collection is applied with the $ argument. This filtered collection is piped to sum, one of the half-dozen built-in aggregation functions, whose result is an object that includes an integer sum property. Finally, that integer property is returned by the select function:

# Euler1 in PowerShell

function euler1 ($size) {
    (1..$size) | where {$_%3 -eq 0 -or $_%5 -eq 0} | measure -sum | select -expand sum
}

euler1 999

Here is a simple imperative solution, demonstrating the use of a function and a for loop:

# Euler1 in Powershell

function euler1 ($size) {
    $ret = 0
    for ($i=1; $i -le $size; $i++) {
        if ($i%3 -eq 0 -or $i%5 -eq 0) {
            $ret += $i
        }
    }
    return $ret
}

euler1 (999)

Next is a functional version that uses tail recursion with an accumulator. One of the main points here is that the function euler is deterministic – it will always return the same output for a given input. This is accomplished in part by the absence of any variable manipulation – there are instead only functions which return values. The other main point is that this recursion uses tail call optimization – it’s written in such a way that an intelligent compiler can optimize its stack usage to be O(n) instead of O(n!). In English, this means that your program will probably not crash even for hugely recursive calls.

# Euler1 in Powershell

function euler ($n, $acc) {
    if ($n -eq 0) {
        $acc
    } elseif ($n % 3 -eq 0 -or $n % 5 -eq 0) {
        euler ($n-1) ($acc+$n)
    } else {
        euler ($n-1) $acc
    }
}

function euler1 ($size) {
    euler $size 0
}

euler1 999

PowerShell doesn't have the canonical Functional programming functions map/filter/reduce built in, but it is easy enough to roll our own. It does have list comprehensions, so we will repurpose them for our map and filter. There is an existing function named filter, so we'll name ours filt. PowerShell does have some built-in aggregation functions such as sum, but let's implement a real general-purpose aggregation whose function is passed in. A real Functional style requires immutability, which we can accomplish through the use of recursion. And as you can see at the bottom with the calls made to map/filt/reduce, lambdas are defined as a code block surrounded by curly braces:

# Euler1 in Powershell

function map  ($f, $l) {$l | ? {$_} | %  $f }

function filt ($f, $l) {$l | ?  $f  | % {$_}}

function reduce ($f, $acc, $l) {
    if ($l -eq $null) {
        $acc
    } elseif ($l.length -eq 1) {
        reduce $f (& $f $acc $l[0]) $null
    } else {
        reduce $f (& $f $acc $l[0]) $l[1..($l.length-1)]
    }
}

function euler1 ($size) {
    reduce {$args[0] + $args[1]} 0 (
        filt {$_%3 -eq 0 -or $_%5 -eq 0} (
            map {$_} $(1..$size)
        )
    )
}

euler1 999

Here’s another version using a Quicksort-based algorithm. Here we recursively break the list up in half and then reassemble it. Instead of sorting each half, though, we’ll filter the pivot value, converting it to 0 if it’s not divisible. Here, euler() returns euler() calculated on the half of the list before the pivot element, euler() calculated on the half of the list after the pivot element, and the pivot element or 0, all added together. Note here array slicing, which is welcome but verbose.

# Euler1 in PowerShell

function euler($l) {
    # if the list is empty, return 0
    if ($l -eq $null) {
        return 0

    } else {
        $pivot = [Math]::Floor($l.length/2)

        #calculate a value for the pivot element
        $i = 0
        if ($l[$pivot]%3 -eq 0 -or $l[$pivot]%5 -eq 0) {
            $i = $l[$pivot]
        }

        #recursively process the half of the list below the middle element
        $pre = 0
        if (0 -le $pivot-1) {
            $pre = euler $l[0..($pivot-1)]
        }

        #recursively process the half of the list above the middle element
        $post = 0
        if ($pivot+1 -le $l.length-1) {
            $post = euler $l[($pivot+1)..($l.length-1)]
        }

        #return thisVal + the results from the first and last halves
        return ($pre + $i + $post)
    }
}

function euler1($size) {
    euler (1..$size)
}

euler1 999

Here’s one more – an elegant algorithm based on an observation by little Carl Friedrich Gauss. It operates in O(1) constant time. Don’t sweat it if this seems inscrutable; click the blog link above for an explanation.

# Euler1 in PowerShell

function mysum ($n, $size) {
    ([Math]::Pow( [Math]::Floor($size/$n),2 ) + [Math]::Floor($size/$n)) * $n / 2
}

function euler1 ($size) {
    [Math]::Floor( (mysum 3 $size) + (mysum 5 $size) - (mysum 15 $size) )
}

euler1 999

PowerShell comes built into Windows since Win8. For security purposes, it requires you to approve its execution or it will throw an error. You can add the following arguments to your script to avoid this:

C:\> powershell.exe -ExecutionPolicy Bypass -NoLogo -NonInteractive -NoProfile -WindowStyle Hidden -File C:\temp\test.ps1
233168

C:\>