bookmark_borderPowershell Postfix to Infix

Here is a powershell example of converting an expression in postfix notation into infix notation. A little background on postfix notation, is that the operators follow the operands. For example “(1 + 2) = 1 2 +”. Postfix is much easier to interpret for a computer, since values are processed as they are used, and their is no need for parenthesis.

#
# Here is an example. 
# Postfix String: 1 2 - 3 * 4 * 5 - = -17
# Infix String:   ((((1 - 2) * 3) * 4) - 5) = -17
#

Here is an example of the algorithm followed by this example.

#
# Algorithm: For every item 'x' in the string
#    x -> number: push it onto the stack
#    x -> operator: pop two items of the stack, join them with x,
#                   then push the result back onto the stack.
#                   EX: "(stack.pop() x stack.pop())"
#
# Given the string "1 2 - 3 * 4 * 5 -"
#
# We use a stack to keep track of our progress.
#
# First item in the string = '1'
# '1' is a number so push it onto the stack
#
#  stack                  remaining: 2 - 3 * 4 * 5 -
#    1
#
# Next item in the string = '2'
# '2' is a number so push it onto the stack
#
#  stack                  remaining: - 3 * 4 * 5 -
#    2
#    1
#
# Next item in the string = '-'
# '-' is an operator, so pop two items of the stack, join, then push
#
#  stack                  remaining: 3 * 4 * 5 -
# (1 + 2)
#
# Next item in the string = '3'
# '3' is a number so push it onto the stack
#
#  stack                  remaining: * 4 * 5 -
#    3
# (1 + 2)
#
# Next item in the string = '*'
# '*' is an operator, so pop two items of the stack, join, then push
#
#  stack                  remaining: 4 * 5 -
# ((1 + 2) * 3)
#
# Next item in the string = '4'
# '4' is a number so push it onto the stack
#
#  stack                  remaining: * 5 -
#    4
# ((1 + 2) * 3)
#
# Next item in the string = '*'
# '*' is an operator, so pop two items of the stack, join, then push
#
#  stack                  remaining: 5 -
# ((1 + 2) * 3) * 4)
#
# Next item in the string = '5'
# '5' is a number so push it onto the stack
#
#  stack                  remaining: -
#    5
# ((1 + 2) * 3) * 4)
#
# Next item in the string = '-'
# '-' is an operator, so pop two items of the stack, join, then push

#  stack                  remaining:
# (((1 + 2) * 3) * 4) - 5)
#
# Now we just pop the last item off the stack, and we have our answer.

Here is the powershell which makes this all possible.

function PostfixTo-Infix
{
    param
    (
        [Parameter(Mandatory=$true)][string]$Postfix
    )
    process
    {
        # Split the string into the individual peices
        $values = $Postfix.Split(' ', [StringSplitOptions]::RemoveEmptyEntries)

        # Stack to store the values as they are being parsed
        $stack = [System.Collections.Generic.Stack[string]]::new()

        foreach($val in $values)
        {
            # Try to parse the value
            $intvalue = 0
            if([int]::TryParse($val, [ref]$intvalue))
            {
                # If the value is an integer, add it to the stack
                $stack.Push($val)

                # Then continue on
                continue;
            }
            else
            {
                # The value is an operator, so pop off the previous two values,
                # And join them with the operator. 
                $b = $stack.Pop();
                $a = $stack.Pop();

                # Then push the result onto the stack
                $stack.Push("($a $val $b)")
            }
        }

        # The final item on the stack must be our result.
        return $stack.Pop()
    }
}

There you have it. Results look like this:

PostfixTo-Infix '1 2 - 3 4 * 5 + *'
((1 - 2) * ((3 * 4) + 5))

In the spirit of good programming, here is a code golfy powershell one liner which also works. It mostly uses the same principal, but uses a hashtable as the stack. One caveat is that it prints all results out backwards, which is fine because there are parenthesis everywhere.

function PostfixTo-InfixGolf
{
    param
    (
        [Parameter(Mandatory=$true)][string]$p
    )
    process
    {
        $s=@{};$a=0;switch -regex($p.Split(' ')){'\d'{$s[$a++]=$_}default{$t="($($s[--$a]) $_ $($s[--$a]))";$s[$a++]=$t}};$s[--$a]
    }
}

bookmark_borderPowershell Postfix Evaluator

There are three different notations for expressing a mathematical equation.

  • prefix
  • infix
  • postfix

Basically, the just describe where operators lie in the equation compared to their operands. The most common of all of the formats is the one everyone is probably most familiar with, infix, which means that the operators lie in between their operands. Lets take for example the equation “1 + 5”.

#
# Equation: "1 + 5"
#
#  Prefix:  "+ 1 5"
#  Infix:   "1 + 5"
#  Postfix: "1 5 +"
#

From the perspective of a computer, postfix if very easy to process, because an operator always follows its two operands, and their is no reason to use parenthesis. Prefix notation also does not require parenthesis, but is a little strange to work with.

In order to process prefix, we always take the right most operator in the expression, and apply it to the next two digits in the string. We do that until we are out of operators. Infix is processed using the order of operations. Postfix is processed by taking the left most operand in the expression, and applying it to the preceding digits every time.

#
# Equation1: "(1 + 5) * 3"
# Equation2: "1 + 5 * 3"
#
#  Prefix1:  "* + 1 5 3"   => "* 6 3"   => "18"
#  Infix1:   "(1 + 5) * 3" => "(6) * 3" => "18"
#  Postfix1: "3 1 5 + *"   => "3 6 *"   => "18"
#
#
#  Prefix2:  "+ * 3 5 1"   => "+ 15 1"  => "16"
#  Infix2:   "1 + 5 * 3"   => "1 + 15"  => "16"
#  Postfix2: "1 5 3 * +"   => "1 15 +"  => "16"
#

The postfix algorithm is quite simple to implement. Going through the string, every time you see a number, add it to a stack. If you see an operator, pop the last two items off of the stack and apply the operator. Push the result back onto the stack so that it can be used in following computations.

So here is an example of the postfix algorithm implemented in powershell.

