Tricky problem -- sql server programming

sql server programming : Tricky problem

Anith Sen
12/28/2004 3:51:14 PM

For simplicity, create a view with the ranks:

CREATE VIEW vw ( Player, rank )
AS
SELECT s1.Player,
( SELECT COUNT( * )
FROM Scores s2
WHERE s2.Score <= s1.Score )
FROM Scores s1

Now, do:

SELECT n1, v1.Player, n2, v2.Player
FROM ( SELECT number + 1, 16 - number
FROM master..spt_values
WHERE type = 'P'
AND number < 8 ) Nbrs ( n1, n2 )
LEFT JOIN vw v1
ON n1 = v1.rank
LEFT JOIN vw v2
ON n2 = v2.rank ;

You might want to replace the undocumented spt_values with a table of
sequential numbers which could make similar queries more versatile. Check
google archives for examples.

--
Anith

Anith Sen
12/28/2004 4:57:22 PM

Do you have another table which represents the players score for each round?
A skeleton DDL might look like:

CREATE TABLE Rounds (
Rnd_Nbr INT NOT NULL,
Player INT NOT NULL,
Score INT NOT NULL,
PRIMARY KEY ( Rnd_Nbr, Player ) );

This will allow you to track the ranks for each round. As a non-specific
case, you might want to have some information about the number of players in
each round as well. This will help you write a generalized query using the
same logic without referring to to 16, 8 etc.

--
Anith

Lasse Edsvik
12/28/2004 9:24:21 PM

Hello

I have 3 tables

CREATE TABLE #Players (
Player char(1)
)

CREATE TABLE #Scores (
Score smallint NOT NULL,
Player char(1) NOT NULL
)

CREATE TABLE #Knockout (
Player char(1),
Player_Opponent char(1),
Player_Winner char(1)
)

INSERT INTO #Players(Player)VALUES('A')
INSERT INTO #Players(Player)VALUES('B')
INSERT INTO #Players(Player)VALUES('C')
INSERT INTO #Players(Player)VALUES('D')
INSERT INTO #Players(Player)VALUES('E')
INSERT INTO #Players(Player)VALUES('F')
INSERT INTO #Players(Player)VALUES('G')
INSERT INTO #Players(Player)VALUES('H')
INSERT INTO #Players(Player)VALUES('I')
INSERT INTO #Players(Player)VALUES('J')

INSERT INTO #Scores(Player,Score)VALUES('A',-1)
INSERT INTO #Scores(Player,Score)VALUES('B',-2)
INSERT INTO #Scores(Player,Score)VALUES('C',-3)
INSERT INTO #Scores(Player,Score)VALUES('D',-4)
INSERT INTO #Scores(Player,Score)VALUES('E',-5)
INSERT INTO #Scores(Player,Score)VALUES('F',-6)
INSERT INTO #Scores(Player,Score)VALUES('G',-7)
INSERT INTO #Scores(Player,Score)VALUES('H',-8)
INSERT INTO #Scores(Player,Score)VALUES('I',-9)
INSERT INTO #Scores(Player,Score)VALUES('J',-10)

----------

I did this just as testing since I knew i was gonna run into trouble, so
dont smack me in the head with your pointer just yet Celko. :)

I'll explain abit what i'm about to do.

As you might figured out this is a golf-reporting kinda thing for a
tournament, but nothing professional, just for home use.

First round is played as stroke, the lower score is the better. I insert
those scores into one table #Scores. No problem so far.

Round 2, 16 players with best score (lowest) qualifies to a "Knockout"-round
(versus) so player with best score plays the one ranked 16th from first
round, 2nd plays 15th ranked and so on

like in this case (number is "rank" from stroke table):

1 J vs 16 NULL
2 I vs 15 NULL
3 H vs 14 NULL
4 G vs 13 NULL
5 F vs 12 NULL
6 E vs 11 NULL
7 D vs 10 A
8 C vs 9 B

since there are not 16 players in first round i somehow need to "generate"
them as NULL, meaning player with no opponent is winner.

same goes with if there aren't even 8 players in round which will be a
problem too.

How i generate that into table #Knockout? Machine isnt something fancy so I
might not be able to run queries that require much cpu and mem, so in worst
case i have to denormalize things..... if this is close to normal that is

Any help would be appriciated.

TIA
/Lasse

Hugo Kornelis
12/28/2004 10:35:56 PM

[quoted text, click to view]

(snip)
[quoted text, click to view]

