Wprowadzenie

Zagrajmy w minigolfa! Piłkę golfową reprezentuje a, .a dołek oznacza O. Chcesz uzyskać dziurę w jednej na każdej dziurze, ale nie jesteś dobry w zakładaniu. W rzeczywistości nie próbujesz układać po przekątnej! Tylko w górę, w dół i na boki.

Masz zamiar oszukać poprzez umieszczenie dodatkowych zderzaki \i /tak można umieścić piłkę w jednym strzałem. Piłka odbija się od zderzaków pod kątem prostym, jak pokazano na tym zdjęciu.

Pamiętaj, aby sprawdzić swoją szansę! Powiedz nam, w jakim kierunku się kierujesz.

Dziury

1: Pierwszy dołek jest łatwy, prosty strzał! Nie trzeba tu umieszczać zderzaków.

Wejście:

.         O

Wynik:

right
.         O

2: Kolejny podstawowy, krótki zakręt. Piłka uderza w zderzak w otwór.

Wejście:

     .
O

Wynik:

left
/    .
O

lub

down
     .
O    /

3: Niektóre dziury mają już zderzaki!

Wejście:

.   \O

Wynik:

right
.   \O
    \/

lub

right
   / \
.  /\O

4: Niektóre dziury są zbyt skomplikowane!

Wejście:

    /  \  \    /
   /  . \  \  /
  /  /\/   /\ \  /
 /  /     /  \ \/
/  /   /\ \  /  \  /
\  \  /  \ \/    \/ 
      \  /          /
  /\   \//\ \      /
 /  \   /  \ \     \/
 \  /\  \  /  \     \
  \/  \  \/    \ O/  \
      /         \/

Wynik: (jedno możliwe rozwiązanie, istnieje więcej)

down
    /  \  \    /
   /  . \  \  /
  /  /\/   /\ \  /
 /  /     /  \ \/
/  /   /\ \  /  \  /
\  \  /  \ \/    \/ 
/     \  /          /
  /\   \//\ \      /
\/  \   /  \ \     \/
 \  /\  \  /  \  /  \
  \/  \  \/    \ O/  \
      /  \      \/
                \   /

Zasady

• Dane wejściowe to włączony minigolf STDIN.
• Wyjście jest kierunek trafisz piłkę i otwór do minigolfa z nowo wprowadzanych na zderzaki STDOUT.
• Istniejących zderzaków nie można przenosić.
• Możesz dodać dowolną liczbę zderzaków, aby rozwiązać dziurę.
• Załóżmy, że istnieją odpowiednie lokalizacje dla zderzaków, które pozwolą rozwiązać kurs w jednym putcie.
• Otwór wyjściowy może być większy niż wejście.
• Dane wejściowe mogą być wypełnione końcowymi białymi spacjami, ale proszę podać w swojej odpowiedzi, jeśli to zrobisz.
• Dane wyjściowe muszą wyglądać poprawnie, ale mogą mieć początkowe lub końcowe białe znaki.
• Twój program powinien działać dla każdej prawidłowej dziury. Możesz również opublikować swoje przypadki testowe!

Punktacja

To jest golf golfowy . Twój wynik to liczba znaków w twoim programie. Najniższy wynik wygrywa!

JavaScript (ES6) - 651 bajtów

G=s=>{Q='\\';S=[[]];n=L=1;s.split(N='\n').map(t=>{j=S[L++]=[];l=t.length;n=n>l?n:l;k=1;t.split('').map(T=>{j[k++]=T})});S[O=L++]=[];n++;for(r=0;r<L;r++)for(c=0;c<=n;c++){v=S[r][c];if(!v)S[r][c]=' ';if(v=='.'){x=c;y=r}if(v=='o'){X=c;Y=r}}f=M=>{J=M?'.':'o';K=M?'o':'.';R=0;for(D=0;1;D++){R=D&4;D=D&3;c=e=D;g=M?X:x;h=M?Y:y;while(c!=K){c=S[h+=[-1,0,1,0][e]][g+=[0,1,0,-1][e]];e=c=='/'?(B=c,e^1):c==Q?(B=c,3-e):e;E=h*(h-O)?g*(g-n)?0:2:1;if(R&&c==' '){S[h][g]=Q;R=D=0;c=K}if(c==J||E){E&&(S[h][g]=(E+M)%2?Q:'/');H=M?E?H:(e+2)&3:D;return}}}};f(0);f(1);S[0][0]=S[O][n]='/';S[0][n]=S[O][0]=Q;return['up','right','down','left'][H]+N+S.map(t=>t.join('')).join(N)}

Tworzy funkcję, Gktóra akceptuje ciąg znaków (pole golfowe) jako dane wejściowe i zwraca żądane rozwiązanie wprowadzania. Łańcuch wejściowy może, ale nie musi, mieć linie wiodące, linie końcowe i końcowe białe znaki. Dane wyjściowe nie będą miały początkowych ani końcowych białych znaków.

Rozszerzony kod to:

