Windows PowerShellでProject Euler（9） SortedList

この問題はPriorityQueueを使えばごく自然に書くことができます。PowerShellでは.NETのコンテナを使うことができます。

しかし、なぜかPriorityQueueが無いんですね。
しょうがないので代替を探しましょう。SortedListが使えそうです。SortedListは辞書なんだけどインデックスでキーの昇順に参照できるものです。

$c = New-Object System.Collections.SortedList
$c.Add(2, "b")
$c.Add(1, "a")
$c.GetKey(0)        # 1
$c.GetByIndex(0)    # a
$c.RemoveAt(0)

ここでは値が大きい方から取り出したいので、キーには積を-1倍したもの、値に被乗数と乗数の配列を指定すればよいでしょう。気を付けなければいけないのは、すでにあるキーを加えることができないということです。キーが存在するか調べるメソッドが用意されています。

$c.contains(1)

これでとりあえず答えを出すことができます。

function fold($f, $init) {
    begin   { $x = $init }
    process { $x = & $f $x $_ }
    end     { $x }
}

function digits($n) {
    while($n -gt 0) {
        $d = $n % 10
        $d
        $n = ($n - $d) / 10
    }
}

function is_palindromic($n) {
    $m = digits $n | fold { $args[0] * 10 + $args[1] } 0
    $m -eq $n
}

function products($n) {
    function put($a, $b) {
        if(-not $c.contains($a)) {
            $c.Add($a, $b)
        }
    }
    
    $c = New-Object System.Collections.SortedList
    $m = $n - 1
    $c.Add((-$m * $m), @($m, $m))
    while($true) {
        -$c.GetKey(0)
        $a, $b = $c.GetByIndex(0)
        $c.RemoveAt(0)
        if($a -eq $b) {
            put (-($a - 1) * ($a - 1)) @(($a - 1), ($a - 1))
        }
        put (-$a * ($b - 1)) @($a, ($b - 1))
    }
}

$n = 1000
products $n | where { is_palindromic $_ }

しかし、これでは回文数がいくつも出てきてしまいます。