Hi Lasse,

First, I'd do a bit of redesigning on your tables:

CREATE TABLE #Players (
Player char(1) NOT NULL,
Score smallint DEFAULT NULL,
PRIMARY KEY (Player)
)

I combined the #Players table and the #Scores table, since there will be
only one score per player. To enable entry of players before the first
round is played, the Score is nullable.
I also declared the primary key. This automatically creates an index, that
will probably speed up several queries using this table.

CREATE TABLE #Knockout (
RoundNo tinyint NOT NULL,
MatchNo tinyint NOT NULL,
Player char(1) DEFAULT NULL,
Player_Opponent char(1) DEFAULT NULL,
Player_Winner char(1) DEFAULT NULL
PRIMARY KEY (RoundNo, MatchNo),
FOREIGN KEY (Player) REFERENCES #Players(Player),
FOREIGN KEY (Player_Opponent) REFERENCES #Players(Player),
FOREIGN KEY (Player_Winner) REFERENCES #Players(Player),
CHECK (Player_Winner IN (Player, Player_Opponent))
)

As you see, I included RoundNo, as I assume you don't want to use seperate
tables for each knockout round. The MatchNo will be needed later, to make
sure that the winner from match 1 (player ranked 1 vs player ranked 16)
will meet the winner from match 8 (players ranked 8 and 9), as is usually
required in tournaments.
The combination of RoundNo and MatchNo is primary key, of course. Ideally,
there would also be UNIQUE constraints for (RoundNo, Player) and (RoundNo,
Player_Opponent), but since both Player_Opponent (in your 10-player
example) and Player (with less than 8 competing players) can be NULL, this
is not an option. (However, it is worth considering creating only 4
matches for the first knockout round if there are less than 9 players, as
a 8-match first round will have no matches at all to begin with).

INSERT INTO #Players(Player,Score)VALUES('A',-1)
INSERT INTO #Players(Player,Score)VALUES('B',-2)
INSERT INTO #Players(Player,Score)VALUES('C',-3)
INSERT INTO #Players(Player,Score)VALUES('D',-4)
INSERT INTO #Players(Player,Score)VALUES('E',-5)
INSERT INTO #Players(Player,Score)VALUES('F',-6)
INSERT INTO #Players(Player,Score)VALUES('G',-7)
INSERT INTO #Players(Player,Score)VALUES('H',-8)
INSERT INTO #Players(Player,Score)VALUES('I',-9)
INSERT INTO #Players(Player,Score)VALUES('J',-10)

Using your test data and a standard numbers table (if you don't have one
yet, go create one now: it is very useful in many queries. Check out this
article: http://www.aspfaq.com/show.asp?id=2516), you can populate the
first knockout round using this query:

INSERT #Knockout (RoundNo, MatchNo, Player, Player_Opponent)
SELECT 1, N.n, P1.Player, P2.Player
FROM numbers AS N
LEFT JOIN #Players AS P1
ON (SELECT COUNT(*)
FROM #Players
WHERE Score < P1.Score
OR (Score = P1.Score AND Player > P1.Player)) = N.n - 1
LEFT JOIN #Players AS P2
ON (SELECT COUNT(*)
FROM #Players
WHERE Score < P2.Score
OR (Score = P2.Score AND Player > P2.Player)) = 16 - N.n
WHERE N.n BETWEEN 1 AND 8

(Note that I use Player as tiebreaker if two players have the same score;
change that to whatever you want to use as tiebreaker; if you are sure
that there will never be ties, the query can be simplified and sped up;
for both subqueries, you'll only need the WHERE Score < Pn.Score clause)

Best, Hugo
--

Lasse Edsvik
12/28/2004 10:38:07 PM

Hugo,

CREATE TABLE #Players (
Player char(1) NOT NULL,
Score smallint DEFAULT NULL,
PRIMARY KEY (Player)
)

I cannot have score in players table since each month a new round starts
again with round 1 played as stroke (score)

[quoted text, click to view]

Lasse Edsvik
12/28/2004 10:47:07 PM

Hugo

as for tiebreakers, i will add lots of attributes to scoretable, as number
of greens hit in regulation, avarage putts in regulation, average putts all,
so there wont be any ties :) so how to remove that part?

[quoted text, click to view]

Lasse Edsvik
12/28/2004 11:00:37 PM

Anith,

thanks,

one question, how i do on round 3, when the 8 winners face eachother, and
based by the rank from round 1