G = s => {
    Q = '\\';
    S = [[]];
    n = L = 1;
    s.split( N = '\n' ).map( t => {
        j = S[L++] = [];
        l = t.length;
        n = n > l ? n : l;
        k = 1;
        t.split('').map( T => {
            j[k++] = T;
        } );
    } );
    S[O = L++] = [];
    n++;
    for( r = 0; r < L; r++ )
        for( c = 0; c <= n; c++ ) {
            v = S[r][c];
            if( !v )
                S[r][c] = ' ';
            if( v == '.' ) {
                x = c;
                y = r;
            }
            if( v == 'o' ) {
                X = c;
                Y = r;
            }
        }
    f = M => {
        J = M ? '.' : 'o';
        K = M ? 'o' : '.';
        R = 0;
        for( D = 0; 1; D++ ) {
            R = D & 4;
            D = D & 3;
            c = e = D;
            g = M ? X : x;
            h = M ? Y : y;
            while( c != K ) {
                c = S[h += [-1,0,1,0][e]][g += [0,1,0,-1][e]];
                e = c == '/' ? (B=c,e^1) : c == Q ? (B=c,3-e) : e;
                E = h*(h-O) ? g*(g-n) ? 0 : 2 : 1;
                if( R && c == ' ' ) {
                    S[h][g] = B;
                    R = D = 0;
                    c = K;
                }
                if( c == J || E ) {
                    E && (S[h][g] = (E+M)%2 ? Q : '/');
                    H = M ? E ? H : (e+2)&3 : D;
                    return;
                }
            }
        }
    };
    f(0);
    f(1);
    S[0][0] = S[O][n] = '/';
    S[0][n] = S[O][0] = Q;
    return ['up','right','down','left'][H] + N + S.map( t => t.join('') ).join( N );
}

Solver działa w oparciu o założenie, że każda ścieżka z piłki (dołka) też będzie

1. poprowadzić ponownie do piłki (dołka)
2. prowadzić do dziury (piłka)
3. opuścić kurs

Śledzimy ścieżkę piłki we wszystkich czterech kierunkach. Jeśli znajdziemy przypadek 3, problem został rozwiązany. Jeśli znajdziemy przypadek 2, zaznaczamy miejsce wyjścia piłki. Jeśli wszystkie cztery kierunki spowodują przypadek 1, przekształcamy pierwszą przestrzeń bez zderzaka wzdłuż dowolnej trajektorii w zderzak (jeśli problem da się rozwiązać, zawsze istnieje taka przestrzeń) i spróbuj ponownie. Zderzak, na który konwertujemy, będzie miał ten sam typ, co ostatni zderzak, z którym spotkała nas trajektoria *. Jeśli piłka nadal utknęła w pętli, powtarzamy ten proces tyle razy, ile potrzeba. Jeśli problem można rozwiązać, procedura ta ostatecznie doprowadzi do wyniku 2 lub 3.

(* Zauważ, że jeśli po prostu przekonwertujemy na stały zderzak [powiedzmy \], istnieją wyjątkowo wymyślone, ale mimo to możliwe przypadki, w których istnieje rozwiązanie, ale nie znajdziemy go.)

Wykonujemy podobny ślad z dołka, prowadząc do wyniku 2 lub wyniku 3.

Jeśli zarówno ślad kuli, jak i ślad dziury dają wynik 2, umieszczamy zderzaki na obrzeżach trasy, które łączą dwa punkty wyjścia (w rzeczywistości te zderzaki peryferyjne są umieszczane niezależnie od wyników śledzenia, aby skrócić kod). To uzupełnia rozwiązanie.

Przypadki testowe i wyniki

W

   /   \   / \ /\    
   \\      /    \  \ 
       /     / o   / 
   /   \       /     
   \   .  \  \    \\ 
       /  /     \ \  
       \          /  
           \      /  
 \ /\     /  \/  //\

Na zewnątrz

right
/   /               \
   /   \   / \ /\    
   \\      /    \  \ 
       /     / o   / 
   /   \       /     
   \   .  \  \    \\ 
       /  /     \ \  
       \          / /
           \      /  
 \ /\     /  \/  //\ 
\                   /

W

  / \   / /    /  \    / \  /  \\ /
\   \ /  \  // \    \   /   /\   \
/ \   // \  //   \ \   \ /  / \\ \
 \  / \    /   \  \  / / \\ / /  //
/ /   /\ \\ //  / \   /  \ / \\ \ \
\   \  \ \ // \ /  /    \ \  /  / /
/ \ /   /  / \     / \ /\   /  \  /
\ /\  //\   .\  \ \ //\ /  \  / \ /
/ \/ \ /\ //\   /   \   / o// \ / \
/   / \    / \ / \\ / \   / \   \ \
/ /   / \  / \ //   \    / \/  /\/
   / \   / \  /   \\  / \    /\ / \
/ \/   \   /   \/  \   /  \    /\\
/ /\\ //\  / \  /\ /\   /  / \ / \/

Na zewnątrz

left
/                                   \
   / \   / /    /  \    / \  /  \\ / 
 \   \ /  \  // \    \   /   /\   \  
 / \   // \  //   \ \   \ /  / \\ \  
  \  / \    /   \  \  / / \\ / /  // 
 / /   /\ \\ //  / \   /  \ / \\ \ \ 
 \   \  \ \ // \ /  /    \ \  /  / / 
 / \ /   /  / \     / \ /\   /  \  / 
 \ /\  //\   .\  \ \ //\ /  \  / \ / 
 / \/ \ /\ //\   /   \   / o// \ / \ 
 /   / \    / \ / \\ / \   / \   \ \ 
 / /   / \  / \ //   \    / \/  /\/  
    / \   / \  /   \\  / \    /\ / \ 
 / \/   \   /   \/  \   /  \    /\\  
 / /\\ //\  / \  /\ /\   /  / \ / \/ 
\         \                         /

W

/\/ \      
\  \ \     
 \ \\ \   o
  \ .\ \   
   \ / /   
    \ /    

Na zewnątrz

down
/   \      /\
 /\/\\       
 \ \\ \      
  \ \\ \   o 
   \ .\ \    
    \ / /    
     \ /     
\           /