3 Solutions to 2018 Oracle SQL Puzzle of the Week #15

800 Phone Puzzle

For a given 800 phone number (like 1-800-123-4567) find all number-letter representations.

  • Use a single SELECT statement only.
  • Only last 4 digits of the phone number have to be replaced with letters.
  • Exactly 1 letter (out of 4) must be vowel,  the rest – consonant
  • The following table shows all possible mappings:
Digit Maps to
1 1
2 A, B, C
3 D, E, F
4 G, H, I
5 J, K, L
6 M, N, O
7 P, Q, R, S
8 T, U, V
9 W, X, Y, Z
0 0

Solutions:

Essentially, all solutions below share the same idea of generating the letter based phone numbers. The differences are in a way the mapping CTE is created and a way to limit the number of vowels to 1.

Solution #1. Compact form of creating the map CTE with recursive check for the vowels:

WITH map AS (
SELECT digit, letter, '4357' phone
FROM TABLE(sys.odcivarchar2list('00','11','2ABC','3DEF','4GHI',
                                '5JKL','6MNO','7PQRS','8TUV','9WXYZ')) t,
 LATERAL(SELECT SUBSTR(t.column_value,1,1) digit, 
                SUBSTR(t.column_value,1+LEVEL,1) letter
         FROM dual
         CONNECT BY SUBSTR(t.column_value,1+LEVEL,1) IS NOT NULL) x
), res(str, lvl, phone,has_vowel) AS ( 
SELECT letter, 1, phone, 
 CASE WHEN letter IN ('A','E','I','O','U') THEN 1 ELSE 0 END
FROM map 
WHERE SUBSTR(phone,1,1)=TO_CHAR(map.digit) 
UNION ALL 
SELECT res.str || letter, res.lvl+1, res.phone,
       CASE WHEN letter IN ('A','E','I','O','U') 
               OR res.has_vowel=1 THEN 1 ELSE 0 END
FROM res JOIN map ON SUBSTR(res.phone, res.lvl+1,1)=TO_CHAR(map.digit) 
WHERE res.lvl+1<=LENGTH(res.phone) 
  AND NOT (letter IN ('A','E','I','O','U') AND res.has_vowel=1)
) 
SELECT '1-800-123-' || str phone 
FROM res
WHERE lvl=LENGTH(phone)
  AND has_vowel=1

Solution #2. Using more efficient way of creating the map CTE :

WITH x AS (
SELECT ROWNUM-1 digit,COLUMN_VALUE letters
FROM TABLE(sys.odcivarchar2list('0','1','ABC','DEF','GHI','JKL',
                                'MNO','PQRS','TUV','WXYZ'))
), map AS (
SELECT digit, SUBSTR(letters, level, 1) letter, '4357' phone
FROM x
CONNECT BY SUBSTR(letters, level, 1) IS NOT NULL
       AND PRIOR digit = digit 
       AND PRIOR DBMS_RANDOM.VALUE IS NOT NULL
), res(str, lvl, phone,has_vowel) AS ( 
SELECT letter, 1, phone, 
       CASE WHEN letter IN ('A','E','I','O','U') THEN 1 ELSE 0 END
FROM map 
WHERE SUBSTR(phone,1,1)=TO_CHAR(map.digit) 
UNION ALL 
SELECT res.str || letter, res.lvl+1, res.phone,
       CASE WHEN letter IN ('A','E','I','O','U') 
              OR res.has_vowel=1 THEN 1 ELSE 0 END
FROM res JOIN map ON SUBSTR(res.phone, res.lvl+1,1)=TO_CHAR(map.digit) 
WHERE res.lvl+1<=LENGTH(res.phone) 
  AND NOT (letter IN ('A','E','I','O','U') AND res.has_vowel=1)
) 
SELECT '1-800-123-' || str phone 
FROM res
WHERE lvl=LENGTH(phone)
 AND has_vowel=1

Solution #3. Much more efficient way of creating the map CTE and using Regular Expression to limit the vowels :

