Der Autopilot-Modus

10

Ein Hubschrauber, der in der oberen linken Ecke startet, senkt sich (in einem 2D-Raum für die Zwecke dieser Frage) in Richtung Boden. Es verfügt über einen Autopilot-Modus und einen manuellen Modus.

Der Autopilot-Modus verhält sich wie folgt:

  • Wenn der Platz direkt darunter frei ist, steigen Sie dorthin ab.
  • Bewegen Sie andernfalls einen Schritt nach links oder rechts, völlig zufällig. (Auf diese Weise können mehrere Schritte verschoben werden.)

Und es wiederholt diese beiden Schritte so lange, bis es auf dem Boden aufschlägt. Der manuelle Modus ist intelligenter und findet den optimalen Weg zum Boden, selbst wenn dies eine Aufwärtsbewegung oder ein geschicktes Manövrieren erfordert.

Ihre Aufgabe ist es festzustellen, ob

  1. Der Autopilot wird im gegebenen Szenario passieren,
  2. Der Autopilot kann im angegebenen Szenario fehlschlagen.
  3. Der Autopilot schlägt fehl, aber der manuelle Modus wird bestanden, oder
  4. Beide Modi schlagen fehl (es gibt keinen gültigen Pfad zum Boden).

Eingang

  • Gegebenes Szenario als nicht leeres 1d- oder 2d-Array, wobei zwei verschiedene Zeichen verwendet werden, um freie und blockierte Leerzeichen darzustellen. Zeichensetzung optional.
  • Optional: Abmessungen des Arrays

Ausgabe

Eines von vier vordefinierten Zeichen, die angeben, welcher der Fälle aufgetreten ist.

Beispieldaten

Verwenden Sie 0 (leer) und 1 (blockiert) in der Eingabe, 1 2 3 4 in der Ausgabe (wie oben nummeriert)

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

Ausgabe: 1

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

Ausgabe: 2(Der Hubschrauber trifft auf die 1 in der vierten Reihe, und es ist möglich, dass er sich am Ende der Reihe 5 einfängt, wenn er sich im Autopilot-Modus befindet.)

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

Ausgabe: 3(Dies erfordert eine Aufwärtsbewegung, damit der Autopilot ausfällt.)

1 0 0
0 0 0

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

Ausgabe: 4

Ghosts_in_the_code
quelle
@ MartinBüttner Fertig. Bevorzugen Sie als Randnotiz, dass Personen in der Sandbox posten oder direkt posten und ihre Fehler korrigieren lassen? Die zweite Option ist einfacher. Wenn es keinen Anreiz gibt, dies nicht zu tun, kann ich mir nicht vorstellen, warum ich Option 1 folgen würde.
Ghosts_in_the_code
7
Ich persönlich bevorzuge die Sandbox, weil sie den Leuten mehr Zeit gibt, über mögliche Fehler, Lücken oder fehlende Testfälle nachzudenken, bevor sie anfangen, an der Herausforderung zu arbeiten. Wenn jemand eine frühe Antwort auf eine fehlerhafte Herausforderung veröffentlicht, können Sie die Herausforderung nicht wirklich beheben, ohne vorhandene Antworten ungültig zu machen.
Martin Ender
Auch - sind die Eingaben immer Zeichen oder können sie Boolesche Werte / Ganzzahlen / usw. sein? Und Ausgabe - kann das eine ganze Zahl sein oder muss es ein Zeichen sein?
Nicht dass Charles

Antworten:

1

Ruby, 259

Ich hatte viel Spaß damit. Vielen Dank! Herausforderungen machen in der Regel viel Spaß mit interessanten Herausforderungen. Dies setzt voraus, dass "Zeichen" in der Frage Ganzzahlen sein können.

Ich denke, die wichtigsten Verbesserungspunkte sind:

  1. Die Kreation von r
  2. Der grässliche ternäre Missbrauch in der dritten Zeile kann wahrscheinlich zu einem grässlicheren, aber etwas kürzeren werden.
->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 (etwas veraltet, aber sehr nahe):

# 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
}
Nicht dass Charles
quelle