1D Hopping Array Maze

Question

Inspired by We do tower hopping and related to 2D Maze Minus 1D

Introduction

Your task is to find the shortest path to get out of an array maze following specified rules.

Challenge

A 1D array a with n elements can be regarded as a maze composed of n points, where point with index k is connected to the points with k+a[k] and k-a[k] in a one-way manner. In other words, you can jump forward or backward exactly a[k] steps from the point with index k. Points with an index outside the bounds of the array are considered outside the maze.

To illustrate this, consider the following array,

[0,8,5,9,4,1,1,1,2,1,2]

If we are at the 5th element right now, since the element is 4, we can hop 4 steps forward to the 9th element, or 4 steps backward to the 1st element. If we do the latter, we end up with the element 0, which indicates no further moves are possible. If we do the former, since the 9th element is 2, we can choose to hop to the 11th element, which is again a 2, and then we can hop again to the "13th element", which is out of the bounds of the array and considered an exit to the maze.

So if we start from the element in the middle, one way to get out of the maze is hopping 1 step back, 4 steps forward, 2 steps forward and again 2 steps forward, which can be expressed as the array [-1,4,2,2]. Alternatively you can express it with the array [4,8,10,12] which records the zero-based index of all intermediate and final points (1-based index is also fine), or just the signs, [-1,1,1,1].

Escaping the maze from the low-index end is also OK.

Using the first notation and starting from the same element, [1,1,1,2,2] is also a solution but it is not optimal since there are 5 steps instead of 4.

The task is to find out the shortest path to get out of the array maze and output the path. If there are more than one optimal paths, you can output any or all of them. If there are no solution, you should output a falsy value chosen by you that is discernible from a valid path (producing no output at all is also OK).

For simplicity, the number of elements in the array is always an odd number and we always start from the element in the middle.

Test cases

The test cases illustrates various forms of output, but you are not limited to these.

Input
Output

[0,8,5,9,4,1,1,1,2,1,2]
[-1,4,2,2]

[2,3,7,1,2,0,2,8,9]
[2,9] (or [2,-5] or [[2,9],[2,-5]])

[0,1,2,2,3,4,4,4,3,2,2,3,0]
[1,-1,1,1]

[0,1,2,2,4,4,6,6,6,6,6,4,2,1,2,2,0]
[]

Specs

• You may write a function or a full program.

• The array only contains nonnegative integers.

• You can take input and output through any standard form, but please specify in your answer which form you are using.

• This is code-golf, the lowest number of bytes wins.

• As usual, default loopholes apply here.

Answer 1

Husk, 22 bytes

ḟȯ¬€ŀ¹FS+o*!¹⌈½L¹ṁπṡ1ŀ

Returns a list of signs, or an empty list if a solution does not exist. Try it online!

Explanation

This is a brute-force solution that checks lists over -1,0,1 of increasing length, and returns the first one that results in a jump out of the array. Since it is of minimal length, it will not contain 0s.

ḟȯ¬€ŀ¹FS+o*!¹⌈½L¹ṁπṡ1ŀ  Implicit input, say A = [0,1,1]
                     ŀ  Indices of A: [1,2,3]
                 ṁ      Map over them and concatenate:
                  π      Cartesian power
                   ṡ1    of the symmetric range [-1,0,1].
                        Result is B = [[-1],[0],[1],[-1,-1],...,[1,1,1]]
ḟ                       Find the first element of B that satisfies this:
                         Argument is a list, say C = [1,-1].
      F                  Reduce C from the left
             ⌈½L¹        using ceil(length(A)/2) as the initial value
       S+o*!¹            with this function:
                          Arguments are an index of A, say I = 2, and a sign, say S = 1.
           !¹             The element of A at I: 1
         o*               Multiply by S: 1
       S+                 Add to I: 2
                         At the end of the reduction, we have a number I, here 2.
   €ŀ¹                   Is it an element of the indices of A: Yes.
 ȯ¬                      Negate: No.
                        The result is the shortest list C for which I is outside of A.

Answer 2

JavaScript (ES6), 117 bytes

Returns an array of 0-indexed intermediate and final points, or an empty array if no solution exists.

a=>(g=(x,p,d=a[x])=>1/d?[d,-d].map(d=>p.includes(X=x+d)||g(X,[...p,X])):o=o==''|o[p.length]?p:o)(a.length>>1,o=[])&&o

Try it online!

Commented

a =>                        // given the maze a[]
(g = (                      // g = recursive function taking:
  x,                        //   x = current position
  p,                        //   p[] = list of visited cells
  d = a[x]                  //   d = value of current cell
) =>                        //
  1 / d ?                   // if d is defined:
    [d, -d].map(d =>        //   for d and -d:
      p.includes(X = x + d) //     if the cell at X=x+d was not yet visited,
      || g(X, [...p, X])    //     do a recursive call to g at this position
    )                       //   end of map()
  :                         // else:
    o =                     //   update o:
      o == '' |             //     if o was empty
      o[p.length] ?         //     or p is shorter than o:
        p                   //       set o to p
      :                     //     else:
        o                   //       let o unchanged
)(a.length >> 1, o = [])    // initial call to g(), starting in the middle
&& o                        // return o

