# Scott Hanselman

## 2008 Window Scripting Games - Advanced PowerShell Event 7

March 04, 2008 Comment on this post [25] Posted in

In a few days the 2008 Scripting Games will come to an end. This is a yearly event that the Script Center does. There's a beginner and an advanced division and a bunch of deceptively hard problems. I was selected to be on of the "Guest Commentators (list here)" which really means they wanted me to solve one of the problems and provide the solution as an example. I'm not sure my solution is the best way, but it did solve the problem they assigned me.

My problem was Event 7: Play Ball! and I was to write a script that schedules all the games for a round-robin baseball tournament. The complete scenario is here, but in a nutshell:

"In a round-robin baseball tournament (or any kind of round-robin tournament, for that matter), every team plays each of the other teams in the tournament one time and one time only. For example, suppose we have a tournament with three teams (teams A, B, and C). In that case, the tournament would consist of the following set of games:

• A vs. B
• A vs. C
• B vs. C

See how that works? Team A plays Team B and Team C; Team B plays Team A and Team C; and Team C plays Teams A and B."

A few other wrinkles thrown in are that the games must be randomized, otherwise Team A will play too many in a row and you need to schedule six teams, A through F. Of course, to be clear, every team must pay every other team once and only once. Here's my solution, hacked together quickly.

```#this only works with an even number of teams
cls
[array]\$global:games = \$nul
function rotateArray(\$a)
{
\$first, \$rest = \$a
\$a = \$rest + \$first
return \$a
}
function makeGames(\$a)
{
\$i = 0;
while(\$i -lt \$a.Length/2)
{
\$global:games = \$global:games + (\$a[\$i].ToString() + " vs. " + \$a[\$a.Length-1-\$i].ToString())
\$i++
}
}
\$a = "A","B","C","D","E","F"
\$z = 0
while(\$z -lt \$a.Length-1)
{
makeGames(\$a)
# hold on to the first one

\$first, \$rest = \$a
#rotate the rest
\$rest = rotateArray(\$rest)
\$a = [array]\$first + \$rest
\$z++
}
#randomize games
\$a = [collections.arraylist]\$global:games
\$r = \$a.count..1 |% {\$R = new-object random}{\$R.next(0,\$a.count) |%{\$a[\$_];\$a.removeat(\$_)}}
\$r```

Doing this in PowerShell took my brain a while to get. Note the RotateArray method's use of multi-variable assignment to chop up he array into first and rest. That wasn't obvious to me as a C-guy for the last 15 years, but it made my solution simpler when I refactored and introduced it.

The solution (remember, it's randomized) will look something like this:

```B vs. D
B vs. C
A vs. D
B vs. F
C vs. D
A vs. F
A vs. B
C vs. F
E vs. F
A vs. E
D vs. F
B vs. E
D vs. E
A vs. C
C vs. E```

Enjoy. Here's the same solution in Perl from Jan Dubois and again in VBScript. Who wants to do the F# version and the Ruby version? What about just LINQ to Objects?

Scott Hanselman is a former professor, former Chief Architect in finance, now speaker, consultant, father, diabetic, and Microsoft employee. He is a failed stand-up comic, a cornrower, and a book author.

Hosting By
March 04, 2008 6:02
I'm fairly new at F#, so I'm sure there's a more elegant solution. Most of the code is the shuffle though, the "guts" are pretty compact.

`open Systemopen System.Collections.Genericlet shuffle list =    let random = Random() in    let array = Array.of_list list in        for i in 0 .. array.Length - 1 do            let k = random.Next(array.Length) in            let temp = array.[i] in                array.[i] <- array.[k];                array.[k] <- temp        done;        List.of_array arraylet matchups =    let rec generate = function          [] -> []        | h :: t -> (List.map (fun c -> (h, c)) t) @ generate t    in generate [ 'A' .. 'F' ];;List.iter (fun (a, b) -> printfn "%c vs. %c" a b) (shuffle matchups)`
March 04, 2008 6:09
Here is a nice little Linq solution. I'm sure I screwed up some part of it:

public static void MakeGames(char[] teams)
{
var rand = new Random();
foreach (
var item in (
from t in teams
from r in teams
where t < r
orderby rand.Next(teams.Length)
select t + " vs " + r))
{
Console.WriteLine(item);
}
}
March 04, 2008 6:25
I'm usually a fairly verbose programmer and would typically write something like that for my day job, but being inspired by the likes of MoW and others I've found the Scripting Games to be an opportunity to let my inner obfuscater come out. Here's my PS version...

[Collections.ArrayList] \$x = 0..4 |%{\$a=\$_;(\$a+1)..5 |%{""+[char](\$a+65)+" vs. "+[char](\$_+65)}}
\$y=New-Object Random
while(\$x.Count -gt 0) {\$z=\$y.Next(0,\$x.Count); \$x[\$z]; \$x.RemoveAt(\$z)}
March 04, 2008 6:34
Here's my python version (even though you didn't ask for one):
`import randomTEAMS = ["A", "B", "C", "D", "E", "F"]RTEAM = TEAMSRTEAM.reverse()LEN = len(TEAMS)GAMES = []for i in TEAMS:    for j in RTEAM:        if i == j:            continue        k = [i,j]        k.sort()        if k in GAMES:            continue                GAMES.append(k)GLEN = len(GAMES)random.shuffle(GAMES)for i in GAMES:    print "Team %s vs. Team %s" % (i[0], i[1])`

