| Bytes | Lang | Time | Link |
|---|---|---|---|
| 351 | Python3 | 240521T193946Z | Ajax1234 |
| 162 | PowerShell 6+ for Windows | 200504T083430Z | mazzy |
| 238 | Perl 5 | 200503T233608Z | Kjetil S |
| 177 | JavaScript ES6 | 200428T193936Z | Arnauld |
| 229 | Retina 0.8.2 | 200428T205034Z | Neil |
Python3, 351 bytes
E=enumerate
def f(b):
d={(x,y):v for x,r in E(b)for y,v in E(r)}
q=[(*[i for i in d if'@'==d[i]][0],[])]
for x,y,p in q:
if'#'==b[x][y]:return len(p)
for X,Y in[(1,0),(-1,0),(0,1),(0,-1)]:
J,F=(x,y),0
while d.get(J:=(J[0]+X,J[1]+Y),-1)in[' ','^','#']:
if d[J]in'^#':F=1;break
if F and(T:=(x,y,x+X,y+Y))not in p:q+=[(x+X,y+Y,p+[T])]
PowerShell 6+ for Windows, 162 bytes
$f={param($m,$l)++$l
1..4|%{switch -r($m){'@#'{$l}'@ *[#^]'{&$f($m-replace'@.','x@')$l}}$m=&{($a=$m[-1..-$m.Count])[0]|% t*y|%{-join($a|% Ch*($i++))}}}|sort -t 1}
Unrolled:
$f = {
param($maze,$len) # len = $null if parm omited
++$len
1..4|%{
#recursive call
switch -Regex ($maze){
'@#'{$len}
'@ *[#^]'{
&$f ($maze -replace '@.','x@') $len # leave a wall behind to avoid infinite loops
}
}
#rotate -90
$maze = &{ # new context to reinit $array and $i
$array=$maze[-1..-$maze.Count]
$array[0]|% toCharArray|%{
-join($array|% Chars($i++))
}
}
}|sort -Top 1 # Powershell 6+ for Windows
# }|sort|select -First 1 # Powershell 5- for Windows
# }|sort-object -Top 1 # Powershell for Linux
}
Perl 5, 238 bytes
sub f{%s=@_=(1,pop);while(@_){$i=shift;$m=shift;for(1..4){@a=$m=~/.+/g;!$s{$m=join$/,reverse map{$j=$_-1;join'',map/.{$j}(.)/?$1:0,@a}1..length$a[0]}++&&push@_,$i,$m};$_=$m;s/@( *[\^#])/'x@'.substr$1,1/e&&(/#/||return$i)&&push@_,$i+1,$_}}
Rotates the maze 90° four times at each position. Easier to regexp-search-replace the entire maze as one string for @ +[^#] with x@ + one less space when the next light or end is always ahead if at all. @^ and @# with no space are replaced by x@ so the # disappears which means the exit has been reached and we return $i steps taken. Array @_ contains mazes to try out next. Hash %s keeps track of which mazes we've already tried so those are skiped. Nothing left to try in @_ means no solution is to be found and 0 is returned.
JavaScript (ES6), 196 ... 179 177 bytes
Takes input as a matrix of characters. Returns \$0\$ if there's no solution.
m=>(o=F=(X,Y,n)=>m.map((r,y)=>r.map((c,x)=>n?(h=x-X)*h+(v=y-Y)*v-1?0:c=='#'?o=o<n?o:n:r[(g=w=>1/(C=m[z+=v][w])?g(w+h):C<g)(x,z=Y)&&F(x,y,n+1,r[x]=g),x]=c:c=='@'&&F(x,y,1))))()|o
How?
This is a depth-first search. We first look for the position of the player and then initiate the recursion. We keep track of the number of moves in \$n\$ and the length of the shortest path in \$o\$.
Given the previous position \$(X,Y)\$, we iterate on all cells \$(x,y)\$ of the maze and compute \$dx=x-X\$ and \$dy=y-Y\$. We can move to the new cell if:
- \$dx^2+dy^2=1\$
- and the first non-empty cell encountered along the ray \$(X+k\cdot dx,Y+k\cdot dy),k>0\$ is either a candle or the exit
Commented
m => ( // m[] = input matrix
o = // o = output, initially non-numeric
F = (X, Y, n) => // F is the main recursive function:
m.map((r, y) => // for each row r[] at position y in m[]:
r.map((c, x) => // for each character c at position x in r[]:
n ? // if n is defined:
(h = x - X) * h + // h = dx, v = dy
(v = y - Y) * v - 1 ? // if the quadrance is not equal to 1:
0 // abort
: // else:
c == '#' ? // if we've reached the exit:
o = o < n ? o : n // update o if n is better
: // else:
r[ // wrapper to update r[]:
( g = // we use g to look for a candle
w => // or the exit in this direction:
1 / (C = // move along (dx, dy) and store
m[z += v][w] // the content of the cell in C
) ? // if C is a space:
g(w + h) // keep moving until it's not
: // else:
C < g // success if C is not 'x'
)(x, z = Y) // initial call to g at (X, Y)
&& // if the move is valid:
F( // do a recursive call:
x, y, n + 1, // at (x, y) with n + 1
r[x] = g // invalidate the current cell
), // end of recursive call
x // actual index in r[] ...
] = c // ... to restore the cell
: // else (n undefined):
c == '@' && F(x, y, 1) // initiate the recursion if c is '@'
)) // end of map() loops
)() | o // initial call to F; return o
Retina 0.8.2, 229 bytes
T`#^`d
s`@.*
$&_
@\d|@ ( *\d)
@=$1
(\d *) @|\d@
$1=@
m`^(((.))*@.*\n(?<-2>.)*(?(2)$))(\d| ((.*\n)+(?<-3>.)*(?(3)$)\d))
$1=$5
m`^(((.))*)(\d|(\d(.*\n)+(?<-2>.)*(?(2)$)) )(.*\n(?<-3>.)*(?(3)$)@)
$1$5=$7
@
x
}sT`=`@`.*0.*
s`.*0.*
_
Try it online! Outputs 0 for unsolvable, since solutions must take at least one step. Explanation:
T`#^`d
Change the candle and exit to golfier characters, saving 7 bytes
s`@.*
$&_
If there are still squares to check, then increment the counter. (This allows the loop to terminate once it runs out of squares to check.)
@\d|@ ( *\d)
@=$1
Mark the square to the right if it is lit.
(\d *) @|\d@
$1=@
Mark the square to the left if it is lit.
m`^(((.))*@.*\n(?<-2>.)*(?(2)$))(\d| ((.*\n)+(?<-3>.)*(?(3)$)\d))
$1=$5
Mark the square below if it is lit.
m`^(((.))*)(\d|(\d(.*\n)+(?<-2>.)*(?(2)$)) )(.*\n(?<-3>.)*(?(3)$)@)
$1$5=$7
Mark the square above if it is lit.
@
x
Turn the squares that were checked into walls.
sT`=`@`.*0.*
If the exit still exists, then turn all of the marked squares into squares that need to be checked.
}`
Repeat the above until the exit is reached or no new steps could be taken.
s`.*0.*
If the exit was not reached then delete the count.
_
Convert the count to decimal and delete the input.