El modo de piloto automático

10

Un helicóptero que comienza en la esquina superior izquierda está descendiendo (en un espacio 2D, para el propósito de esta pregunta) hacia el suelo. Tiene un modo de piloto automático y un modo manual.

El modo de piloto automático se comporta de la siguiente manera:

  • Si el espacio directamente debajo es libre, desciende a él.
  • De lo contrario, mueva un paso hacia la izquierda o hacia la derecha, totalmente al azar. (Puede mover varios pasos de esta manera).

Y sigue repitiendo estos dos pasos hasta que toca el suelo. El modo manual es más inteligente y encontrará el camino óptimo hacia el suelo, incluso si esto requiere moverse hacia arriba o algunas maniobras hábiles.

Tu trabajo es determinar si

  1. El piloto automático pasará en el escenario dado,
  2. El piloto automático puede fallar en el escenario dado,
  3. El piloto automático fallará, pero el modo manual pasará, o
  4. Ambos modos fallarán (no hay una ruta válida al suelo).

Entrada

  • Escenario dado como una matriz no vacía 1d o 2d, usando dos caracteres diferentes para representar espacios libres y bloqueados. Puntuación opcional.
  • Opcional: dimensiones de la matriz

Salida

Uno de los cuatro caracteres predefinidos que indica cuál de los casos ha ocurrido.

Data de muestra

Usando 0 (vacío) y 1 (bloqueado) en la entrada, 1 2 3 4 en la salida (como se enumera arriba)

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

Salida: 1

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

Salida: 2(El helicóptero encontrará el 1 en la cuarta fila, y es posible que se atrape al final de la fila 5, si está en modo piloto automático)

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

Salida: 3(Esto requiere moverse hacia arriba, por lo que falla el piloto automático)

1 0 0
0 0 0

Salida: 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

Salida: 4

fantasmas_en_el_código
fuente
@ MartinBüttner Hecho. Como nota al margen, ¿prefiere que las personas publiquen en el sandbox, o que publiquen directamente y corrijan sus errores? La segunda opción es más simple, así que a menos que haya algún incentivo para no hacerlo, no puedo imaginar por qué seguiría la opción uno.
ghosts_in_the_code el
77
Personalmente prefiero el sandbox, porque les da a las personas más tiempo para pensar en posibles errores, lagunas o casos de prueba faltantes, antes de que las personas comiencen a trabajar en el desafío. Si alguien publica una respuesta temprana a un desafío defectuoso, entonces realmente no puede solucionar el desafío sin invalidar las respuestas existentes.
Martin Ender
Además, ¿las entradas son siempre caracteres, o pueden ser booleanos / enteros / etc.? Y salida: ¿puede ser entero o se requiere que sea un personaje?
No es que Charles

Respuestas:

1

Rubí, 259

Me divertí mucho con esto. ¡Gracias! desafíos de la tienden a ser muy divertidos con desafíos interesantes. Esto supone que los "caracteres" en la pregunta pueden ser enteros.

Creo que los principales puntos de mejora aquí son:

  1. La creacion de r
  2. El espantoso abuso ternario en la tercera línea probablemente puede convertirse en algo más espantoso, pero algo más terso.
->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}

Sin golf (un poco desactualizado, pero muy cerca):

# 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
}
No es que Charles
fuente