Answer 3

Python 3, 195 188 179 bytes

def f(a):
 v=len(a);x,*s={v//2},[v//2]
 while all(v>b>-1for*c,b in s)*s:s=[x.add(u)or c+[b,u]for*c,b in s for u in[b+a[b],b-a[b]]if{u}-x]
 return[b[1:]for b in s if not-1<b[-1]<v]

Try it online!

Edit:

• Saved 9 bytes by all(..)and s => all(..)*s, if u not in x => if{u}-x
  The former exploits boolean * list == int * list, the latter uses set difference (empty set is also falsy).

Output format: Nested array of all optimal answers, given as zero-based indices of intermediate and final points.

For example: f([0,8,5,9,4,1,1,1,2,1,2]) == [[4, 8, 10, 12]].

The algorithm is simple BFS. s records all possible i-length paths on ith iteration, excluding the indices already visited. Note that the extended star notation is (ab)used because repeated array access is expensive. I found that such a notation can also reduce some whitespace if used correctly.

I also made a recursive (but longer) version out of the above solution. Both s and and or s are needed, otherwise it doesn't work.

Python 3, 210 bytes

lambda a:[b[1:]for b in g(a,[[len(a)//2]],{len(a)//2})if not-1<b[-1]<len(a)]
g=lambda a,s,x:s and all(-1<b<len(a)for*c,b in s)and g(a,[x.add(u)or c+[b,u]for*c,b in s for u in[b+a[b],b-a[b]]if u not in x],x)or s

Try it online!

Answer 4

Haskell, 207 202 bytes

^{5 bytes saved thanks to BMO.}

l=length
x!p|i<-h p,d<-x!!i=[p++[x]|x<-[(-d,i-d),(d,i+d)],x`notElem`p]
x?p|i<-h p=i<0||i>=l x
h=snd.last
x#[]=[]
x#p|l(x%p)<1=x#(p>>=(x!))|1>0=x%p
(%)=filter.(?)
f x=(tail.map fst)<$>x#[[(0,l x`div`2)]]

Try it online!

This is a function that takes a list of Int as a parameter and returns a list of paths where each path is a list of relative jumps taken to get out of the array.

The ungolfed version:

move :: [Int] -> [(Int, Int)] -> [Path]
move xs path = map(\x->path++[x]) $ filter (\s -> s`notElem`path) $ [(-delta, i-delta), (delta, i+delta)]
  where (_,i) = last path
        delta = xs!!i :: Int

outside :: [Int] -> Path -> Bool
outside xs paths = i < 0 || i >= length xs
  where (_,i) = last paths

shortest' :: [Path] -> [Int] -> [Path]
shortest' paths xs | null paths       = []
                   | not (null ready) = ready
                   | otherwise        = shortest' paths' xs
                   where ready  = filter (outside xs) paths
                         paths' = concatMap (move xs) paths

shortest xs = map tail $ map (map fst) $ shortest' [[(0,length xs`div`2)]] xs

Answer 5

C (gcc), 269 bytes

#define A n){for(printf("%d,",n);i^l[i];i=l[i])printf("%d,",x[i]);break;}if(!u[n]){u[n]=x[m]=n;l[m++]=i;
#define M calloc(r,sizeof(s))
*x,*u,*l,s,m=1,i,j,n,w;main(r,v)char**v;{s=r-1;x=M;u=M;l=M;for(*x=1+s/2;i<m;i++){j=x[i];if(w=atoi(v[j])){n=j+w;if(s<A}n=j-w;if(1>A}}}}

Try it online!

Initially tried a recursive backtracking search, because using main for recursion is always fun. In the end though a straightforward non-recursive breadth-first search was able to be made smaller, which is what this version is. This program takes the input array as command-line arguments, with no braces, e.g. 0 8 5 9 4 1 1 1 2 1 2 for the first provided example. The program outputs on stdout a list of 1-indexed, comma-delimited array indices in reverse order, starting from the final, out-of-bounds/'escaped' index and working back through the intermediate indices reached (it does not output the center, starting index). The program does not output braces around the array and leaves a trailing comma because separate printf statements take a lot of characters. The output corresponding to the first test example above is 13,11,9,5,, for example.

If there is no escape route from the array maze, the program does not output anything.

Degolfed and explained it is below (heavily degolfed with some changes for readability):

int *x, *u, *l, s, m = 1, i, j, n, w;                        //Declare all the state we'll need
int main(r, v) char** v;{                            
    s = r - 1;                                               //s is our actual array size, since v[0] is the program name.
    x = calloc(r, sizeof(int));                              //x is an array that will form our BFS queue. Since it is a BFS we've no need to visit any elements more than once (first visit will have been on a shortest route to it), so the amount of space we have here should suffice.
    u = calloc(r, sizeof(int));                              //u is an array that will be used to flag when an array index has been visited; only reason it's int* is for ease of declaration
    l = calloc(r, sizeof(int));                              //l is an array that will be used parallel to x and stores backpointers in the form of indexes into x, which will be used to construct the actual path once it is found.
    x[0] = 1 + (s/2);                                        //Init the first element in the queue to our center index of the array, adding one because of the program name in v/argv.
    for(; i < m; i++) {                                      //m is the number of elements in our BFS queue. It starts at 1 and grows during iteration; if this loop terminates before finding a path there is none.
        j = x[i];                                            //Current index in the array we are examining
        if (w = atoi(v[j])) {                                //Set w to be the actual array value at the current index (and check that it's nonzero since if it isn't we can't get anywhere from here)
            n = j + w;                                       //Try a move in the positive direction
            if (n > s) {                                     //If the move escapes the array
                for(printf("%d,", n); i ^ l[i]; i = l[i]) {  //Print the location escaped to and then loop back through the backpointers to reconstruct the path. The only backpointer that will point to its own queue index is the starting one, so terminate there.
                    printf("%d,", x[i]);                     //Print each intermediate array index
                }
                break;                                       //Then break the outer for loop and exit.
            }
            if(!u[n]) {                                      //If the jump didn't take us out of the array and we haven't visited where it goes to, add it to the queue.
                u[n] = x[m] = n;                             //m is the current tail of the queue, so put this new location there. Since we're 1-indexed and if n was zero we'd have escaped, we know it isn't so can use it to mark this index as visited also.
                l[m++] = i;                                  //Also set the backpointer for this new queue element to point back to the current index, then increment the tail of the queue.
            }
            n = j - w;                                       //Now the backwards move
            if (n < 1) {                                     //Repeat analogous to the forward case.
                for(printf("%d,", n); i ^ l[i]; i = l[i]) {
                    printf("%d,", x[i]);
                }
                break;
            }
            if (!u[n]) {
                u[n] = x[m] = n;
                l[m++] = i;
            }
        }
    }
}

As usual for golfed C code, compilation output will of course include a friendly wall of warnings and notes.

Answer 6

Perl 5, -a: 73 bytes

(old style counting: 75 bytes, +1 for a and +1 for replacing -// by -/$/ and using $` for $')

#!/usr/bin/perl -a
use 5.10.0;
@;=$#F/2;$v{$^H=$_}//=push@;,map$'+$_*($F[$^H]//1/!say$').$".$',-//,1for@

Give the input array as one line on STDIN e.g. 0 8 5 9 4 1 1 1 2 1 2

prints the visited positions in reverse order including the starting point, then crashes

Prints nothing if there is no solution

Try it online!

Answer 7

Ruby, 102 bytes

->a{b=[[a.size>>1]];b.map{|x|(v=a[w=x[0]])&&w>=0?[w-v,w+v].map{|j|x.index(j)?0:b<<[j]+x}:(break p x)}}

Try it online!

Takes input maze as an array, outputs by printing the escape path in reverse, from the exit to the starting point (inclusive). Prints nothing if there is no escape.

This approach misuses the map method to iterate through a temporary array storing the history of paths, which is constantly extended on the fly whenever there is another possible step to take.

In principle, I could save another byte by using return x instead of break p x, but that would mean claiming that my falsy value is equal to all the monstrous rubbish stored in b. Probably, this would be too much, even considering the allowed flexibility of the output...

Walkthrough

->a{
  b=[[a.size>>1]] #Initialize an array of paths with our starting point index
  b.map{|x|       #Iterate through this array
    (v=a[w=x[0]]) #w is the current point in the path, v is its array value
    &&w>=0        #Ruby's support for negative indexing costs us 6 bytes :(
    ?             #If we are still within the bounds of the maze
      [w-v,w+v].map{|j| #Try moving in both directions
        x.index(j)? #If we have been there before, or stuck on zero
        0         #This is a dead-end, just assign a throwaway value
        :b<<[j]+x #Otherwise push the elongated path on top of our iterator
      } 
    :(break p x)  #Escaped! Exit the loop and report the path
  }  
}

Answer 8

Python 3, 133 bytes

def f(k,*s):*p,x=len(k)//2,*s;return{x}-{*p}and min([a for a in(f(k,*s,x-k[x]),f(k,*s,x+k[x]))if a]or[()],key=len)if~0<x<len(k)else s

Try it online!

Outputs the shortest list of all visited indices.

Port of my answer to Find the shortest route on an ASCII road.