PowerShell Associative Arrays and Anagrams

Jon Bentley's Programming Pearls describes the following pipeline for finding anagrams from a list of words: generate a signature for the word, then group together all words with the same signature. The signature is just a sorted list of all letters in a word. For instance, dame, edam, made and mead all have the same signature adem.

Associative Arrays

To implement an anagram-finder in PowerShell, let's use an associative array and we store the signatures in the keys and each word that has the same signature is stored in an array related to that key. Below is a concrete example of what we plan to do:

> $a = @{adem:("dame","edam","made","mead")}
> $a
Name                           Value
----                           -----
adem                           {dame, edam, made, mead}

Notes

• The key for an associative array does not have to be quoted if it is a string without a whitespace.
• Oddly, arrays in the value column are printed delimited by braces instead of parentheses.

Generating Word Signatures

A word signature is just a string with the letters in the original word sorted. We split a string into a char[] type, sort it, then make it into a string again:

> $sig = [string]("edam".ToCharArray() | sort-object)
> $sig
a d e m
> $sig.length
7

Note that the signature sig is a string with a space between each character. We can prettify the signature but it doesn't hurt because all the signatures will have the same format.

Find Anagrams in a Word List

Now that we can create a signature, we can find all anagrams in a word list by assigning each word's signature as a key in the associative array's value and adding the word to that key's array:

> get-content <test.txt> | foreach-object { $h = @{} } { $t = $_.clone(); $sig = [string]($t.ToCharArray() | sort-object); if (!$h.containsKey($sig)) { $h[$sig] = @() } $h[$sig] += $t } { $h }

Name                           Value
----                           -----
adem                           {dame, edam, made, mead}

Let's decompose this longish statement to understand what it is doing:

get-content <test.txt> |

Send every line in the input file into a pipeline.

foreach-object

Apply some operation on each object in the pipeline.

{ $h = @{} }

Initialize the associative array h in the begin script block.

{ process block }

Here is where words with the same signature are grouped together in the associative array.

$t = $_.clone();

Copy the input word from the current pipeline object before it is overwritten in the next statement.

$sig = [string]($t.ToCharArray() | sort-object);

Get the signature of the input word.

if (!$h.containsKey($sig)) { $h[$sig] = @() }

Create an array of anagrams if the signature does not already exist.

$h[$sig] += $t

Add the current word to the array of anagrams.

{ $h }

Output the associative array h in the end script block.

Conclusion

This article presented an imperative approach to grouping data with the same property using a loop and an associative array. You could apply the same style to any programming language and get the same result. In a future article, I will explore how to use a more streamlined approach to solve similar problems.

Code Noise Ratio

Using Scott Hickey's article on reducing code noise in Groovy as a starting point, can we measure of the noisiness of a programming language and environment? Let's say that the quietest code where the developer has to add the least amount boilerplate code to implement a particular feature. Just to keep the metric simple, let's just measure the size of the source files for different implementations of the same feature and assume that the developer is trying to write sensible code. We assume that the shortest version is the quietest and calculate the ratio between the shortest version and all other versions.

Let's test this ratio on several versions of Hello World implemented using different scripting languages in previous articles. What is the noisiness of each implementation?

Version	Platform	Size	Ratio
Groovy + SwingBuilder	Java	240	0%
Jython	Java	253	5.42%
Groovy	Java	270	12.50%
IronPython	.Net	473	91.25%
PowerShell	.Net	579	141.25%

What does this table tell us about reducing code noise for small programs?

• Script environment should pre-import common classes. Groovy + SwingBuilder and plain Groovy makes it very easy to write a small GUI program because all the Java Swing references are pre-imported. The Jython and IronPython implementations are nearly the same but the IronPython version is longer because it has to load .Net references.
• Use class aliases. One reason the PowerShell version is very long is you can't add a class name into the current namespace (such as Python's from <library> import <class> or C# using namespace <blah>). You can define class aliases like this: $Form = [System.Windows.Forms.Form] but that only starts reducing noise when you use that class more than once.
• Define properties in constructors. Another reason the PowerShell version is long is that only the .Net constructors for GUI controls are available through the platform interface, so to define a control, you have to write a sequence of statements starting with creating a new object followed by some SetX() methods. I wonder if PowerShell adaptors can overload constructors?

