Rozwiązanie wieży Hanoi za pomocą listy cyklicznej

Już parę razy pisałem o problemie wieży Hanoi oraz rozwiązaniu jej.

Tym razem chciałbym przedstawić Ci rozwiązanie iteracyjne wieży Hanoi za pomocą listy cyklicznej w PowerShellu.
Algorytm jest bardzo prosty:
1. Połącz słupki w sposób cykliczny
2. Jeżeli liczba wszystkich krążków jest parzysta to ruch słupków jest zgodny z ruchem zegara. W przeciwnym przypadku jest to ruch przeciwny do ruchu zegara.
3. Znajdź najmniejszy krążek i przenieś go na następny słupek
4. Jeżeli wszystkie krążki jest są na słupku docelowym to zakończ program
5. Dla każdego krążka, który nie jest najmniejszym krążkiem spróbuj przenieś krążek na następne miejsce.
6. Przej do kroku nr 3


Do implementacji tego algorytmu będzie nam potrzebny typ stosu. Skorzystamy z akceleratora. =

$accelerators = [psobject].Assembly.gettype("System.Management.Automation.TypeAccelerators")
$stackType = [type]'System.Collections.Generic.Stack`1'
$accelerators::Add('stack', $stackType)

Stworzymy węzeł, który w problemie wieży Hanoi będzie jako słup:

function Create-Node
{
    param($value, $previous, $next, $key=$([guid]::NewGuid()))

    return new-object PSObject | 
               Add-Member -MemberType NoteProperty -Name "Key" -Value  $key -PassThru |                
               Add-Member -MemberType NoteProperty -Name "Value" -Value $value  -PassThru |
               Add-Member -MemberType NoteProperty  -Name "Next" -Value $next  -PassThru |
               Add-Member -MemberType NoteProperty  -Name "Previous" -Value $previous -PassThru
}

I teraz będziemy mogli stworzyć listę cykliczną z tablicy:

function Create-CircularList
{
    param([array]$arr, [switch]$nonCircular, [array]$keys)

    $CircularList =@()
    for($i=0; $i -lt $arr.Length; $i++)
    {
        $node = Create-Node -value $arr[$i] -key $keys[$i] 
        if($i -gt 0)
        {
            $prevNode =   $CircularList[$i-1]
            $node.Previous = $prevNode
            $prevNode.Next = $node
        }
        $CircularList += $node
    }

    if(!$nonCircular)
    {
        $firstNode = $CircularList[0]
        $lastNode = $CircularList[$arr.Lengt-1]

        $firstNode.Previous = $lastNode 
        $lastNode.Next = $firstNode
    }
    return $CircularList
}

Jeszcze będziemy potrzebować funkcji która by zwracała index listy, która posiada najmniejszy krążek:

function Find-ItemInValue
{
    param([array]$arr, [int]$item)

    for($i=0; $i -lt $arr.Length; $i++)
    {
        $value = $arr[$i].Value
        if($value -is [int] -and [int]$value -eq [int]$item)
        {
            return $i
        }
        elseif($value)
        {
            $index = [array]::IndexOf($value,$item)
            if($index -ge 0)
            {
                return $i
            }
        }
    }
    return -1
}

I teraz wystarczy zaimplementować algorytm rozwiązujący wieżę Hanoi:

function Solve-Hanoi
{
[CmdletBinding()]
param(
[Alias("circularList")]$list,
[switch]$optDir
)

$startPeg = $list[0]
$maxItems =  $list.Value.Count
$listMeasure = $list.Value | measure -Minimum -Maximum
$minSpotValue = $listMeasure.Minimum
$maxSpotValue = $listMeasure.Maximum
$endPeg = $list[$list.Length-1]
 
$moveDir = "Next"
if($optDir)
{
    [bool]$even = $maxItems % 2 -eq 0
    if(!$even)
    {
        $moveDir = "Previous"
    }
}

$step=0
 while($endPeg.Value.Count -lt $maxItems)
 {
    for($searchSpot = $minSpotValue; $searchSpot -le $maxSpotValue; $searchSpot++)
    {
        $indexOfMin = Find-ItemInValue -arr $list -item $searchSpot
        if($indexOfMin  -eq -1)
        {
            continue
        }
        $currentPeg = $list[$indexOfMin]
 
        $nextPeg = $currentPeg.$moveDir
        $currentSpot = $currentPeg.Value.Peek()
        if($currentSpot -eq $searchSpot)
        {
            while($nextPeg -ne $currentPeg)
            {
                if($nextPeg.Value.Count -eq 0 -OR $nextPeg.Value.Peek() -gt $currentSpot)
                {
                    $nextPeg.Value.Push($currentPeg.Value.Pop())
                        
                    $step++
                    Write-Verbose "Step: $step"
                    Write-Verbose " $($list | select Key,Value |out-string)"
                    break
                }
                $nextPeg = $nextPeg.$moveDir
            }
        }
    }
}
return $list
}

Wywołanie tego algorytmu jest następujące:

[stack[int]]$pegA = 5,4,3,2,1 #last in, first out
[stack[int]]$pegB = @()
[stack[int]]$pegC = @()

$CircularList= Create-CircularList -arr $pegA,$pegB,$pegC -keys 'A','B','C'
Solve-Hanoi -circularList $CircularList -Verbose -optDir

Możemy wywołać wieżę Hanoi z dowolnego układu:

$arr = 1..4
[array]::Reverse($arr)
[stack[int]]$pegA =$arr
[stack[int]]$pegB = @(6)
[stack[int]]$pegC = @(5)

$CircularList= Create-CircularList -arr $pegA,$pegB,$pegC -keys 'A','B','C'
Solve-Hanoi -circularList $CircularList -Verbose -optDir

No, prawię z dowolnego. Dla takiego układu początkowego musiałem wyłączyć parametr optymalizujący kierunek przesunięcia krążków.

$arr = 1..2
[array]::Reverse($arr)
[stack[int]]$pegA =$arr
[stack[int]]$pegB = 7,6
[stack[int]]$pegC = @(5)

$CircularList= Create-CircularList -arr $pegA,$pegB,$pegC -keys 'A','B','C'
Solve-Hanoi -circularList $CircularList -Verbose