Eine Kurve ist eine Menge von Punkten auf einem quadratischen Gitter, sodass jeder Punkt genau zwei Nachbarn in der Nachbarschaft mit vier Nachbarn hat und die Punkte eine einzelne verbundene Komponente bilden. Das heißt, der Graph, der durch die Punkte in einem Gittergraph induziert wird, ist isomorph zu einem einzelnen Zyklus. "Induziert" bedeutet, dass sich zwei Punkte in der Eingabe nicht berühren können, ohne Nachbarn im Zyklus zu sein.

Ein Antipode eines Scheitelpunkts V in einem Diagramm ist ein Scheitelpunkt, der am weitesten von V entfernt ist. Der Antipode ist in einem Zyklus mit gerader Länge immer eindeutig (und jeder Zyklus in einem Gitterdiagramm hat eine gerade Länge). Der Abstand ist so zu messen, wie er durch den Zyklus selbst ohne Berücksichtigung des zugrunde liegenden quadratischen Gitters hervorgerufen wird.

Ihre Eingabe soll ein Bild einer Kurve sein. Die Kurve wird mit einer Folge von Zahlenzeichen ( #) auf einem Hintergrund aus Leerzeichen ( ) markiert . Einer der Punkte auf der Kurve wird mit dem PZeichen ("pode") markiert . Ihre Ausgabe muss mit der Eingabe identisch sein, mit der Ausnahme, dass ein Kurvenpunkt durch A("Antipode") ersetzt werden soll.

Sie können davon ausgehen, dass die Zeichen zu einer rechteckigen Form aufgefüllt werden. Sie können davon ausgehen, dass die erste und letzte Zeile und Spalte der Eingabe vollständig aus Leerzeichen bestehen (Eingabe wird mit Hintergrund aufgefüllt). Alternativ können Sie davon ausgehen, dass die erste und die letzte Zeile und Spalte jeweils einen Kurvenpunkt enthalten (Eingabe mit minimaler Auffüllung).

Sie können dieses Raster als einzelne durch Zeilenumbrüche getrennte Zeichenfolge, als Array von Zeilen oder als 2D-Array einzelner Zeichen eingeben und ausgeben. Diese Auswahl muss für die Eingabe und Ausgabe gleich sein. Wenn Ihre Sprache dies zulässt, können Sie die Ausgabe durchführen, indem Sie die Eingabe ändern, anstatt die geänderte Zeichenfolge oder das geänderte Array zurückzugeben.

Mögliche Eingaben:

P#    P##   #P#   #####      #####P# #######   #####P#########   #####P#########
##    # #   # #   #   #      #     # #     #   #             #   #             #
      ###   ###   ## ##      # ### # # ### #   # ### ### ### #   #             #
###                # # ###   # # # # # # # #   # # # # # # # #   #             #
# P#    ### ###    # ### #   # # ### ### # #   # # ### ### # #   #             #
## #    # ### #    #     #   # #         # #   # #         # #   #             #
 # #    P     #    ##### P   # ########### #   # ##### ##### #   #             #
 ###    #######        ###   #             #   #     # #     #   #             #
                             ###############   ####### #######   ###############

Entsprechende Ausgänge:

P#    P##   #P#   #A###      #####P# #A#####   #####P#########   #####P#########
#A    # #   # #   #   #      #     # #     #   #             #   #             #
      ##A   #A#   ## ##      # ### # # ### #   # ### ### ### #   #             #
###                # # ###   # # # # # # # #   # # # # A # # #   #             #
# P#    ### ##A    # ### #   # # ### ### # #   # # ### ### # #   #             #
## #    # ### #    #     #   # #         # #   # #         # #   #             #
 A #    P     #    ##### P   # ########### #   # ##### ##### #   #             #
 ###    #######        ###   #             #   #     # #     #   #             #
                             ###############   ####### #######   #########A#####

Scheitelpunktabstände zu den Pods (Modulo 10) (diese nicht ausgeben):

P1    P12   1P1   5A543      54321P1 9A98765   54321P123456789   54321P123456789
1A    1 3   2 2   4   2      6     2 8     4   6             0   6             0
      23A   3A3   32 01      7 109 3 7 109 3   7 901 789 543 1   7             1
321                1 9 543   8 2 8 4 6 2 8 2   8 8 2 6 A 6 2 2   8             2
4 P1    234 89A    0 876 2   9 3 765 543 7 1   9 7 345 987 1 3   9             3
56 2    1 567 9    9     1   0 4         6 0   0 6         0 4   0             4
 A 3    P     8    87654 P   1 56789012345 9   1 54321 56789 5   1             5
 654    1234567        321   2             8   2     0 4     6   2             6
                             345678901234567   3456789 3210987   345678901A10987

JavaScript (ES6), 193 181 Bytes

f=s=>s==(`P#1P#21#12#221A`[r=`replace`](/.../g,([n,f,t])=>s=s[r](eval(`/([${n+=f}])([^]{${s.search`\n`}})?(?!\\1)[${n}]/`),m=>m[r](eval(`/^${f}|${f}$/`),t))),s)?s[r](/\d/g,`#`):f(s)

Version, die eine Loop-Animation bereitstellt:

f=s=>s==(`#A#1#12#221AP#1P#2`[r=`replace`](/.../g,([n,f,t])=>s=s[r](eval(`/([${n+=f}])([^]{${s.search`\n`}})?(?!\\1)[${n}]/`),m=>m[r](eval(`/^${f}|${f}$/`),t))),s)?s[r](/\d/g,`#`):s
;setInterval(_=>i.value=f(i.value),1e3)

<textarea rows=10 cols=20 id=i style="font-family:monospace"></textarea>

Python 2 , 333 221 215 Bytes

-17 Bytes dank @JanDvorak

g=input()
y=map(max,g).index('P')
x=g[y].index('P')
m=[k[:]for k in g]
v=x;w=y
while'#'in sum(m,[]):x,y,(v,w)=v,w,[(x+a,y+b)for a,b in((1,0),(-1,0),(0,1),(0,-1))if'#'==m[y+b][x+a]][0];m[w][v]='_'
g[w][v]='A'
print g

Probieren Sie es online!

Python 3 , 402 288 282 Bytes, String IO

g=[[*k]for k in open(0).read().split('\n')]
y=[max(k)for k in g].index('P')
x=g[y].index('P')
m=[k[:]for k in g]
v=x;w=y
while'#'in sum(m,[]):x,y,(v,w)=v,w,[(x+a,y+b)for a,b in((1,0),(-1,0),(0,1),(0,-1))if'#'==m[y+b][x+a]][0];m[w][v]='_'
g[w][v]='A'
print('\n'.join(map(''.join,g)))

Probieren Sie es online!

Animation des laufenden Codes:

MATL , 43 42 Bytes

32-I#fbbJ*+!w3>y"&)yy-|&X<]vJQ2/)G65b&Zj&(

Der Code akzeptiert eine beliebige Menge an Leerzeichen in der ersten und letzten Zeile und Spalte. Die Eingabe ist eine rechteckige Zeichenfolge, die ;als Zeilentrennzeichen verwendet wird. Zum Beispiel die Eingabe

#####   
#   #   
## ##   
 # # ###
 # ### #
 #     #
 ##### P
     ###

wird dargestellt als

['#####   ';
 '#   #   ';
 '## ##   ';
 ' # # ###';
 ' # ### #';
 ' #     #';
 ' ##### P';
 '     ###']

oder, in einer Zeile (so kann es durch STDIN eingegeben werden),

['#####   '; '#   #   '; '## ##   '; ' # # ###'; ' # ### #'; ' #     #'; ' ##### P'; '     ###']

Probieren Sie es online! Oder verifizieren Sie die letzten vier Fälle: 1 , 2 , 3 , 4 (diese wurden ausgewählt, weil sie die kompliziertesten Kurven haben; der letzte hat ein gewisses Leerzeichen).

Erläuterung

TL; WR: Komplexe Zahlen, viel Indizierung, keine Faltung.

32-     % Implicitly input char matrix. Subtract 32. Space becomes zero
I#f     % 3-output find: pushes nonzero values, their row indices,
        % and their column indices, as column vectors
bb      % Bubble up twice, so row and column indices are on top
J*+     % Times 1j, add. This transforms row and column indices into
        % complex numbers, where real is row and imaginary is column
!       % Transpose into a row vector
w       % Swap, so vector of nonzero values is on top
3>      % Logical index of elements exceeding 3. ASCII codes of space,
        % '#' and 'P0 are 32, 35 and 80 respectively. Since 32 was
        % subtracted these became 0, 3 and 48. So the only entry with
        % value exceeding 3 is that corresponding to the original 'P'.
y"      % Do this as many times as the number of complex positions
        %   The stack now contains the vector of complex positions and an
        %   index into that vector. The index points to the complex position 
        %   to be processed next.
  &)    %   Two-output reference indexing: pushes the indexed entry and
        %   a vector with the remaining entries. This pulls off the
        %   current complex position, which is initially that of 'P'
  yy    %   Duplicate top two elements, i.e. current position and vector
        %   of remaining positions
  -|    %   Absolute differences
  &X<   %   Index of minimum. Gives the index of the complex position
        %   that is closest to the current one. In case of tie (which
        %   only happens in the first iteration) it picks the first. The 
        %   result is the index of the complex position to be processed in 
        %   the next iteration. This index will be empty if this is the last
        %   iteration.
]       % End
        % The stack now contains the complex positions as individual
        % values, starting from 'P' and sorted as per the curve; plus two 
        % empty arrays. These empty arrays have been produced by the last
        % iteration as the index for the "next" iteration and the array of
        % "remaining" complex positions
