Puzzle of the week #4 Solution

Round 1 Playoff Schedule

N teams (N between 1 and 32) just finished the season and are all qualified for the playoff. If the number of teams were 2, 4, 8, 16, or 32 (powers of 2), the playoff schedule would be trivial: 1st team plays vs last team, 2nd – vs 2nd from the last, etc. However, there is no guarantee that the number of teams would be a power of 2. The challenge is to write a single SELECT statement that accepts the number of teams as a parameter and generates the round 1 pairings.

There should be 1, 2, 4, 6, or 16 teams (power of 2) in the 2nd round.

Solution

WITH x AS (
  SELECT &teams p
  FROM dual
), y AS (
SELECT ROWNUM home, POWER(2,CEIL(LOG(2,p)))-ROWNUM+1 away, 
       POWER(2,CEIL(LOG(2,p))) maxp
FROM dual, x
CONNECT BY LEVEL<=POWER(2,CEIL(LOG(2,p))-1)
)
SELECT CASE WHEN away<=p AND p>1 THEN ROWNUM+p-maxp END AS "Game #",
       CASE WHEN away>p AND p>1 THEN 'Team-' || home || ' advances to Round 2'
            WHEN p=1 THEN 'Team-1 is a Champion!'
            ELSE 'Team-' || home || ' vs Team-' || away
       END AS "Playoff Round 1 Pairings"
FROM y, x
ORDER BY 1 NULLS LAST, home

Explanation

The trick here was to figure out which teams should be playing and which simply advance to the Round 2. Suppose that we have a power of 2 number of teams. Then top 1st team plays against the bottom 1st, top 2ng vs bottom 2nd, etc. If there are N teams, then we will have N/2 games. This is the simplest case. What if we have 6 teams? We should add 2 fake teams to “round up” the number of teams to the nearest power of 2 that is greater or equal to N. For 6 teams, we round up to 8. Those 2 fake teams should be paired against top 2 teams, and this gives us an answer which teams should advance to the Round 2 without playing. General rule, if we have to add K “faked teams” to “round up” to the nearest power of 2 number, this means that top K teams advance to the next round without playing.

We used CEIL, LOG, and POWER functions to get the next power of 2 for any whole N:

POWER(2,CEIL(LOG(2,p)))

 

If you like this post, you may want to join my new Oracle group on Facebook: https://www.facebook.com/groups/sqlpatterns/

For more tricks and cool techniques check my book “Oracle SQL Tricks and Workarounds” for instructions.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s