Ice Golf Challenge

24

Celem tego wyzwania jest napisanie programu lub funkcji, która zwraca najmniejszą liczbę uderzeń potrzebnych do ukończenia danego kursu.

Wkład

  • Układ kursu można przekazać w dowolny odpowiedni sposób i format. (odczytane z konsoli, przekazane jako parametr wejściowy, odczytane z pliku lub dowolnego innego, wielowierszowego łańcucha znaków, tablicy znaków, dwuwymiarowej tablicy znaków / bajtów).
  • Pozycja początkowa piłki i dołka można również podać jako dane wejściowe, nie trzeba go analizować od wartości wejściowej. W przypadkach testowych są one uwzględnione w kursie, aby upewnić się, że nie ma wątpliwości co do rzeczywistej pozycji.
  • Możesz ponownie przypisać znaki wejściowe do czegoś innego, o ile nadal są one rozpoznawalne jako odrębne znaki (np. Znaki ASCII do wydruku).

Wydajność

  • Program musi zwrócić najniższą możliwą liczbę punktów (najmniejszą liczbę uderzeń potrzebnych do dotarcia do dołka) dla każdego kursu zaliczonego jako dane wejściowe w rozsądnym formacie (łańcuch, liczba całkowita, liczba zmiennoprzecinkowa lub haiku opisujące wynik)
  • Jeśli nie można pokonać kursu, zwróć -1(lub dowolną inną wybraną przez ciebie wartość fałszowania , która nie zostałaby zwrócona dla kursu możliwego do pokonania ).

Przykład:

W tym przykładzie pozycje są zapisywane w oparciu o 0, X / Y, od lewej do prawej, od góry do dołu - ale możesz użyć dowolnego formatu, który ci się podoba, ponieważ wynik i tak jest całkowicie niezależny od formatu.

Wkład:

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

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

Wydajność:

8

Przykładowy kurs

Zasady i pola

Kurs może składać się z następujących pól:

  • '@' Piłka - początek kursu
  • 'o' Dziura - cel kursu
  • '#' Ściana - kula zatrzyma się, gdy uderzy w ścianę
  • '~' Woda - należy tego unikać
  • '.' Piasek - kula natychmiast zatrzyma się na piasku
  • ' ' Ice - Ball będzie się ślizgać, dopóki nie trafi w coś

Podstawowe zasady i ograniczenia gry:

  • Piłka nie może się poruszać po przekątnej, tylko w lewo, w prawo, w górę iw dół.
  • Piłka nie zatrzyma się przed wodą, tylko przed ścianami, na piasku i dołku.
    • Strzały do ​​wody są nieprawidłowe / niemożliwe
    • Piłka pozostanie w dołku, nie przeskakując nad nią jak na lodzie
  • Pole jest zawsze prostokątne.
  • Kurs zawsze graniczy z wodą lub ścianami (nie są wymagane kontrole graniczne).
  • Zawsze jest dokładnie jedna piłka i jeden dołek.
  • Nie wszystkie kursy można pokonać.
  • Może istnieć wiele ścieżek, które dają ten sam (najniższy) wynik.

Luki i warunki wygranej

  • Standardowe luki są zabronione
  • Programy muszą zostać zakończone
  • Nie możesz wymyślić dodatkowych zasad (uderzanie piłki tak mocno, że przeskakuje nad wodą, odbija się od ściany, przeskakuje pola piasku, zakręty wokół narożników itp.)
  • To jest , więc wygrywa rozwiązanie z najmniejszą liczbą znaków.
  • Rozwiązania muszą być w stanie obsłużyć wszystkie dostarczone przypadki testowe, jeśli jest to niemożliwe z powodu ograniczeń używanego języka, należy to zaznaczyć w odpowiedzi.

Przypadki testowe

Kurs nr 1 (2 uderzenia)

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

Kurs nr 2 (niemożliwy)

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

Kurs nr 3 (3 uderzenia)

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

Kurs nr 4 (2 uderzenia)

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

Kurs nr 5 (niemożliwy)

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

Więcej przypadków testowych:

https://pastebin.com/Azdyym00

Manfred Radlwimmer
źródło
1
Powiązane: Raz , dwa .
AdmBorkBork
Jeśli użyjemy dwuwymiarowej tablicy bajtów jako danych wejściowych, czy możemy użyć niestandardowego odwzorowania symboli?
Arnauld
@Arnauld Nie jestem pewien, jaki jest tutaj zwykły konsensus, ale powiedziałbym, że jest w porządku, dopóki dane wejściowe są nadal rozpoznawalne. Zaktualizowałem sekcję Input .
Manfred Radlwimmer
Jeśli wpisujesz cel bezpośrednio, czy możemy wymagać, aby miejscem przeznaczenia był symbol „piasku”?
l4m2
@ l4m2 Jasne, w ten sposób pozostanie on zgodny ze wszystkimi innymi zasadami.
Manfred Radlwimmer

Odpowiedzi:

6

JavaScript (ES6), 174 bajty

Staje się wkład w zwijając zmiękczania składni ([x, y])(a), gdzie x i y są indeksowane 0 współrzędne położenia wyjściowego i w [] jest macierzą liczb z 0= lód 1= ściennego 2= piaskowej 3= otworu i 4= woda

Zwraca, 0jeśli nie ma rozwiązania.

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

Wypróbuj online!

Skomentował

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
źródło
5

Python 3 , 273 bajty

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

Wypróbuj online!

-41 bajtów dzięki ovs
-1 bajtów dzięki Jonathanowi Frechowi

HyperNeutrino
źródło
Mogłoby if k+1nie być if-~k?
Jonathan Frech,
@JathanathanFrech tak, dzięki
HyperNeutrino,
2

C #, 461 418 bajtów

To jest tylko niekonkurencyjna implementacja referencyjna, która (miejmy nadzieję) ożywi to wyzwanie:

Grał w golfa 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;}}

Bez golfa

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;
    }
}

Wypróbuj online

Manfred Radlwimmer
źródło
1
Grał w golfa trochę więcej: 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 bajtów). A może mógłbyś dodać link TIO z kodem testowym?
Kevin Cruijssen
Dzięki za link TIO. Powyższy kod nie działał, więc go naprawiłem i grałem w golfa jeszcze trzy bajty. Wypróbuj online 415 bajtów . (Będziesz musiał ponownie dodać swoją ogromną walizkę testową z obecnego TIO. Nie mogłem wkleić linku w tym komentarzu, ponieważ link był za duży w tym przypadku testowym ..; p)
Kevin Cruijssen