2008 Window Scripting Games - Advanced PowerShell Event 7
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?
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.
About Newsletter
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);
}
}
[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)}
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
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);
If the number of teams is odd:
add one more team called "Bye."
Maybe change the output formatting on that condition to something prettier.
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)
#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
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);}
<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>
###########################################################
puts (1..N=6).map{|i| (i...N).map{|j| "#{(i+64).chr} vs. #{(j+65).chr}"}}.sort_by{rand}
###########################################################
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}
games.each { |g| puts "#{g[0]} - #{g[1]}" }
Inefficient as all get-out, but what can ya do?
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...
$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
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);
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
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)
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
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
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.