1 vs 8
2 vs 7
3 vs 6
4 vs 5

may not be 1-8 in rank as i did there, but "best ranked from round 1" to
left and the lowest ranked winners on right

i always gotta keep track of how they ranked on round 1

Thanks for helping
/Lasse

[quoted text, click to view]

Lasse Edsvik
12/29/2004 3:06:26 AM

problem is to get it rendered as top 8 vs bottom 8, if they are 18 players
of if there arent....

lets say I denormalize things and put a column Rank in #Scores table, how
would would #Knockout look then?

not sure if i should create a view for each round in a "
[quoted text, click to view]

Anith Sen
12/29/2004 7:51:50 AM

Lasse,

[quoted text, click to view]

You can rank the data in several ways you want using a single query, for
instance here is an example ranking the orders with Freight ( using the
Orders table in Northwind which has 830 rows )

SELECT o1.OrderID, o1.Freight ,
SUM( CASE WHEN o2.Freight <= o1.Freight
THEN 1 END ) AS "rank_asc",
SUM( CASE WHEN o2.Freight >= o1.Freight
THEN 1 END ) AS "rank_desc"
FROM Northwind..Orders o1,
Northwind..Orders o2
GROUP BY o1.OrderID, o1.Freight
ORDER BY o1.Freight ;

You can easily derive the required n ranks from such datasets easily.

--
Anith

Hugo Kornelis
12/29/2004 11:34:09 AM

[quoted text, click to view]

Hi Lasse,

If the score value in itself is unique, you can simplify the query to

INSERT #Knockout (RoundNo, MatchNo, Player, Player_Opponent)
SELECT 1, N.n, P1.Player, P2.Player
FROM numbers AS N
LEFT JOIN #Players AS P1
ON (SELECT COUNT(*)
FROM #Players
WHERE Score < P1.Score) = N.n - 1
LEFT JOIN #Players AS P2
ON (SELECT COUNT(*)
FROM #Players
WHERE Score < P2.Score) = 16 - N.n
WHERE N.n BETWEEN 1 AND 8

If the score value can contain duplicates and you need another column to
make it unique, use that column instead of the Player column (in my first
suggestion). If you need several columns, things can get tricky. The
general scheme will be

WHERE Score < P1.Score
OR (Score = P1.Score AND TieBreak1 < P1.TieBreak1)
OR (Score = P1.Score AND TieBreak1 = P1.TieBreak1 AND TieBreak2
< TieBreak2)
....

