Author Archive

Dec 29 2014

A maze with recursive sql

I’ve used recursive sql in DB2 for some years to look into tree-like structures and concatenating and splitting strings. That made me think what else to use it for, so I made this. Its a maze build in one piece of sql. There are of course room for improvements. Height and wide need to be uneven.

 

-- generate maze
-- author Per Trangbæk
-- email  pertrang@gmail.com
--
-- height, wide and max depth
WITH init(w, h, max_depth) AS
(
   SELECT 17, 13, 8000
        FROM sysibm.sysdummy1 root
),
-- build the box containing the maxe
box(box) AS
(
   SELECT CAST(repeat('.', (w+2)*2) concat
           repeat('.' concat repeat('#', w) concat '.', h)
          concat repeat('.', (w+2)*2) AS VARCHAR(2000))
   FROM init
),
-- main loop
-- command  next command in loop
-- maze     the maze
-- rnd      posible ways to go
-- rndPos
-- rndnr    way to try to go
-- pos      where we are
-- posoff   offset for wall to be deleted
-- chk
-- visit    counter for valid places visited
-- depth    depth of loop
-- xp       where to start when stuck
-- yp       where to start when stuck
lab(command, maze, rnd, rndPos, rndNr,
    pos, posoff, chk, visit, depth, xp, yp) AS