function Eval-Postfix
{
    param
    (
        [Parameter(Mandatory = $true)][string]$expression
    )
    process
    {
        # Create a stack to store the numbers which aren't yet processed
        $stack = [System.Collections.Generic.Stack[int]]::new()

        # Split the input string into individual values
        $values = $expression.Split(' ', [System.StringSplitOptions]::RemoveEmptyEntries)

        foreach($val in $values)
        {
            # Try to parse the value
            $intvalue = 0
            if([int]::TryParse($val, [ref]$intvalue))
            {
                # If the value is an integer, add it to the stack
                $stack.Push($intvalue)

                # Then continue on
                continue;
            }

            # If the value is not an integer, we pop the top two numbers off the stack
            $b = $stack.Pop()
            $a = $stack.Pop()

            # Then perform the correct operation on them
            $result = switch($val)
            {
                '+' { $a + $b; break; }
                '-' { $a - $b; break; }
                '*' { $a * $b; break; }
                '/' { $a / $b; break; }
            }

            # Push the result back onto the stack
            $stack.Push($result)
        }

        # The only thing left on the stack should be a single value,
        # which is the result of the final operation
        return $stack.Pop()
    }
}

Just to be safe, here is code golf one liner which uses the same queue approach to solve the problem.

function Eval-Postfix
{
    param
    (
        [Parameter(Mandatory = $true)][string]$e
    )
    process
    {
        $s=@();switch -regex($e.Split(' ')){'\d'{$s=,+$_+$s}default{$a,$b,$s=$s;$s+=iex "$b$_$a"}};$s
    }
}

The code golf version uses a powershell array rather than a stack, and uses a switch as a loop. There you have it, both of these functions will output the results of postfix operations.

#
#  > Eval-Postfix "1 2 + 5 6 * +"
#     33
#

bookmark_borderC# Bit Buffer Performance

There have been a few cases recently where I have needed to keep track of an array of bits. Basically as a record to mark off when sections of something have completed. The simplest scenario is for something like a torrent file transfer. Let’s say the file is made up of 100 chunks, which we can keep track of each completed chunk which was written by marking it in our bit buffer.

For example, our buffer “00000000”. When the third item completes we can say “00100000”, and so on. The simplest way to do this in C# would be to make an array of Booleans. This seemed like a total waste of memory to me, since Booleans in c# take up much more space than a single bit.

public class ByteBitBuffer
{
    /// <summary>
    /// The binary buffer.
    /// </summary>
    private readonly byte[] bytes;

    /// <summary>
    /// Initializes a new instance of the <see cref="ByteBitBuffer"/> class.
    /// </summary>
    /// <param name="length">The length of the buffer.</param>
    public ByteBitBuffer(int length)
    {
        var len = length / 8;
        if(length % 8 != 0)
        {
            len++;
        }

        this.bytes = new byte[len];
    }

    /// <summary>
    /// Sets the value at an index.
    /// </summary>
    /// <param name="index">The index.</param>
    /// <param name="value">The value.</param>
    public void Set(int index, bool value)
    {
        byte mask = (byte)(1 << (index % 8));
        if(value)
        {
            this.bytes[index / 8] |= mask;
        }
        else
        {
            this.bytes[index / 8] &amp;= (byte)~mask;
        }
    }

    /// <summary>
    /// Gets the value at an index.
    /// </summary>
    /// <param name="index">The index.</param>
    /// <returns>The value.</returns>
    public bool Get(int index)
    {
        return ((this.bytes[index / 8] >> (index % 8)) &amp; 1) != 0; 
    }
}

This is what I ended up with. From a programmers perspective, this is great. I got to do everything that I love: bit manipulation and cramming as much data into as little space as possible. The real question is, how fast is this compared to the basic Boolean[] implementation.

The Boolean implementation is much simpler of course.

public class BitBufferBools
{
    /// <summary>
    /// The boolean array.
    /// </summary>
    private readonly bool[] bools;

    /// <summary>
    /// Initializes a new instance of the <see cref="BitBufferBools"/> class.
    /// </summary>
    /// <param name="length">The length of the buffer.</param>
    public BitBufferBools(int length)
    {
        this.bools = new bool[length];
    }

    /// <summary>
    /// Sets the value at the index.
    /// </summary>
    /// <param name="index">The index.</param>
    /// <param name="value">The value.</param>
    public void Set(int index, bool value)
    {
        this.bools[index] = value;
    }

    /// <summary>
    /// Gets the value at the index.
    /// </summary>
    /// <param name="index">The index.</param>
    /// <returns>The value.</returns>
    public bool Get(int index)
    {
        return this.bools[index];
    }
}

C# also provides a class by default which can do the same thing as the two previous implementations named “System.Collections.BitArray”.

My test harness for the code:

static void Main(string[] args)
{
    // Run each method once to make sure they are all compiled
    Program.TestBitArray(1, 100);
    Program.TestBooleanArray(1, 100);
    Program.TestByteArray(1, 100);
    Program.TestIntArray(1, 100);
    Program.TestLongArray(1, 100);

    // Get the test values
    Console.Write("Iterations? ");
    var iterations = int.Parse(Console.ReadLine());
    Console.Write("Length? ");
    var length = int.Parse(Console.ReadLine());

    Console.WriteLine($"Performing tests with {iterations} iterations and length {length}.");

    // Test the boolean array
    Program.TestHarness("An array of bools", iterations, length, Program.TestBooleanArray);

    // Test System.Collection.BitArray
    Program.TestHarness("System.Collections.BitArray", iterations, length, Program.TestBitArray);

    // Test custom binary implementations
    Program.TestHarness("byte[]", iterations, length, Program.TestByteArray);
    Program.TestHarness("uint[]", iterations, length, Program.TestIntArray);
    Program.TestHarness("ulong[]", iterations, length, Program.TestLongArray);

    Console.ReadLine();
}

/// <summary>
/// The test harness.
/// </summary>
/// <param name="testName">The name of the test.</param>
/// <param name="iterations">The number of iterations.</param>
/// <param name="length">The length of the bit array.</param>
/// <param name="testAction">The test action.</param>
private static void TestHarness(string testName, int iterations, int length, Action<int, int> testAction)
{
    var watch = Stopwatch.StartNew();

    testAction(iterations, length);

    watch.Stop();
    Console.WriteLine($"Finished test: {testName} -> {watch.ElapsedMilliseconds}ms");
}

/// <summary>
/// Under the hood, just an array of bools.
/// </summary>
private static void TestBooleanArray(int iterations, int length)
{
    var bools = new BitBufferBools(length);

    for(var i = 0; i < iterations; i++)
    {
        for (var l = 0; l < length; l++)
        {
            bools.Set(l, !bools.Get(length - l - 1));
        }
    }
}

