piątek, 28 lutego 2014

Rozwiązanie problemu Józefa Flawiusza w PowerShell

Józef Flawiusz walczył w powstaniu żydowskim przeciwko rzymianom. Pewnego razu, żołnierze żydowscy zostali otoczeni przez wojsko rzymskie i 40 powstańców wolało popełnić samobójstwo niż oddać się w niewolę. Żeby nie było łatwo w przewidzeniu kto będzie ostatni w tym czynie, postanowiono, że powstańcy staną w okręgu i co 3 osoba będzie dokonywać samobójstwa. Pomysł samobójstwa nie podobał się Józefowi i chciał stanąć w takim miejscu, aby jako ostatni mógł oddać się do niewoli i przeżyć. Wyznaczenie tego ostatniego miejsca nazywa się problemem Józefa Flawiusza.

Symulację graficzną algorytmu można zobaczyć na tej stronie.

Dla uproszczenia numeracja miejsc jest od 0. Poniżej jest rozwiązanie iteracyjne:
function Solve-JosephusProblem
{
    param(
        [ValidateRange(1,1000)]
        [int]$killEvery = 3,
        [ValidateRange(1,1000)]        
        [int]$soldiers = 40
      )
      $i=1
      $rest=0
      while($i -le $soldiers)
      {
        $rest = ($rest + $killEvery ) % $i 
        $i++
      }
      return $rest
}
Sprawdzenie miejsca dla 10 żołnierzy:
Solve-JosephusProblem -soldiers 10 -killEvery 3
#3


Gdyby samobójca był wybierany co 1 osobę to ostatnia osoba dokona samobójstwa.

Solve-JosephusProblem -soldiers 41 -killEvery 1



Poniżej jest rozwiązanie rekurencyjne:
function Solve-JosephusProblemRec
{
    param(
        [ValidateRange(1,1000)]
        [int]$killEvery = 3,
        [ValidateRange(1,1000)]
        [int]$soldiers = 40
      )

    if($soldiers -eq 1)
    { 
        return 0 
    }
    else
    {
        [int]$recSolve = Solve-JosephusProblemRec -killEvery $killEvery -soldiers ($soldiers-1)
        return (($recSolve +$killEvery  ) % $soldiers )  
    }
}

Nie ukrywam, że dużo pomogła mi strona na wiki opisująca ogólny problem.

Sprawdzamy na którym miejscu powinien Józef Flawiusz się ustawić:
$soldiers =41
$killEvery =3
Solve-JosephusProblem -soldiers $soldiers -killEvery $killEvery  #30
Solve-JosephusProblemRec -soldiers $soldiers -killEvery $killEvery #30

Generowanie start.bat dla projektu w VS

Czy kiedykolwiek musiałeś uruchomić aplikację z linii poleceń, która miała tak dużo linijek z argumentami, że nie mieściła się w oknie cmd? Ja miałe taką przyjemność i ten post jest właśnie o tym jak rozwiązać taki problem. Problem można rozwiązać za pomocą programu wsadowego (na ogół nazywam go start.bat). W nim zawarte jest polecenie startujące aplikację z argumentami. Aby debugować taką aplikację z poziomy VS to należy dodać parametry do właściwości programu. Poniżej są przedstawione 2 argumenty:
Napisałem skrypt w PS, aby wygenerować start.bat, który będzie mógł być wystartowany z tymi argumentami:
function New-StartBat
{
    param(
        [string] $csprojFilePath,
        [string] $outputDir = "." 
    )

    $userFileExtension = ".user"
    $startBatFileName = "start.bat"

    if(!(test-path $csprojFilePath))
    {
        throw "Wrong path to csproj file: $csprojFilePath"
    }

    [xml]$csprojContent = gc $csprojFilePath 
    [string]$outputType = ([string]$csprojContent.Project.PropertyGroup.OutputType)
               .Trim();

    if( -not($outputType -match  "Exe"))
    {
        throw "Output type is not exe"
    } 

    $assemblyName = ([string]$csprojContent.Project.PropertyGroup.AssemblyName)
                  .Trim()
    $startbarContent = "start /B $assemblyName.$outputType"
    $userFile = $csprojFilePath + $userFileExtension

    if(!(test-path $userFile))
    {
        Write-host "No user file for $csprojFilePath"
        $outputConditionStartBat  = join-path  $outputDir  $startBatFileName
        Write-Host "Genereting start.bat. Output is  $outputConditionStartBat"
        
        $startbarContent |
             out-file  $outputConditionStartBat  -Encoding ascii
    }
    else 
    {
        #region For each condition in user file
        [xml]$userFileContent = gc $userFile
        $userCondition = $userFileContent.Project.PropertyGroup.Condition

        $csProjConditions = $csprojContent.Project.PropertyGroup.Condition
        foreach($csprojCondition in $csProjConditions)
        {
            if($csprojCondition -eq $null)
            {
                continue;
            }

            [string]$conditionString =  ([string]$csprojCondition)
                                  .Trim()


            $indexOfequals = $conditionString.LastIndexOf("==")+2;
            if($indexOfequals -gt 2)
            {
                $conditionSimpleString = $conditionString
                     .Substring($indexOfequals)
                     .Trim()
                     .Replace("'","")
                     .Replace("|","_")

                if($contains =  $userCondition -contains $conditionString)
                {
                   $propertyGroup =  $userFileContent.Project.PropertyGroup | 
                                ?{$_.Condition -eq $conditionString }

                   $startArguments = $propertyGroup.StartArguments

                   $startBatContentWithArgs = $startbarContent+ " " + $startArguments 
           
                   $outputConditionStartBat  = join-path  $outputDir  ($conditionSimpleString + "_" +$startBatFileName) 

                   Write-Host "Genereting start.bat for $conditionSimpleString. Output file is $outputConditionStartBat"

                   $startBatContentWithArgs |
                    out-file  $outputConditionStartBat  -Encoding ascii
                }
            }

        }
        #endregion
    }
}
Dla różnej konfiguracji (Platform Configuration) możemy mieć różne parametry. Wygenerowany start.bat możemy uzyskać poprzez wywołanie polecenia:
New-StartBat -csprojFilePath "SuperProjectName.csproj" -outputDir ".\bin\Debug"

