World Cup group stage: Difference between revisions

Content added Content deleted

Inline

Revision as of 19:04, 18 August 2014

It's World Cup season (or at least it was when this page was created)! The World Cup is an international football/soccer tournament that happens every 4 years. Countries put their international teams together in the years between tournaments and qualify for the tournament based on their performance in other international games. Once a team has qualified they are put into a group with 3 other teams. For the first part of the World Cup tournament the teams play in "group stage" games where each of the four teams in a group plays all three other teams once. The results of these games determine which teams will move on to the "knockout stage" which is a standard single-elimination tournament. The two teams from each group with the most standings points move on to the knockout stage. Each game can result in a win for one team and a loss for the other team or it can result in a draw/tie for each team. A win is worth three points in the standings. A draw/tie is worth one point. A loss is not worth any points.

Generate all possible outcome combinations for the six group stage games. With three possible outcomes for each game there should be 3⁶ = 729 of them. Calculate the standings points for each team with each combination of outcomes. Show a histogram (graphical, ASCII art, or straight counts--whichever is easiest/most fun) of the standings points for all four teams over all possible outcomes.

Don't worry about tiebreakers as they can get complicated. We are basically looking to answer the question "if a team gets x standings points, where can they expect to end up in the group standings?".

Hint: there should be no possible way to end up in second place with less than two points as well as no way to end up in first with less than three. Oddly enough, there is no way to get 8 points at all.

D

This imports the module of the third D solution of the Combinations Task.

Translation of: Python

<lang d>void main() {

   import std.stdio, std.range, std.array, std.algorithm, combinations3;

   immutable scoring = [0, 1, 3];
   /*immutable*/ auto r3 = [0, 1, 2];
   immutable combs = 4.iota.array.combinations(2).array;
   uint[10][4] histo;

   foreach (immutable results; cartesianProduct(r3, r3, r3, r3, r3, r3)) {
       int[4] s;
       foreach (immutable r, const g; [results[]].zip(combs)) {
           s[g[0]] += scoring[r];
           s[g[1]] += scoring[2 - r];
       }

       foreach (immutable i, immutable v; s[].sort().release)
           histo[i][v]++;
   }
   writefln("%(%s\n%)", histo[].retro);

}</lang>

Output:

[0, 0, 0, 1, 14, 148, 152, 306, 0, 108]
[0, 0, 4, 33, 338, 172, 164, 18, 0, 0]
[0, 18, 136, 273, 290, 4, 8, 0, 0, 0]
[108, 306, 184, 125, 6, 0, 0, 0, 0, 0]

This alternative version is not fully idiomatic D, it shows what to currently do to tag the main function of the precedent version as @nogc. <lang d>import core.stdc.stdio, std.range, std.array, std.algorithm, combinations3;

immutable uint[2][6] combs = 4u.iota.array.combinations(2).array;

void main() nothrow @nogc {

   immutable uint[3] scoring = [0, 1, 3];
   uint[10][4] histo;

   foreach (immutable r0; 0 .. 3)
    foreach (immutable r1; 0 .. 3)
     foreach (immutable r2; 0 .. 3)
      foreach (immutable r3; 0 .. 3)
       foreach (immutable r4; 0 .. 3)
        foreach (immutable r5; 0 .. 3) {
           uint[4] s;
           foreach (immutable i, immutable r; [r0, r1, r2, r3, r4, r5]) {
               s[combs[i][0]] += scoring[r];
               s[combs[i][1]] += scoring[2 - r];
           }

           foreach (immutable i, immutable v; s[].sort().release)
               histo[i][v]++;
        }

   foreach_reverse (const ref h; histo) {
       foreach (immutable x; h)
           printf("%u ", x);
       printf("\n");
   }

}</lang>

Output:

0 0 0 1 14 148 152 306 0 108 
0 0 4 33 338 172 164 18 0 0 
0 18 136 273 290 4 8 0 0 0 
108 306 184 125 6 0 0 0 0 0

Java

Works with: Java version 1.5+

This example codes results as a 6-digit number in base 3. Each digit is a game. A 2 is a win for the team on the left, a 1 is a draw, and a 0 is a loss for the team on the left. <lang java5>import java.util.Arrays;

public class GroupStage{

   //team left digit vs team right digit
   static String[] games = {"12", "13", "14", "23", "24", "34"};
   static String results = "000000";//start with left teams all losing

   private static boolean nextResult(){
       if(results.equals("222222")) return false;
       int res = Integer.parseInt(results, 3) + 1;
       results = Integer.toString(res, 3);
       while(results.length() < 6) results = "0" + results;	//left pad with 0s
       return true;
   }

