Escape the Candlelit Maze

Question

You find yourself in a strange place. A frighteningly dark maze, lit only by dim candles resting in the occasional hallway. Numerous paths lie only in impassable darkness, foreboding and-- ...Hm? What? Pick up a candle and carry it with you? No, no, that would be extremely rude.

The Task

Given a maze as input, output the minimum moves to solve it, or any falsey/invalid output if the maze cannot be solved. The catch: The maze is very dark, but is lit by candles placed on some of the grid squares. The player may only move in a direction if they can see light in that direction.

Rules

• Take the maze as input in any convenient format (string, 1d array, 2d array, etc).
• x represents a wall, @ represents the player, ^ represents a candle and # represents the exit.
• The maze will be surrounded on all sides by walls, except for the player's starting space and the exit space, each of which will be in one of the walls. The corners will always be walls.
• The player may only make orthogonal moves one space at a time in the direction of visible light. This is either a candle or the exit.
• Candlelight only reaches the space it's on, but is visible from any distance.
• Output the minimum number of legal moves the player can make to reach the exit, or any "invalid" value (such as a negative value, zero, false, the string "Unsolvable!", etc) if the maze is unsolvable within the rules. The player must move into the exit space to solve the maze.
• Standard loophole restrictions and i/o rules apply.

Test Cases

1-

Input:
xxxxxxxxxx
@^x    ^xx
x^  ^xxxxx
xxxx x^  #
x xx x xxx
x ^ ^ ^x x
x xxxx  ^x
xxxxxxxxxx

Output:
15

2-

Input:
xxxxxxxxxxxx
x^ ^xxxxxxxx
x x        #
x x^xxxx xxx
x xxxx   xxx
x^  ^xxx^xxx
xxxx@xxxxxxx

Output:
19

Once the player moves into a space that can see a new light source, such as the exit, they can then start moving towards that light source.

3-

Input:
xxxxxxxx
#  xx ^x
xx^  ^xx
x ^xx xx
xxxxx@xx

Output:
Unsolvable

4-

Input:
xxxxxxxxx
@      ^x
x xxxxx x
x x^   ^x
x x xxxxx
x x^   ^x
x xxxxx x
x^ ^   ^x
xxx#xxxxx

Output:
10

The player must take the shortest path.

5-

Input:
xxxxxxxxx
x   ^  ^x
xxxx xxxx
#  x    x
x^xx^xxxx
x^   x  x
xxxx x xx
x     ^ x
xxxx@xxxx

Output:
Unsolvable

Scoring

This is code-golf, so shortest code in bytes wins.

Answer 1

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.

Answer 2

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

Try it online!

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

Answer 3

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}

Try it online!

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
}

Answer 4

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,$_}}

Try it online!

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.

Answer 5

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])]

Try it online!