czwartek, 27 lutego 2014

Wartość oczekiwana w PS

Ostatnio bawiłem się statystyką i postanowiłem napisać super prostą funkcję do zliczania wartości oczekiwanej w PowerShell.


function Get-ExpectedValue
{
    param(
        [Parameter(Mandatory=$true)]
        [ValidateNotNullOrEmpty()]
        [array]$values=@(),
        
        [Parameter(Mandatory=$false)]
        [ValidateNotNullOrEmpty()]
        [array]$probability=$( @(1/$values.Length) * $values.Length)
    )
        [int]$min =[math]::Min($values.Length, $probability.Length)
        $sum=0
        $probabilitySum=0
        for($i=0; $i -lt $min; $i++)
        {
            $product = [double]$values[$i] * $probability[$i]
            $sum+=  $product
            $probabilitySum+=$probability[$i]
        }

        return ($sum / $probabilitySum)
}
Wprowadźmy wartość oczekiwaną w praktykę. Wartość oczekiwana sprawdza się w grach.

Kostka sześcienna ma wartość oczekiwaną 3.5
Get-ExpectedValue  -values 1,2,3,4,5,6  #3,5

Gdyby prawdopodobieństwo wystąpienia ilości oczek nie było takie same to wartość oczekiwana była by inna:
Get-ExpectedValue  -values 1,2,3,4,5,6 -probability ((1/6), (1/5),(1/3),(1/3))  #2,80645161290323


Dajmy na to, że gramy w kości. Jeżeli uzyskasz liczbę oczek mniejszą lub równą 2 to dasz mi kwadrat różnicy 6 i ilości oczek. Natomiast jak uzyskasz liczbę oczek 3,4,5,6 to ja tobie daję dwu-krotność liczby oczek.
Get-ExpectedValue  -values ( (-1* (6-1) *(6-1) ), (-1*(6-2)*(6-2)),  6,8,10,12 ) #-0,833333333333333



Bardzo lubię grać w Osadników z catanu i w grze występują dwie kostki. Wiesz może dlaczego złodziejem ruszasz się, gdy masz sumę równa 7?? Rozwiązanie jest przedstawione poniżej:
$dice  = 1,2,3,4,5,6
$dice2=  $arr | %{ 
    $outter = $_
    $arr | %{
        $inner = $_
        return $outter + $inner
    }
} | sort
Get-ExpectedValue $dice2 #7

$dice2 | group 
Count Name                      Group                                                                                                                                    
----- ----                      -----                                                                                                                                    
    1 2                         {2}                                                                                                                                      
    2 3                         {3, 3}                                                                                                                                   
    3 4                         {4, 4, 4}                                                                                                                                
    4 5                         {5, 5, 5, 5}                                                                                                                             
    5 6                         {6, 6, 6, 6...}                                                                                                                          
    6 7                         {7, 7, 7, 7...}                                                                                                                          
    5 8                         {8, 8, 8, 8...}                                                                                                                          
    4 9                         {9, 9, 9, 9}                                                                                                                             
    3 10                        {10, 10, 10}                                                                                                                             
    2 11                        {11, 11}                                                                                                                                 
    1 12                        {12}  


Jest to wartość oczekiwana, a jednocześnie najczęściej spotykana suma.

Algorytmy przeszukiwania w PowerShell

Przeglądałem książkę o algorytmach i strukturach danych i postanowiłem zaimplementować przeszukiwanie tablicy w PowerShellu. Założenie jest takie, że może występować w tablicy więcej niż jeden szukany element oraz funkcja przeszukująca powinna zwrócić numery indeksów szukanego elementu. Najprostszy algorytm przeszukiwania sekwencyjnego jest prosty:
function Search-Sequential([array]$arr, $item, [switch]$firstfound)
{
    $found=@()

    for($i=0; $i -lt $arr.Length; $i++)
    {
        if($arr[$i].Equals($item) )
        {
            $found+=$i
            if($firstfound)
            {
                return $found
            }
        }
    }
    return $found
}
Użycie funkcji jest intuicyjne:
$arr = 1,2,3,4,4,4,4,4,5,5,5,6,6,7,8,99,120
Search-Sequential -arr $arr -item 5   #8,9,10
Drugim ciekawym algorytmem przeszukiwania jest przeszukiwanie binarne:
function Search-Binare([array]$arr, $item, [switch]$firstfound)
{
    $low =0
    $high = $arr.Length -1
    $found=@()
    While($low -le $high)
    {
        $middleIdx = [math]::Floor(($low + $high)/2)
        $middleValue = $arr[$middleIdx]

        if($middleValue -lt $item)
        {
            $low = $middleIdx+1
        }
        elseif($middleValue -gt $item)
        {
            $high = $middleIdx -1
        }
        else{
            $found+=$middleIdx

            if(!$firstfound)
            {
                $leftNeighborMiddleIdx = $middleIdx-1

                if($low -le $leftNeighborMiddleIdx)
                {
                    $leftArr =  $arr[$low..$leftNeighborMiddleIdx]
                    $foundOnLeftWithOffset = 
Search-Binare -arr $leftArr -item $item -firstfound:$firstfound
                    $foundOnLeft = $foundOnLeftWithOffset | 
%{ $low + $_  }
                    $found+=$foundOnLeft
                }

                $rightNeighborMiddleIdx = $middleIdx+1
                if($rightNeighborMiddleIdx -le $high)
                {
                    $rightArr = $arr[$rightNeighborMiddleIdx..$high]
                    $foundOnRightWithOffset = 
Search-Binare -arr $rightArr -item $item -firstfound:$firstfound
                    $foundOnRigh = $foundOnRightWithOffset | 
%{$rightNeighborMiddleIdx + $_}
                    $found+=$foundOnRigh
                }
            }
            return $found
        }
    }
}
Niestety musiałem dodać wywołanie rekurencyjne, aby przeszukał sąsiednie elementy. Przeszukiwanie binarne dla tej samej tabeli zwraca te same elementy, ale w innej kolejności:
Search-Binare -arr $arr -item 5  #8,10,9
Postanowiłem napisać jeszcze jeden alg. za pomocą tablicy haszującej. Na samym początku potrzebowalibyśmy funkcji do przekształcenia zwyczajnej tablicy na hashtable:
function ConvertTo-Hashtable(
[array]$arr,
 [scriptblock]$hashFunction = 
$({param($x) return $x.GetHashCode()}))
{
    [array]$hashTable =   @(,$null) * 100
    
    for($i=0; $i -lt $arr.Length; $i++)
    {
        $item = $arr[$i]
        $hashCode = $hashFunction.InvokeReturnAsIs($item)

        $diff = $hashCode - $hashTable.Length
        if($diff -ge 0)
        {
            $hashTable +=  @(,$null) * ($diff +1)
        }

        if(-not($hashTable[$hashCode]))
        {
            $hashTable[$hashCode] =@()
        }

        $hashTable[$hashCode] += $i
    }
    return $hashTable
}
Warto zauważyć tutaj jaka jest funkcja haszująca. Korzystamy z ogólnodostępnej funkcji GetHashCode.
Funkcja haszująca jest zapisana w script bloku. Konwersja i wyszukiwanie wygląda następująco:
$arr = 1,2,3,4,4,4,4,4,5,5,5,6,6,7,8,99,120
$hashtable  = ConvertTo-Hashtable -arr $arr
Search-Hashed -arr $hashtable -item 5 #8,9,10

