Skip to content

Instantly share code, notes, and snippets.

@malisper
Created February 24, 2019 18:36
Show Gist options
  • Star 4 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save malisper/2d6ec4077f3097559b2206663ae39bec to your computer and use it in GitHub Desktop.
Save malisper/2d6ec4077f3097559b2206663ae39bec to your computer and use it in GitHub Desktop.
SQL Queries that Produce Fractals
-- Sierpinski's Triangle.
WITH points AS (
SELECT ROW, col FROM generate_series(0, 63) a(ROW)
CROSS JOIN generate_series(0, 63) b(col)
ORDER BY ROW DESC, col ASC
), marked_points AS (
SELECT ROW, col, (CASE WHEN ROW & col != 0
THEN ' '
ELSE '*'
END) AS marker
FROM points
ORDER BY ROW DESC, col ASC
), ROWS AS (
SELECT ROW, string_agg(marker, '') AS row_text
FROM marked_points
GROUP BY row
ORDER BY ROW DESC
) SELECT string_agg(row_text, E'\n') FROM ROWS;
-- Mandelbrot Set
WITH RECURSIVE points AS (
SELECT r, c FROM generate_series(-2, 2, 0.05) a(r)
CROSS JOIN generate_series(-2, 1, 0.05) b(c)
ORDER BY r DESC, c ASC
), iterations AS (
SELECT r, c, 0.0::float AS zr, 0.0::float AS zc, 0 AS iteration FROM points
UNION ALL
SELECT r, c, zr*zr - zc*zc + c AS zr, 2*zr*zc + r AS zc, iteration+1 AS iteration
FROM iterations WHERE zr*zr + zc*zc < 4 AND iteration < 1000
), final_iteration AS (
SELECT * FROM iterations WHERE iteration = 1000
), marked_points AS (
SELECT r, c, (CASE WHEN EXISTS (SELECT 1 FROM final_iteration i WHERE p.r = i.r AND p.c = i.c)
THEN '**'
ELSE ' '
END) AS marker
FROM points p
ORDER BY r DESC, c ASC
), lines AS (
SELECT r, string_agg(marker, '') AS r_text
FROM marked_points
GROUP BY r
ORDER BY r DESC
) SELECT string_agg(r_text, E'\n') FROM lines;
-- Julia Set Fractal
WITH RECURSIVE points AS (
SELECT ROW, col FROM generate_series(-2, 2, 0.05) a(ROW)
CROSS JOIN generate_series(-2, 2, 0.05) b(col)
ORDER BY ROW DESC, col ASC
), iterations AS (
SELECT ROW, col, col::float AS zr, row::float AS zc, 0 AS iteration FROM points
UNION ALL
SELECT ROW, col, zr*zr - zc*zc + 1 - 1.61803398875 AS zr, 2*zr*zc AS zc, iteration+1 AS iteration
FROM iterations WHERE zr*zr + zc*zc < 4 AND iteration < 1000
), final_iteration AS (
SELECT * FROM iterations WHERE iteration = 1000
), marked_points AS (
SELECT ROW, col, (CASE WHEN EXISTS (SELECT 1 FROM final_iteration i WHERE p.ROW = i.ROW AND p.col = i.col)
THEN '**'
ELSE ' '
END) AS marker
FROM points p
ORDER BY ROW DESC, col ASC
), ROWS AS (
SELECT ROW, string_agg(marker, '') AS row_text
FROM marked_points
GROUP BY row
ORDER BY ROW DESC
) SELECT string_agg(row_text, E'\n') FROM ROWS;
-- Hilbert Curve
WITH RECURSIVE iterations AS (
SELECT 'A' AS PATH, 0 AS iteration
UNION ALL
SELECT replace(replace(replace(PATH, 'A', '-CF+AFA+FC-'), 'B', '+AF-BFB-FA+'), 'C', 'B'), iteration+1 AS iteration
FROM iterations WHERE iteration < 3
), segments AS (
SELECT 0 AS r1, 0 AS c1, 0 AS r2, 0 AS c2, 0 AS r3, 0 AS c3, 0 AS dr, 1 AS dc, (SELECT path FROM iterations ORDER BY iteration DESC LIMIT 1) AS path_left
UNION ALL
SELECT r3 AS r1, c3 AS c1, r3 + dr * movement AS r2, c3 + dc * movement AS c2, r3 + 2 * dr * movement AS r3, c3 + 2 * dc * movement AS c3, dr, dc, SUBSTRING(path_left FROM 2) AS path_left
FROM (
SELECT r1, c1, r2, c2, r3, c3,
CASE WHEN SUBSTRING(path_left FOR 1) = '-' THEN -dc
WHEN SUBSTRING(path_left FOR 1) = '+' THEN dc
ELSE dr
END AS dr,
CASE WHEN SUBSTRING(path_left FOR 1) = '-' THEN dr
WHEN SUBSTRING(path_left FOR 1) = '+' THEN -dr
ELSE dc
END AS dc,
path_left,
CASE WHEN SUBSTRING(path_left FOR 1) = 'F' THEN 1 ELSE 0 END AS movement
FROM segments
WHERE CHAR_LENGTH(path_left) > 0
) sub
), end_points AS (SELECT r1 AS r, c1 AS c FROM segments UNION SELECT r3, c3 FROM segments),
points AS (
SELECT r, c FROM generate_series((SELECT MIN(r) FROM end_points), (SELECT MAX(r) FROM end_points)) a(r)
CROSS JOIN generate_series((SELECT MIN(c) FROM end_points), (SELECT MAX(c) FROM end_points)) b(c)
), marked_points AS (
SELECT r, c, (CASE WHEN
EXISTS (SELECT 1 FROM end_points e WHERE p.r = e.r AND p.c = e.c)
THEN '*'
WHEN EXISTS (SELECT 1 FROM segments s WHERE p.r = s.r2 AND p.c = s.c2 AND dc != 0)
THEN '-'
WHEN EXISTS (SELECT 1 FROM segments s WHERE p.r = s.r2 AND p.c = s.c2 AND dr != 0)
THEN '|'
ELSE ' '
END
) AS marker
FROM points p
), lines AS (
SELECT r, string_agg(marker, '') AS row_text
FROM marked_points
GROUP BY r
ORDER BY r DESC
) SELECT string_agg(row_text, E'\n') FROM lines;
-- Dragon Curve
WITH RECURSIVE iterations AS (
SELECT 'FX' AS PATH, 0 AS iteration
UNION ALL
SELECT replace(replace(replace(PATH, 'X', 'X+ZF+'), 'Y', '-FX-Y'), 'Z', 'Y'), iteration+1 AS iteration
FROM iterations WHERE iteration < 8
), segments AS (
SELECT 0 AS r1, 0 AS c1, 0 AS r2, 0 AS c2, 0 AS r3, 0 AS c3, 0 AS dr, 1 AS dc, (SELECT path FROM iterations ORDER BY iteration DESC LIMIT 1) AS path_left
UNION ALL
SELECT r3 AS r1, c3 AS c1, r3 + dr * movement AS r2, c3 + dc * movement AS c2, r3 + 2 * dr * movement AS r3, c3 + 2 * dc * movement AS c3, dr, dc, SUBSTRING(path_left FROM 2) AS path_left
FROM (
SELECT r1, c1, r2, c2, r3, c3,
CASE WHEN SUBSTRING(path_left FOR 1) = '-' THEN -dc
WHEN SUBSTRING(path_left FOR 1) = '+' THEN dc
ELSE dr
END AS dr,
CASE WHEN SUBSTRING(path_left FOR 1) = '-' THEN dr
WHEN SUBSTRING(path_left FOR 1) = '+' THEN -dr
ELSE dc
END AS dc,
path_left,
CASE WHEN SUBSTRING(path_left FOR 1) = 'F' THEN 1 ELSE 0 END AS movement
FROM segments
WHERE CHAR_LENGTH(path_left) > 0
) sub
), end_points AS (SELECT r1 AS r, c1 AS c FROM segments UNION SELECT r3, c3 FROM segments),
points AS (
SELECT r, c FROM generate_series((SELECT MIN(r) FROM end_points), (SELECT MAX(r) FROM end_points)) a(r)
CROSS JOIN generate_series((SELECT MIN(c) FROM end_points), (SELECT MAX(c) FROM end_points)) b(c)
), marked_points AS (
SELECT r, c, (CASE WHEN
EXISTS (SELECT 1 FROM end_points e WHERE p.r = e.r AND p.c = e.c)
THEN '*'
WHEN EXISTS (SELECT 1 FROM segments s WHERE p.r = s.r2 AND p.c = s.c2 AND dc != 0)
THEN '-'
WHEN EXISTS (SELECT 1 FROM segments s WHERE p.r = s.r2 AND p.c = s.c2 AND dr != 0)
THEN '|'
ELSE ' '
END
) AS marker
FROM points p
), lines AS (
SELECT r, string_agg(marker, '') AS row_text
FROM marked_points
GROUP BY r
ORDER BY r DESC
) SELECT string_agg(row_text, E'\n') FROM lines;
-- Board
WITH RECURSIVE iterations AS (
SELECT 'F+F+F+F' AS PATH, 0 AS iteration
UNION ALL
SELECT replace(replace(replace(PATH, 'F', 'FF+F+F+F+FF'), 'R', '+LF-RFR-FL+'), 'Z', 'R'), iteration+1 AS iteration
FROM iterations WHERE iteration < 3
), segments AS (
SELECT 0 AS r1, 0 AS c1, 0 AS r2, 0 AS c2, 0 AS r3, 0 AS c3, 0 AS dr, 1 AS dc, (SELECT path FROM iterations ORDER BY iteration DESC LIMIT 1) AS path_left
UNION ALL
SELECT r3 AS r1, c3 AS c1, r3 + dr * movement AS r2, c3 + dc * movement AS c2, r3 + 2 * dr * movement AS r3, c3 + 2 * dc * movement AS c3, dr, dc, SUBSTRING(path_left FROM 2) AS path_left
FROM (
SELECT r1, c1, r2, c2, r3, c3,
CASE WHEN SUBSTRING(path_left FOR 1) = '-' THEN -dc
WHEN SUBSTRING(path_left FOR 1) = '+' THEN dc
ELSE dr
END AS dr,
CASE WHEN SUBSTRING(path_left FOR 1) = '-' THEN dr
WHEN SUBSTRING(path_left FOR 1) = '+' THEN -dr
ELSE dc
END AS dc,
path_left,
CASE WHEN SUBSTRING(path_left FOR 1) = 'F' THEN 1 ELSE 0 END AS movement
FROM segments
WHERE CHAR_LENGTH(path_left) > 0
) sub
), end_points AS (SELECT r1 AS r, c1 AS c FROM segments UNION SELECT r3, c3 FROM segments),
points AS (
SELECT r, c FROM generate_series((SELECT MIN(r) FROM end_points), (SELECT MAX(r) FROM end_points)) a(r)
CROSS JOIN generate_series((SELECT MIN(c) FROM end_points), (SELECT MAX(c) FROM end_points)) b(c)
), marked_points AS (
SELECT r, c, (CASE WHEN
EXISTS (SELECT 1 FROM end_points e WHERE p.r = e.r AND p.c = e.c)
THEN '*'
WHEN EXISTS (SELECT 1 FROM segments s WHERE p.r = s.r2 AND p.c = s.c2 AND dc != 0)
THEN '-'
WHEN EXISTS (SELECT 1 FROM segments s WHERE p.r = s.r2 AND p.c = s.c2 AND dr != 0)
THEN '|'
ELSE ' '
END
) AS marker
FROM points p
), lines AS (
SELECT r, string_agg(marker, '') AS row_text
FROM marked_points
GROUP BY r
ORDER BY r DESC
) SELECT string_agg(row_text, E'\n') FROM lines;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment