Calculer l'antipode d'un point sur une courbe

14

Une courbe est un ensemble de points sur une grille carrée de telle sorte que chaque point a exactement deux voisins dans le voisinage à quatre voisins et les points forment une seule composante connectée. C'est-à-dire que le graphique induit par les points sur un graphique en grille est isomorphe à un seul cycle. "Induit" signifie que deux points ne peuvent pas se toucher dans l'entrée sans être voisins dans le cycle.

Un antipode d'un sommet V dans un graphique est un sommet le plus éloigné de V. L'antipode est toujours unique sur un cycle de longueur paire (et chaque cycle sur un graphique en grille est de longueur paire). La distance doit être mesurée comme induite par le cycle lui-même sans respecter la grille carrée sous-jacente.

Votre entrée doit être une image d'une courbe. La courbe sera délimitée par une séquence de caractères de signe numérique ( #) sur un arrière-plan sans espace ( ). Un des points de la courbe sera marqué du Pcaractère ("pode"). Votre sortie doit être la même que l'entrée sauf un point de courbe doit être remplacé par A("antipode").

Vous pouvez supposer que les caractères seront rembourrés dans une forme rectangulaire. Vous pouvez supposer que la première et la dernière ligne et colonne d'entrée seront entièrement composées d'espaces (l'entrée est remplie d'arrière-plan). Vous pouvez également supposer que la première et la dernière ligne et colonne contiendront chacune un point de courbe (l'entrée a un remplissage minimal).

Vous pouvez entrer et sortir cette grille sous la forme d'une chaîne séparée par des sauts de ligne, sous forme de tableau de lignes ou sous forme de tableau 2D de caractères individuels. Ce choix doit être le même pour l'entrée et la sortie. Si votre langue le permet, vous pouvez produire en modifiant l'entrée en place au lieu de renvoyer la chaîne ou le tableau modifié.

Entrées possibles:

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

Sorties correspondantes:

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

Distances des sommets par rapport aux podes (modulo 10) (ne pas les afficher):

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
John Dvorak
la source

Réponses:

4

JavaScript (ES6), 193 181 octets

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 qui fournit une animation en boucle:

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>

Neil
la source
4

Python 2 , 333 221 215 octets

-17 octets grâce à @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

Essayez-le en ligne!


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

Essayez-le en ligne!


Animation du code en cours d'exécution:

Animation du code en cours d'exécution

ovs
la source
4

MATL , 43 42 octets

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

Le code accepte une quantité arbitraire de remplissage d'espace dans les première et dernière lignes et colonnes. L'entrée est un tableau rectangulaire de caractères, utilisant ;comme séparateur de ligne. Par exemple, l'entrée

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

est représenté comme

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

ou, sur une seule ligne (pour pouvoir être saisie via STDIN),

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

Essayez-le en ligne! Ou vérifiez les quatre derniers cas: 1 , 2 , 3 , 4 (ceux-ci ont été choisis car ils ont les courbes les plus compliquées; le dernier a un peu d'espace).

Explication

TL; WR: nombres complexes, beaucoup d'indexation, pas de convolution.

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
Luis Mendo
la source
0

Python 3 , 421 octets

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

Essayez-le en ligne!

officialaimm
la source
0

Mathematica, 234 223 octets

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

Ce code fait vêtre la liste des sommets du graphe: les indices des "#"et "P"s. Alors nest la longueur (nécessairement égale) etq extrait le sommet en entrée (ignorant ainsi la forme de la boucle).

Ensuite, hune fonction qui construit le graphique avec des sommets vet des bords non orientés entre les sommets lorsque la longueur de la différence de leurs paires d'index est exactement de 1 (leur différence est donc quelque chose comme {-1,0}ou{0,1} ), puis trouve une liste de tous les cycles et fournit le premier (uniquement) cycle (comme une liste d'arêtes), puis prend l'arête d'entrée-e et prend le premier sommet constituant cette arête.

En utilisant h, nous pouvons trouver l'index du "P"dans le cycle, et faire le tour (en utilisant Mod pour envelopper si nous dépassons les limites de la liste des cycles) pour trouver l'antipode, puis nous pouvons remplacer l'entrée correspondante de l'original entrée mavec"A"

Vous pouvez l' essayer en ligne avec en collant ce qui suit dans le Wolfram Cloud Sandbox et en cliquant sur "évaluer la cellule" ou en appuyant sur Maj + Entrée ou Entrée du pavé numérique:

(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

Idée alternative, 258 octets

Un peu inspiré par les solutions Python d' Ovs , j'ai essayé d'écrire du code qui n'utiliserait aucune fonction de théorie des graphes de Mathematica et calculerait simplement les distances à l'aveugle. Je ne pouvais pas le faire aussi court, mais je soupçonne que quelqu'un pourrait l'améliorer:

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

Ce code est très inefficace. Fondamentalement, il remplace "P"par 0puis recherche un "#"élément à côté de quelque chose qui n'est pas un "#"en parcourant deux fois l'intégralité de la chose et en les remplaçant par des nombres représentant la distance à partir de laquelle "P", pour être sûr qu'elle se termine, elle exécute les ntemps de traitement . En fait, cela ne calcule même pas correctement les distances, car une branche pourrait dépasser l'antipode, mais un seul emplacement sera numéroté n/2, quoi qu'il arrive.

Des marques.
la source