Natomiast funkcja przeszukująca tablice haszującą ma 2 linijki implementacji:
function Search-Hashed
([array]$arr, $item, 
[scriptblock]$hashFunction= 
$({param($x) return $x.GetHashCode()}))
{
    $hashCode = $hashFunction.InvokeReturnAsIs($item)
    return $arr[$hashCode]
}
Zamiast domyślnej funkcji haszującej można stworzyć swoją własną. Mój przykład dla znaków to:
$hashFunction = {param($x) [int][char]$x}
A wywołanie wygląda następująco:
$arr = 'A','V','b','b','C'
$hashtable = ConvertTo-Hashtable -arr $arr -hashFunction $hashFunction
Search-Hashed -arr $hashtable -item 'b' -hashFunction $hashFunction  #2,3
Równie dobrze mogę zastosować własną funkcję haszującą string:
$hashFunctionString = {param($x)  [int[]][char[]]$x-join ''}
$hashFunctionString.InvokeReturnAsIs("Hello Arek ") #72101108111326511410110732
Oczywiście nie mogę stworzyć tak wielkiej tablicy, ale może coś się wymyśli :)

wtorek, 25 lutego 2014

Symbol Newtona w PowerShell

Chciałem poćwiczyć z symbolem Newtona, więc postanowiłem napisać skrypt w PS, aby porównać te sposoby uzyskiwania współczynnika dwumianowego.
Oczywiście do symbolu Newtona będziemy potrzebowali funkcję zwracającą wartość silni.
function Get-Factorial([int]$n)
{
    if($n -lt 1) {
        return 1
    }
    $facttorialRec = Get-Factorial($n -1)
    return ($n * $facttorialRec )
}
Jak na razie funkcja oblicza silnie rekurencyjnie (ale mam w planach dodać jeszcze silnie obliczoną w sposób iteracyjnie).

Mamy też funkcję obliczającą symbol Newtona za pomocą rekurencji:
function Get-BinomialCoefficientRec([int]$n, [int]$k)
{
    if($k -lt 0 -OR $k -gt $n)
        {return 0}

    if($k -eq 0 -OR $k -eq $n -OR $n -lt 1)
        {return 1} 

    $diff = $n - $k
    if($k -gt $diff)
    {
        $k = $diff
    }
    
    $binomial1 = Get-BinomialCoefficientRec -n ($n-1) -k $k
    $binomial2 = Get-BinomialCoefficientRec -n ($n-1) -k ($k-1)
    return $binomial1 + $binomial2
}


Oraz funkcję korzystającą z tożsamości algebraicznej:
function Get-BinomialCoefficientIteratively([int]$n, [int]$k)
{
    if ($k -lt 0 -or  $k -gt $n)
    {return 0}
 
    if($k -eq  0 -or  $k -eq  $n)
    { return 1}

    $diff = $n - $k
    if ($k -gt $diff)
    {  $k = $diff }
    
    $prod = 1
    for($i=1; $i -le $k; $i++)
    {
        $prod = $prod * (  ($n - $i + 1) / $i  )    
    }

    return $prod
}

Możemy wyliczyć symbol Newtona na ze wzoru Sterlinga. Wzór ten stosuje się dla bardzo dużych liczb, gdyż błędy względne są małe.
function Get-StirlingApproximation([int]$n)
{

    $numDivE = $n / [math]::E
    $const = [math]::Sqrt(2.0 * $n * [math]::PI)
    $result = $const * ([math]::Pow(($numDivE) ,$n))   
    if($result -eq 0)
        {return 1}
    return $result
}


Główna funkcja, która agreguje funkcje zliczające współczynnik dwumianowy jest przedstawiona poniżej:

function Get-BinomialCoefficient
{
    param(
    [ValidateSet('factorial','recursive', 'multiplicative', 'stirling'  )]
    [string]$arg='factorial',

    [Parameter(Mandatory=$true, Position=0)]  
    [int]$n,

    [Parameter(Mandatory=$true, Position=1)]  
    [int]$k
    )

    if($arg -eq 'factorial')
    {
         $upperFractal = Get-Factorial($n) 
         $lowerFractalK = Get-Factorial ($k) 
         $lowerFractalNK=  Get-Factorial($n- $k)
         return $upperFractal  / ($lowerFractalK * $lowerFractalNK)
    }
    elseif($arg -eq 'stirling')
    {
        $aproxN = Get-StirlingApproximation($n)
        $aproxK = Get-StirlingApproximation ($k)
        $aproxNK = Get-StirlingApproximation($n- $k)
        return  $aproxN/ ( $aproxK  *$aproxNK )
    }
    elseif($arg -eq 'recursive')
    {
        return Get-BinomialCoefficientRec -n $n -k $k
    }
    elseif($arg -eq 'multiplicative')
    {
        return Get-BinomialCoefficientIteratively -n $n -k $k
    }

    throw 'Wrong argument in parameter $arg'
}


