Huddled Masses
Posts Tagged ‘Programming’
September 16th, 2008 | 
Author: There’s fun stuff happening lately, so here’s a post full of tidbits you may have missed. Like:
Codeplex has announced Subversion support. They will be running a server-side SvnBridge to allow access to all the projects so you can grab source more easily because it supports anonymous access. Amusingly, it’s actually easier to use than TFS, all you need to know is the project name to get in. E.g.: https://PoshConsole.svn.codeplex.com/svn
Clarius has just released of their T4 template editor for Visual Studio. There’s a free version, and a pro ($99) version. It’s excellent, and if you haven’t gotten into generating code using t4, what are you waiting for?
StackOverflow The new programming question-and-answer forum from CodingHorror Jeff Atwood and Joel Spolsky has launched.
Dave Glover wrote a cool post about how simple it is to create a bootable USB install disc for Vista and Miguel de Icasa created a C# Eval statement and console shell for the Mono Project.
Sir Tim Berners Lee launched the world wide Web Foundation to proactively advance the goals that “a single web” should be “open to any device and software” and to extend the capabilities of the web and ensuring they can be accessed securely by everyone on the planet… Hard to say what this all means, at this point.
Present.ly and Yammer launched as attempts at private corporate Twitter implementations. Present.ly looks most promising, they have the concept of “groups” that is missing from twitter, and they have a few different types of posts (questions, urgent messages, group broadcast messages, etc). However, they charge for anything more than the most basic account (ie: no IM without paying). Yammer has a more curious business model (it’s almost like extortion): employees can join for free based on their email address, companies can then pay to take over their (pre-established on-the-fly) corporate network and exert some control over it, but their Jabber/IM is working great already.
So, I’ve been called out on this latest meme posting by /\/\o\/\/ and although I usually just ignore these things,
As with any curious developer, I had to trace this thing back to it’s root cause … it turns out this started as a Software Development thing, and it was altered into a sort of SysAdmin thing.
So, since I’m putting up with this in the first place, I think I’ll go back to that original developer-oriented list of questions, if you don’t mind. 
Well … my brother called me with an odd compiler problem with his C++ homework today (he’s working on another degree, and taking some programming courses) ... but the homework problem he was working on was the infamous N Queens problem:
Given a chess board of N x N squares, place N queens on the board in such a way than none threatens the others. In chess, a queen can move diagonally or horizontally, so solving this requires placing each queen on her own row and column, and ordered such that none of them are on the same diagonal in either direction.
The problem is solvable using a backtracking recursive algorithm: the program must place a queen on the first row and then find a spot that works for the next row, and continue for each row. If it can’t find a spot for a row, it backtracks to the previous row and uses the next legal spot on that row, and if there is none, it backtracks to the previous row, and so on.
Anyway. There’s lots of information about this stuff out there on the ‘net, including dozens of slides shows and lecture notes from dozens of schools, so I’m just going to move on to the fun part: my solution in PowerShell. I wrote it just to make sure I understood the algorithm correctly, without giving away the C++ answer as much as a quick web search would. In fact, I followed the restrictions my brother’s professor had placed on them to break it up into a specific set of functions…
## N-Queens problem using backtracking
################################################################################
## Backtracking is a problem-solving strategy that, when it reaches an impasse,
## retraces its steps in reverse order before trying a new sequence of steps.
param($size=8) # By default, we use a board of size 8
function Check-Queen($r1,$c1,$r2,$c2) {
return -not (
# they can't be on the same column
($c1 -eq $c2) -or
# nor on the same row
($r1 -eq $r2) -or
# nor on the same diagonal
([Math]::Abs($r1-$r2) -eq [Math]::Abs($c1-$c2)));
}
function Out-Board($board){
foreach($c in $board) {
switch(0..($board.Count-1)) {
{$_-eq$c} { write-host "Q" -fore red -nonew }
default { write-host "#" -nonew}
}
Write-Host
}
}
function Set-Queen($board,$row,$column) {
# Set the queen location for this row
$board[$row]=$column;
# if this is the last row, then we're done
if($row+1 -eq $board.Count) { return $true }
# place the queen in the next row
# try every column ....
for($c=0;$c -lt $board.Count; $c++) {
$clean = $true
# check it against every prior row
for($r=0; $r -le $row; $r++) {
$clean = $clean -and (Check-Queen $r $board[$r] ($row+1) $c)
if(!$clean) { break; }
}
# if we found the spot, recurse the next row...
if($clean -and( Set-Queen $board ($row+1) $c )) {
return $true;
}
}
return $false
}
$board = new-object int[] $size
# if starting in 0,0 doesn't work 0,1 will
if(Set-Queen $board 0 0){
Out-Board $board
}elseif(Set-Queen $board 0 1){
Out-Board $board
}
Posted in Huddled | 
Tags: Algorithms, Backtracking, Challenges, PowerShell, Programming, Recursion, Scripting | 
Comments Closed
In a continuation of what is, sadly, becoming a series on how the PowerShell Pipeline works … Karl Prosser brought to my attention that certain powershell commands which have an -InputObject parameter don’t actually work when you pass something into it … so I thought I should create a cmdlet to show you how to correctly handle the InputObject parameter with the ValueFromPipeline set so you can pass the input in either way.
To demonstrate the problem, try this:
$a = @("A","B","A","C")
$a | Select -First 3 -Unique
Select -First 3 -Unique -InputObject $a
This should expose two weirdnesses about how the Select-Object cmdlet works:
- The -First parameter affects the input before the -Unique parameter does.
- When you pass the input in via -InputObject, the whole array is treated as a single object, and the command basically doesn’t do anything.
The big problem with this behavior is that there’s essentially no hint that you’ve done something wrong — there’s actually no way to make Select-Object work properly except by passing the objects in via the pipeline. The bigger problem is that it would have been simple for the Microsoft team to catch this and alert you, but they didn’t — so you probably won’t even notice there’s a problem until you run it on a trivial data set like my example. The even bigger problem is that it doesn’t just affect Select-Object (try it with Where-Object, just for instance). Read the rest of this entry »
Posted in Huddled |
Tags: Cmdlet, Development, My Software, Pipeline, PowerShell, Programming, Scripting, SourceCode |
4 Comments »