Find Longest (or Shortest) Line in a File

Quick scripts to find the longest line in a file. To find the shortest line, just invert the appropriate test.

Gawk

gawk "{ if (length > max) { max = length; m = $0 } }  END { print m }" <file>

Gawk + Sort + Tail

gawk "{ printf("""%4.0f %s\n""", length,$0) }" <file> | sort | tail -1

In Windows Cmd, three double-quotes are required to escape a double-quote, and the %4.0f format control ensures that lines up to 9999 characters long are sorted correctly.

PowerShell

get-content <file> | sort-object -property length | select-object -last 1

WC

wc -L gives the length of the longest line, but not the line itself.

2008-04-20: Consolidated all samples into this article.

PowerShell String and Char[] Sort and Conversion

Introduction

I wanted to sort the characters in a string to use as a signature for that string. A string is basically an array of characters but System.String class does not have a Sort() method. Hmm, looks like we have to break the process into the following steps:

1. Convert a string to a character array.
2. Sort the character array.
3. Convert the character array back into a string.

First cut

A hitch: System.String can only be converted into a char[], so we have to use an external sorter such as Sort-Object cmdlet. If we could have made an Array of char, then we could have used the Array's Sort() method. The first cut looks like this:

> $s = "mad"
> $sig = sort-object -inputObject $s.ToCharArray()
> $sig
m
a
d

Eh? Why isn't sig sorted? Either Sort-Object or PowerShell doesn't do the expected when presented with an array using the -inputObject parameter. Let's test this:

> "m","a","d" | sort-object
a
d
m
> sort-object -inputObject "m","a","d"
m
a
d

Second Cut

Because of the strange behaviour found in the previous section, we call Sort-Object in a pipeline. In addition, we reconstruct the output into a string:

> $s = "mad"
> $sig = (string)($s.ToCharArray() | sort-object)
> $sig
a d m
> $sig.length
5

What's wrong now? Why does sig have a whitespace between each character? This was getting a bit deep into PowerShell for me at the moment, so let's use an appropriate constructor in System.String such as String(char[]).

21-Dec-2007: Solution is to change OFS (Output Field Separator) to an empty string, like this: $OFS = "".

Third Cut

We try the System.String(char[]) constructor and make the sorted array output into a string:

> $s = "mad"
> $sig = new-object String(($s.ToCharArray() | sort-object))
New-Object : Exception calling ".ctor" with "3" argument(s): "Index was out of range. Must be non-negative and less than the size of the collection.
Parameter name: startIndex"
At line:1 char:16
+ $t = new-object  <<<< String($s.ToCharArray())

What gives? The error indicates that a different constructor, String(char[], startIndex, length) should be used. It's not clear why the first constructor is not available.

Fourth Cut

Finally, taking into account all that we learnt above, we end up with the following statement which gives us the result we wanted:

> $s = "mad"
> $sig = new-object String(($s.ToCharArray() | sort-object), 0, $s.length)
> $sig
adm

Conclusion

The resulting statement to sort characters in a string is mostly noise because the purpose of the statement statement is obscured by the need to convert an object from one type to another. In an earlier article about palindromes, another way to make a string from an character array is to use the static method [string]::Join(). That is …

> $sig = [string]::Join("", ($s.ToCharArray() | sort-object))

The second method is shorter but still rather obscure because it relies on the side-effect of the empty string argument when calling the Join() method. It's a rather disappointing end to this exercise because I spent most of the time fighting instead of using PowerShell.

19-Dec-2007. PowerShell 2.0 will have a new Join operator that should make this exercise moot.

21-Dec-2007. Fourth method is to change OFS first, leading to:

> $OFS = ""
> $s = "mad"
$gt; $sig = [string]($s.ToCharArray() | sort-object)
> $sig
adm
> $sig.length
3