Kurva adalah seperangkat titik pada kotak persegi sedemikian rupa sehingga setiap titik memiliki tepat dua tetangga di lingkungan empat tetangga dan titik tersebut membentuk komponen yang terhubung tunggal. Yaitu, grafik yang diinduksi oleh titik-titik pada grafik kotak adalah isomorfik untuk satu siklus tunggal. "Diinduksi" berarti bahwa dua titik tidak dapat menyentuh input tanpa menjadi tetangga dalam siklus.

Antipode dari vertex V dalam grafik adalah vertex terjauh dari V. Antipode selalu unik pada siklus panjang genap (dan setiap siklus pada grafik kotak adalah panjang gelombang genap). Jarak harus diukur sebagaimana diinduksi oleh siklus itu sendiri tanpa menghormati grid persegi yang mendasarinya.

Masukan Anda harus berupa gambar kurva. Kurva akan ditandai dengan urutan karakter tanda angka ( #) pada latar belakang karakter spasi ( ). Salah satu titik pada kurva akan ditandai dengan Pkarakter ("pode"). Output Anda harus sama dengan input kecuali satu titik kurva harus diganti dengan A("antipode").

Anda mungkin menganggap karakter akan diisi ke bentuk persegi panjang. Anda dapat mengasumsikan baris pertama dan terakhir dan kolom input akan seluruhnya terdiri dari spasi (input diisi dengan latar belakang). Atau Anda dapat mengasumsikan bahwa baris dan kolom pertama dan terakhir masing-masing akan berisi titik kurva (input memiliki padding minimum).

Anda dapat memasukkan dan menampilkan kisi ini sebagai string yang dipisahkan oleh baris baru, sebagai larik baris, atau sebagai larik 2D karakter individu. Pilihan ini harus sama untuk input dan output. Jika bahasa Anda memungkinkan ini, Anda dapat menampilkan dengan memodifikasi input di tempat alih-alih mengembalikan string atau array yang dimodifikasi.

Input yang mungkin:

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

Output yang sesuai:

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

Jarak vertex dari podes (modulo 10) (jangan output ini):

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 byte

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)

Versi yang menyediakan animasi pengulangan:

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 byte

-17 byte terima kasih kepada @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

Cobalah online!

Python 3 , 402 288 282 byte, 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)))

Cobalah online!

Animasi menjalankan kode:

MATL , 43 42 byte

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

Kode menerima jumlah ruang padding sewenang-wenang di baris dan kolom pertama dan terakhir. Input adalah array karakter persegi panjang, menggunakan ;pemisah baris. Misalnya input

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

direpresentasikan sebagai

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

atau, dalam satu baris (sehingga dapat dimasukkan melalui STDIN),

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

Cobalah online! Atau verifikasi empat kasus terakhir: 1 , 2 , 3 , 4 (ini telah dipilih karena mereka memiliki kurva paling rumit; yang terakhir memiliki beberapa ruang bantalan).

Penjelasan

TL; WR: Bilangan kompleks, banyak pengindeksan, tidak ada konvolusi.

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 byte

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)))

Cobalah online!

Mathematica, 234 223 byte

(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"])&

Kode ini vmenjadi daftar simpul untuk grafik: indeks "#"dan "P"s. Kemudian nadalah panjang (tentu genap) dan qmengekstrak input-th vertex (jadi mengabaikan bentuk loop).

Kemudian hadalah fungsi yang membangun grafik dengan simpul di dalam vdan tepi tidak langsung di antara simpul ketika panjang perbedaan pasangan indeks mereka tepat 1 (jadi perbedaannya adalah seperti {-1,0}atau {0,1}) dan kemudian menemukan daftar semua siklus dan memberikan yang pertama (hanya) siklus (sebagai daftar tepi) dan kemudian mengambil tepi input-th dan mengambil simpul pertama yang membentuk tepi itu.

Dengan menggunakan h, kita dapat menemukan indeks "P"dalam siklus, dan pergi setengah jalan (menggunakan Mod untuk membungkus jika kita melewati batas-batas daftar siklus) untuk menemukan antipode, dan kemudian kita dapat mengganti entri yang sesuai dengan aslinya masukan mdengan"A"

Anda dapat mencobanya secara online dengan menempelkan yang berikut di Wolfram Cloud Sandbox dan mengklik "evaluasi sel" atau menekan Shift + Enter atau Numpad Enter:

(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

Gagasan alternatif, 258 byte

Sedikit terinspirasi oleh solusi Python ovs , saya mencoba menulis kode yang tidak akan menggunakan fitur teori grafik apapun dari Mathematica dan hanya secara membabi buta menghitung jarak. Saya tidak bisa membuatnya sesingkat itu, tetapi mencurigai seseorang dapat memperbaikinya:

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"])`

Kode ini sangat tidak efisien. Pada dasarnya, itu menggantikan "P"dengan 0dan kemudian mencari di "#"sebelah sesuatu yang bukan "#"dengan mengulangi seluruh hal dua kali dan menggantikannya dengan angka-angka yang mewakili jarak dari "P", dan untuk memastikan itu selesai, ia melakukan itu proses nkali. Ini sebenarnya bahkan tidak menghitung jarak dengan benar karena satu cabang bisa melewati antipode, tetapi hanya satu lokasi yang akan diberi nomor n/2tanpa peduli apa.