(
   SELECT 'RND', overlay(box, ' ', (w+2)*2+2, 1, OCTETS),
          CAST('' AS VARCHAR(4)), 'UDLR',
          rand(SECOND(CURRENT_TIMESTAMP))*4+1,
          (w+2)*2+2, 0,  '  ', ((h+1)/2*(w+1)/2) - 1, 1, 1, 1
     FROM sysibm.sysdummy1,
          init,
          box
  UNION ALL
     SELECT CASE
               WHEN LENGTH(rndPos) = 1 THEN 'MZE'
               ELSE command
            END,
            maze,
            concat(rnd, substr(rndPos, rndNr, 1)),
            REPLACE(rndPos, substr(rndPos, rndNr, 1), ''),
            rand()*(LENGTH(rndPos) - 1) + 1,
            pos, 0,'  ', visit, depth + 1, xp, yp
      FROM lab, init
     WHERE command = 'RND'
    AND depth < init.max_depth
  UNION ALL
     SELECT 'CHK', maze, rnd, rndPos, rndNr, pos, 1,
            substr(maze, pos + 1, 2),
            visit, depth + 1, xp, yp
       FROM lab, init
      WHERE command = 'MZE'
        AND LEFT(rnd, 1) = 'R'
        AND depth < init.max_depth
  UNION ALL
     SELECT 'CHK', maze, rnd, rndPos, rndNr, pos, -1,
            substr(maze, pos - 2, 2),
            visit, depth + 1, xp, yp
       FROM lab, init
      WHERE command = 'MZE'
        AND LEFT(rnd, 1) = 'L'
        AND depth < init.max_depth
  UNION ALL
     SELECT 'CHK', maze, rnd, rndPos, rndNr, pos, (w+2),
            substr(maze, pos + (w+2), 1) concat
            substr(maze, pos + (w+2)*2, 1),
            visit, depth + 1, xp, yp
       FROM lab,init
      WHERE command = 'MZE'
        AND LEFT(rnd, 1) = 'D'
        AND depth < init.max_depth
  UNION ALL
     SELECT 'CHK', maze, rnd, rndPos, rndNr, pos, -(w+2),
            substr(maze, pos - (w+2), 1) concat
            substr(maze, pos - (w+2)*2, 1),
            visit, depth + 1, xp, yp
       FROM lab,init
      WHERE command = 'MZE'
        AND LEFT(rnd, 1) = 'U'
        AND depth < init.max_depth
  UNION ALL
     SELECT 'RND',
            overlay(overlay(maze,' ',pos + posoff, OCTETS),
            ' ', pos + 2 * posoff, OCTETS),
            '','UDLR', rand()*4+1, pos + 2 * posOff, 0, '  ',
            CASE
               WHEN substr(maze, pos+2*posoff, 1) = '#' THEN visit - 1
               ELSE visit
            END,
            depth + 1, xp, yp
       FROM lab, init
      WHERE command = 'CHK'
        AND chk = '##'
        AND depth < init.max_depth
  UNION ALL
     SELECT CASE
               WHEN LENGTH(rnd) = 1 THEN 'FI?'
               ELSE 'MZE'
            END,
            maze,
            REPLACE(rnd, LEFT(rnd, 1), ''),'',1,  pos, posOff, '',
            visit, depth + 1, xp, yp
       FROM lab, init
      WHERE command = 'CHK'
        AND chk <> '##'
        AND depth < init.max_depth
  UNION ALL
     SELECT 'FST',
            maze,
            '','',0, 1, 0, '',
            visit, depth + 1, xp, yp
       FROM lab, init
      WHERE command = 'FI?'
        AND visit > 0
        AND depth < init.max_depth
  UNION ALL
     SELECT 'RND',
            maze,
            '','UDLR', rand()*4+1, pos, 0, '',
            visit, depth + 1, xp, yp
       FROM lab, init
      WHERE command = 'FST'
        AND substr(maze,pos, 1) = ' '
        AND depth < init.max_depth
        AND yp <= h
  UNION ALL
     SELECT 'FST',maze, '','', 0,
            (w + 2) * 2 + 2,
            0, '', visit, depth + 1, 1, 1
       FROM lab, init
      WHERE command = 'FST'
        AND yp > h
        AND depth < init.max_depth
  UNION ALL
     SELECT 'FST',
            maze,
            '','', 0,
            1 * (w + 2) + yp * (w + 2) + xp + 1,
            0, '',
            visit, depth + 1,
            CASE WHEN xp + 2 = w THEN 1 ELSE xp + 2 END,
            CASE WHEN xp + 2 = w THEN yp + 2 ELSE yp END
       FROM lab, init
      WHERE command = 'FST'
        AND substr(maze,pos, 1) <> ' '
        AND depth < init.max_depth
        AND yp <= h
  UNION ALL
     SELECT 'END',
            translate(maze, '#', '.'),
            '','',0, 0, 0, '',
            visit, depth + 1, xp, yp
       FROM lab, init
      WHERE command = 'FI?'
        AND visit <= 0
        AND depth < init.max_depth
  UNION ALL
     SELECT 'END',
            translate(maze, '#', '.'),
            '','',0, 0, 0, '',
            visit, depth + 1, xp, yp
       FROM lab, init
      WHERE depth = init.max_depth
),
splitbox(depth, linenr, frame2, string) AS
(
  SELECT depth, 1, substr(maze, (w + 2)*2+1)                 ,
    CAST(overlay(substr(maze, w,  w+2), ' ', 2, OCTETS) AS VARCHAR(200))
    FROM lab, init
    WHERE lab.command = 'END'
 UNION ALL
  SELECT depth, linenr + 1, substr(frame2, w+3), LEFT(frame2, w+2)
   FROM splitbox, init
  WHERE LENGTH(frame2) > w * 3
 UNION ALL
  SELECT depth, linenr + 1, '',
      overlay(LEFT(frame2, w+2), ' ', w + 1, octets)
   FROM splitbox, init
  WHERE linenr = h + 1
)
SELECT string FROM splitbox;

Example of output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

STRING
---------+---------+-
# #################
#     #           #
# # # ####### # ###
# # #     #   #   #
# ####### # ##### #
#   #   # #   #   #
# # # ### ### #####
# # #   #   #     #
# # # # ### # ### #
# # # # #   #   # #
# # ### # ####### #
# #   # #   #   # #
# ### # # # # # # #
#   #   # #   #   #
################# #
Permalink | Categories sql on December 29, 2014 by Per Trangbæk | No Comments