Based on one of your replies to Anith, I have a question about the second
knockout round (third total round). Your first KO round looks like this:
(1) 1 - 16 Winner: 16
(2) 2 - 15 Winner: 2
(3) 3 - 14 Winner: 3
(4) 4 - 13 Winner: 13
(5) 5 - 12 Winner: 5
(6) 6 - 11 Winner: 11
(7) 7 - 10 Winner: 7
(8) 8 - 9 Winner: 8
Now what will the second round look like? A common approach is this:
(9') Winner (1) - Winner (8) 16 - 8
(10') Winner (2) - Winner (7) 2 - 7
(11') Winner (3) - Winner (6) 3 - 11
(12') Winner (4) - Winner (5) 13 - 5
But somewhere, you write that this will also be based on the ranks after
round 1:
(9'') 2 - 16
(10'') 3 - 13
(11'') 5 - 11
(12'') 7 - 8
As you see, the different algorithms result in different couplngs of
players. If I understand you correctly, you want to implement code to get
the last set of results (9'' through 12''), even though the first set (9'
through 12') is more common in sports events. Is my understanding correct?

The code to generate the correct couplings for the rounds after the first
KO round will depend on the answer to the above question...

Best, Hugo
--

Lasse Edsvik
12/29/2004 1:36:11 PM

Hugo,

thanks for helping so far :)

(1) 1 - 16 Winner: 16
(2) 2 - 15 Winner: 2
(3) 3 - 14 Winner: 3
(4) 4 - 13 Winner: 13
(5) 5 - 12 Winner: 5
(6) 6 - 11 Winner: 11
(7) 7 - 10 Winner: 7
(8) 8 - 9 Winner: 8

as 2nd knockout round there will be 4 games played, the winners with highest
rank from first round will be playing the players with lowest rank (that
ofcourse won first knockout-round).

so in that case (best ranked to left)

(1) 2 - 16
(2) 3 - 13
(3) 5 - 11
(4) 7 - 8

Was wondering if I was to simplify things and calculate rank and put it as a
column in Score-table, it would make things alot easier but I have another
problem. Not sure if your query fixes it but lets say one player cannot play
2nd knockout round, and somehow i need to get ones opponent as NULL, or if
both players dont play, someone in 3rd kockout round will advance to next
round since he dont have an opponent to play.

TIA
/Lasse

[quoted text, click to view]

Hugo Kornelis
12/29/2004 11:03:31 PM

[quoted text, click to view]

Hi Lasse,

I believe that the following script will work for you. I tested it with as
little as two competitors and as many as 18 and I couldn't find any
errors.

Adding rank as an extra column, as you suggest, would simplify the
queries, but it will have it's own complexity. What if an erroneaous score
is corrected after the ranks are calculated? Ideally, rank would be
calculated in a trigger, but -like I said- this brings some complexitiy of
it's own.

I suggest you try if the code below performs adequately in your system
before trying other solutions. :-)

CREATE TABLE #Players (
Player char(1) NOT NULL,
Score smallint DEFAULT NULL,
PRIMARY KEY (Player)
)

go
CREATE TABLE #Knockout (
RoundNo tinyint NOT NULL,
MatchNo tinyint NOT NULL,
Player char(1) DEFAULT NULL,
Player_Opponent char(1) DEFAULT NULL,
Player_Winner char(1) DEFAULT NULL
PRIMARY KEY (RoundNo, MatchNo),
FOREIGN KEY (Player) REFERENCES #Players(Player),
FOREIGN KEY (Player_Opponent) REFERENCES #Players(Player),
FOREIGN KEY (Player_Winner) REFERENCES #Players(Player),
CHECK (Player_Winner IN (Player, Player_Opponent))
)

go

INSERT INTO #Players(Player,Score)VALUES('A',-1)
INSERT INTO #Players(Player,Score)VALUES('B',-2)
INSERT INTO #Players(Player,Score)VALUES('C',-3)
INSERT INTO #Players(Player,Score)VALUES('D',-4)
INSERT INTO #Players(Player,Score)VALUES('E',-5)
INSERT INTO #Players(Player,Score)VALUES('F',-6)
INSERT INTO #Players(Player,Score)VALUES('G',-7)
INSERT INTO #Players(Player,Score)VALUES('H',-8)
INSERT INTO #Players(Player,Score)VALUES('I',-9)
INSERT INTO #Players(Player,Score)VALUES('J',-10)
go

-- Find couplings for round 2 (first KO round)
INSERT #Knockout (RoundNo, MatchNo, Player, Player_Opponent)
SELECT 2, N.n, P1.Player, P2.Player
FROM numbers AS N
LEFT JOIN #Players AS P1
ON (SELECT COUNT(*)
FROM #Players
WHERE Score < P1.Score
OR (Score = P1.Score AND Player > P1.Player)) = N.n - 1
LEFT JOIN #Players AS P2
ON (SELECT COUNT(*)
FROM #Players
WHERE Score < P2.Score
OR (Score = P2.Score AND Player > P2.Player)) = 16 - N.n
WHERE N.n BETWEEN 1 AND 8
go

-- For testing, randomize 2nd round's winners
UPDATE #Knockout
SET Player_Winner = CASE WHEN LEFT(NEWID(),1) BETWEEN '0' AND '7'
THEN COALESCE(Player, Player_Opponent)
ELSE COALESCE(Player_Opponent, Player) END
WHERE RoundNo = 2
go

-- Find couplings for round 3 (second KO round)
INSERT #Knockout (RoundNo, MatchNo, Player, Player_Opponent)
SELECT 3, N.n, P1.Player, P2.Player
FROM numbers AS N
LEFT JOIN #Players AS P1
ON P1.Player IN (SELECT Player_Winner
FROM #Knockout
WHERE RoundNo = 2)
AND (SELECT COUNT(*)
FROM #Players
WHERE Player IN (SELECT Player_Winner
FROM #Knockout
WHERE RoundNo = 2)
AND Score < P1.Score
OR (Score = P1.Score AND Player > P1.Player)) = N.n - 1
LEFT JOIN #Players AS P2
ON P2.Player IN (SELECT Player_Winner
FROM #Knockout
WHERE RoundNo = 2)
AND (SELECT COUNT(*)
FROM #Players
WHERE Player IN (SELECT Player_Winner
FROM #Knockout
WHERE RoundNo = 2)
AND Score < P2.Score
OR (Score = P2.Score AND Player > P2.Player)) = 8 - N.n
WHERE N.n BETWEEN 1 AND 4
go

-- For testing, randomize 3rd round's winners
UPDATE #Knockout
SET Player_Winner = CASE WHEN LEFT(NEWID(),1) BETWEEN '0' AND '7'
THEN COALESCE(Player, Player_Opponent)
ELSE COALESCE(Player_Opponent, Player) END
WHERE RoundNo = 3
go

-- Find couplings for round 4 (third KO round)
INSERT #Knockout (RoundNo, MatchNo, Player, Player_Opponent)
SELECT 4, N.n, P1.Player, P2.Player
FROM numbers AS N
LEFT JOIN #Players AS P1
ON P1.Player IN (SELECT Player_Winner
FROM #Knockout
WHERE RoundNo = 3)
AND (SELECT COUNT(*)
FROM #Players
WHERE Player IN (SELECT Player_Winner
FROM #Knockout
WHERE RoundNo = 3)
AND Score < P1.Score
OR (Score = P1.Score AND Player > P1.Player)) = N.n - 1
LEFT JOIN #Players AS P2
ON P2.Player IN (SELECT Player_Winner
FROM #Knockout
WHERE RoundNo = 3)
AND (SELECT COUNT(*)
FROM #Players
WHERE Player IN (SELECT Player_Winner
FROM #Knockout
WHERE RoundNo = 3)
AND Score < P2.Score
OR (Score = P2.Score AND Player > P2.Player)) = 4 - N.n
WHERE N.n BETWEEN 1 AND 2
go

-- For testing, randomize 4th round's winners
UPDATE #Knockout
SET Player_Winner = CASE WHEN LEFT(NEWID(),1) BETWEEN '0' AND '7'
THEN COALESCE(Player, Player_Opponent)
ELSE COALESCE(Player_Opponent, Player) END
WHERE RoundNo = 4
go

-- Find couplings for round 5 (fourth KO round)
INSERT #Knockout (RoundNo, MatchNo, Player, Player_Opponent)
SELECT 5, N.n, P1.Player, P2.Player
FROM numbers AS N
LEFT JOIN #Players AS P1
ON P1.Player IN (SELECT Player_Winner
FROM #Knockout

--CELKO--
12/30/2004 11:02:03 AM

[quoted text, click to view]
trouble, so don't smack me in the head with your pointer just yet
Celko. :) <<

Sorry to be late beating you :) This will give you (low, high) pairs
for (n) rankings.