WITH d AS ( 
SELECT LEVEL+1 n, CASE WHEN LEVEL+1 IN (7,9) THEN 4 ELSE 3 END cnt,
       '4357' phone
FROM dual 
CONNECT BY LEVEL<=8 
), a AS ( 
SELECT CHR(ASCII('A')+LEVEL-1) letter, ROWNUM rn 
FROM dual 
CONNECT BY CHR(ASCII('A')+LEVEL-1)<='Z' 
), x AS ( 
SELECT n, 
       1+NVL(SUM(cnt) OVER(ORDER BY n ROWS BETWEEN UNBOUNDED PRECEDING 
                                           AND 1 PRECEDING),0) c1, 
       SUM(cnt) OVER(ORDER BY n) c2,
       phone
FROM d 
), map AS ( 
SELECT n digit, letter, x.phone
FROM x JOIN a ON a.rn BETWEEN x.c1 AND x.c2 
UNION 
SELECT ROWNUM-1, TO_CHAR(ROWNUM-1), x.phone
FROM x
WHERE ROWNUM<=2
), res(str, lvl) AS ( 
SELECT letter, 1 
FROM map 
WHERE SUBSTR(map.phone,1,1)=TO_CHAR(map.digit) 
UNION ALL 
SELECT res.str || letter, res.lvl+1
FROM res JOIN map ON SUBSTR(map.phone, res.lvl+1,1)=TO_CHAR(map.digit) 
WHERE res.lvl+1<=LENGTH(map.phone) 
 AND REGEXP_COUNT(res.str || letter,'[AEIOU]')<=1
) 
SELECT str phone 
FROM res 
WHERE lvl=4
 AND REGEXP_COUNT(str,'[AEIOU]')=1

You can execute the above SQL statements in Oracle Live SQL environment.
My Oracle Group on Facebook:

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

Further Reading:

Would you like to read about many more tricks and puzzles?

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

Advertisements

How to generate a list of first N binary numbers in Oracle SQL?

In my recent post I showed how to convert a decimal number (i.e. an integer) into a binary string. We can build upon that technique to answer the question:

WITH x AS (
SELECT LEVEL n
FROM dual
CONNECT BY LEVEL<=50
)
SELECT x.N, y.bin
FROM x, LATERAL (SELECT LISTAGG(SIGN(BITAND(x.N, POWER(2,LEVEL-1))),'') 
                        WITHIN GROUP(ORDER BY LEVEL DESC) bin
                 FROM dual
                 CONNECT BY POWER(2, LEVEL-1)<=x.N) y

Note the LATERAL keyword (Oracle 12c new feature) that enables us to reference “x” in the inline view “y”. In pre-12c world, we would have to use TABLE/CAST/MULTISET function composition to achieve the same result:

WITH x AS (
SELECT LEVEL n
FROM dual
CONNECT BY LEVEL<=50
)
SELECT x.N, y.column_value bin
FROM x, TABLE(CAST(MULTISET(
          SELECT LISTAGG(SIGN(BITAND(x.N, POWER(2,LEVEL-1))),'') 
                 WITHIN GROUP(ORDER BY LEVEL DESC) bin
          FROM dual
          CONNECT BY POWER(2, LEVEL-1)<=x.N) AS sys.odcivarchar2list)) y

The idea used in the following query is based on a totally different approach. It builds a string of “0”s and “1”s in a loop until its length reaches a desired value:

WITH x(v, n) AS (
SELECT column_value, 1
FROM TABLE(sys.odcivarchar2list('0','1'))
UNION ALL
SELECT x.v || t.column_value, x.n+1
FROM TABLE(sys.odcivarchar2list('0','1')) t JOIN x on LENGTH(x.v)=n
WHERE n<=CEIL(LOG(2,50))
), y AS (
SELECT NVL(LTRIM(x.v,'0'),'0') bin, ROWNUM-1 dec
FROM x
WHERE n=(SELECT MAX(n) FROM x)
)
SELECT *
FROM y
WHERE dec<=50

To better understand the above query, try the following one:

SELECT *                            
FROM TABLE(sys.odcivarchar2list('0','1')), 
     TABLE(sys.odcivarchar2list('0','1')),
     TABLE(sys.odcivarchar2list('0','1')),
     TABLE(sys.odcivarchar2list('0','1'))

If we put enough tables in the Cartesian product and concatenate all column_value columns in a single character string expression, we will achieve our goal. The challenge with this approach is to dynamically change the number of the tables in the FROM clause. This can be simulated in the recursive WITH clause by repeatedly adding more and more collections of bits (0 and 1).

My Oracle Group on Facebook:

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

Would you like to read about many more tricks and puzzles?

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

 

Solutions to Puzzle of the Week #13

Puzzle of the Week #13:

Table Setup and Puzzle description can be located here

Expected Result:

  ID FULL_NAME                             GROUP_ID