/// <summary>
/// Under the hood, a System.Collections.BitArray
/// </summary>
private static void TestBitArray(int iterations, int length)
{
    var bits = new BitArray(length);

    for (var i = 0; i < iterations; i++)
    {
        for (var l = 0; l < length; l++)
        {
            bits.Set(l, !bits.Get(length - l - 1));
        }
    }
}

/// <summary>
/// Under the hood, a byte[]
/// </summary>
private static void TestByteArray(int iterations, int length)
{
    var bits = new ByteBitBuffer(length);

    for (var i = 0; i < iterations; i++)
    {
        for (var l = 0; l < length; l++)
        {
            bits.Set(l, !bits.Get(length - l - 1));
        }
    }
}

/// <summary>
/// Under the hood, a uint[]
/// </summary>
private static void TestIntArray(int iterations, int length)
{
    var bits = new IntBitBuffer(length);

    for (var i = 0; i < iterations; i++)
    {
        for (var l = 0; l < length; l++)
        {
            bits.Set(l, !bits.Get(length - l - 1));
        }
    }
}

/// <summary>
/// Under the hood, a ulong[]
/// </summary>
private static void TestLongArray(int iterations, int length)
{
    var bits = new LongBitBuffer(length);

    for (var i = 0; i < iterations; i++)
    {
        for (var l = 0; l < length; l++)
        {
            bits.Set(l, !bits.Get(length - l - 1));
        }
    }
}

Here are the results, needless to say I was a little disappointed. But as it turns out, all of the bit manipulations are pretty expensive. So what you do save in space, you lose dearly in performance.

// Iterations? 1000
// Length? 1000000
// Performing tests with 1000 iterations and length 1000000.
// Finished test: An array of bools -> 1255ms
// Finished test: System.Collections.BitArray -> 8127ms
// Finished test: byte[] -> 6462ms
// Finished test: uint[] -> 5609ms
// Finished test: ulong[] -> 5531ms

Since I was a little annoyed, I thought I would try one more thing. Maybe I could improve performance significantly by allocating my custom collections directly onto the stack.

private static unsafe void TestStackAllocInts(int iterations, int length)
{
    var len = length / 32;
    if (length % 32 != 0)
    {
        len++;
    }

    uint * bits = stackalloc uint[len];

    for (var i = 0; i < iterations; i++)
    {
        for (var l = 0; l < length; l++)
        {
            PointerBitBuffer.Set(bits, l, !PointerBitBuffer.Get(bits, length - l - 1));
        }
    }
}

public static unsafe class PointerBitBuffer
{
    public static void Set(uint * self, int index, bool value)
    {
        var mask = 1U << (index % 32);
        if (value)
        {
            self[index / 32] |= mask;
        }
        else
        {
            self[index / 32] &amp;= ~mask;
        }
    }

    public static bool Get(uint* self, int index)
    {
        return ((self[index / 32] >> (index % 32)) &amp; 1) != 0;
    }
}

This did improve performance a little. But sadly, allocating the Boolean[] directly onto the stack is an even larger performance increase.

private static unsafe void TestStackAllocBools(int iterations, int length)
{
    bool* bits = stackalloc bool[length];

    for (var i = 0; i < iterations; i++)
    {
        for (var l = 0; l < length; l++)
        {
            bits[i] = !bits[length - l - 1];
        }
    }
}

So here are the final results:

// Iterations? 1000
// Length? 1000000
// Performing tests with 1000 iterations and length 1000000.
// Finished test: An array of bools -> 1255ms
// Finished test: System.Collections.BitArray -> 8127ms
// Finished test: byte[] -> 6462ms
// Finished test: uint[] -> 5609ms
// Finished test: ulong[] -> 5531ms
// Finished test: stackalloc uint[] -> 4102ms
// Finished test: stackalloc ulong[] -> 5106ms
// Finished test: stackalloc bool[] -> 723ms

The moral of the story is, C# is incredibly fast with basic arrays. So if space is no constraint, just use a basic Boolean array to store a bit buffer, unless you actually need the ability to write it directly to binary.

bookmark_borderReflection Emit Hello World

C# has a pretty neat namespace named “System.Reflection.Emit”, which allows you to build assemblies at runtime using Intermediate Language. This is a basic example of how to create an assembly, define a global function, and execute that function.

The following is an example. It is designed to be easy to follow, but here is a quick overview. The first thing we do is define a dynamic assembly. Within that assembly, we define a module. The whole assembly vs. module thing can be a little confusing. An assembly contains the manifest, and a collection of modules. Now in practice, an assembly usually only has a single module defined inside of it. Any C# project you create will also follow this 1 to 1 relationship. The module contains all of the actual code. Within the module, we define a global function (unsupported by C#, but IL is cool with it). Using the IL generator on the function, we can load a string onto the evaluation stack (“hello world”), call a function (Console.WriteLine), and then return from our function.

namespace ReflectionEmitHelloWorld
{
    using System;
    using System.Reflection;
    using System.Reflection.Emit;

    class Program
    {
        static void Main(string[] args)
        {
            // Define the assembly and module
            const string AssemblyName = "Badflyer.HelloWorld.dll";
            var assembly = AssemblyBuilder.DefineDynamicAssembly(new AssemblyName(AssemblyName), AssemblyBuilderAccess.RunAndCollect);
            var module = assembly.DefineDynamicModule(AssemblyName);

            // Define the method and get the Intermediate Language generator.
            var methodBuilder = module.DefineGlobalMethod("HelloWorld", MethodAttributes.Final | MethodAttributes.Public | MethodAttributes.Static, typeof(void), new Type[0]);
            var ilGenerator = methodBuilder.GetILGenerator();

            //// Too easy - but this works too
            // ilGenerator.EmitWriteLine("Hello World");

            // Get the method info for writeline
            var writeline = typeof(Console).GetMethod("WriteLine", BindingFlags.Public | BindingFlags.Static, Type.DefaultBinder, new[] { typeof(string) }, null);

            // Load the string onto the evaluation stack
            ilGenerator.Emit(OpCodes.Ldstr, "Hello World");

            // Call writeline
            ilGenerator.EmitCall(OpCodes.Call, writeline, new[] { typeof(string) });

            // Return
            ilGenerator.Emit(OpCodes.Ret);

            // Create the global functions (since that is what we defined)
            module.CreateGlobalFunctions();

            // Get our new method info
            var helloWorld = module.GetMethod("HelloWorld");
            // Invoke our new method.

            helloWorld.Invoke(null, null);

            // Wait for input
            Console.ReadLine();
        }
    }
}