A funkcja do pomiaru wygląda następująco:
function Measure-BinomialCoefficient([int]$to)
{
    $Nenum = 1..$to
    $Nenum | %{
        $n = $_
        $Kenum = 1..$n 
        $Kenum | %{
           $k = $_
           $factorialMeasure =         
(Invoke-Command  {  Get-BinomialCoefficient -arg factorial -n $n -k $k       })

           $multiplicativeMeasure =    
(Invoke-Command  {  Get-BinomialCoefficient -arg multiplicative -n $n -k $k  })

           $recursiveMeasure =         
(Invoke-Command  {  Get-BinomialCoefficient -arg recursive -n $n -k $k       })

           $stirlingMeasure =          
(Invoke-Command  {  Get-BinomialCoefficient -arg stirling -n $n -k $k        })


            return new-object PSObject | 
                
Add-Member -PassThru -MemberType NoteProperty 
-Name  n  -Value $n |
               
Add-Member -PassThru -MemberType NoteProperty 
-Name  k  -Value $k |
                
Add-Member -PassThru -MemberType NoteProperty 
-Name  factorial  -Value $factorialMeasure |
                
Add-Member -PassThru -MemberType NoteProperty 
-Name  multiplicative  -Value $multiplicativeMeasure |
                
Add-Member -PassThru -MemberType NoteProperty 
-Name  recursive  -Value $recursiveMeasure |
                
Add-Member -PassThru -MemberType NoteProperty 
-Name  stirling  -Value $stirlingMeasure
        }
    }
}

Wyniki tych wywołań są przedstawione poniżej. Co prawda wzór Stirling nie daje dokładnej wartości, ale jestem pod wrażeniem przybliżenia wartości symbolu Newtona.



Aby uzyskać czasy działania algorytmów to wystarczy zamienić słowa Invoke na Measure oraz dodać TotalMilliseconds - pomiary są w milisekundach.
           $factorialMeasure =         
(Measure-Command  {  Get-BinomialCoefficient -arg factorial -n $n -k $k       }).TotalMilliseconds

           $multiplicativeMeasure =    
(Measure-Command  {  Get-BinomialCoefficient -arg multiplicative -n $n -k $k  }).TotalMilliseconds

           $recursiveMeasure =         
(Measure-Command  {  Get-BinomialCoefficient -arg recursive -n $n -k $k       }).TotalMilliseconds

           $stirlingMeasure =          
(Measure-Command  {  Get-BinomialCoefficient -arg stirling -n $n -k $k        }).TotalMilliseconds

A poniżej wykres przedstawiający czasy działania algorytmów (dla różnych n i k):



Gdybyśmy ograniczyli ilość danych poprzez wprowadzenie parametru k jako połowa parametru n oraz przedstawili dane na wykresie w skali logarytmicznej to mamy taki wykres:

Co dla mnie jest dziwne, to czasy obliczeń symbolu Newtona za pomocą wzoru Sterlinga oraz dla iteracyjnego sposób wyliczenia się zmniejszają :)
Takie rzeczy to tylko w PS.


Ref parametry i wieża Hanoi w PowerShellu

Niestety, przekazywanie wartości przez referencję w PS nie jest wskazane. Postanowiłem troszkę poćwiczyć z tym typem danych. Jednym z zadań algorytmicznych, dla którego przydatne jest przekazywanie wartości przez referencje jest problem wieży Hanoi. Postanowiłem rozwiązać ten problem za pomocą obiektu z .NET. Stwórzmy klasę, która będzie reprezentowała stan wieży:
$HanoiRodsClassDefinition = @"
using System.Collections.Generic;
using System.Linq;

public class HanoiRods
{
    public List<int> RotA;
    public List<int> RotB;
    public List<int> RotC;
    public HanoiRods (int spots=1)
    {
        RotA =  Enumerable.Range(0,spots).ToList();
        RotB= new List<int>();
        RotC= new List<int>();
    }

    public int GetSpots()
    {
        return RotA.Count;
    }

    public HanoiRods New( List<int> rotA,  List<int> rotB, List<int> rotC)
    {
        return new HanoiRods{
        RotA = rotA,
        RotB = rotB,
        RotC = rotC,
        };
    }
}
"@

Aby dodać definicję klasy do PS to wystarczy:
Add-Type -Language CSharp -TypeDefinition $HanoiRodsClassDefinition

A sam algorytm rozwiązywania wieży Hanoi w PS jest następujący:
function Solve-Hanoi
{
    param(
    [Parameter(Mandatory=$true)]
    [HanoiRods]$rots,

    [Parameter(Mandatory=$false)]
    [int]$spots=$($rots.GetSpots()),

    [ref]$moves
    )

    if($spots -gt 0)
    {
        
        Solve-Hanoi -spots ($spots-1) -rots ($rots.New($rots.RotA, $rots.RotC, $rots.RotB)) -moves $moves

        $rots.RotC.Insert(0,$rots.RotA[0])
        $rots.RotA.RemoveAt(0)
        $moves.Value  +=1

        Write-Host ""
        Write-Host "Spot $spots"
        Write-Host "A $($rots.RotA)"
        Write-Host "B $($rots.RotB)"
        Write-Host "C $($rots.RotC)"

        Solve-Hanoi -spots  ($spots-1) -rots ($rots.New($rots.RotB, $rots.RotA, $rots.RotC)) -moves $moves
    }
}
Z ciekawych parametrów jest zmienna [ref]$moves, którą przekazujemy przez referencje.

Możemy teraz definiować parametry do rozwiązania wieży Hanoi:
$hanoi = new-object HanoiRods 5
[ref]$moves=0

A same wywołanie jest następujące:
Solve-Hanoi -rots $hanoi -moves $moves
$moves

Dla 5 krążków musimy wykonać 31 ruchów, aby rozwiązać problem wieży Hanoi.

poniedziałek, 24 lutego 2014

Alternatywa dla Measure-Command w PS

Measure-Command jest całkiem fajną komendą. Pozwala wyświetlić czas trwania polecenie. Niestety, ma parę wad, m.in. nie ma aliasu, a kiedy chce sprawdzić czas działania komend w pipe to na początku i na końcu polecenie muszę dopisywać nawiasy klamrowe - '{' i '}'. Measure-Command ma wymagający parametr Expression, który jest script blockiem i nie może byc w pipe.

