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."
"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:
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?
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)
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])
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
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);
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)
#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
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);}
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]}" }
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...
$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() }
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)
%% 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
gs -dBATCH -c "[(A)(B)(C)(D)(E)(F)] ScheduleTeams stack"
%% 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
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
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
Ads by The Lounge