Ice Golf Challenge

24

Das Ziel dieser Herausforderung besteht darin, ein Programm oder eine Funktion zu schreiben , die die geringste Anzahl von Schlägen zurückgibt, die zum Abschließen eines bestimmten Kurses erforderlich sind.

Eingang

  • Das Layout des Kurses kann auf jede geeignete Art und Weise und in jedem von Ihnen bevorzugten Format übergeben werden. (Lesen von der Konsole, Übergabe als Eingabeparameter, Lesen aus einer Datei oder einem anderen mehrzeiligen String, String-Array, zweidimensionalem Zeichen- / Byte-Array).
  • Die Startposition des Balls und des Lochs kann auch als Eingabe übergeben werden, sie muss nicht aus der Eingabe analysiert werden. In den Testfällen werden sie in den Kurs einbezogen, um sicherzustellen, dass keine Verwechslungen mit der tatsächlichen Position auftreten.
  • Sie können die eingegebenen Zeichen neu zuordnen, sofern sie noch als unterschiedliche Zeichen erkennbar sind (z. B. druckbare ASCII-Zeichen).

Ausgabe

  • Das Programm muss für jeden Kurs, der als Eingabe in einem vernünftigen Format (String, Integer, Float oder ein Haiku, das das Ergebnis beschreibt) übergeben wird, die niedrigstmögliche Punktzahl (die geringste Anzahl von Schlägen, die zum Erreichen des Lochs erforderlich sind) zurückgeben.
  • Wenn der Kurs nicht zu schlagen ist, kehren Sie zurück -1(oder ein anderer falscher Wert Ihrer Wahl, der für einen schlagbaren Kurs nicht zurückgegeben würde).

Beispiel:

In diesem Beispiel sind die Positionen 0-basiert, X / Y, von links nach rechts, von oben nach unten notiert. Sie können jedoch jedes beliebige Format verwenden, da das Ergebnis sowieso vollständig formatunabhängig ist.

Eingang:

###########
#     ....# 
#      ...# 
#  ~    . # 
# ~~~   . # 
# ~~~~    # 
# ~~~~    # 
# ~~~~  o # 
# ~~~~    # 
#@~~~~    # 
###########

Ball (Start-Position): 1/9
Hole (End-Position):   8/7

Ausgabe:

8

Beispielkurs

Regeln und Felder

Der Kurs kann aus folgenden Feldern bestehen:

  • '@' Ball - Der Beginn des Kurses
  • 'o' Loch - Das Ziel des Platzes
  • '#' Mauer - Der Ball stoppt, wenn er auf eine Mauer trifft
  • '~' Wasser - muss vermieden werden
  • '.' Sand - Der Ball stoppt sofort auf Sand
  • ' ' Der Eisball rutscht weiter, bis er auf etwas trifft

Die Grundregeln und Einschränkungen des Spiels:

  • Der Ball kann sich nicht diagonal bewegen, sondern nur nach links, rechts, oben und unten.
  • Der Ball stoppt nicht vor Wasser, sondern nur vor Wänden, auf Sand und im Loch.
    • Schüsse ins Wasser sind ungültig / unmöglich
    • Der Ball bleibt im Loch und wird nicht wie auf Eis übersprungen
  • Der Kurs ist immer rechteckig.
  • Die Strecke ist immer von Wasser oder Mauern begrenzt (keine Grenzkontrollen erforderlich).
  • Es gibt immer genau eine Kugel und ein Loch.
  • Nicht alle Kurse sind zu schlagen.
  • Möglicherweise gibt es mehrere Pfade, die zu derselben (niedrigsten) Punktzahl führen.

Schlupflöcher und Gewinnbedingung

  • Standardlücken sind verboten
  • Programme müssen beendet werden
  • Du kannst keine zusätzlichen Regeln aufstellen (den Ball so hart treffen, dass er über Wasser springt, von einer Wand abprallt, über Sandfelder springt, Kurven um Ecken herum usw.)
  • Das ist , also gewinnt die Lösung mit der geringsten Anzahl von Zeichen.
  • Lösungen müssen in der Lage sein, alle bereitgestellten Testfälle zu verarbeiten. Wenn dies aufgrund von Einschränkungen der verwendeten Sprache nicht möglich ist, geben Sie dies bitte in Ihrer Antwort an.

Testfälle

Kurs # 1 (2 Treffer)

####
# @#
#o~#
####