Sample output:
`Team A vs. Team DTeam D vs. Team FTeam C vs. Team DTeam C vs. Team ETeam A vs. Team FTeam B vs. Team DTeam A vs. Team ETeam A vs. Team BTeam A vs. Team CTeam B vs. Team CTeam E vs. Team FTeam B vs. Team FTeam D vs. Team ETeam B vs. Team ETeam C vs. Team F`

Someone with more experience using generators and iterators could likely do a better job.

Kevin
March 04, 2008 6:34
Wow... that's such a strange language. The impression imparted upon me by this small sample is that they're trying to graft certain syntax elements from bash scripting onto C#. Yay, lots of dollar signs... hash marks for comments... and "-lt" instead of an actual operator... then of course your usual scripting language stuff: variable declaration not required, and some cryptic syntactic sugar for arrays. Weird.

Here's a quick attempt at a LINQ version... untested, of course. But damn, does it look good.

`char[] players = {'A', 'B', 'C', 'D', 'E', 'F'};Random rand = new Random();var matches = from player1 in players              from player2 in players.SkipWhile(p => (p <= player1))              orderby rand.Next()              select string.Format(CultureInfo.CurrentUICulture, "{0} vs. {1}", player1, player2);`
March 04, 2008 7:26
I don't have a solution for you, except that I can solve your 'even number of teams only' problem.

If the number of teams is odd:
add one more team called "Bye."

Maybe change the output formatting on that condition to something prettier.
March 04, 2008 8:05
Here's a python version that utilizes generator expressions and sets to do the heavy lifting. It's not as terse as it could be, but it demonstrates some of the powerful aspects of the language.

`from random import shufflefrom sets import ImmutableSetteams = 'ABCDEFG'# create a class to identify two opposing teamsclass OpponentPair(ImmutableSet):	def __init__(self, team_a, team_b):		assert team_a != team_b, "team_a and team_b must be distinct"		super(self.__class__, self).__init__((team_a,team_b))get_distinct_pairs = lambda items: (OpponentPair(x,y) for x in items for y in items if x != y)distinct_pairs = get_distinct_pairs(teams)# remove duplicate pairings# Note, since OpponentPair((A,B)) == OpponentPair((B,A)), the two#  will be considered the same, and only one will remain.unique_pairs = set(distinct_pairs)# put the pairs into a list to fix their order (sets are orderless)fixed_pairs = list(unique_pairs)# randomize the ordershuffle(fixed_pairs)def print_pair(pair):	print '%s vs %s' % tuple(pair)map(print_pair, fixed_pairs)`
March 04, 2008 8:35
Here's my F# solution. The shuffle was definitely a fun bit of code to write.

`#lightopen Systemlet compareWith f x y = compare (f x) (f y)let shuffle lst =  let rnd = new Random()  let genPair x = x, rnd.NextDouble()  lst  |> List.map genPair  |> List.sort (compareWith snd)  |> List.map fst  let getGames lst =  let rec aux l acc =    match l with    | h::t -> aux t (t |> List.map (fun x -> h, x) |> List.append acc)    | [] -> acc    aux lst []  let printGame t =  printfn "%c vs. %c" (fst t) (snd t)  ['A' .. 'F'] |> getGames |> shuffle |> List.iter printGame`
March 04, 2008 8:41
Domenic: The LINQ version certainly looked nice but didn't work (outputs nothing). I haven't picked up Linq yet so i didn't attempt to debug it.

