Scott Hanselman

2008 Window Scripting Games - Advanced PowerShell Event 7

March 4, '08 Comments [25] Posted in Learning .NET | PowerShell | Ruby
Sponsored By

Olympic_flameIn 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?

About Scott

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.

facebook twitter subscribe
About   Newsletter
Sponsored By
Hosting By
Dedicated Windows Server Hosting by SherWeb
Tuesday, March 04, 2008 2:02:39 AM UTC
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 System
open System.Collections.Generic

let 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 array

let 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)
Tuesday, March 04, 2008 2:09:13 AM UTC
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);
}
}
Tuesday, March 04, 2008 2:25:07 AM UTC
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)}
Jason Turnage
Tuesday, March 04, 2008 2:34:18 AM UTC
Here's my python version (even though you didn't ask for one):

import random
TEAMS = ["A", "B", "C", "D", "E", "F"]
RTEAM = TEAMS
RTEAM.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 D
Team D vs. Team F
Team C vs. Team D
Team C vs. Team E
Team A vs. Team F
Team B vs. Team D
Team A vs. Team E
Team A vs. Team B
Team A vs. Team C
Team B vs. Team C
Team E vs. Team F
Team B vs. Team F
Team D vs. Team E
Team B vs. Team E
Team C vs. Team F

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

Kevin
Tuesday, March 04, 2008 2:34:40 AM UTC
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);
Tuesday, March 04, 2008 3:26:03 AM UTC
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.
Brett Morien
Tuesday, March 04, 2008 4:05:30 AM UTC
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 shuffle
from sets import ImmutableSet

teams = 'ABCDEFG'

# create a class to identify two opposing teams
class 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 order
shuffle(fixed_pairs)

def print_pair(pair):
print '%s vs %s' % tuple(pair)

map(print_pair, fixed_pairs)
Tuesday, March 04, 2008 4:35:04 AM UTC
Here's my F# solution. The shuffle was definitely a fun bit of code to write.


#light

open System

let 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

Tuesday, March 04, 2008 4:41:22 AM UTC
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);}
Tuesday, March 04, 2008 4:54:17 AM UTC
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

def add_match(team1,team2)
@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|
schedule.add_match(home,away) unless home == away
end
end
schedule.to_s

</code>
Tuesday, March 04, 2008 8:34:45 AM UTC
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}
###########################################################
Eric
Tuesday, March 04, 2008 3:01:00 PM UTC
Less verbose than Leon and more so than Eric, in ruby:

Teams = ['A', 'B', 'C', 'D', 'E', 'F']
games = Array.new

#Generate all possible matchups
Teams.each { |t|
Teams.each { |o|
games << [t, o] if t != o
}
}

#Randomize
games = games.sort_by{rand}

#Print
games.each { |g| puts "#{g[0]} - #{g[1]}" }

Inefficient as all get-out, but what can ya do?
Nathan
Tuesday, March 04, 2008 3:25:52 PM UTC
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...
Tuesday, March 04, 2008 3:59:26 PM UTC
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.
Bela Istok
Tuesday, March 04, 2008 7:25:09 PM UTC

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 Teams
WHERE Row % 2 = 0
ORDER BY RAND(CHECKSUM(NewID()))


And mine:

select
team_one + ' vs. ' + team_two
from
(
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
) a
where a.t3val > ((t1val * 10) + t1val)
order by rand(checksum(newid()))


Cheers...

Tuesday, March 04, 2008 7:26:16 PM UTC
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
Wednesday, March 05, 2008 12:21:57 AM UTC
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);
if (!games.Contains(game)) games.Add(game);
}
}

foreach (string game in games) Console.WriteLine(game);
Chris
Wednesday, March 05, 2008 4:10:48 AM UTC
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.
Wednesday, March 05, 2008 5:45:53 PM UTC
Because somebody had to: Ladies and Gentlemen I present....LOLCODE:

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
Ryan Smith
Thursday, March 06, 2008 2:07:30 AM UTC
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)

Thursday, March 06, 2008 5:58:28 AM UTC
I wrote an implemenntation in F#: Play Ball Script in F#
Friday, March 07, 2008 7:36:02 PM UTC
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 setfont

0 1 count 3 sub {
12 mul 712 exch sub
36 exch moveto
show
} for

showpage



Output should look like:


B vs C
C vs F
A vs F
B vs F
D vs E
A vs E
C vs E
C vs D
D vs F
A vs D
B vs E
A vs C
E vs F
B vs D
A vs B



Enjoy,
Troy
Troy Howard
Saturday, March 08, 2008 12:00:37 AM UTC
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
) gameSchedule
ORDER BY
sortColumn

Troy Howard
Saturday, March 08, 2008 4:24:52 AM UTC
Duh.. the "teams.teamName != teams2.teamName" clause in the join constraints is redundant.. typing faster than thinking. Reduce that code by a line!
Troy Howard
Saturday, March 08, 2008 4:42:29 PM UTC
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!


Comments are closed.

Disclaimer: The opinions expressed herein are my own personal opinions and do not represent my employer's view in any way.