Kurs # 2 (nicht möglich)

#####
#@  #
# o #
#   #
#####

Kurs # 3 (3 Treffer)

~~~
~@~
~.~
~ ~
~ ~
~ ~
~ ~
~.~
~o~
~~~

Kurs 4 (2 Schläge)

#########
#~~~~~~~#
#~~~@~~~#
##  .  ##
#~ ~ ~ ~#
#~. o .~#
#~~~ ~~~#
#~~~~~~~#
#########

Kurs # 5 (nicht möglich)

~~~~~~~
~...  ~
~.@.~.~
~...  ~
~ ~ ~.~
~ . .o~
~~~~~~~

Weitere Testfälle:

https://pastebin.com/Azdyym00

Manfred Radlwimmer
quelle
1
Verwandte: Eins , zwei .
AdmBorkBork
Wenn wir ein zweidimensionales Byte-Array als Eingabe verwenden, dürfen wir eine benutzerdefinierte Zuordnung für die Symbole verwenden?
Arnauld
@Arnauld Ich bin mir nicht sicher, inwiefern diesbezüglich der übliche Konsens besteht, aber ich würde sagen, es ist in Ordnung, solange die Eingabe noch erkennbar ist. Ich habe den Eingabebereich aktualisiert .
Manfred Radlwimmer
Wenn Sie das Ziel direkt eingeben, kann der Bestimmungsort ein "Sand" -Symbol sein?
14 m 2
@ l4m2 Klar, so würde es mit allen anderen Regeln in Einklang bleiben.
Manfred Radlwimmer

Antworten:

6

JavaScript (ES6), 174 Byte

Nimmt Eingaben in Curling- Currysyntax vor ([x, y])(a), wobei x und y die 0-indexierten Koordinaten der Startposition sind und a [] eine Ganzzahlmatrix mit 0= Eis, 1= Wand, 2= Sand, 3= Loch und 4= Wasser ist

Gibt zurück, 0wenn es keine Lösung gibt.

p=>a=>(r=F=([x,y],n,R=a[y],c=R[x])=>R[c&(R[x]=4)|n>=r||[-1,0,1,2].map(d=>(g=_=>(k=a[v=Y,Y+=d%2][h=X,X+=~-d%2])||g())(X=x,Y=y)>3?0:k>2?r=-~n:F(k>1?[X,Y]:[h,v],-~n)),x]=c)(p)|r

Probieren Sie es online!

Kommentiert

p => a => (                       // given the starting position p[] and the matrix a[]
  r =                             // r = best result, initialized to a non-numeric value
  F = (                           // F = recursive function taking:
    [x, y],                       //   (x, y) = current position
    n,                            //   n = number of shots, initially undefined
    R = a[y],                     //   R = current row in the matrix
    c = R[x]                      //   c = value of the current cell
  ) =>                            //
    R[                            // this will update R[x] once the inner code is executed
      c & (R[x] = 4) |            //   set the current cell to 4 (water); abort if it was
      n >= r ||                   //   already set to 4 or n is greater than or equal to r
      [-1, 0, 1, 2].map(d =>      //   otherwise, for each direction d:
        (g = _ => (               //     g = recursive function performing the shot by
          k = a[                  //         saving a backup (h, v) of (X, Y)
            v = Y, Y += d % 2][   //         and updating (X, Y) until we reach a cell
            h = X, X += ~-d % 2]) //         whose value k is not 0 (ice)
          || g()                  //   
        )(X = x, Y = y)           //     initial call to g() with (X, Y) = (x, y)
        > 3 ?                     //     if k = 4 (water -> fail):
          0                       //       abort immediately
        :                         //     else:
          k > 2 ?                 //       if k = 3 (hole -> success):
            r = -~n               //         set r to n + 1
          :                       //       else:
            F(                    //         do a recursive call to F():
              k > 1 ?             //           if k = 2 (sand):
                [X, Y]            //             start the next shots from the last cell
              :                   //           else (wall):
                [h, v],           //             start from the last ice cell
              -~n                 //           increment the number of shots
            )                     //         end of recursive call
      ), x                        //   end of map(); x = actual index used to access R[]
    ] = c                         // restore the value of the current cell to c
)(p) | r                          // initial call to F() at the starting position; return r
Arnauld
quelle
5

Python 3 , 273 Bytes

def p(g,c,d,k=0):
	while 1>k:c+=d;k=g.get(c,9)
	return-(k==2)or c-d*(k==3)
