This was the title of a thread on OTN's SQL and PL/SQL Forum. Centinul posted an interesting puzzle to be solved by either SQL or PL/SQL here. If you like to puzzle yourself, then stop reading here, and go visit the link (and don't look at the answers of course :-) ).
The puzzle was not only a great way to spend time, it's also a nice show case for hierarchical queries and the answer of Frank Kulash taught me something new. The setup:
rwijk@ORA11GR1> create table matrix (id,a,b,c,d,e,f,g,h,i,j)
2 as
3 select 'A',1,1,1,0,0,0,1,0,1,0 from dual union all
4 select 'B',0,0,0,0,1,1,1,0,1,0 from dual union all
5 select 'C',0,1,1,1,1,0,0,0,0,1 from dual union all
6 select 'D',1,0,0,0,1,0,1,0,0,0 from dual union all
7 select 'E',1,1,0,0,0,0,0,0,0,1 from dual union all
8 select 'F',0,1,1,0,1,1,0,0,0,0 from dual union all
9 select 'G',0,1,0,1,1,1,0,1,0,1 from dual union all
10 select 'H',1,1,0,1,0,0,0,1,0,0 from dual union all
11 select 'I',0,1,1,1,0,1,1,1,0,1 from dual union all
12 select 'J',1,0,0,0,0,0,0,1,0,1 from dual union all
13 select 'K',1,0,0,1,1,1,0,1,1,0 from dual union all
14 select 'L',0,0,1,0,1,1,0,0,1,0 from dual union all
15 select 'M',0,0,1,0,0,0,0,1,1,1 from dual union all
16 select 'N',1,0,1,0,0,0,1,1,1,0 from dual union all
17 select 'O',1,0,0,1,1,0,1,0,0,0 from dual
18 /
Table created.
The table looks like this:
Quoting the challenge:
Our goal is from a start position identified as (A,E), First Row, Fifth column, traverse DOWN the matrix to reach a valid point on row "O."
Restrictions
1. You can only move UP, DOWN, LEFT, or RIGHT (not diagonally) by one unit.
2. The path must be a repeating pattern of 0 1 0 1 0 1 ... etc For example a move from (A,E) to (B,E) is valid while a move from (A,E) to (A,F) is not.
The correct solution has the following requirements:
1. Identifies the path from start to finish using an identifiable way to determine the ROW,COLUMN for each entry point in the path while abiding by the restrictions above.
My solution is to first transform the table with a matrix layout to a transactional layout using three columns:
- rw, an integer between 1 and 15, representing the row
- col, an integer between 1 and 10, representing the column
- value, an integer between 0 and 1, representing the matrix cell's value
In this layout a hierarchical query can do the job relatively easy:
rwijk@ORA11GR1> with matrix_transformed as
2 ( select ascii(id) - 64 rw
3 , col
4 , case col
5 when 1 then a
6 when 2 then b
7 when 3 then c
8 when 4 then d
9 when 5 then e
10 when 6 then f
11 when 7 then g
12 when 8 then h
13 when 9 then i
14 when 10 then j
15 end as value
16 from matrix
17 , ( select level col from dual connect by level <= 10 )
18 )
19 select ltrim
20 ( sys_connect_by_path('['||chr(64+rw)||','||chr(64+col)||']',';')
21 , ';'
22 ) path
23 from matrix_transformed
24 where rw = 15
25 start with rw = 1
26 and col = 5
27 connect by nocycle
28 prior value != value
29 and prior rw != 15
30 and ( ( rw = prior rw and col = prior col - 1 )
31 or ( rw = prior rw and col = prior col + 1 )
32 or ( rw = prior rw - 1 and col = prior col )
33 or ( rw = prior rw + 1 and col = prior col )
34 )
35 /
PATH
------------------------------------------------------------------------------
[A,E];[B,E];[B,D];[C,D];[D,D];[D,E];[D,F];[D,G];[C,G];[B,G];[B,H];[B,I];[C,I];
[C,J];[D,J];[E,J];[F,J];[G,J];[G,I];[G,H];[G,G];[G,F];[H,F];[I,F];[J,F];[K,F];
[K,G];[K,H];[L,H];[L,I];[L,J];[M,J];[N,J];[N,I];[O,I]
[A,E];[B,E];[B,D];[C,D];[D,D];[D,E];[D,F];[D,G];[C,G];[B,G];[B,H];[B,I];[B,J];
[C,J];[D,J];[E,J];[F,J];[G,J];[G,I];[G,H];[G,G];[G,F];[H,F];[I,F];[J,F];[K,F];
[K,G];[K,H];[L,H];[L,I];[L,J];[M,J];[N,J];[N,I];[O,I]
2 rows selected.
These two rows represent these paths:
Lines 1-18 transform the table to 150 rows in transactional layout. A hierarchical query then solves the puzzle by starting with the row [A,E] (lines 25-26 of the query). Line 27 specifies NOCYCLE to ignore loops. When joining the table with itself - like you do when using hierarchical queries - you want the next level of rows to be only the rows that are immediately UP, DOWN, LEFT or RIGHT of the current cell. This is what lines 30-34 implement. You want to discard the row when the cell value of the matrix is the same as in the previous level to ensure that 0's are followed by 1's and vice versa (line 28). And when you've reached row O - when rw equals 15 - the query needs to stop (line 29). Of this entire hierarchy, you only want one output row: the last one, which equals the one with rw = 15. And this was new to me: you can specify a where clause in your hierarchical query, which is evaluated AFTER the connect by. Of course this behaviour is
documented:
Oracle processes hierarchical queries as follows:
* A join, if present, is evaluated first, whether the join is specified in the FROM clause or with WHERE clause predicates.
* The CONNECT BY condition is evaluated.
* Any remaining WHERE clause predicates are evaluated.
If you look closely at my answer in the thread and here, you'll notice the difference. Finally a SYS_CONNECT_BY_PATH is used to print the entire route from [A,E] to [O,I].
