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 

Odwracanie hashtable w PS

Postanowiłem napisać odwracanie hashtable. Ta operacja jest nazywana pivotem. Dlaczego to zrobiłem? Przedstawię przykład. Jak stworzysz kolekcję hashtablicy to w PS źle (moim zdaniem) wyświetla się:

$hashtables = @()
$hashtables += @{FName="Arek";  Number=18}
$hashtables += @{FName="Gosia"; Number=1}
$hashtables += @{FName="Dawid"; Number=9}

Wynik tych kolekcji hashowania jest następujący:

Name                    Value                                                                                        
----                    ----                                                                                    
Number                  18                                                                                           
FName                   Arek                                                                                         
Number                  1                                                                                            
FName                   Gosia                                                                                        
Number                  9                                                                                            
FName                   Dawid  

Potrzebna będzie nam funkcja odwracanie hastable:

function Pivot-Hashtable
{
    param([hashtable[]]$hashes)

    $names = ($hashes.keys | group).name

    $hashes | % {
        $hash = $_
        $row = New-Object PSObject
        foreach($name in  $names)
        {
             $row | Add-Member  -MemberType NoteProperty -Name $name -Value $hash[$name]
        }
        return $row
    } 
}

Rezultat jest poniżej:

Pivot-Hashtable $hashtables


Number FName                                                         
------ ----                                                         
18     Arek                                                         
1      Gosia                                                        
9      Dawid  

Mapowanie w Spring.NET za pomocą PS

Spring.NET jest dla mnie bardzo ciężkim frameworkiem i do tego napisałem pomocną funkcję do wyświetlania wszystkich mappingów object:

function Get-SpringMapping
{
    param([string[]]$files)

    $files | %{
        $file = $_
        $springMapping = [xml](gc $file)
        $springMapping.objects.object | %{
            $obj  =$_
            if($obj.name -and $obj.type)
            {
                if($obj.name -ne 'object')
                {
                    [int]$constructors=0
                    if($obj."constructor-arg")
                    {
                        $constructors = $obj."constructor-arg".Count
                    }

                    @{      Name = $obj.name; 
                            Type = $obj.type;
                            ConstructorArgs =  $constructors;
                            File = $file;
                    }
                }
            }
        }
    }
}

Wywołanie wygląda następująco:

$springFiles = gci ".\SpringRep\" -Filter "*.spring" -Recurse 
$mapping = Get-SpringMapping ($springFiles.FullName)

W obiekcie $mapping jest wszystkie mapowania z plików springowych z folderu SpringRep

Lista cykliczna w PS

Postanowiłem zrobić listę cykliczną w PowerShellu.
Na samym początku zrobiłem węzeł reprezentujący wartość oraz wskazuje na następny i poprzedni węzeł:

function Create-Node
{
    param($value, $previous, $next)

    return new-object PSObject | 
               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
}