Here's my C# 2.0 version... I think this algorithm should be very doable in Powershell. Not sure about the Sort(delegate) part. I am sure there's an easy way to sort an array randomly with Powershell.

`string[] teams = { "A", "B", "C", "D", "E", "F" };List<string> games = new List<string>();for (int i = 0; i < teams.Length; i++){	for (int j = i + 1; j < teams.Length; j++) { games.Add(teams[i] + " vs. " + teams[j]); }}Random r = new Random(Environment.TickCount);games.Sort(delegate(string a, string b) { return a.CompareTo(b) == 0 ? 0 : r.Next(-1, 1); });foreach (string game in games) {Console.WriteLine(game);}`
March 04, 2008 8:54
Here's a simple one I threw together in Ruby...

<code>
class Team
attr_accessor :name
def initialize(name)
@name=name
end
end

class Game
attr_accessor :home_team, :away_team
def initialize(home,away)
@home_team = home
@away_team = away
end
end

class Schedule
attr_accessor :games
def initialize()
@games=[]
end

def scheduled_to_play?(team1, team2)
@games.each do |game|
if (game.home_team == team1 || game.away_team == team1) && (game.home_team == team2 || game.away_team == team2)
return true
end
end
return false
end

@games << Game.new(team1,team2) unless scheduled_to_play?(team1,team2)
end

def to_s
@games.sort_by{rand}.each{|game| puts "#{game.home_team.name} vs. #{game.away_team.name}\n"}
end
end

schedule = Schedule.new
teams= []

("A".."F").to_a.each{|letter| teams << Team.new(letter)}
teams.each do |home|
teams.each do |away|
end
end
schedule.to_s

</code>
March 04, 2008 12:34
Here's a Ruby one-liner (N is the number of teams that are involved in the tournament):

###########################################################
puts (1..N=6).map{|i| (i...N).map{|j| "#{(i+64).chr} vs. #{(j+65).chr}"}}.sort_by{rand}
###########################################################
March 04, 2008 19:01
Less verbose than Leon and more so than Eric, in ruby:
`Teams = ['A', 'B', 'C', 'D', 'E', 'F']games = Array.new#Generate all possible matchupsTeams.each { |t|   Teams.each { |o|      games << [t, o] if t != o   }}#Randomizegames = games.sort_by{rand}#Printgames.each { |g| puts "#{g[0]} - #{g[1]}" }`

Inefficient as all get-out, but what can ya do?
March 04, 2008 19:25
Chinh Do: well yeah, you might notice there's no calls to Console :P. I thought gift-wrapping the matches for you in a nice IEnumerable<string> object would be good enough, but noooooo.... some people...
March 04, 2008 19:59
The LINQ example from Domenic Works well the only that he don't do is write the result to the console but I like it.
March 04, 2008 23:25
`My co-worker Ed and I had a battle to the finish to do this in SQL.  Here's his solution:WITH Teams (HomeTeam, AwayTeam, ID, Row) AS      (	SELECT HomeTeam.Team, AwayTeam.Team, CHECKSUM(HomeTeam.Team+AwayTeam.Team) * 		CHECKSUM(AwayTeam.Team+HomeTeam.Team), Row_Number() 		Over (Order By CHECKSUM(HomeTeam.Team+AwayTeam.Team) * 		CHECKSUM(AwayTeam.Team+HomeTeam.Team))            FROM (SELECT 'A' AS Team UNION ALL                  SELECT 'B' UNION ALL                  SELECT 'C' UNION ALL                  SELECT 'D' UNION ALL                  SELECT 'E' UNION ALL                  SELECT 'F') HomeTeam            FULL OUTER JOIN (SELECT 'A' AS Team UNION ALL                  SELECT 'B' UNION ALL                  SELECT 'C' UNION ALL                  SELECT 'D' UNION ALL                  SELECT 'E' UNION ALL                  SELECT 'F') AwayTeam ON AwayTeam.Team <> HomeTeam.Team      )SELECT HomeTeam, AwayTeam FROM TeamsWHERE Row % 2 = 0ORDER BY RAND(CHECKSUM(NewID()))And mine:select	team_one + ' vs. ' + team_twofrom(	select 		team_one, team_two, 		ascii(team_one) - 65 as t1val, ascii(team_two) - 65 as t2val,		((ascii(team_one) - 65) * 10) + ascii(team_two) - 65 as t3val	from	(		select teams.team as team_one		from (		select 'A' as team union		select 'B' as team union		select 'C' as team union		select 'D' as team union		select 'E' as team union		select 'F' as team ) teams	) one, (		select teams.team as team_two		from (		select 'A' as team union		select 'B' as team union		select 'C' as team union		select 'D' as team union		select 'E' as team union		select 'F' as team ) teams	) two	where team_one <> team_two) awhere a.t3val > ((t1val * 10) + t1val)order by rand(checksum(newid()))Cheers...`