---- ----------------------------------- ----------
   8 Oscar Pedro Fernando Rodriguez               1
   9 Rodriguez, Oscar Pedro Fernando              1
  10 Oscar Fernando Rodriguez Pedro               1
   1 John Smith                                   2
   2 John L. Smith                                2
   4 Smith, John                                  2
   5 Tom Khan                                     3
  11 KHAN, TOM S.                                 3

Solutions:

#1. Using CTE (Recursive WITH) and LISTAGG

WITH x AS (
SELECT name_id, UPPER(REGEXP_REPLACE(full_name,'[[:punct:]]')) full_name
FROM name_list
), y(id, token, lvl) AS (
SELECT name_id, REGEXP_SUBSTR(full_name, '[^ ]+', 1, 1), 1 
FROM x
UNION ALL
SELECT x.name_id, REGEXP_SUBSTR(full_name, '[^ ]+', 1, y.lvl+1), y.lvl+1
FROM x JOIN y ON x.name_id=y.id AND REGEXP_SUBSTR(full_name, '[^ ]+', 1, y.lvl+1) IS NOT NULL
), z AS (
SELECT id, LISTAGG(token, ' ') WITHIN GROUP(ORDER BY token) ordered_name, 
       COUNT(*)OVER(PARTITION BY LISTAGG(token, ' ') WITHIN GROUP(ORDER BY token)) cnt,
       DENSE_RANK()OVER(ORDER BY LISTAGG(token, ' ') WITHIN GROUP(ORDER BY token)) group_id
FROM y
WHERE LENGTH(token)>1
GROUP BY id
)
SELECT z.id, n.full_name, DENSE_RANK()OVER(ORDER BY group_id) group_id
FROM z JOIN name_list n ON z.id=n.name_id
WHERE z.cnt>1
ORDER BY 3, 1;

  ID FULL_NAME                                  GROUP_ID
--- ---------------------------------------- ----------
  8 Oscar Pedro Fernando Rodrigues                    1
  9 Rodrigues, Oscar Pedro Fernando                   1
 10 Oscar Fernando Rodrigues Pedro                    1
  1 John Smith                                        2
  2 John L. Smith                                     2
  4 Smith, John                                       2
  5 Tom Khan                                          3
 11 KHAN, TOM S.                                      3

Explanation:

The key idea is to split each name into multiple name tokens, then sort and merge them back into a single line. Matching (duplicate) names will have the same merged line so we could use it to identify duplicates. DENSE_RANK analytic function is used to generate sequential group id values.

The same idea is used in the solution below. The only difference is the way to split the names into tokens.

#2: Using CONNECT BY and TABLE/CAST/MULTISET functions

 WITH x AS (
SELECT name_id, UPPER(REGEXP_REPLACE(full_name,'[[:punct:]]')) full_name
FROM name_list
), y AS (
SELECT name_id AS id, y.column_value AS token
FROM x,
     TABLE(CAST(MULTISET(SELECT REGEXP_SUBSTR(x.full_name, '[^ ]+', 1, LEVEL) token
                    FROM dual
                    CONNECT BY LEVEL <= LENGTH(full_name)-LENGTH(REPLACE(full_name,' '))+1
                        )
                AS sys.odcivarchar2list)
          ) y
WHERE LENGTH(y.column_value)>1
), z AS (
SELECT id, LISTAGG(token, ' ') WITHIN GROUP(ORDER BY token) ordered_name,
       COUNT(*)OVER(PARTITION BY LISTAGG(token, ' ') WITHIN GROUP(ORDER BY token)) cnt,
       DENSE_RANK()OVER(ORDER BY LISTAGG(token, ' ') WITHIN GROUP(ORDER BY token)) group_id
FROM y
WHERE LENGTH(token)>1
GROUP BY id
)
SELECT z.id, n.full_name, DENSE_RANK()OVER(ORDER BY group_id) group_id
FROM z JOIN name_list n ON z.id=n.name_id
WHERE z.cnt>1
ORDER BY 3, 1;

  ID FULL_NAME                                  GROUP_ID
---- ---------------------------------------- ----------
   8 Oscar Pedro Fernando Rodrigues                    1
   9 Rodrigues, Oscar Pedro Fernando                   1
  10 Oscar Fernando Rodrigues Pedro                    1
   1 John Smith                                        2
   2 John L. Smith                                     2
   4 Smith, John                                       2
   5 Tom Khan                                          3
  11 KHAN, TOM S.                                      3