The autopilot mode

Question

A helicopter starting at the top left corner is descending (in a 2D space, for the purpose of this question) towards the ground. It has an autopilot mode and a manual mode.

The autopilot mode behaves as follows:

• If the space directly below is free, descend to it.
• Otherwise move a step left or right, totally at random. (It may move multiple steps in this manner.)

And it keeps repeating these two steps until it hits the ground. The manual mode is more smart and will find the optimal path to the ground, even if this requires moving upwards, or some skillful manoeuvring.

Your job is to determine if

1. The autopilot will pass in the given scenario,
2. The autopilot might fail in the given scenario,
3. The autopilot will fail, but the manual mode will pass, or
4. Both modes will fail (there is no valid path to the ground).

Input

• Given scenario as a 1d or 2d non-empty array, using two different characters to represent free and blocked spaces. Punctuation optional.
• Optional: dimensions of array

Output

One of four predefined characters indicating which of the cases has occurred.

Sample data

Using 0 (empty) and 1 (blocked) in input, 1 2 3 4 in output (as numbered above)

0 0 0 0
0 1 0 0
0 0 0 1
1 1 0 0

Output: 1

0 0 1 0
1 0 0 1
0 0 0 0
0 1 1 0
0 0 0 1

Output: 2 (The helicopter will encounter the 1 in the fourth row, and it is possible it will trap itself at the end of row 5, if on autopilot mode)

0 0 0 1 0
0 1 1 0 0
0 1 0 0 0
0 0 0 1 0
1 1 1 1 0

Output: 3 (This requires moving upwards, so the autopilot fails)

1 0 0
0 0 0

Output: 4

0 0 0 0 1
1 1 1 0 0
1 0 0 1 0
0 1 0 0 0
0 0 1 1 1

Output: 4

Answer 1

Ruby, 259

I had a lot of fun with this. Thank you! grid challenges tend to be excellent fun with interesting challenges. This assumes that "characters" in the question can be integers.

I think the major points of improvement here are:

1. The creation of r
2. The ghastly ternary abuse on the third line can likely be made into a more-ghastly, but terser something.

->a,h,w{f=->l,s=0,y=[0]{r=w-2<s%w ?w:1,1>s%w ?w:-1,w
v=(l ?r+[-w]:a[s+w]==0?[w]:r).map{|d|a[m=s+d]==0&&!y[m]?m:p}-q=[p]
a[s]>0?q:s/w>h-2?8:v[0]?v.map{|o|f[l,y[o]=o,y]}.flatten-q :r.any?{|i|a[s+i]<1}?p: !0}
g=f[p]
[8,g[0]&&g.all?,g.any?,f[8].any?,!p].index !p}

Ungolfed (slightly out of date, but real close):

# a is a one-dimensional array of 0s and 1s, h is height, w is width
->a,h,w{
  # f recursively walks the array and returns true/false/nil for each path.
  #    True means we can reach ground.
  #    False means we are stuck in a local minimum and cannot escape
  #    Nil means we reached a local dead-end and need to backtrack.
  # l: {true=>"manual", false=>"autopilot"}
  # s: the position index
  # y: an array of booleans - true-ish means we've visited that square before
  #         (this is to prevent infinite loops, esp in manual mode)
  f=->l,s=0,y=[0]{
    # d: all the legal deltas from s (maximally, that's [1,-1,w,-w], aka [LRDU])
    # r: but the right and left get tricky on the edges, so let's pre-calculate those
    #    we'll default to "down" if "left" or "right" are illegal
    r=[w-2<s%w ?w:1,1>s%w ?w:-1]
    # if manual, [LRDU]; if auto, and you can go down, [D]. else, [LR] 
    d=l ?r+[w,-w]:a[s+w]==0?[w]:r
    # v: the legal deltas that you can go to from s (that is, unvisited and unblocked)
    v=d.map{|d|a[m=s+d]==0&&!y[m]?m:p}-[p]


    a[s]>0 ? [p]     # if we're currently blocked, return [nil] (this is only the case when a[0]==1)
      : s/w>h-2 ? !p # if we're at the bottom, return true
        : v[0] ?     # if we have a place to go....
        v.map{|o|f[l,y[o]=o,y]}.flatten-[p] # recurse with each step.
                                            # y[o]=o is a neat trick to make y[o] truthy and return o
          : r.any?{|i|a[s+i]==0} ? # otherwise, we have nowhere to go. If we could visit left/right, but have already been there
            p                      #    this is not a dead-end - return nil to remove this path
            : !!p                  # If we have a true dead-end (auto-mode with a local minimum), false
  }
  # g is the auto flight
  g=f[p]
  # finally, choose the first "true" out of:
  # 0: always 8.  Cuz why not 8?
  # 1: there is at least one auto path, and all are truthy
  # 2: any auto path is truthy
  # 3: any manual path is truthy
  # 4: true
  [8,g[0]&&g.all?,g.any?,f[!p].any?,!p].index !p
}