def f(g):
	c={q for q in g if g.get(q,9)>4};I=0;s=[c]
	while all(g.get(q,9)-4for q in c):
		c={k for k in{p(g,k,1j**q)for k in c for q in range(4)}if-~k}
		if c in s:return-1
		s+=[c];I+=1
	return I

Probieren Sie es online!

-41 Bytes dank ovs
-1 Bytes dank Jonathan Frech

HyperNeutrino
quelle
Könnte if k+1nicht sein if-~k?
Jonathan Frech
@ JonathanFrech ja, danke
HyperNeutrino
2

C #, 461 418 Bytes

Dies ist nur eine nicht wettbewerbsfähige Referenzimplementierung, um diese Herausforderung (hoffentlich) wiederzubeleben:

Golf gespielt von Kevin Cruijssen

int P(string[]C){int w=C[0].Length,i=0,l=c.Length;var c=string.Join("",C);var h=new int[l];for(var n=new List<int>();i<l;n.Add(i++))h[i]=c[i]!='@'?int.MaxValue:0;for(i=1;;i++){var t=n;n=new List<int>();foreach(int x in t){foreach(int d in new[]{-1,1,-w,w}){for(int j=x+d;c[j]==' ';j+=d);if(c[j]=='#'&h[j-d]>s){h[j-d]=s;n.Add(j-d);}if(c[j]=='.'&h[j]>s){h[j]=s;n.Add(j);}if(c[j]=='o')return s;}}if(n.Count<1)return -1;}}

Ungolfed

int IceGolf(string[] course)
{
    // Width of the course
    int w = course[0].Length;

    // Course as single string
    var c = string.Join("", course);

    // Array of hits per field
    var hits = new int[c.Length];

    // Fields to continue from
    var nextRound = new List<int>();

    // Initialize hits
    for (int i = 0; i < hits.Length; i++)
    {
        if (c[i] != '@')
            // All fields start with a high value
            hits[i] = Int32.MaxValue;
        else
        {
            // Puck field starts with 0
            hits[i] = 0;
            nextRound.Add(i);
        }
    }

    for (int s = 1; ; s++)
    {
        // clear the fields that will be used in the next iteration
        var thisRound = nextRound;
        nextRound = new List<int>();

        foreach (int i in thisRound)
        {
            // test all 4 directions
            foreach (int d in new[] { -1, 1, -w, w })
            {
                int j = i+d;

                // ICE - slide along
                while (c[j] == ' ')
                    j += d;

                // WALL - stop on previous field
                if (c[j] == '#' && hits[j-d] > s)
                {
                    hits[j-d] = s;
                    nextRound.Add(j-d);
                }

                // SAND - stop
                if (c[j] == '.' && hits[j] > s)
                {
                    hits[j] = s;
                    nextRound.Add(j);
                }

                // HOLE return strikes
                if (c[j] == 'o')
                    return s;
            }
        }

        // No possible path found
        if (nextRound.Count == 0)
            return -1;
    }
}

Probieren Sie es online aus

Manfred Radlwimmer
quelle
1
Golf ein bisschen mehr: int P(string[]C){int w=C[0].Length,i=0,l=c.Length;var c=string.Join("",C);var h=new int[l];for(var n=new List<int>();i<l;n.Add(i++))h[i]=c[i]!='@'?int.MaxValue:0;for(i=1;;i++){var t=n;n=new List<int>();foreach(int x in t){foreach(int d in new[]{-1,1,-w,w}){for(int j=x+d;c[j]==' ';j+=d);if(c[j]=='#'&h[j-d]>s){h[j-d]=s;n.Add(j-d);}if(c[j]=='.'&h[j]>s){h[j]=s;n.Add(j);}if(c[j]=='o')return s;}}if(n.Count<1)return -1;}}(418 Bytes). Könnten Sie vielleicht auch einen TIO-Link mit Testcode hinzufügen ?
Kevin Cruijssen
Danke für den TIO Link. Der Code, den ich oben angegeben habe, hat nicht funktioniert, also habe ich ihn behoben und drei weitere Bytes abgelegt. Probieren Sie es online 415 Bytes . (Sie müssen Ihren umfangreichen Testfall von Ihrem aktuellen TIO erneut hinzufügen. Ich konnte den Link nicht in diesen Kommentar einfügen, da der Link für diesen Testfall zu groß war.; P)
Kevin Cruijssen