Hilbert curve: Difference between revisions
Content added Content deleted
(Added JavaScript) |
(→{{header|Python}}: Added a Python draft - composing pure functions.) |
||
Line 960: | Line 960: | ||
end procedure |
end procedure |
||
main()</lang> |
main()</lang> |
||
=={{header|Python}}== |
|||
===Functional=== |
|||
Composition of pure functions, with type comments for the reader rather than the compiler. |
|||
An SVG path is serialised from the Nth application of re-write rules to a Hilbert tree structure. |
|||
(Save the output SVG text in a file, and load in browser, to view the Hilbert curve). |
|||
<lang Python>from itertools import (chain, islice, starmap) |
|||
# rule :: Dict Char [Char] |
|||
rule = { |
|||
'a': ['d', 'a', 'a', 'b'], |
|||
'b': ['c', 'b', 'b', 'a'], |
|||
'c': ['b', 'c', 'c', 'd'], |
|||
'd': ['a', 'd', 'd', 'c'] |
|||
} |
|||
# vectors :: Dict Char [(Int, Int)] |
|||
vectors = { |
|||
'a': [(-1, 1), (-1, -1), (1, -1), (1, 1)], |
|||
'b': [(1, -1), (-1, -1), (-1, 1), (1, 1)], |
|||
'c': [(1, -1), (1, 1), (-1, 1), (-1, -1)], |
|||
'd': [(-1, 1), (1, 1), (1, -1), (-1, -1)] |
|||
} |
|||
# hilbertCurve :: Int -> SVG String |
|||
def hilbertCurve(n): |
|||
w = 1024 |
|||
return svgFromPoints(w)( |
|||
hilbertPoints(w)( |
|||
hilbertTree(n) |
|||
) |
|||
) |
|||
# hilbertTree :: Int -> Tree Char |
|||
def hilbertTree(n): |
|||
'''Nth application of a rule to a tree seedling''' |
|||
# go :: Tree Char -> Tree Char |
|||
def go(tree): |
|||
c = tree['root'] |
|||
xs = tree['nest'] |
|||
return Node(c)( |
|||
map(go, xs) if xs else map( |
|||
lambda x: Node(x)([]), |
|||
rule[c] |
|||
) |
|||
) |
|||
seed = Node('a')([]) |
|||
return list(islice( |
|||
iterate(go)(seed), n |
|||
))[-1] if 0 < n else seed |
|||
# hilbertPoints :: Int -> Tree Char -> [(Int, Int)] |
|||
def hilbertPoints(w): |
|||
'''Serialization of a tree to a list of points in a square of side w''' |
|||
# points :: Int -> ((Int, Int), Tree Char) -> [(Int, Int)] |
|||
def points(d): |
|||
def go(xy, tree): |
|||
r = d // 2 |
|||
centres = map( |
|||
lambda tpl: ( |
|||
xy[0] + (r * tpl[0]), |
|||
xy[1] + (r * tpl[1]) |
|||
), |
|||
vectors[tree['root']] |
|||
) |
|||
return chain.from_iterable( |
|||
starmap(points(r), zip(centres, tree['nest'])) |
|||
) if tree['nest'] else centres |
|||
return lambda xy, tree: go(xy, tree) |
|||
d = w // 2 |
|||
return lambda tree: list(points(d)((d, d), tree)) |
|||
# svgFromPoints :: Int -> [(Int, Int)] -> SVG String |
|||
def svgFromPoints(w): |
|||
'''Width of square canvas -> Point list -> SVG string''' |
|||
def go(w, xys): |
|||
xs = ' '.join(map( |
|||
lambda xy: str(xy[0]) + ' ' + str(xy[1]), |
|||
xys |
|||
)) |
|||
return '\n'.join( |
|||
['<svg xmlns="http://www.w3.org/2000/svg"', |
|||
f'width="512" height="512" viewBox="5 5 {w} {w}">', |
|||
f'<path d="M{xs}" ', |
|||
'stroke-width="2" stroke="red" fill="transparent"/>', |
|||
'</svg>' |
|||
] |
|||
) |
|||
return lambda xys: go(w, xys) |
|||
# GENERIC FUNCTIONS --------------------------------------- |
|||
# Node :: a -> [Tree a] -> Tree a |
|||
def Node(v): |
|||
return lambda xs: { |
|||
'type': 'Node', 'root': v, 'nest': xs |
|||
} |
|||
# iterate :: (a -> a) -> a -> Gen [a] |
|||
def iterate(f): |
|||
def go(x): |
|||
v = x |
|||
while True: |
|||
yield(v) |
|||
v = f(v) |
|||
return lambda x: go(x) |
|||
# TEST --------------------------------------------------- |
|||
if __name__ == '__main__': |
|||
print ( |
|||
hilbertCurve(6) |
|||
)</lang> |
|||
=={{header|Ring}}== |
=={{header|Ring}}== |