March 04, 2008 23:26
LINQ and PowerShell have a lot of concepts in common. The sequence operations that underly the LINQ "from" statement correspond pretty closely with cmdlets (at least at some level :-). This makes it quite simple to translate the LINQ solution into PowerShell:
`\$players = 'A', 'B', 'C', 'D', 'E', 'F'\$rand = new-object random\$matches = \$( foreach (\$p1 in \$players) {              foreach (\$p2 in \$players | where {\$_ -gt \$p1}) { "\$p1 vs. \$p2" }} ) |              sort {\$rand.Next() }`

-bruce
==============================
Bruce Payette
Principal Developer, Windows PowerShell
Microsoft Corporation
March 05, 2008 4:21
Random randObj = new Random();
int teams = 30;

int numGames = ((teams * teams) - teams) / 2; // Get number of games
List<string> games = new List<string>();

while (games.Count() != numGames)
{
int a = randObj.Next(teams);
int b = randObj.Next(teams);

if (a > b)
{
string game = string.Format("Team {0} vs. Team {1} ", a, b);
}
}

foreach (string game in games) Console.WriteLine(game);
March 05, 2008 8:10
Domenic: Thanks for the clarification. I thought the "select" part was somehow doing the output. Well I did say I don't know no Linq. Nice code.
March 05, 2008 21:45

`HAI   CAN HAS System?	I HAS A NUMBEROFTEAMS ITZ 6	I HAS A NUMBEROFGAMES ITZ 15	I HAS A HT ITZ NJU ArrayList ON Collections ON System WIT 15	I HAS A RANDOBJ ITZ NJU Random ON System	I HAS A COWNTER ITZ 0	I HAS A INTA ITZ 0	I HAS A INTB ITZ 0	I HAS A THING	I HAS A NOTHERTHING	I HAS A HMMMM	I HAS A GAME 	IM IN YR	  LOL HMMMM R COL get_Count ON HT	     IZ HMMMM SMALR NUMBEROFGAMES?		YARLY		   LOL INTA R COL Next ON RANDOBJ WIT NUMBEROFTEAMS		   LOL INTB R COL Next ON RANDOBJ WIT NUMBEROFTEAMS		   IZ INTA BIGR INTB?			YARLY			   LOL GAME R COL Format ON String ON System WIT "Team {0} vs. Team {1}" AN INTA AN INTB			   LOL THING R COL Contains ON HT WIT GAME			   LOL NOTHERTHING R COL ToString ON THING			   IZ NOTHERTHING LIEK "False"?				YARLY				   COL Add ON HT WIT GAME				NOWAI				   BTW NUFFIN HERE			   KTHX			NOWAI		   KTHX				NOWAI		   GTFO			     KTHX	KTHX	I HAS A LUPESIZE ITZ COL get_Count ON HT	LOL COWNTER R 0	IM IN YR		IZ COWNTER SMALR LUPESIZE?			YARLY				VISIBLE COL get_Item ON HT WIT COWNTER			NOWAI				GTFO		KTHX	UPZ COWNTER!!1	KTHX	KTHXBYE`
March 06, 2008 6:07
Here's a Python implementation that I think is a little cleaner than Kevin's. It shows off array slicing, which is nice for this sort of thing.
`import random# Note: Should be an ordered set rather than a list - items should be unique.team_names = ["A", "B", "C", "D", "E", "F"]games = []for first_team in team_names:  for second_team in team_names[team_names.index(first_team)+1:]:    games.append((first_team, second_team))    random.shuffle(games)for game in games:    print("Team %s vs. Team %s" % game)`

