Combinaison linéaire de deux vecteurs

11

Résumé

Étant donné une entrée représentant deux vecteurs et leurs «poids» respectifs, produire une sortie qui représente également la somme pondérée de ces vecteurs.

Défi

L'entrée consistera en une ou plusieurs lignes des caractères suivants:

  • exactement une occurrence du chiffre 0, qui représente l'origine dans un plan bidimensionnel;
  • exactement deux autres chiffres (1-9; peuvent ou non être le même chiffre), dont les positions par rapport à l'origine représentent des vecteurs, et dont les valeurs représentent les poids attachés à ces vecteurs;
  • un certain nombre de "caractères d'arrière-plan". Le solveur peut choisir un caractère d'arrière-plan spécifique; par exemple, je choisirai "." (principalement pour la lisibilité humaine). Alternativement, les caractères d'arrière-plan peuvent être tout ce qui ressemble à un espace vide.

(Le solveur peut choisir si l'entrée est une seule chaîne à plusieurs lignes ou un tableau de chaînes à une seule ligne.)

Par exemple, l'entrée

....2
.0...
...3.

représente un vecteur aux coordonnées (3,1) de poids 2, et un vecteur aux coordonnées (2, -1) de poids 3.

La sortie doit être presque la même que l'entrée, avec les modifications suivantes:

  • un "caractère de résultat", choisi par le solveur, à ajouter à la position spécifiée par la somme pondérée des vecteurs d'entrée (de manière équivalente, à la position qui est la combinaison linéaire appropriée des vecteurs d'entrée);
  • autant de caractères d'arrière-plan que nécessaire pour adapter l'origine, les deux vecteurs d'entrée et le vecteur de sortie dans la même image. Des caractères d'arrière-plan supplémentaires peuvent être inclus si vous le souhaitez; la seule contrainte est que, si le caractère d'arrière-plan est un caractère visible, la sortie entière doit être de forme rectangulaire et chaque caractère ne représentant pas un vecteur doit être le caractère d'arrière-plan. (Si un espace vide est utilisé comme caractères d'arrière-plan, ces contraintes n'ont pas besoin d'être appliquées.)

(En général, si nous avons un vecteur (v, w) avec le poids a et un deuxième vecteur (x, y) avec le poids b, leur somme pondérée est a (v, w) + b (x, y) = (av + bx, aw + par).)

Dans l'exemple précédent, la combinaison linéaire appropriée est 2 * (3,1) + 3 * (2, -1) = (12, -1). Si nous utilisons "X" comme caractère de résultat, la sortie pourrait ressembler à

....2.........
.0............
...3.........X

ou

................
...2............
0...............
..3.........X...
................
................

Score de habituel : la réponse la plus courte, en octets, l'emporte.

Exemple d'entrée et de sortie

Si un espace vide est utilisé, l'entrée ci-dessus ressemblerait à

    2
 0
   3

et la sortie ressemblerait

    2
 0
   3         X

Les caractères / lignes d'espacement avant / arrière ne sont pas pertinents; s'ils sont invisibles pour le lecteur, ça va. (Cela étant dit, pour le reste des exemples, je vais recommencer à utiliser "." Pour le caractère d'arrière-plan, pour le rendre plus facile à lire.)

Si les deux vecteurs ont le poids 1, alors le résultat ressemblera à un parallélogramme: l'entrée

.1.
...
1.0

conduit à la sortie

X.1.
....
.1.0

Notez que ce parallélogramme peut être dégénéré si les vecteurs d'entrée sont colinéaires: l'entrée

0.1..1

conduit à la sortie

0.1..1.X

Il est possible que le vecteur résultat soit égal à l'un des vecteurs d'entrée ou à l'origine; dans ce cas, il remplace simplement le caractère saisi. Par exemple, l'entrée

..2.0.1...

donne la sortie

..X.0.1...

(où en entrée et / ou en sortie, les périodes de début et de fin pourraient être supprimées). L'entrée

.....3
......
...0..
......
......
2.....

donne la sortie

.....3
......
...X..
......
......
2.....

Enfin, l'entrée

90
.8

donne la sortie

........90
.........8
..........
..........
..........
..........
..........
..........
X.........
Greg Martin
la source
1
Bienvenue chez PPCG! Beau premier défi.
AdmBorkBork
@TimmyD Merci pour l'accueil et les encouragements :)
Greg Martin
1
Enfin, comme je suis sûr que d'autres le soulèveront, cela est proche d'un défi de caméléon, car un gros morceau de code va simplement analyser l'analyse, alors que ce n'est pas vraiment l'objectif principal du défi.
AdmBorkBork
Y a-t-il une limite au nombre de lignes / colonnes dans l'entrée ou la sortie correcte?
Sparr
@TimmyD J'ai ajouté la formule générale de la somme pondérée, et j'ai également précisé que l'un ou l'autre format d'entrée est correct. Je suis d'accord que cela est proche d'un défi de caméléon (bien que j'espérais que certaines langues pourraient avoir la capacité de "marcher" directement sur le tableau pour résoudre le problème); Cependant, les commentaires sur Sandbox ont été légèrement plus positifs que négatifs, j'ai donc décidé d'y aller.
Greg Martin

Réponses:

7

MATL , 48 octets

tZyyX:UX>*Yat48-tt0>*3#fbbhb~2#fh-*s7M+'X'wZ}4$(

Le caractère d'arrière-plan est l'espace. L'entrée est un tableau de caractères 2D avec des lignes séparées par des points-virgules. Les cas de test ont donc des entrées respectives:

['    2'; ' 0   '; '   3 ']
[' 1 '; '   '; '1 0']
['0 1  1']
['  2 0 1   ']
['     3'; '      '; '   0  '; '      '; '      '; '2     ']
['90'; ' 8']

La sortie comprend une quantité importante d'espaces blancs de remplissage.

Essayez-le en ligne!

Luis Mendo
la source
2

Python 3, 374 355 octets

Solution de python pas trop raffinée et très généreuse avec un rembourrage (utilise la distance maximale de l'échiquier). L'entrée est une seule ligne où les lignes sont séparées par des tuyaux | (bien que l'algorithme puisse facilement utiliser tout ce qui n'est pas alphanumérique qui n'est pas une nouvelle ligne ou un EOF). Tout ce qui n'est pas alphanumérique ou | fonctionne pour le remplissage d'entrée, le remplissage de sortie utilise des points. Les commentaires et les améliorations des golfeurs plus expérimentés en python sont appréciés.

Edit: Quelques améliorations grâce à @TheBikingViking. J'ai également ajouté encore plus de marges car je n'étais pas assez généreux avec le rembourrage.

s=input()
l=[len(s),1+s.find('|')]['|'in s]
P=sorted([int(c),i%l,i//l]for i,c in enumerate(s)if c.isalnum())
L=X=Y=0
P[0][0]=-sum(p[0]for p in P)
for w,x,y in P:L=max(abs(x),abs(y),L);X+=x*w;Y+=y*w
P+=[['X',P[0][1]+X,P[0][2]+Y]]
P[0][0]=0
L=2*max(abs(X),abs(Y),L)
S=[2*L*["."]for _ in[0]*2*L]
for w,x,y in P:S[L+y][L+x]=str(w)
for s in S:print(''.join(s))
algmyr
la source
Bonne réponse! Jetez un œil aux astuces Python . Quelques pointeurs: 1.C'est une bonne idée de spécifier si vous avez utilisé Python 2/3, car certaines fonctionnalités diffèrent. 2.Vous pouvez le faire à la [a,b][condition]place de la b if condition else cligne 2. sortedprend n'importe quel itérateur, y compris une instruction de générateur, vous pouvez donc supprimer la paire externe de crochets. 3. zip(p)devrait fonctionner au lieu de p[0] for p in P.
TheBikingViking
4. Vous pouvez faire à la P+=[stuff]place de la P.append([stuff])ligne 7. 5. Faire à la ["."]place de list("."). (3. aurait dû l'être zip(p)[0].)
TheBikingViking
Désolé, devrait être capitale Pdans zip.
TheBikingViking
5. Vous devriez pouvoir le faire S=[stuff]*2*Lsur la ligne 10.
TheBikingViking
[1] Bon point, ajoutera la version python. [2] Bon modèle, mais cela ne fonctionnera pas index(erreur sur rien trouvé). Fonctionnera avec findcependant. [Ré. trié] Merci d'avoir manqué de les supprimer lors de l'ajout de sorted. [3] zip (* P) ​​[0] ne fonctionne pas en python 3 (objet zip non indexable). [4] P + = [stuff] ne fonctionnera pas, bien que P + = [[stuff]] fonctionnera. [5] Merci. [les 5 autres] Ne fonctionne pas. J'ai besoin de nouvelles listes, pas de références.
algmyr
2

JavaScript, 534 528 502 octets

n="indexOf"
J="join"
B=X=>X.split(O)
O='\n'
w=i[n](O)+1
h=B(i).length
Z=(X,Y,R)=>{C[R]+=X-1;return Array(X)[J](Y)}
C=[0,0,0]
G=(X,E,T,U,R)=>X>0&E>=0?Z(X+E+1+T,U,R):""
o=i[n]("0")
L=X=>Math.floor(X/(w-1))
l=L(o)
c=o%w
x=y=0
j=i
for(z="1";z<="9";z++){while(p=~j[n](z)){j=j.replace(z," ")
x+=~p%w-l
y+=L(~p)-c}}
I=B(i).map(X=>G(-x,-l,0," ",0)+X+G(x,l-w+2,0," ",2))
N=Z(I[0].length+1," ",2)
A=B(G(-y,-c,0,N+O,1)+I[J](O)+G(y,c-h,1,O+N,2))
M=y+c+C[1]
O=""
m=B(A[M])
m[x+l+C[0]/h]="x"
A[M]=m[J]("")
A[J]("\n")

Notez que le rembourrage est optimal. Ce programme suppose que i contient la chaîne brute, avec les lignes séparées par des \ncaractères. Le remplissage est effectué avec des espaces et le caractère résultant est en minuscules x.

Ceci est ma première tentative de code-golf.

Trucs techniques: - La taille du programme a pratiquement doublé (et sa complexité a considérablement augmenté) pour ne prendre en compte que le caractère du résultat, principalement parce que les chaînes JavaScript sont immuables.


Explication ligne par ligne:

n="indexOf"
J="join"
B=X=>X.split(O)

Je les utilise beaucoup, donc les stocker dans des chaînes m'a fait gagner de l'espace. Vous pouvez voir ci-dessous que pour la splitfonction, j'ai simplement créé un alias; c'est parce que je n'avais besoin que d'un seul argument, l'autre étant constant. Pour indexOfet join, cela aurait cependant été plus long.

O='\n'
w=i[n](O)+1
h=B(i).length

Rien de compliqué ici, je lis la largeur et la hauteur du tableau initial. Notez l'utilisation de i[n]pour accéder à indexOf, tandis que splitest géré différemment.

Z=(X,Y,R)=>{C[R]+=X-1;return Array(X)[J](Y)}

Cela devient intéressant. Cette fonction crée essentiellement concatène J-1 fois la chaîne X et la renvoie. Ceci est utilisé pour générer des chaînes d'espaces pour le remplissage.

C=[0,0,0]

Ce tableau contiendra le nombre de lignes et de colonnes ajoutées par le remplissage (désactivé d'un facteur h dans le premier cas). La dernière cellule est indésirable et m'empêche d'avoir un argument supplémentaire dans la fonction ci-dessous.

G=(X,E,T,U,R)=>X>0&E>=0?Z(X+E+1+T,U,R):""

Cette fonction gère à elle seule le remplissage (lignes et colonnes); il détermine, sur la base d'une coordonnée du vecteur résultat (X), et du nombre de lignes / colonnes à générer (E), s'il est nécessaire d'en créer un. l' X+E+1+Test juste un truc pour économiser un peu d' espace, Uest la chaîne de remplissage (un espace pour les colonnes et une ligne entière pour les lignes), et nous y reviendrons R. Cette fonction renvoie essentiellement, dans le cas d'une ligne, le remplissage requis au début ou à la fin de ladite ligne, et, dans le cas d'une colonne, elle retourne les lignes de remplissage requises avant ou après les lignes d'origine.

o=i[n]("0")
L=X=>Math.floor(X/(w-1))
l=L(o)
c=o%w

Ici, nous lisons la position de l'origine, et nous récupérons ses coordonnées. L est une fonction pour convertir un index en un numéro de ligne.

x=y=0
j=i
for(z="1";z<="9";z++){
    while(p=~j[n](z)){
        j=j.replace(z," ")
        x+=~p%w-l
        y+=L(~p)-c
    }
}

J'ai ajouté des espaces pour faciliter la lecture. Ce qui se passe ici, c'est que pour chaque nombre possible, nous continuons à le chercher dans la chaîne d'origine. L' ~astuce est relativement courante en Javascript; c'est l'opérateur NOT au niveau du bit, mais tout ce qui compte ici, c'est celui ~-1==0qui me permet de tester la fin de la boucle. J'efface ensuite le caractère de la chaîne (c'est pourquoi j'ai fait une copie), ce qui me permet de continuer la recherche aussi longtemps que nécessaire. J'ajoute ensuite les coordonnées du vecteur à (x, y), en utilisant une simple soustraction.

I=B(i).map(X=>G(-x,-l,0," ",0)+X+G(x,l-w+2,0," ",2))

Je divise ici la chaîne d'origine en lignes, et pour chaque ligne, j'appelle Gqui générera le remplissage avant et après les lignes. Le l-w+2et ainsi de suite proviennent d'un simple calcul d'index qui me permet de tester si j'ai besoin d'ajouter du rembourrage ou non. Par exemple, si x>0et x+l-w+1>0, alors des (x+l-w+1)+1espaces doivent être ajoutés après la ligne. Le +xest supprimé car il s'agit du premier paramètre et X+E+1+Tutilisé dans la définition de G.

Une opération similaire est effectuée pour les premiers caractères, puis pour les colonnes. Il y a beaucoup de factorisation ici qui me permet d'utiliser une seule fonction. Notez le dernier paramètre; dans le premier cas, je veux écrire pour C[0]pouvoir savoir plus tard combien de colonnes j'ai ajoutées au début de chaque ligne; cela me permet de récupérer la position finale du caractère résultat. Je ne me soucie cependant pas des colonnes ajoutées après la ligne d'origine, c'est pourquoi le deuxième appel à Gécrit dans la cellule indésirable C[2]qui n'est pas utilisé.

N=Z(I[0].length+1," ",2)

Ici, je lis simplement la nouvelle longueur des lignes et j'en crée une ligne d'espaces. Il sera utilisé pour créer le rembourrage vertical.

A=B(G(-y,-c,0,N+O,1)+I[J](O)+G(y,c-h,1,O+N,2))

C'est exactement la même chose que deux lignes ci-dessus. La seule différence est d'écrire à C[1]cette heure et d'utiliser les séparateurs N+Oet O+N. N'oubliez pas qu'il Os'agit d'une nouvelle ligne et d' Nune ligne d'espaces. J'applique ensuite Bsur le résultat pour le diviser à nouveau (j'ai besoin de récupérer la ligne contenant le caractère du résultat pour le modifier).

M=y+c+C[1]

Il s'agit de l'index vertical du caractère résultant.

O=""
m=B(A[M])
m[x+l+C[0]/h]="x"

Ici, je suis obligé de modifier Opour pouvoir diviser la ligne appropriée en un tableau de caractères. En effet, les chaînes JavaScript sont immuables; la seule façon de modifier une chaîne est de la convertir en un tableau (c'est ce que je fais ici), de la modifier à la bonne position et de joindre à nouveau la chaîne. Notez également le hfacteur, car la Gfonction a été appelée une fois par ligne initiale.

A[M]=m[J]("")
A[J]("\n")

Je remplace enfin la nouvelle chaîne dans le tableau et la rejoins à nouveau dans une chaîne. Woohoo!

pie3636
la source