v       % Concatenate into a column vector. The empty arrays have no effect.
        % The resulting vector contains the sorted complex positions
JQ      % Push 1j and add 1
2/      % Divide by 2. This gives (1+1j)/2. When used as an index this is
        % interpreted as (1+end)/2. Since the length of the curve is even
        % this gives a non-integer number, which will be implicitly
        % rounded up (because of .5 fracctional part). As an example, for
        % length 32 this gives 16.5, which rounded becomes 17. Position 17
        % along the curve is the antipode of position 1
)       % Reference indexing. Gives the complex position of the antipode
G       % Push input char matrix again
65      % Push 65 (ASCII for 'A')
b       % Bubble up, so complex position is on top
&Zj     % Separate into real and imagimary parts, corresponding to row and
        % column indices
&(      % 4-input assignment indexing. This writes 'A' at the specified row
        % and column of the char matrix. Implicitly display

Python 3 , 421 Bytes

l,e=len,enumerate
r=open(0).read()
n=lambda x:[(x[0]-1,x[1]),(x[0]+1,x[1]),(x[0],x[1]-1),(x[0],x[1]+1)]
p=a={(i,j):y for i,x in e(r.split('\n'))for j,y in e(x)}
t=l(r.split('\n'));s=l(r.split('\n')[0])
for i in a:p=[p,i][a[i]=='P']
w=[p]
while l(w)!=r.count('#')+1:
 for x in a:
  if x in n(w[-1])and a[x]!=' 'and x not in w:w+=[x]
a[w[(l(w)+1)//2]]='A';print('\n'.join(''.join(a[j,i]for i in range(s))for j in range(t)))

Probieren Sie es online!

Mathematica, 234 223 Bytes

(p=Position;v=p[#,"#"|"P"];n=Length@v;q=v[[#]]&;h=FindCycle[Graph[v,Join@@Table[If[Norm[q@i-q@j]==1,q@i<->q@j,Nothing],{i,n},{j,i-1}]]][[1,#,1]]&;ReplacePart[#,h@Mod[p[Table[h@x,{x,n}],p[#,"P"][[1]]][[1,1]]+n/2,n,1]->"A"])&

Dieser Code ist vdie Scheitelpunktliste für das Diagramm: die Indizes von "#"und "P". Dann nist die Länge (unbedingt gerade) undq extrahiert den eingegebenen Eckpunkt (ignoriert also die Form der Schleife).

Dann hist es eine Funktion, die den Graphen mit Eckpunkten in vund ungerichteten Kanten zwischen Eckpunkten erstellt, wenn die Länge der Differenz ihrer Indexpaare genau 1 beträgt (ihre Differenz ist also so etwas wie {-1,0}oder){0,1} ) und dann eine Liste aller Zyklen findet und die erste liefert (nur) Zyklus (als eine Liste von Kanten) und nimmt dann die eingegebene Kante und nimmt den ersten Scheitelpunkt, der diese Kante bildet.

Mit hkönnen wir den Index von "P"im Zyklus finden und auf halber Strecke (mit Mod zum Umbrechen, wenn wir die Grenzen der Zyklusliste überschreiten) nach dem Antipoden suchen und dann den entsprechenden Eintrag des Originals ersetzen Eingangm mit"A"

Sie können es online ausprobieren, indem Sie Folgendes in die Wolfram Cloud Sandbox einfügen und auf "Zelle auswerten" klicken oder Umschalt + Eingabetaste oder Ziffernblock-Eingabetaste drücken:

(p=Position;v=p[#,"#"|"P"];n=Length@v;q=v[[#]]&;h=FindCycle[Graph[v,Join@@Table[If[Norm[q@i-q@j]==1,q@i<->q@j,Nothing],{i,n},{j,i-1}]]][[1,#,1]]&;ReplacePart[#,h@Mod[p[Table[h@x,{x,n}],p[#,"P"][[1]]][[1,1]]+n/2,n,1]->"A"])&@{{"#","#","#","#","#"," "," "," "},{"#"," "," "," ","#"," "," "," "},{"#","#"," ","#","#"," "," "," "},{" ","#"," ","#"," ","#","#","#"},{" ","#"," ","#","#","#"," ","#"},{" ","#"," "," "," "," "," ","#"},{" ","#","#","#","#","#"," ","P"},{" "," "," "," "," ","#","#","#"}}//MatrixForm

Alternative Idee, 258 Bytes

Etwas inspiriert von den Python-Lösungen von ovs habe ich versucht, Code zu schreiben, der keine graphentheoretischen Funktionen von Mathematica verwendet und die Entfernungen einfach blind berechnet. Ich konnte es nicht so kurz fassen, aber ich vermute, jemand könnte es verbessern:

f[m_]:=(x="#";t=ReplacePart;p=Position;l=t[m,p[m,"P"][[1]]->0];v=p[l,x|0];n=Length[v];q=v[[#]]&;r=l[[q[#][[1]],q[#][[2]]]]&;y=t[l,q@#->(r@#2+1)]&;Do[If[Norm[q@i-q@j]==1&&Xor[r@i==x,r@j==x],If[r@i==x,l=y[i,j],l=y[j,i]]],n,{i,n},{j,n}];t[m,p[l,n/2][[1]]->"A"])`

Dieser Code ist sehr ineffizient. Grundsätzlich ersetzt es "P"mit 0und sucht dann nach einem "#"neben etwas , das kein ist "#"durch Looping durch die ganze Sache zweimal und ersetzt sie mit Zahlen , die den Abstand von "P"und um sicherzustellen , dass es fertig ist , tut es , die nProzesszeiten. Dies berechnet die Entfernungen nicht einmal richtig, da ein Zweig den Antipode passieren könnte, aber nur ein Standort wird nummeriert, n/2egal was passiert .