March 06, 2008 9:58
I wrote an implemenntation in F#: Play Ball Script in F#
March 07, 2008 23:36
Well, I just couldn't resist...

Here's the Postscript version of this. It will work with any amount of team names.

`%%  ScheduleTeams.ps - 03/07/2007, thoward37@gmail.com% %    Contains a function used to schedule matches between a set of teams.%    Also contains supporting functions.%%  Usage:%    gs -dBATCH ScheduleTeams.ps -c "[(A)(B)(C)(D)(E)(F)] ScheduleTeams stack"% %  Functions included are:%   ScheduleTeams	- when supplied with a string array of team names, emits a list of game matches to the stack.%    strcat			- concatenates two strings.%    randRange 		- generates a random integer between two specified integers%    min 			- returns the smaller of two integers.%    max 			- returns the larger of two integers.%    -- 			- decrements an integer.%%   See also  PrintSchedule.ps, which works with this file to output to a printer instead of the console.% (a) (b) strcat (ab)  % Concatenates two strings/strcat { 	exch dup length	2 index length add string        dup dup 4 2 roll copy length    4 -1 roll putinterval} bind def % int1 int2 randRange int% Generates a random integer between two specified integers. /randRange {	2 copy max min 	dup 3 1 roll sub 	rand 100 mod 100 div	mul cvi add 	} bind def % int1 int2 max int % Returns the smaller of two numbers./min { 	2 copy gt 	{ 				exch 	} if pop } bind def% int1 int2 max int % Returns the larger of two numbers./max { 	2 copy lt 	{ 		exch 	} if pop } bind def% int -- int% Decrements an integer /-- { 1 sub } bind def% Pushes a randomized list of game matches between the teams in the supplied array% stack shoudl contain a string array of teams, and function will push each game onto % the stack as output. % The number of games outputted will equal N*2/(N-1) where N is the number of teams./ScheduleTeams {		/teams exch def			% emit games to stack	0 1 teams length -- {		dup 		teams exch get				/firstTeam exch def						1 add 1 teams length -- {						firstTeam ( vs ) strcat 						teams 3 -1 roll get strcat					} for 				} for 		% randomize stack	count { 		0 count 1 sub 		randRange cvi 1 		roll 	} repeat	} bind def`

To run it, save the following code as ScheduleTeams.ps then run ghostscript with the following commandline:
`gs -dBATCH -c "[(A)(B)(C)(D)(E)(F)] ScheduleTeams stack"`

or, you could just tack "[(A)(B)(C)(D)(E)(F)] ScheduleTeams stack" onto the end of the file,
and run it however you want to.. if you'd rather print it to a page (instead of echo to the
console), just remove the stack command, and add some code to do a xshow for each
string on the stack and then showpage.. Here's an example of that..

`%%  PrintSchedule.ps - 03/06/2007, thoward37@gmail.com%%  Prints a game schedule to a printer%%  Usage:%    gs -dBATCH ScheduleTeams.ps PrintSchedule.ps%  % edit this line to contain the team names, instead of a,b,c, d, etc..[(A)(B)(C)(D)(E)(F)] ScheduleTeams /Helvetica findfont 12 scalefont setfont0 1 count 3 sub {		12 mul 712 exch sub 	36 exch moveto 	show} forshowpage`

Output should look like:

`B vs CC vs FA vs FB vs FD vs EA vs EC vs EC vs DD vs FA vs DB vs EA vs CE vs FB vs DA vs B`

Enjoy,
Troy
March 08, 2008 4:00
Regarding the SQL version posted... Why didn't you do it this way? This will work for any table "Teams" with any varchar column "TeamName" for any amount of teams, regardless of the names.

`SELECT     games FROM (        SELECT             teams.TeamName + ' vs ' + teams2.TeamName as games,             NEWID() as sortColumn        FROM             teams        JOIN             teams teams2            ON teams.teamName != teams2.teamName                 AND teams.teamName > teams2.teamName         ) gameScheduleORDER BY     sortColumn`
March 08, 2008 8:24
Duh.. the "teams.teamName != teams2.teamName" clause in the join constraints is redundant.. typing faster than thinking. Reduce that code by a line!
March 08, 2008 20:42
Re: Re: SQL version

ACH!

Troy, it was one of those things where we got too into outdo-ing each other that we missed the simple solution.

Hats off to you. We're both smacking our heads on our cube desks!