   public static void main(String[] args){
       int[][] points = new int[4][10]; 		//playing 3 games, points range from 0 to 9
       do{
           int[] records = {0,0,0,0};
           for(int i = 0; i < 6; i++){
               switch(results.charAt(i)){
                   case '2': records[games[i].charAt(0) - '1'] += 3; break;    //win for left team
                   case '1':                                                   //draw
                       records[games[i].charAt(0) - '1']++;
                       records[games[i].charAt(1) - '1']++;
                       break;
                   case '0': records[games[i].charAt(1) - '1'] += 3; break;    //win for right team
               }
           }
           Arrays.sort(records);	//sort ascending, first place team on the right
           points[0][records[0]]++;
           points[1][records[1]]++;
           points[2][records[2]]++;
           points[3][records[3]]++;
       }while(nextResult());
       System.out.println("First place: " + Arrays.toString(points[3]));
       System.out.println("Second place: " + Arrays.toString(points[2]));
       System.out.println("Third place: " + Arrays.toString(points[1]));
       System.out.println("Fourth place: " + Arrays.toString(points[0]));
   }

}</lang>

Output:

First place: [0, 0, 0, 1, 14, 148, 152, 306, 0, 108]
Second place: [0, 0, 4, 33, 338, 172, 164, 18, 0, 0]
Third place: [0, 18, 136, 273, 290, 4, 8, 0, 0, 0]
Fourth place: [108, 306, 184, 125, 6, 0, 0, 0, 0, 0]

Perl 6

Translation of: Python

<lang perl6>constant scoring = 0, 1, 3; constant r = 0..2; my @histo = [0 xx 10] xx 4;

for ([X] r,r,r,r,r,r).tree -> @results {

   my @s;

   for @results Z (^4).combinations(2)
    -> $r,        @g {
       @s[@g[0]] += scoring[$r];
       @s[@g[1]] += scoring[2 - $r];
   }

   for @histo Z @s.sort
    -> @h,      $v {
       ++@h[$v];
   }

}

say .fmt('%3d',' ') for @histo.reverse;</lang>

Output:

  0   0   0   1  14 148 152 306   0 108
  0   0   4  33 338 172 164  18   0   0
  0  18 136 273 290   4   8   0   0   0
108 306 184 125   6   0   0   0   0   0

Python

<lang python>from itertools import product, combinations, izip

scoring = [0, 1, 3] histo = [[0] * 10 for _ in xrange(4)]

for results in product(range(3), repeat=6):

   s = [0] * 4
   for r, g in izip(results, combinations(range(4), 2)):
       s[g[0]] += scoring[r]
       s[g[1]] += scoring[2 - r]

   for h, v in izip(histo, sorted(s)):
       h[v] += 1

for x in reversed(histo):

   print x</lang>

Output:

[0, 0, 0, 1, 14, 148, 152, 306, 0, 108]
[0, 0, 4, 33, 338, 172, 164, 18, 0, 0]
[0, 18, 136, 273, 290, 4, 8, 0, 0, 0]
[108, 306, 184, 125, 6, 0, 0, 0, 0, 0]

Tcl

Translation of: Java

Works with: Tcl version 8.6

<lang tcl>package require Tcl 8.6 proc groupStage {} {

   foreach n {0 1 2 3} {

set points($n) {0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0}

   }
   set results 0
   set games {0 1 0 2 0 3 1 2 1 3 2 3}
   while true {

set R {0 0 1 0 2 0 3 0} foreach r [split [format %06d $results] ""] {A B} $games { switch $r { 2 {dict incr R $A 3} 1 {dict incr R $A; dict incr R $B} 0 {dict incr R $B 3} } } foreach n {0 1 2 3} r [lsort -integer [dict values $R]] { dict incr points($n) $r }

if {$results eq "222222"} break while {[regexp {[^012]} [incr results]]} continue

   }
   return [lmap n {3 2 1 0} {dict values $points($n)}]

}

foreach nth {First Second Third Fourth} nums [groupStage] {

   puts "$nth place:\t[join [lmap n $nums {format %3s $n}] {, }]"

}</lang>

Output:

First place:	  0,   0,   0,   1,  14, 148, 152, 306,   0, 108
Second place:	  0,   0,   4,  33, 338, 172, 164,  18,   0,   0
Third place:	  0,  18, 136, 273, 290,   4,   8,   0,   0,   0
Fourth place:	108, 306, 184, 125,   6,   0,   0,   0,   0,   0

zkl

Translation of: D

Translation of: Python

<lang zkl>combos :=Utils.Helpers.pickNFrom(2,T(0,1,2,3)); // ( (0,1),(0,2) ... ) scoring:=T(0,1,3); histo :=(0).pump(4,List().write,(0).pump(10,List().write,0).copy); //[4][10] of zeros

foreach r0,r1,r2,r3,r4,r5 in ([0..2],[0..2],[0..2],[0..2],[0..2],[0..2]){

  s:=L(0,0,0,0);
  foreach i,r in (T(r0,r1,r2,r3,r4,r5).enumerate()){
     g:=combos[i];
     z:=s[g[0]]+=scoring[r];
     z:=s[g[1]]+=scoring[2 - r];
  }
  foreach h,v in (histo.zip(s.sort())){ h[v]+=1; }

} foreach h in (histo.reverse()){ println(h.apply("%3d ".fmt).concat()) }</lang>

Output:

  0   0   0   1  14 148 152 306   0 108 
  0   0   4  33 338 172 164  18   0   0 
  0  18 136 273 290   4   8   0   0   0 
108 306 184 125   6   0   0   0   0   0