BEGIN
DECLARE @n INTEGER;
SET @n = 7;

SELECT seq AS low_score,
CASE WHEN seq <= (@n - seq)
THEN (@n - seq)+1
ELSE NULL END AS high_score
FROM Sequence AS S1
WHERE S1.seq
<= CASE WHEN @n%2 = 1
THEN FLOOR(@n/2)+1
ELSE (@n/2) END ;
END;

Lasse Edsvik
12/30/2004 7:40:49 PM

Hugo,

I got it all sorted out now thanks to you :)

Drinks are on me, just come on over :)

[quoted text, click to view]

Hugo Kornelis
12/31/2004 12:40:02 AM

[quoted text, click to view]

Hi Lasse,

Judging by your name, I guess that would be a long drive north, a boat
ferry and another long drive north. I might be quite thirsty after such a
long trip!!

Glad to hear you got it sorted out. Have fun with the tournaments!

All the best for 2005!

Best, Hugo
--

Got something to say? Click here to post a reply to this thread.

Don't see what you're looking for? Try a search.

View other messages about sql server programming

View Other Months
January 2003
March 2003
April 2003
May 2003
June 2003
July 2003
August 2003
September 2003
October 2003
November 2003
December 2003
January 2004
February 2004
March 2004
April 2004
May 2004
June 2004
July 2004
August 2004
September 2004
October 2004
November 2004
December 2004
January 2005
February 2005
March 2005
April 2005
May 2005
June 2005
July 2005
August 2005
September 2005
October 2005
November 2005
December 2005
January 2006
February 2006
March 2006
April 2006
May 2006
June 2006
July 2006
August 2006
September 2006
October 2006
November 2006
December 2006
January 2007
February 2007
March 2007
April 2007
May 2007
June 2007
July 2007
August 2007
September 2007
October 2007
November 2007
April 2008
August 2008

home · blog · groups

Questions? Comments? Contact the dn