Jeszcze do tego jest potrzebna funkcja do wypełnienia tych węzłów:

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

    $CircularList =@()

    for($i=0; $i -lt $arr.Length; $i++)
    {
        $node = Create-Node -value $arr[$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
}

Wywołanie jest bardzo proste:

$list= Create-CircularList -arr "A","B","C"
$item = $list[0]
$item.Next.Next.Next

Zmienna $item reprezentuje pierwszy element, a jak wywołały 3 razy następny element to również uzyskamy pierwszy element z listy.
Jeżeli będziesz chciał stworzyć połączenia, bez cyklu to wystarczy wywołać funkcję z parametrem nonCircular:

$list= Create-CircularList -arr "A","B","C" -nonCircular
$item = $list[0]
$item.Next.Next.Next

Plik z liczbami w PS

Przesyłam Ci funkcję do tworzenia pliku z liczbami naturalnymi.

function New-RandomNumericFile([uint64]$maxNumer,[uint64]$amount, [string]$fileName)
{
    [uint64]$counter=0
    $stream = [System.IO.StreamWriter]$fileName
    if($stream)
    {
        $random = New-Object 'System.Random'
       
        while($counter -le $amount)
        {
            $counter++
            $randomNumber = $random.Next($maxNumer)
            $stream.WriteLine($randomNumber)
        }
        $stream.Close()
    }
    return  $counter
}

Przydatna będzie funkcja sprawdzająca czy liczby w pliku są posortowane:

function IsSorted-NumericFile
{
    [CmdletBinding()]
    param([string]$fileName)

    $stream = [System.IO.StreamReader]$fileName
    [uint64]$counter=0
    [int]$lastNumber=-1
    [bool]$isSorted=$true
    while(-not($stream.EndOfStream))
    { 
        $line = $stream.ReadLine()
        $counter++
        $number = [Convert]::ToInt32( $line)
        Write-verbose "$counter line has: $number "

        if($isSorted)
        {
               if($lastNumber -gt $number)
               {
                $isSorted =$false
                break
               }
         }
        $lastNumber = $number
    }
    $stream.Close()

    return $isSorted
}

A jak już masz posortowane pliki to można je porównać:

function CompareLine-NumericFile
{
    [CmdletBinding()]
    param([string]$fileLeft,  [string]$fileRight='' )

    [uint64]$counter=0
    $streamLeft = [System.IO.StreamReader]$fileLeft
    $streamRight = [System.IO.StreamReader]$fileRight
    $aresame = $true

    if($streamLeft -AND $streamRight)
    {
        while(-not($streamLeft.EndOfStream))
        { 
            if($streamRight.EndOfStream)
            {
                Write-Verbose "EOF has been reached for file $fileRight"
                $aresame =$false
            }

            $lineLeft = $streamLeft.ReadLine()
            $lineRight = $streamRight.ReadLine()

            if([string]::IsNullOrEmpty($lineLeft) -and [string]::IsNullOrEmpty($lineRight))
            {
                continue
            } 

            if($lineLeft -ne $lineRight)
            {
                $aresame = $false
                break
            }
                
            $counter++
        }
        if($streamLeft.EndOfStream -and -not($streamRight.EndOfStream))
        {
            Write-Verbose "EOF has been reached for file $fileLeft"
            $aresame =$false
        }


        $streamLeft.Close()
        $streamRight.Close()
    }
    else
    {
        Write-Verbose "One of file is empty"
        $aresame  = $false;
    }

    if($aresame)
    {
        Write-Verbose "Checked $counter lines in 2 files"
    }
    else
    {
        Write-Verbose "First inequality in line $counter"
    }

    return $aresame 
}

Wywołanie funkcji do porównywania wygląda następująco:

CompareLine-NumericFile -fileLeft "test_sorted1.txt" -fileRight "test_sorted2.txt" -Verbose

Ceiling i Floor w PS

Postanowiłem poćwiczyć implementację sufitu i podłogi w PS. Jak jesteś zainteresowany jak działa Ceiling i Floor to sprawdź klasę Math.
Implementacja sufitu jest następująca:

function Get-Ceiling($x)
{
    [int]$ceil = [int]$x
    if($ceil  -ne $x)
    {
        $diff = $ceil - $x
        if($diff -ge 0)
        {
            return $ceil
        }else{
            return $ceil+1
        }
    }
    return $ceil
}

A podłogi jest taka:

function Get-Floor($x)
{
    [int]$floor = [int]$x
    if($floor  -ne $x)
    {
        $diff = $floor - $x
        if($diff -ge 0)
        {
            return $floor-1
        }else{
            return $floor
        }
    }
    return $floor
}

Implementacja algorytmu podłogi i i sufitu jest zupełnie inna niż dla c podobnych języków programowania (C,C++,java, c#) jak i dla VB

Postanowiłem zaimplementować inne funkcje, za pomocą już zdefiniowanych funkcji:

function Get-Sign([int]$x)
{
    if($x -gt 0)
    {
        return 1
    }
    elseif($x -lt 0)
    {
        return -1
    }
    return $x
}

function Get-Abs([decimal]$x)
{
    return  $x * (Get-Sign($x))
}

function Get-Round($x)
{
    if([int]$x -ge 0)
    {
        return Get-Floor($x + 0.5D)   # D for Decimal
    }
    return Get-Ceiling($x - 0.5D)
}

function Get-Sawtooth($x)
{
    return $x - (Get-Floor($x))
}

Funkcja Sawtooth zwraca ułamek ( może powinna się nazywać funkcją zębatej piły)

function Get-Truncate($x)
{
    return (Get-Sign($x)) * (Get-Floor(Get-Abs($x)))
}

Dla funkcji Get-Truncate złe będzie zwracana liczba jeżeli funkcja zwracająca sygnału będzie bez nawiasów:

Get-Sign($x) * (Get-Floor(Get-Abs($x)))

Dodatkowo mamy implementację tych części funkcji dla licz używanych jako wartość pieniądza (z dokładności liczby do 2 miejsc po przecinku):

function Get-RoundMoney($x)
{
    return (Get-Round($x*100))/100    
}

function Get-SawtoothMoney($x)
{
    return [decimal]($x*100) - (Get-Floor($x*100))
}

function Get-TruncateMoney($x)
{
    return (Get-Sign($x)) * ((Get-Floor(Get-Abs([decimal]$x*100)))/100)
}

Dla funkcji Get-TruncateMoney też będziemy mieli problem z ze zmienną $x.
Bez [decimal] nie zadziała Get-TruncateMoney.
Przy wywołaniu Get-TruncateMoney -19.0190 uzyskamy błąd z tekstem:-19.0190-19.0190-19.0190-19.0190-19.0190-19.0190... itd.

Tak się zastanawiam czy nie lepiej było by zaimplementować te funkcje w .NET i skorzystać z wygenerowanej biblioteki.

Pobranie ról użytkownika w PS

Kiedy pracujesz zdalnie przez konsole PS i nie możesz uruchomić polecenia PS to być może nie masz uprawnień. Aby sprawdzić z jakimi uprawnieniami pracujesz na konsoli wystarczy uruchomić poleceni Get-Role. Implementacja tej funkcji jest poniżej:

function Get-Role
{
param(
$user =  
$([Security.Principal.WindowsIdentity]::GetCurrent()),

[Security.Principal.WindowsBuiltinRole[]]$role= 
$([Security.Principal.WindowsBuiltinRole].GetEnumValues())
)
 $userPrincipal = New-Object Security.Principal.WindowsPrincipal $user
 $role | %{
    return New-Object PSOBJECT  | 
Add-Member -MemberType NoteProperty 
-Name "Role" -Value $_  
-PassThru |
               
Add-Member -MemberType NoteProperty 
-Name "IsIn" -Value ($userPrincipal.IsInRole($_)) 
-PassThru
 }
}

Jak widać użytkownik nie ma praw administratora.
Gdy tą samą funkcję uruchomisz na konsoli z prawami admina to twój użytkownik też jest w roli administratora.