Maze generation: Difference between revisions
Content added Content deleted
m (→{{header|Uiua}}: minor fix) |
|||
Line 5,574: | Line 5,574: | ||
<a id='solve' style='display:none' href='javascript:solve(); void(0)'>Solve</a> |
<a id='solve' style='display:none' href='javascript:solve(); void(0)'>Solve</a> |
||
</fieldset></form><table id='maze'/></body></html></syntaxhighlight> |
</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}}== |
=={{header|Julia}}== |