Przykład wywołania measure-command jest kod przedstawiony poniżej:
 Measure-Command {Get-ChildItem –Path "C:\Program Files\*.txt" -Recurse}

A dla pipów mam własną funkcję:
function  Measure-Time
{
    param([switch] $PassThru)
    begin{
        $sw = [Diagnostics.Stopwatch]::StartNew()
    }
    process {
        if($PassThru)
        {
            $_
        }
    }
    end{
        $sw.Stop()
        return $sw.Elapsed
    }
}

Wywołanie jest następujące:
 Get-ChildItem –Path "C:\Program Files\*.txt" -Recurse | Measure-Time -PassThru

I oczywiście alias:
New-Alias -Name measureT -Value Measure-Time
Ok, wiem, że pipy są wolne, ale zaletą PS nie jest szybkość działania, ale szybkość implementacji prostych rzeczy.

sobota, 22 lutego 2014

MSCW jako proces normalizacji

Procesem normalizacji nazywa się proces, który przekształca dane źródłowe w ustandaryzowany format, nazwy oraz wartości bazując na pewnych regułach. Dane wyjściowe uzyskujemy z danych wejściowych oraz wykonanych regułach na tych danych. W tym przypadku będzie to normalizacja MSCW:



Reguły MSCW są regułami, które zapewniają istotne informacje (lub ich brak) w danych wyjściowych. Zapewne, nie świadomie korzystasz z tych reguł, gdyż są bardzo popularne, ale bardzo rzadko nazywa się je. Są bardzo ważne w bezpieczeństwie przesyłanych danych.

Znaczenie skrótu MSCW wyjaśnia wszystko:
Must - pole musi być w danych wejściowych oraz musi być sprawdzone i zwalidowane
Should - pole musi być w danych wejściowych, a jak nie ma wartości to zostanie zastąpione przez inną (być może domyślną) wartością
Could - jeżeli pole będzie w danych wejściowych, to te pole będzie procesowanie dalej
Won't - jeżeli pole będzie w danych wejściowych, to te pole będzie zablokowane

Przykładem normalizacji MSCW jest proces rejestracji użytkownika na stronie internetowej. Po rejestracji, dostępne informację dla innych użytkowników strony są ograniczone do podstawowych pól:


Normalizacja MSCW występuje również w dużych projektach ETL. Zawsze powinniśmy wiedzieć jakie dane powinny być procesowane, a jakie powinny być ukryte.

poniedziałek, 17 lutego 2014

Quicksort w PowerShell

W trakcie nauki algorytmów napisałem alg. quick sort w PS. Średnio jestem z niego zadowolony, ale za pomocą PS widać jak z małą ilością kodu można zaimplementować ten algorytm.

function QuickSort-Object
{
    param([array] $arr)
    $Count = $arr.Count
    if($Count  -le 1 -OR (($arr |  select –unique).count -eq 1))
    {
        return $arr
    }

    $pivot = $arr[$Count/2]

    return [array](sort-object ($arr | ? {$_ -lt  $pivot})) +  
      (sort-object ($arr  | ? {$_ -eq  $pivot})) +
      (sort-object ($arr | ? {$_ -gt  $pivot}))
}

Jeszcze raz chciałbym przedstawić filmik, który świetnie przedstawia algorytm sortowania. Co prawda początek filmiku mnie troszkę zdezorientował, ale reszta jest taka sama :)


niedziela, 16 lutego 2014

Sprawdzanie sln'a

Często dostaje się błąd solucji z wiadomością:
"Error MSB4025: The project file could not be loaded. Data at the root level is invalid. Line 2, position 1."

Jest to błąd przy kompilowaniu solucji Visual Studio. Jest to problem z plikiem sln, najprawdopodobniej jest on związany z mergowaniem z innego brancha. Nie może zależ guid projektu lub guid jest z duplikowany. Aby sprawdzić czy wszystko jest ok, wystarczy uruchomić skrypt sprawdzający identyfikatory projektów:

function Test-Sln
{
    Param
    (
        [string] $slnPath
    )
    Write-Host "Testing sln in $slnPath"
    if(! (Test-Path($slnPath)))
    {
        throw "No file for $slnPath"
    }
    else
    {
        $slnContent = gc $slnPath
        $regex_id = '(\{[0-9A-F]{8}-[0-9A-F]{4}-[0-9A-F]{4}-[0-9A-F]{4}-[0-9A-F]{12}\})'
        $regex_id_proj = '(\"{[0-9A-F]{8}-[0-9A-F]{4}-[0-9A-F]{4}-[0-9A-F]{4}-[0-9A-F]{12}\}")'
        $matches_id =  [regex]::Matches($slnContent,$regex_id)
        $matches_id_proj =  [regex]::Matches($slnContent,$regex_id_proj)
        $dict_id =   Count-List $matches_id 
        $dict_id_proj = Count-List $matches_id_proj
        $returnValue = $true
        $keyChecked = 0
        $dict_id.Keys | foreach {
          $key=  $_
          $count = $dict_id[$key]
          $key_proj = '"' +  $key + '"'

           if( $dict_id_proj.Keys -contains $key_proj)
           {
                $count_proj = $dict_id_proj[$key_proj]
                if(($count -ne $count_proj) -and ($count_proj -gt 1))
                {
                     Write-Error "Wrong amount of reference for id $key. $count refers to $count_proj projects"
                     $returnValue=$false
                } 
                else
                {
                    Write-Host "Project with id $key is ok"
                }
           }
           else
           {
                Write-Error "Problem on id $key. There are $count refers in sln"
                $returnValue=$false
           }
           $keyChecked+=1
        }
        Write-host "Checked $keyChecked projects"
        return $returnValue
    }
}

Do tego potrzebujemy funkcję zliczającą ilość elementów w liście:
function Count-List ($List) #not explicitly list type 
{
$dic = @{}
$List| Foreach {
$id = $_.ToString()
    if($dic.ContainsKey($id))
    {
      $counter =  $dic.Get_Item($id);
      $counter +=1
      $dic.Set_Item($id,$counter);
    }
    else
    {
      $dic.Add($id,1)
    }
}
return $dic
}

