This question is inspired by ongoing tournament of "the hooligan's game played by gentlemen", the Rugby World Cup, which has just completed the pool stage. There are 20 teams in the tournament, and they are divided into 4 pools of 5 teams each. During the pool stage each team plays against all the other teams in their pool (a total of 10 matches per pool), and the top 2 teams of each pool progress to the knockout stage.

At the end of the pool stage there is a table for each pool showing the number of wins, losses and draws for each team. The challenge for this question is to write a program that inputs the count of wins, losses and draws for each team in a pool, and from that information outputs the individual results of each of the 10 matches (who won, lost or drew against who) if possible or outputs an error message if not.

For example, here is the table for Pool D of this year's tournament:

            Win    Loss    Draw
Canada        0       4       0
France        3       1       0
Ireland       4       0       0
Italy         2       2       0
Romania       1       3       0

From this information, we can deduce that Ireland won against Canada, France, Italy and Romania, because they won all their games. France must have won against Canada, Italy and Romania but lost to Ireland, because they only lost one and it must have been to the undefeated Ireland. We have just worked out that Italy lost to Ireland and France, so they must have won against Canada and Romania. Canada lost all their games, and so Romania's win must have been against Canada.

         Canada  France Ireland   Italy Romania
Canada        -       L       L       L       L
France        W       -       L       W       W
Ireland       W       W       -       W       W
Italy         W       L       L       -       W
Romania       W       L       L       L       -

Here's a more complicated (fictional) example:

            Win    Loss    Draw
Canada        3       1       0
France        1       2       1
Ireland       0       3       1
Italy         0       2       2
Romania       4       0       0

In this case, we can deduce that Romania won against Canada, France, Italy and Ireland, because they won all their games. Canada must have won against Ireland, Italy and France but lost to Romania. We have just worked out that Italy lost to Romania and Canada, so they must have drawn against France and Ireland. That means Ireland drew with Italy and lost to everyone else, and therefore France must have beaten Ireland, drawn with Italy and lost to Canada and Romania.

         Canada  France Ireland   Italy Romania
Canada        -       W       W       W       L
France        L       -       W       D       L
Ireland       L       L       -       D       L
Italy         L       D       D       -       L
Romania       W       W       W       W       -

Some tables are unsolvable, for example this year's Pool B, in which 3 teams got the same W/L/D totals:

            Win    Loss    Draw
Japan         3       1       0
Samoa         1       3       0
Scotland      3       1       0
South Africa  3       1       0
United States 0       4       0

However some tables with duplicate rows are solvable, like this (fictional) one:

            Win    Loss    Draw
Japan         4       0       0
Samoa         0       3       1
Scotland      2       2       0
South Africa  0       3       1
United States 3       1       0


Your program or function should accept 15 numbers specifying the win, loss and draw totals for each of the 5 teams. You can use any delimiter you want, input the numbers in row or column major order, and accept the numbers either via stdin or passed via an array to a function.

Because wins + losses + draws = 4, you can omit one of the values and work it out from the others if you wish, meaning that you only have to input 10 numbers.

You don't need to input any team names.

Sample input:

3 1 0
1 2 1
0 3 1
0 2 2
4 0 0


Your program or function's output should be in the form of a 5 x 5 grid printed to stdout, or an array returned from a function. Each element should specify whether the team given in the row position won, lost or drew against the team in the column position. The row ordering for the output should match the input. You can define what denotes a win, loss or draw, so the letters W, L, D or digits 0 1 2 or whatever you want can be used as long as they are clearly defined and can be distinguished from each other. Diagonal elements are undefined, you can output anything, but it should be the same in each case. Values can be separated with commas, spaces or whatever character you like, or not character. Both input and output can be formatted with all values on a single line if desired.

If a table does not have a unique solution then you must output a simple error message of your choice.

Sample output:

- W W W L
L - W D L
L L - D L
L D D - L
W W W W -

Sample output for unsolvable table:

dunno mate

This is code golf so the shortest program in bytes wins.

Pic related (Japan versus South Africa):

enter image description here


2 Answers 2


CJam, 57 49 47 45 bytes


This is an anonymous function that pops a two-dimensional array from the stack and leaves one in return. It contains 2 for wins, 1 for draws and 0 for losses. It also contains 1 for diagonal elements , for which you can output anything. If the problem isn't solvable, the function returns -1.

The code will work online, but it will take a while. Try it in the CJam interpreter.

Test run

$ cat input
3 1 0
1 2 1
0 3 1
0 2 2
4 0 0
$ time cjam results.cjam < input
[1 2 2 2 0]
[0 1 2 1 0]
[0 0 1 1 0]
[0 1 1 1 0]
[2 2 2 2 1]

real    0m1.584s
user    0m4.020s
sys     0m0.146s

How it works

JZb:a e# Push 19 in base 3; wrap each digit in an array. Pushes [[2] [0] [1]].
f{    e# For each row of the input, push it and [[2] [0] [1]]; then:
  .*  e# Repeat 2, 0 and 1 (win, loss, draw) the specified number of times.
  e_  e# Flatten the resulting array.
  1+  e# Append a 1 for the diagonal.
  e!  e# Push all possible permutations.
}     e#
:m*   e# Cartesian product; push all possible combinations of permutations.
:e_   e# Flatten the results.
5f/   e# Split into rows of length 5.
{     e# Filter:
  _z  e#   Push a transposed copy of the array.
  2\  e#   Swap the result with 2.
  ff- e#   Subtract all elements from 2.
  =   e#   Check for equality.
},    e# Keep the element if `=' pushed 1.
_,(   e# Get the length of the array of solutions and subtract 1.
0@?   e# Keep the array for length 1, push 0 otherwise.
~     e# Either dump the singleton array or turn 0 into -1.

Haskell, 180 177 bytes

import Data.List
a#b|(c,d)<-splitAt a b=c++[0]++d
f t=take 1[x|x<-m(z(#)[0..])$sequence$m(permutations.concat.z(flip replicate)[1,-1,0])t,transpose x==m(m(0-))x]

A win is shown as 1, a loss as -1 and a draw as 0. Diagonal elements are also 0. Unsolvable tables are empty lists, i.e. [].

Usage example: f [[3,1,0],[1,2,1],[0,3,1],[0,2,2],[4,0,0]] -> [[[0,1,1,1,-1],[-1,0,1,0,-1],[-1,-1,0,0,-1],[-1,0,0,0,-1],[1,1,1,1,0]]].

How it works: brute force! Create a list of wins/losses/draws according to the input, e.g. [3,1,0] -> [1,1,1,-1], permute, build all combinations, insert diagonals and keep all tables that are equal to their transposition with all elements negated. Take the first one.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.