Pretty cool! You can do things in IL which you cannot do from C# directly. Here for example we defined a global function which is not the member of any class. Following is the resulting IL which was generated from saving our generated .dll. Just a warning, dotnet core does not allow you to save the generated .dll. The regular .NET framework does.

// To Save: var assembly = AssemblyBuilder.DefineDynamicAssembly(new AssemblyName(AssemblyName), AssemblyBuilderAccess.RunAndSave);
// To Save: assembly.Save(AssemblyName);
.method public final static 
 void HelloWorld () cil managed 
{
 // Method begins at RVA 0x2050
 // Code size 11 (0xb)
 .maxstack 1
 IL_0000: ldstr "Hello World"
 IL_0005: call void [mscorlib]System.Console::WriteLine(string)
 IL_000a: ret
}

And that’s all there is to it! You can do a lot of learning by writing C# code snippets, and viewing the generated IL within the .dll with a tool. (For example ILSpy).

bookmark_borderTSQL Fizz Buzz

Here’s another journey through the world of simple programming problems… FizzBuzz, T-SQL edition. So just like the rest of the Fizz Buzz solutions. The idea is simple, for every number 1-100, if it’s divisible by 3 print ‘fizz’, if it’s divisible by 5 print ‘buzz’, if both print ‘fizzbuzz’, otherwise print the number. So here is a basic SQL solution:

WITH ctCounter AS
(
	SELECT 1 AS Number

	UNION ALL

	SELECT Number + 1 AS Number
	FROM ctCounter
	WHERE Number < 100
)
SELECT ISNULL(NULLIF(CONCAT(fizz.f, buzz.b), ''), c.Number) FROM ctCounter c
LEFT JOIN (VALUES('fizz')) fizz(f)
  ON c.Number % 3 = 0
LEFT JOIN (VALUES('buzz')) buzz(b)
  ON c.Number % 5 = 0

This is a common table expression, which generates a row for each number between 1 and 100. Then joins with the values ‘fizz’ and ‘buzz’. After that, it concatenates the fizz and buzz together, and if it still results in an empty string, selects the original number. The NULLIF function is useful for that, because it is basically the inverse of ISNULL. If the first parameter matches the second parameter, it returns null, otherwise returns the first parameter.

bookmark_borderPascals Triangle in SQL

Looking around online, I could not find a great example of how to draw Pascal’s Triangle in SQL. The solution is quite cool in SQL, because management studio prints out a nice grid for you. Here are three examples. The first one is simple and well documented, the second one is a little more squished, and the third one is a complete dumpster fire that I got too by looking up how to code golf in SQL.

CREATE PROCEDURE PascalsTriangle
    @Levels INT
AS
BEGIN
    SET NOCOUNT ON

    -- Declare variables
    DECLARE @counter        INT = 2
    DECLARE @innerCount     INT
    DECLARE @tmp            DECIMAL(38,0)
    DECLARE @tmp2           DECIMAL(38,0)
    DECLARE @dquery         NVARCHAR(2048)

    -- Create the results table with its one column
    CREATE TABLE #result
    (
        [1] DECIMAL(38,0)
    )
    INSERT INTO #result VALUES (1)

    -- For every level beyond 1
    WHILE(@counter <= @Levels)
    BEGIN
        
        -- Add another column to to the table
        EXEC('ALTER TABLE #result ADD [' + @counter + '] DECIMAL(38,0)')

        -- Select the previous row into a temp table
        SELECT *
        INTO #row
        FROM #result
        ORDER BY 1
        OFFSET (@counter - 2) ROWS
        FETCH NEXT 1 ROWS ONLY

        -- Re-initialize the temp variables, and loop counter
        SET @tmp = 1
        SET @tmp2 = 1
        SET @innerCount = 2

        -- For every column beyond 1
        WHILE(@innerCount <= @counter)
        BEGIN

            -- Create a query which selects the current value of the cell to back it up.
            SET @dquery = 'SELECT @t = [' + CAST(@innerCount AS NVARCHAR(10)) + '] FROM #row'
            EXEC sp_executesql @dquery, N'@t DECIMAL(38,0) OUTPUT', @t = @tmp2 OUTPUT

            -- Set the value of this cell in this row to that + @tmp
            EXEC('UPDATE #row SET [' + @innerCount + '] = ISNULL([' + @innerCount + '], 0) + ' + @tmp)

            -- Reset the temp variable
            SET @tmp = @tmp2

            -- Increment the count
            SET @innerCount += 1

        END

        -- Insert the row into result
        INSERT INTO #result
        SELECT * FROM #row

        -- Increment the counter
        SET @counter += 1

        -- Drop the row temp table
        DROP TABLE #row
    END

    -- Output the result
    SELECT * FROM #result
    DROP TABLE #result
END

There is another post in PowerShell which does a much better job actually explaining details about how this triangle works. But long story short, every item is the sum of the two above it added together. So now let’s make the script a little smaller.

CREATE PROCEDURE PascalsTriangle2
	@Levels INT
AS
BEGIN
	SET NOCOUNT ON
	DECLARE @o INT=2
	DECLARE @ INT
	DECLARE @1 DECIMAL(38,0)
	DECLARE @2 DECIMAL(38,0)
	DECLARE @q NVARCHAR(2048)
	CREATE TABLE #o([1] DECIMAL(38,0))
	INSERT #o VALUES(1)
	o:
 		EXEC('ALTER TABLE #o ADD['+@o+']DECIMAL(38,0)')
 		SELECT *INTO #r FROM #o ORDER BY 1 OFFSET(@o-2)ROWS	FETCH NEXT 1 ROWS ONLY
 		SET @1 = 1
 		SET @2 = 1
 		SET @ = 2
 		i:
			SET @q = CONCAT('DECLARE @ TABLE (val DECIMAL(38,0));UPDATE #r SET [',@,']=ISNULL([',@,'], 0)+',@1,'OUTPUT deleted.[',@,']INTO @;SET @t=(SELECT *FROM @)')
			EXEC sp_executesql @q,N'@t DECIMAL(38,0) OUTPUT',@t=@2 OUTPUT  			
  			SET @1 = @2
  			SET @ += 1
 		IF @ <= @o GOTO i
 		INSERT #o
 		SELECT * FROM #r
 		SET @o += 1
 		DROP TABLE #r
	IF @o <= @Levels GOTO o
	SELECT * FROM #o
	DROP TABLE #o