Przykład wywołania jest poniżej:
if(!(Test-Sln "SuperSolution.sln"))
{
   throw "Errors in sln file" 
}

Wyświetlanie zdjęć w PS

Brakowało mi polecenia w PS, które mogło by wyświetlić zdjęcie. Niestety nie mogłem znaleźć takiego polecenia i postanowiłem napisać funkcyjkę :)

[void][reflection.assembly]::LoadWithPartialName("System.Windows.Forms")
function Show-Image
{   
    [CmdletBinding(DefaultParametersetName="s")] 
    param(
    [Parameter(ParameterSetName="f", Position=0,ValueFromPipeline=$true)] 
    [System.IO.FileInfo]$fileInfo,

    [Parameter(ParameterSetName="s", Position=0,ValueFromPipeline=$true)] 
    [string]$filePath
    )

    begin{
        [System.Windows.Forms.Application]::EnableVisualStyles()
        $form = new-object Windows.Forms.Form
        $pictureBox = new-object Windows.Forms.PictureBox
        $form.controls.add($pictureBox)
        $form.Add_Shown( { $form.Activate() } )
        $form.StartPosition = [System.Windows.Forms.FormStartPosition]::CenterParent        
    }

    process{
        switch ($PsCmdlet.ParameterSetName) 
        { 
 
        "f" {
                $file = $fileInfo
            }
        "s" {
                $fileInfo =get-item $filePath
            }
        }

        $fileName = $fileInfo.FullName
        $img = [System.Drawing.Image]::Fromfile($fileInfo)
        
        $form.Text = $fileName
        $form.Width = $img.Size.Width 
        $form.Height =  $img.Size.Height
        $pictureBox.Width =  $img.Size.Width
        $pictureBox.Height =  $img.Size.Height
        $pictureBox.Image = $img
        [void]$form.ShowDialog()

        $img.Dispose()
    }
    end{
    $pictureBox.Dispose()
    $form.Dispose()
    }
}
Wywołanie jest w formie pipu:
gi .\image.jpg |show-image
A tak wygląda funkcja w akcji:

sobota, 15 lutego 2014

Skróty klawiszowe do VS

Jak wiadomo skróty klawiszowe są bardzo przydatne bo polepszają naszą produktywność, więc dobrze jest mieć skróty dopasowane do własnych potrzeb. Z indywidualnymi skrótami klawiszowymi jest jeden problem - osoba, która nie zna twoich skrótów może mieć problemy z obsługą środowiska programistycznego, już nie mówiąc o takim dziwnym tworze jak Ping-Pong Pair Programming. Ja mam skróty dopasowane do siebie i osoby na moim komputerze nie wiedzą jak ja mogę w ogóle kodować :)

Poniżej jest tabelka ze skrótami. Wywołanie polecenia składa się z kombinacji skrótów. Pierwszy skrót oznacza grupę, a drugi skrót już konkretne polecenie. Jeżeli chcesz odpalić polecenie debugowania to korzystasz z grupy RUN (CTRL + R) i polecenie Debug.Start (CTRL + D). Jeżeli bez chcesz uruchomić bez debagowania to pod tej samej grupie jest polecenie Debug.StartWithoutDebugging (CTRL + SHIFT + D).
Niektóre skróty już coś oznaczają (CTRL + F czy CTRL + A), więc musiałem dołożyć dodatkowy klawisz.



Plik z ustawieniami importu w Visual Studio jest poniżej:


Moje skróty ewoluują, Wcześniej miałem skrót do zen codingu, czy do GhostDoc'a. Czasami skróty są zależne od projektu.

czwartek, 13 lutego 2014

Wizualizacja algorytmu Wieży Hanoi

Ilość wykonywanych ruchów w algorytmie Wieży Hanoi wzrasta bardzo szybko wraz ze wzrostem ilości krążków. Stworzyłem parę obrazków, które przedstawiają kroki jakie należy zrobić, aby rozwiązać wieże. Wierzchołki grafu są słupkami wieży, a numer na krawędzi grafu symbolizuje kolejność przesuwania krążka.


Przeniesienie dla 1 krążka:

Przeniesienia dla 2 krążków:

Przeniesienia dla 3 krążków:

Przeniesienia dla 4 krążków:

Przeniesienia dla 5 krążków:

Przeniesienia dla 6 krążków:

Przeniesienia dla 7 krążków:

Więcej o Wieży Hanoi można poczytać tutaj.

wtorek, 11 lutego 2014

PowerShell i GraphViz

Już wcześniej pisałem o grafie w Power Shellu, a tym razem o przedstawieniu połączeń w grafie na obrazie. Do przedstawienia grafu użyjemy darmowego narzędzia GraphViz. Użyjemy grafu z poprzedniego wpisu.


$graph  = Create-Graph | 
    Add-Edge -edge (Create-Edge A B  1 ) |
    Add-Edge -edge (Create-Edge A C  5) |
    Add-Edge -edge (Create-Edge A D  3) |
    Add-Edge -edge (Create-Edge A E  11) |
    Add-Edge -edge (Create-Edge B C  9) |
    Add-Edge -edge (Create-Edge B D  1) |
    Add-Edge -edge (Create-Edge B E  2) |
    Add-Edge -edge (Create-Edge C D  6) |
    Add-Edge -edge (Create-Edge C E  4) |
    Add-Edge -edge (Create-Edge D E  3) 



Rozdzielimy to zadanie na 2 części. Pierwsza część będzie translacja grafu do języka dot używanego w GraphVizie (w praktyce jest to zapis danych w podobnej postaci co przykład z galerii GraphViz).
function ConvertTo-GraphViz
{
        param(
        [Parameter(Mandatory=$true, Position=1,ValueFromPipeline=$true)]  
        [ValidateNotNull()]  
        $graph,

        [ValidateNotNullOrEmpty()] 
        [string]$name='G',

        [ValidateRange(8, 52)]
        [int]$fontSize =12,

        [ValidateNotNullOrEmpty()] 
        [string]$label='Graph from PowerShell',
        
        [ValidateNotNullOrEmpty()] 
        [string]$arrowSign = '->',

        [ValidateNotNullOrEmpty()] 
        [ValidateSet('LR','RL')]
        [string]$rankdir='LR'
    )
    begin{
#region Strings
        $templateBegin ="digraph $name {
rankdir=$rankdir;
"
        $templateEnd = "
fontsize=$fontSize;
}"
        $templateBody= ''
        $format = "{0} $arrowSign {1} [label = {2} ];
"
#endregion
        }
    process{
        $graph.Edges | %{ 
             $templateBody += $format -f $_.From, $_.To, $_.Weight
            }

        }
    
    end{
        return $templateBegin + $templateBody + $templateEnd 
    }
}



