Maze generation: Difference between revisions
→{{header|jq}}
m (→{{header|Uiua}}: minor fix) |
|||
Line 5,574:
<a id='solve' style='display:none' href='javascript:solve(); void(0)'>Solve</a>
</fieldset></form><table id='maze'/></body></html></syntaxhighlight>
=={{header|jq}}==
'''Adapted from [[#Wren|Wren]]'''
'''Works with jq, the C implementation of jq'''
'''Works with gojq, the Go implementation of jq'''
Since jq does not have a builtin PRNG,
it is assumed that /dev/urandom is available.
An invocation such as the following may be used:
<pre>
< /dev/urandom tr -cd '0-9' | fold -w 1 | jq -Rcnr -f maze-generation.jq
</pre>
In the following, a maze is represented by a matrix, each of whose elements
is in turn a boolean array representing the bounding box:
$box[$i] is true iff edge $i open,
where $i is:
0 for the top (north) side,
1 bottom (south)
2 right (east)
3 left (west)
Note that for simplicity, in the following the "walk" always starts at the (0,0) cell.
<syntaxhighlight lang="jq">
# Output: a prn in range(0;$n) where $n is .
def prn:
if . == 1 then 0
else . as $n
| (($n-1)|tostring|length) as $w
| [limit($w; inputs)] | join("") | tonumber
| if . < $n then . else ($n | prn) end
end;
# Input: an array
def knuthShuffle:
length as $n
| if $n <= 1 then .
else {i: $n, a: .}
| until(.i == 0;
.i += -1
| (.i + 1 | prn) as $j
| .a[.i] as $t
| .a[.i] = .a[$j]
| .a[$j] = $t)
| .a
end;
# Arrays wherein `false` and `null` are the only falsey values.
# The input array and $y need not be of the same length.
def lor($y): [., $y] | transpose | map(.[0] or .[1]);
def falsey: all(.[]; IN(false, null) );
# Create an array such that .[$n] is true, and .[$i] is null for $i < $n
def bit($n): [] | .[$n] = true;
# Compass is a JSON object {n,s,e,w} representing the four possible
# directions in which to move, i.e. to open a gate.
# For example, Compass.n corresponds to a move north (i.e. dx is 0, dy is 1),
# and Compass.n.gates[0] is true indicating that the "northern" gate should be opened.
def Compass:
{n: { gates: bit(0), dx: 0, dy: -1},
s: { gates: bit(1), dx: 0, dy: 1},
e: { gates: bit(2), dx: 1, dy: 0},
w: { gates: bit(3), dx:-1, dy: 0} }
| .n.opposite = .s
| .s.opposite = .n
| .e.opposite = .w
| .w.opposite = .e
;
# Produce a matrix representing an $x x $y maze.
# .[$i][$j] represents the box in row $i, column $j.
# Initially, all the gates of all the boxes are closed (falsey).
def MazeMatrix($x; $y):
[range(0;$x) | [] ] as $v | [range(0;$y) | $v];
# Input: a MazeMatrix
def generate($cx; $cy):
def interior($a; $upper): $a >= 0 and $a < $upper;
length as $x
| (.[0]|length) as $y
| Compass as $Compass
| ([$Compass.n, $Compass.s, $Compass.e, $Compass.w] | knuthShuffle) as $directions
| reduce $directions[] as $v (.;
($cx + $v.dx) as $nx
| ($cy + $v.dy) as $ny
| if interior($nx; $x) and interior($ny; $y) and (.[$nx][$ny]|falsey)
then .[$cx][$cy] |= lor($v.gates)
| .[$nx][$ny] |= lor($v.opposite.gates)
| generate($nx; $ny)
end );
# Input: a MazeMatrix
def display:
. as $maze
| ($maze|length) as $x
| ($maze[0]|length) as $y
| ( range(0;$y) as $i
# draw the north edge
| ([range(0;$x) as $j
| if $maze[$j][$i][0] then "+ " else "+---" end] | join("")) + "+",
# draw the west edge
([range(0;$x) as $j
| if $maze[$j][$i][3] then " " else "| " end] | join("")) + "|" ),
# draw the bottom line
($x * "+---") + "+"
;
# Always start at (0,0)
def amaze($x;$y):
MazeMatrix($x; $y)
| generate(0; 0)
| display;
# Example
amaze(4; 5);
</syntaxhighlight>
{{output}}
Example output:
<pre>
+---+---+---+---+---+
| | |
+---+ + +---+ +
| | | | |
+ + + + + +
| | | | | |
+ + +---+ + +
| | |
+---+---+---+---+---+
</pre>
=={{header|Julia}}==
| |||