END

As you can see, I removed all the pesky comments which were just getting in the way of looking small. Also, the while loops were all turned into GOTO loops to take up a little less space. The variable names were shortened a little as well.

DECLARE @s NVARCHAR(MAX)='CREATE PROCEDURE PascalsTriangle3
@Levels INT
AS
BEGIN
	SET NOCOUNT ON
	~o |=2~ |~1 &amp;~2 &amp;~q NVARCHAR(2048)CREATE TABLE #o([1] &amp;)INSERT #o VALUES(1)
	o:EXEC(''ALTER TABLE #o ADD[''+@o+'']&amp;'')$|O #r ^#o ORDER BY 1 OFFSET(@o-2)ROWS	FETCH NEXT 1 ROWS ONLY!1 = 1!2 = 1! = 2
 		i:!q = CONCAT(''~ TABLE (val &amp;);UPDATE #r SET ['',@,'']=ISNULL(['',@,''], 0)+'',@1,''OUTPUT deleted.['',@,'']|O @;!t=($^@)'')EXEC sp_executesql @q,N''@t &amp; OUTPUT'',@t=@2 OUTPUT!1 = @2!+=1IF @ <= @o GOTO i
 		INSERT #o$ ^#r!o += 1%#r IF @o <= @Levels goto o$ ^#o%#o
END'
SELECT @s=REPLACE(@s,LEFT(i,1),SUBSTRING(i,2,20))
FROM(VALUES('~ DECLARE @'),('! SET @'),('&amp; DECIMAL(38,0)'),('% DROP TABLE '),('$ SELECT *'),('^ FROM '),('| INT'))a(i)
EXEC(@s)

Now there’s the real beast. It does a bunch of replacements on a string, to make some longer valid SQL, then executes the SQL dynamically to produce the stored procedure. That’s some production quality code.

bookmark_borderPascals Triangle In SQL

Looking around online, I could not find a great example of how to draw Pascal’s Triangle in SQL. The solution is quite cool in SQL, because management studio prints out a nice grid for you. Here are three examples. The first one is simple and well documented, the second one is a little more squished, and the third one is a complete dumpster fire that I got too by looking up how to code golf in SQL.



CREATE PROCEDURE PascalsTriangle
    @Levels INT
AS
BEGIN
    SET NOCOUNT ON

    -- Declare variables
    DECLARE @counter        INT = 2
    DECLARE @innerCount     INT
    DECLARE @tmp            DECIMAL(38,0)
    DECLARE @tmp2           DECIMAL(38,0)
    DECLARE @dquery         NVARCHAR(2048)

    -- Create the results table with its one column
    CREATE TABLE #result
    (
        [1] DECIMAL(38,0)
    )
    INSERT INTO #result VALUES (1)

    -- For every level beyond 1
    WHILE(@counter <= @Levels)
    BEGIN
        
        -- Add another column to to the table
        EXEC('ALTER TABLE #result ADD [' + @counter + '] DECIMAL(38,0)')

        -- Select the previous row into a temp table
        SELECT *
        INTO #row
        FROM #result
        ORDER BY 1
        OFFSET (@counter - 2) ROWS
        FETCH NEXT 1 ROWS ONLY

        -- Re-initialize the temp variables, and loop counter
        SET @tmp = 1
        SET @tmp2 = 1
        SET @innerCount = 2

        -- For every column beyond 1
        WHILE(@innerCount <= @counter)
        BEGIN

            -- Create a query which selects the current value of the cell to back it up.
            SET @dquery = 'SELECT @t = [' + CAST(@innerCount AS NVARCHAR(10)) + '] FROM #row'
            EXEC sp_executesql @dquery, N'@t DECIMAL(38,0) OUTPUT', @t = @tmp2 OUTPUT

            -- Set the value of this cell in this row to that + @tmp
            EXEC('UPDATE #row SET [' + @innerCount + '] = ISNULL([' + @innerCount + '], 0) + ' + @tmp)

            -- Reset the temp variable
            SET @tmp = @tmp2

            -- Increment the count
            SET @innerCount += 1

        END

        -- Insert the row into result
        INSERT INTO #result
        SELECT * FROM #row

        -- Increment the counter
        SET @counter += 1

        -- Drop the row temp table
        DROP TABLE #row
    END

    -- Output the result
    SELECT * FROM #result
    DROP TABLE #result
END


There is another post in PowerShell which does a much better job actually explaining details about how this triangle works. But long story short, every item is the sum of the two above it added together. So now let’s make the script a little smaller.



CREATE PROCEDURE PascalsTriangle2
	@Levels INT
AS
BEGIN
	SET NOCOUNT ON
	DECLARE @o INT=2
	DECLARE @ INT
	DECLARE @1 DECIMAL(38,0)
	DECLARE @2 DECIMAL(38,0)
	DECLARE @q NVARCHAR(2048)
	CREATE TABLE #o([1] DECIMAL(38,0))
	INSERT #o VALUES(1)
	o:
 		EXEC('ALTER TABLE #o ADD['+@o+']DECIMAL(38,0)')
 		SELECT *INTO #r FROM #o ORDER BY 1 OFFSET(@o-2)ROWS	FETCH NEXT 1 ROWS ONLY
 		SET @1 = 1
 		SET @2 = 1
 		SET @ = 2
 		i:
			SET @q = CONCAT('DECLARE @ TABLE (val DECIMAL(38,0));UPDATE #r SET [',@,']=ISNULL([',@,'], 0)+',@1,'OUTPUT deleted.[',@,']INTO @;SET @t=(SELECT *FROM @)')
			EXEC sp_executesql @q,N'@t DECIMAL(38,0) OUTPUT',@t=@2 OUTPUT  			
  			SET @1 = @2
  			SET @ += 1
 		IF @ <= @o GOTO i
 		INSERT #o
 		SELECT * FROM #r
 		SET @o += 1
 		DROP TABLE #r
	IF @o <= @Levels GOTO o
	SELECT * FROM #o
	DROP TABLE #o
END

As you can see, I removed all the pesky comments which were just getting in the way of looking small. Also, the while loops were all turned into GOTO loops to take up a little less space. The variable names were shortened a little as well.

DECLARE @s NVARCHAR(MAX)='CREATE PROCEDURE PascalsTriangle3
@Levels INT
AS
BEGIN
	SET NOCOUNT ON
	~o |=2~ |~1 &amp;~2 &amp;~q NVARCHAR(2048)CREATE TABLE #o([1] &amp;)INSERT #o VALUES(1)
	o:EXEC(''ALTER TABLE #o ADD[''+@o+'']&amp;'')$|O #r ^#o ORDER BY 1 OFFSET(@o-2)ROWS	FETCH NEXT 1 ROWS ONLY!1 = 1!2 = 1! = 2
 		i:!q = CONCAT(''~ TABLE (val &amp;);UPDATE #r SET ['',@,'']=ISNULL(['',@,''], 0)+'',@1,''OUTPUT deleted.['',@,'']|O @;!t=($^@)'')EXEC sp_executesql @q,N''@t &amp; OUTPUT'',@t=@2 OUTPUT!1 = @2!+=1IF @ <= @o GOTO i
 		INSERT #o$ ^#r!o += 1%#r IF @o <= @Levels goto o$ ^#o%#o
END'
SELECT @s=REPLACE(@s,LEFT(i,1),SUBSTRING(i,2,20))
FROM(VALUES('~ DECLARE @'),('! SET @'),('&amp; DECIMAL(38,0)'),('% DROP TABLE '),('$ SELECT *'),('^ FROM '),('| INT'))a(i)
EXEC(@s)

Now there’s the real beast. It does a bunch of replacements on a string, to make some longer valid SQL, then executes the SQL dynamically to produce the stored procedure. That’s some production quality code.

bookmark_borderPascals Triangle In Powershell

A programming question that I’m sure everyone has been asked at some point during the interview is ‘Pascal’s Triangle’. Besides solving it, nothing would impress your interviewer more than solving it in PowerShell, with support for massively huge numbers. Wikipedia could probably explain this better than I can, but the premise is simple: start with ‘1’, then each row is one element longer than the previous and is made up of the to values above it added together (Except for the values on either end, which are always 1).

function Pascals-Triangle
{
    [CmdLetBinding()]
    param
    (
        # Single parameter is the number of levels
        [Parameter(Mandatory=$true)][ValidateRange(1, [int]::MaxValue)][int]$Levels
    )
    process
    {
        # Create a dummy previous array, just so that we know what is going on.
        $prev = [System.Numerics.BigInteger[]]::new(0)

        # Now for each level
        for($l = 0; $l -lt $Levels; $l++)
        {
            # Create the current working array
            $current = [System.Numerics.BigInteger[]]::new($prev.Length + 1)
            
            # We know for sure that the first and the last element are 1 (This avoids bounds checking in the loop below)
            $current[0] = 1
            $current[$current.Length - 1] = 1

            # Now for all other elements add the previous two together
            for($i = 1; $i -lt $current.Length - 1; $i++)
            {
                $current[$i] = $prev[$i - 1] + $prev[$i]
            }

            # Write out our result
            Write-Output ([string]::Join(' ', $current))

            # Set the previous to the current for the next iteration
            $prev = $current
        }

    }
}

This is most likely the solution that any interviewer would be expecting, because it is by far the simplest to follow. The idea is simple, start with an array of zero length and for every level of the triangle allocate an array which is 1 element longer, and populate it by adding together elements from the previous array. I’m not sure why, but whenever I got this question in college I wanted to do it recursively, which totally screwed me. Also, the reason behind using ‘BigInteger’, is that these number expand very rapidly. Try it out with ‘int’ or even ‘ulong’, and you wont be able to do too many levels. Anyway, the results in powershell end up looking like this.

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1

So now, to mix things up, lets do it in a way that doesn’t require us to keep reallocating arrays. This next solution does the whole thing in place, reusing the same array each time. This is not a big deal, because we always know how long the array needs to be when we start. (Length = Levels). We can just go through and add up the values of the previous row each time.

function Pascals-Triangle2
{
    [CmdLetBinding()]
    param
    (
        # Single parameter is the number of levels
        [Parameter(Mandatory=$true)][ValidateRange(1, [int]::MaxValue)][int]$Levels
    )
    process
    {
        # Create our working array
        $row = [System.Numerics.BigInteger[]]::new($Levels)

        # Now for each level
        for($l = 1; $l -le $Levels; $l++)
        {
            # The first index is always 1, and set our previous
            $iPrevious = $row[0] = 1
            for($i = 1; $i -lt $l; $i++)
            {
                # Back up the current value
                $temp = $row[$i]

                # Add in the previous value
                $row[$i] += $iPrevious

                # Swap out the previous
                $iPrevious = $temp
            }

            # Write out our result
            Write-Output ([string]::Join(' ', ($row | select -First $l)))
        }

    }
}
        

And there we have it. So what about a more obfuscated version for those really hard core interviewees? Lets do it. Taking solution 2 and squishing everything together as much as possible we get a horribly confusing solution.

function Pascals-Triangle3
{
    [CmdLetBinding()]
    param
    (
        # Single parameter is the number of levels
        [Parameter(Mandatory=$true)][ValidateRange(1, [int]::MaxValue)][int]$Levels
    )
    process
    {
        ($r=[System.Numerics.BigInteger[]]::new(($l=$Levels)+1))[0]=1
        1..$l|%{"$($r|?{$_-ne0})";$t=1;1..$_|%{$a=$r[$_];$r[$_]+=$t;$t=$a}}
    }
}

I’m sure everyone is better at code golf than I am, but this solution already confuses me so it should be a good start.

bookmark_borderPowershell IPv4 to IPv6 and Expand IPv6

Here is the easy answer using built in .NET functions:

#
# Converts an IPV4 address to an IPV6 address.
#
function Map-IPv4ToIPv6
{
    [CmdletBinding()]
    param
    (
        [Parameter(Mandatory = $true, 
                   Position = 0,
                   ValueFromPipeline=$true,
                   ValueFromPipelineByPropertyName=$true)][String]$IPv4
    )
    process
    {
        [ipaddress]$parsedAddress = $null;
        if (-not [ipaddress]::TryParse($IPv4, [ref]$parsedAddress))
        {
            throw "Could not parse IPV4 address $IPv4"
        }

        # Already done
        if ($parsedAddress.AddressFamily -eq [System.Net.Sockets.AddressFamily]::InterNetworkV6)
        {
            return $parsedAddress;
        }
        elseif ($parsedAddress.AddressFamily -eq [System.Net.Sockets.AddressFamily]::InterNetwork)
        {
            return $parsedAddress.MapToIPv6();
        }
    }
}

#
# Converts an IPV6 address to an IPV4 address.
#
function Map-IPv6ToIPv4
{
    [CmdletBinding()]
    param
    (
        [Parameter(Mandatory = $true, 
                   Position = 0,
                   ValueFromPipeline=$true,
                   ValueFromPipelineByPropertyName=$true)][String]$IPv6
    )
    process
    {
        [ipaddress]$parsedAddress = $null;
        if (-not [ipaddress]::TryParse($IPv6, [ref]$parsedAddress))
        {
            throw "Could not parse IPv6 address $IPv6"
        }

        # Already done
        if ($parsedAddress.AddressFamily -eq [System.Net.Sockets.AddressFamily]::InterNetwork)
        {
            return $parsedAddress;
        }
        elseif ($parsedAddress.AddressFamily -eq [System.Net.Sockets.AddressFamily]::InterNetworkV6)
        {
            return $parsedAddress.MapToIPv4();
        }
    }
}

For a more detailed, and “manual” approach, you can keep reading.

IPv4 is simple, 32 bits of easy to understand goodness. Every single IPv4 address is made up of 4 bytes. For example “192.168.1.1”. There is no shorthand either, that is the address, that’s it. There is no better way to write it. Ok, so now that that is out of the picture, what is IPv6.

IPv6 is 128 bits of a little bit more confusing. Well actually, it’s not the address that is confusing, it’s the notation. When you see IPv6, a lot of times you see things like “::1” and “FE80::1”. What does that even mean. How is that 128 bits. How will we ever know. So the secret is in the “::”, which is pretty much just shorthand for “a lot of zeros go here”.

For example: if we take the address “::1”, it actually expands out to “0000:0000:0000:0000:0000:0000:0000:0001”. Literally just means fill in this space with zeros. Another example: “FE80::1” becomes “FE80:0000:0000:0000:0000:0000:0000:0001”. Just FYI, you are only allowed to use the “::” once, otherwise addresses would be unreadable. (“::1::”) So before anything, here is a function to automate that, because it drives me nuts.

#
# Expand an IPv6 address. For example ::1 becomes 0000:0000:0000:0000:0000:0000:0000:0001
#
function Expand-IPV6
{
    [CmdletBinding()]
    param
    (
        [Parameter(Mandatory = $true, 
                   Position = 0,
                   ValueFromPipeline=$true,
                   ValueFromPipelineByPropertyName=$true)][String]$IPv6
    )
    process
    {
        $count = 0
        $loc = -1

        # Count the number of colons, and keep track of the double colon
        for($i = 0; $i -lt $IPv6.Length; $i++) 
        { 
            if($IPv6[$i] -eq ':') 
            {
                $count++
                if(($i - 1) -ge 0 -and $IPv6[$i-1] -eq ':')
                {
                    $loc = $i
                }
            }
        }

        # If we didnt find a double colon and the count isn't 7, then throw an exception
        if($loc -lt 0 -and $count -ne 7)
        {
            throw "Invalid IPv6 Address"
        }

        # Add in any missing colons if we had a double
        $cleaned = $IPv6
        if($count -lt 7)
        {
            $cleaned = $IPv6.Substring(0, $loc) + (':'*(7-$count)) + $IPv6.Substring($loc)
        }

        # Parse current values in fill in new IP with hex numbers padded to 4 digits
        $result = @()
        foreach($splt in $cleaned -split ':')
        {
            $val = 0
            $r = [int]::TryParse($splt, [System.Globalization.NumberStyles]::HexNumber, [System.Globalization.CultureInfo]::InvariantCulture, [ref]$val)
            $result += ('{0:X4}' -f $val)
        }

        return $result -join ':'
    }
}

So this does the expansions work for us, because it’s a pain in the butt to deal with these addresses in their short form. Also, I know the code is gross and I apologize for that, but there is more to come. Ok, so now, what happens if we have an IPv4 address and we need to turn it into IPv6. Boom, its easy. The last 32 bits of the IPv6 address are equal to our IPv4 address, and the 16 bits preceding those are all set to 1. Easy enough! That means, the IP address 1.1.1.1 would turn into “::FFFF:0101:0101” or “0000:0000:0000:0000:0000:FFFF:0101:0101” in full form. So how do we make that happen?

# Map an IPv4 address to IPv6
function Map-IPv4ToIPv6
{
    [CmdletBinding()]
    param
    (
        [Parameter(Mandatory = $true, 
            Position = 0,
            ValueFromPipeline=$true,
            ValueFromPipelineByPropertyName=$true)][String]$IPv4
    )
    process
    {
        # Split on the dots
        $split = $IPv4 -split '\.'
        if($split.Length -ne 4)
        {
            throw 'Not a valid IPv4 Address'
        }

        # Parse into numbers
        $vals = @()
        foreach($v in $split)
        {
            $vals += [int]::Parse($v)
        }

        # Return as shorthand ipv6
        return "::FFFF:{0:X2}{1:X2}:{2:X2}{3:X2}" -f $vals
    }
}

BOOM, mission accomplished. Hopefully (it worked in a few tests). Also, for completeness, here is a function which turns an IPv4 address which is represented in IPv6 back into an IPv4 address.

#
# Transforms an IPv4 address which is represented in IPv6 back into IPv4
#
function Map-IPv6ToIPv4
{
    [CmdletBinding()]
    param
    (
        [Parameter(Mandatory = $true, 
            Position = 0,
            ValueFromPipeline=$true,
            ValueFromPipelineByPropertyName=$true)][String]$IPv6
    )
    process
    {
        # Get the expanded form
        $expanded = Expand-IPV6 $IPv6
        $split = $expanded.Split(':')

        # Make sure this is valid...
        $is4MappedTo6 = $split[5] -match 'FFFF'
        if(-not $is4MappedTo6)
        {
            throw 'This is not an IPv4 Address mapped to IPv6'
        }

        # Parse each byte as an integer
        $addr = @()
        for($i = 0; $i -lt 8; $i+=2)
        {
            $addr += [int]::Parse(($split[6 + [math]::Floor(($i / 4))][($i % 4)..(($i%4)+1)] -join ''), [System.Globalization.NumberStyles]::HexNumber)
        }

        return $addr -join '.'
    }
}

The classes built in to handle IP addresses are definitely much smarter, and the way to go, but hopefully this has explained an easy way to do it.

bookmark_borderPowershell Sha1 Implementation

This is an implementation of the SHA1 cryptographic hash algorithm in Powershell. It was a little harder than it seems, since Powershell naturally assumes all numbers are signed. Lets take for example: 0xFFFFFFFF (the maximum 32 bit unsigned int), which one would assume is equal to 4294967295. Well.. Check out this simple line of code.

#This wont throw an exception right?
[uint32]0xFFFFFFFF

Well, in PowerShell this just throws an exception. Why!? Because under the hood, PowerShell thinks: “0xFFFFFFFF”, that’s 32 bits. Let me stick it in a 32 bit signed integer. But wait… “0xFFFFFFFF” is just 32 1s. So in 2s complement, that’s -1. So in PowerShell 0xFFFFFFFF == -1. So now its pretty clear why the above code throws an exception, there is no unsigned value to represent -1. For an example, just go type “0xFFFFFFFF” into PowerShell. So.. because of that, everything here has to be done in a 64 bit integer.

#
# Implemenation of SHA1
#
function SHA1
{
    [CmdLetBinding()]
    param
    (
        [Parameter(Mandatory = $false, Position=1)][string]$Str
    )
    process
    {
        #
        # Truncate a value to UInt32
        #
        function TUI
        {
            param($val)
            process
            {
                [uint64]($val -band (((-bnot [uint64]0)) -shr 32))
            }
        }

        #
        # Get a 32 bit value from a byte array
        #
        function GetBigEndianUInt
        {
            param
            (
                [byte[]]$bytes,
                [int]$index
            )
            process
            {
                return ([uint64]$bytes[$index] -shl 24) -bor ([uint64]$bytes[$index+1] -shl 16) -bor ([uint64]$bytes[$index+2] -shl 8) -bor ([uint64]$bytes[$index+3])
            }
        }

        #
        # Left rotate
        #
        function LeftRotate
        {
            param
            (
                [uint64]$val,
                [int]$amount
            )
            process
            {
                $res = TUI ([uint64]$val -shr (32 - $amount))
                $res = $res -bor ($val -shl $amount)
                return TUI $res
            }
        }

        # Initialize constants
        $h0 = TUI 0x67452301
        $h1 = TUI 0xEFCDAB89
        $h2 = TUI 0x98BADCFE
        $h3 = TUI 0x10325476
        $h4 = TUI 0xC3D2E1F0
        
        # Get the message bytes
        $message = [System.Text.ASCIIEncoding]::ASCII.GetBytes($Str)

        # Get the length in bytes which we need. Message length + 0x80 + (64bit message len)
        $len = ($message.Length + 9)
        
        # Get the padded length of our our byte array
        if($len % 64 -ne 0){
            $len += (64 - ($len % 64))
        }

        # Copy the bytes in the message to our byte array
        $bytes = ([byte[]]0 * $len)
        for($i = 0; $i -lt $message.Length; $i++){
            $bytes[$i] = [byte]$message[$i]
        }

        # Pad the message with 1000 0000
        $bytes[$i] = 128

        # The message length in bits
        $bitLen = $message.Length * 8

        # Set the last [uint64] as the messsage length. (We only do 32 bits)
        $bytes[$len-1] = [byte]($bitLen -band 0xFF)
        $bytes[$len-2] = [byte](($bitLen -shr 8) -band 0xFF)
        $bytes[$len-3] = [byte](($bitLen -shr 16) -band 0xFF)
        $bytes[$len-4] = [byte](($bitLen -shr 24) -band 0xFF)

        # Divide the message into 512 bit chunks
        for($chunk = 0; $chunk -lt $bytes.Length; $chunk += 64)
        {
            $w = ([uint64[]]0 * 80)

            # Copy the chunk into our working array as uints
            for($i = 0; $i -lt 16; $i++){
                $w[$i] = GetBigEndianUInt -bytes $bytes -index ($i*4 + $chunk)
            }

            for($i = 16; $i -lt 80; $i++){
                $w[$i] = LeftRotate -val (TUI ($w[$i-3] -bxor $w[$i-8] -bxor $w[$i-14] -bxor $w[$i-16])) -amount 1
            }

            $a = TUI $h0
            $b = TUI $h1
            $c = TUI $h2
            $d = TUI $h3
            $e = TUI $h4

            # A bunch of crazy stuff
            for($i = 0; $i -lt 80; $i++){
                $k=0
                if($i -lt 20){
                    $f = TUI (($b -band $c) -bor ((-bnot $b) -band $d))
                    $k = TUI 0x5A827999
                }
                elseif($i -lt 40){
                    $f = TUI ($b -bxor $c -bxor $d)
                    $k = TUI 0x6ED9EBA1
                }
                elseif($i -lt 60){
                    $f = TUI (($b -band $c) -bor ($b -band $d) -bor ($c -band $d))
                    $k = TUI 0x8F1BBCDC
                }
                else{
                    $f = TUI ($b -bxor $c -bxor $d)
                    $k = TUI 0xCA62C1D6
                }
            
                $temp = TUI ((LeftRotate -val $a -amount 5) + $f + $e + $k + $w[$i])

                $e = $d
                $d = $c
                $c = LeftRotate -val $b -amount 30
                $b = $a
                $a = $temp
            }

            $h0 = TUI ($h0 + $a)
            $h1 = TUI ($h1 + $b)
            $h2 = TUI ($h2 + $c)
            $h3 = TUI ($h3 + $d)
            $h4 = TUI ($h4 + $e)   
        }

        '{0:X8}{1:X8}{2:X8}{3:X8}{4:X8}' -f $h0, $h1, $h2, $h3, $h4
    }
}

There it is. I may have overused my TUI(To uint) function a little bit, since values larger than 32 bits could actually cause problems. I got most of the implementation details from the Wikipedia article on SHA1.