Drugą częścią zadania będzie zapisanie kodu dot do pliku i uruchomienie aplikacji, która przekonwertuje do obrazu przedstawiającego ten graf:
function Out-GraphViz
{
    param(
    [Parameter(Mandatory=$true, Position=1,ValueFromPipeline=$true)] 
    [ValidateNotNullOrEmpty()] 
    $graphVizDot,
    
    [ValidateNotNullOrEmpty()]
    [string]$fiepath='PsGraphViz.png',
    [ValidateNotNullOrEmpty()]

    [stinrg]$dotFilePath ='PsGraphViz.dot',
    
    [ValidateNotNullOrEmpty()]
    [ValidateSet('bmp', 'canon', 'cmap', 'cmapx', 'cmapx_np', 'dot', 'emf', 'emfplus', 'eps', 'fig', 'gd', 'gd2', 'gif', 'gv', 'imap', 'imap_np', 'ismap', 'jpe', 'jpeg', 'jpg', 'metafile', 'pdf', 'pic', 'plain', 'plain-ext', 'png', '
pov', 'ps', 'ps2', 'svg', 'svgz', 'tif', 'tiff', 'tk', 'vml', 'vmlz', 'vrml', 'wbmp', 'xdot', 'xdot1.2', 'xdot1.4')]
    [string]$format='png'
    )
    process{

        $graphVizDot| Out-File -FilePath $dotFilePath -Encoding ascii 

        $cmdpath  ="~\Programs\graphviz\bin\dot.exe"
        Write-Verbose "Running app from $cmdpath"
        Invoke-Expression "& `"$cmdpath`" -T$format -o $fiepath $dotFilePath" 
    }
}



Wywołanie wygląda następująco:
$graph | ConvertTo-GraphViz  | Out-GraphViz

A po tej komendzie zostaną wygenerowane 2 pliki (dot plik oraz obraz grafu):

poniedziałek, 10 lutego 2014

Graf w PowerShell

Dzisiaj troszkę się namęczyłem z implementacją grafu skierowanego w PowerShellu. Co prawda dużo łatwiej było by mi zaimplementować graf w c#, ale w ramach ćwiczeń ... chciałem się namęczyć :)

Poniżej jest moja implementacji grafu skierowane
Na początku tworzymy obiekt, który będzie zawierał listę krawędzi:
function Create-Graph
{
    return new-object PSObject | 
            Add-Member -PassThru -MemberType NoteProperty -Name  Edges  -Value @()  -TypeName "array" 
}

Do dodawania krawędzi potrzebujemy dodatkowych funkcja. Zakładamy, że krawędź będzie zawierała informację o połączeniu dwóch wierzchołków oraz wartości tego połączenia.
function Create-Edge
{
    param(
        [ValidateNotNullOrEmpty()] 
        [string]$from,
        [ValidateNotNullOrEmpty()]
        [string]$to,
        [int]$weight=1
    )
    return @{
        From  = $from;
        To = $to;
        Weight = $weight;
    }
}

function Add-Edge
{
    param(
        [Parameter(Mandatory=$true, Position=1,ValueFromPipeline=$true)]  
        [ValidateNotNull()]    
        $graph,

        [Parameter(Mandatory=$true, Position=2)] 
        [ValidateNotNull()]     
        $edge
      )
    process{
        $graph.Edges +=$edge
        return $graph
    }
}



Wtedy poniższy kod tworzy graf skierowany:
$graph  = Create-Graph | 
    Add-Edge -edge (Create-Edge A B  1 ) |
    Add-Edge -edge (Create-Edge A C  5) |
    Add-Edge -edge (Create-Edge A D  3) |
    Add-Edge -edge (Create-Edge A E  11) |
    Add-Edge -edge (Create-Edge B C  9) |
    Add-Edge -edge (Create-Edge B D  1) |
    Add-Edge -edge (Create-Edge B E  2) |
    Add-Edge -edge (Create-Edge C D  6) |
    Add-Edge -edge (Create-Edge C E  4) |
    Add-Edge -edge (Create-Edge D E  3) 
Do sprawdzenia nazw wierzchołków pomocne będą poniższe funkcje:
function Get-EdgesNumber
{
    param(
        [Parameter(Mandatory=$true, Position=1)] 
        [ValidateNotNull()]     
        $graph
      )
    return $graph.Edges.Count
}

function Get-Vertices
{
    [cmdletBinding(SupportsShouldProcess=$true,ConfirmImpact='Medium')] 
    param(
        [Parameter(Mandatory=$true, Position=1)]
        [ValidateNotNull()]      
        $graph
      )
      Write-Verbose "Getting number of Vertices in graph"

      [array] $toVertices = $graph.Edges.To 
      [array] $fromVertices =   $graph.Edges.From
      return [array](($toVertices + $fromVertices) | select -Unique | sort)
}

function ConvertFrom-Graph
{
    [cmdletBinding(SupportsShouldProcess=$true,ConfirmImpact='Medium')] 
    param(
        [Parameter(Mandatory=$true, Position=1,ValueFromPipeline=$true)]
        [ValidateNotNull()] 
        $graph
      )
    process {
        $graph.Edges | %{
              $from =  $_.From 
              $to = $_.To
              $weight = $_.Weight
              Write-Verbose "Weight is $weight for:"
              "$from -> $to"
              }
    }
}

A poniżej przedstawione są wywołania tych funkcji:
Get-EdgesNumber $graph

Get-Vertices $graph

$graph | ConvertFrom-Graph


Oprócz reprezentacji grafu za pomocą kolekcji krawędzi można przedstawić graf za pomocą macierzy:
function ConvertTo-Matrix
{
   param(
        [Parameter(Mandatory=$true, Position=1,ValueFromPipeline=$true)]
        [ValidateNotNull()] 
        $graph
      )
  process{
        $vertices= Get-Vertices $graph
        $dim  = $vertices.Length
        [object[][]]$matrix =  Create-ZeroMatrix $dim
   
        $graph.Edges | % {
            $from = $_.From
            $to = $_.To
            $weight = $_.Weight

            $fromIndex = $vertices.IndexOf($from)
            $toIndex = $vertices.IndexOf($to)

            $matrix[$fromIndex][$toIndex]= $weight
        }
        return $matrix
    }
}

function Create-ZeroMatrix 
{
    param(
        [ValidateScript({$_ -ge 0})]
        [int]$dim
      )
      $matrix = New-Object 'object[][]' $dim,$dim

      for($i =0; $i -lt $dim; $i++ )
      {
        for($j=0; $j -lt $dim ; $j++)
        {
            $matrix[$i][$j] = 0
        }
      }
      return $matrix
}

function ConvertFrom-Matrix 
{
    [cmdletBinding(SupportsShouldProcess=$true,ConfirmImpact='Medium')] 
    param(
    [Parameter(Mandatory=$true, Position=1)]
    [object[][]]$matrix,
    [string]$seperator = ' '
      )
    for($i=0; $i -lt $matrix.Length; $i++)
    {
        Write-Verbose $i
        $(($matrix[$i]) -join $seperator)
    }
}

Konwersja kolekcji krawędzi na macierz jest przestawiona poniżej:
$matrix =  $graph | ConvertTo-Matrix
ConvertFrom-Matrix $matrix 
Oczywiście jeszcze wiele muszę poprawić m.in. konwersja z reprezentacji macierzowej do kolekcji krawędzi, modyfikacja wierzchołków, modyfikacja grafu skierowanego na graf nieskierowanego, walidacja czy wszystkie punkty są ze sobą połączone, ujednolicenie operacji na grafie itd.

sobota, 8 lutego 2014

Porównywanie tablic w PS

Tak się bawiłem z porównywaniem tablic i stwierdziłem, że takiej funkcji zawsze mi brakowało.
function AreEqual-Arrays 
{ 
    [CmdletBinding()]
    param
    (
       [parameter(Mandatory=$true, Position=0)]
       [array] $a1,

       [parameter(Mandatory=$true, Position=1)]
       [array] $a2
    )
 
if ($a1.Rank -ne $a2.Rank) 
{ 
    return $false 
} 

if ([System.Object]::ReferenceEquals($a1, $a2)) 
{ 
    return $true 
}

 
for ($r = 0; $r -lt $a1.Rank; $r++) 
{ 
    if ($a1.GetLength($r) -ne $a2.GetLength($r)) 
    { 
        return $false 
    } 
}
 
$enum1 = $a1.GetEnumerator() 
$enum2 = $a2.GetEnumerator() 
while ($enum1.MoveNext() -and $enum2.MoveNext()) 
{ 
    if ($enum1.Current -ne $enum2.Current) 
    { 
        return $false 
    } 
} 
return $true 
}

Poniższe wywołania zwracają true:
AreEqual-Arrays -a1 @(1) -a2 @(1)
AreEqual-Arrays -a1 @(1,"a") -a2 @(1,"A")
AreEqual-Arrays -a1 @(1,-123) -a2 @("1","-123")
AreEqual-Arrays -a1 @(12,34) -a2 12,34

środa, 5 lutego 2014

Im mniej IE tym mniej morderstw


Natrafiłem na ciekawy wykres. Okazuje się, że jest zależność między popularnością IE, a ilością morderstw w USA.


niedziela, 2 lutego 2014

Skrypt w parametrach domyślnych w PS

Jak piszę kod w C# i mam metodę z możliwością ustawienia domyślnych parametrów to staram się użyć domyślnych parametrów (jednak, nie polecam robienia czegoś takiego dla interfejsów). Czasami problem pojawia się, kiedy do parametru chciałbym przypisać wartość z innej metody. Składnia języka C# na to nie pozwala:


Domyślne parametry mają pewne ograniczenia m.in.:
- nie mogą posiadać modyfikatora ref, out, czy params
- muszą być stałymi w czasie kompilacji
- nie mogą być metodami, właściwościami ani wyrażeniem
- domyślne parametry muszą być definiowane po wymaganych parametrach w metodzie

Co mi się bardzo podoba w PowerShellu to możliwość wywoływania polecenia razem z domyślnymi wartości ( mogą to być bloki skryptów).
PS jest dużo bardziej elastyczny językiem programowania i możemy wprowadzić wymóg wprowadzenia parametru user oraz podania hasła, które na ekranie będzie 'ukryte' :)
function Do-SomeThing
{
    param(
    [string] $computerName = $env:computerName,
    [string] $user =  $(throw "Argument user is not set"),
    [string] $passwd =  $(Get-Password)
    )
    Write-Host "user:$user passwd:$passwd on computer:$computerName"
} 

Przy wywołaniu prostego polecenia dostajemy błąd:
PS>Do-SomeThing 
Argument user is not set

Kiedy wywołamy polecenie z użytkownikiem to dostajemy okienko z możliwością wpisania hasła


Możesz wywołać funkcję z hasłem i nazwą komputera:
Do-SomeThing -user "Arek" -passwd "Abc" -computerName "MyPc"

No i jeszcze funkcja do pobierania hasła:
function Get-Password
{
    $securePass = Read-Host "Enter Password" -AsSecureString
    $bstr = [System.Runtime.InteropServices.Marshal]::SecureStringToBSTR($securePass)
    $pass = [System.Runtime.InteropServices.Marshal]::PtrToStringAuto($bstr)
    [System.Runtime.InteropServices.Marshal]::ZeroFreeBSTR($bstr)
    return $pass
}
Oczywiście w niektórych przypadkach można użyć Parameter(Mandatory) oraz walidatorów (ValidateScript), ale chciałem Ci przedstawić co można zrobić z domyślnymi parametrami.

sobota, 1 lutego 2014

Czytanie mojego kodu

Kolega przesłał mi zdjęcie przedstawiający co myśli, gdy czyta mój kod :)
No cóż, nikt nie jest idealny