Liniowa kombinacja dwóch wektorów

11

Streszczenie wykonawcze

Biorąc pod uwagę dane wejściowe reprezentujące dwa wektory i ich odpowiednie „wagi”, uzyskaj dane wyjściowe, które reprezentują również ważoną sumę tych wektorów.

Wyzwanie

Dane wejściowe będą się składać z co najmniej jednego wiersza następujących znaków:

  • dokładnie jedno wystąpienie cyfry 0, która reprezentuje początek w płaszczyźnie dwuwymiarowej;
  • dokładnie dwie inne cyfry (1-9; mogą, ale nie muszą być tą samą cyfrą), których pozycje w stosunku do źródła reprezentują wektory, a których wartości reprezentują wagi przypisane do tych wektorów;
  • pewna liczba „znaków tła”. Solver może wybrać konkretny znak tła; na przykład wybiorę „.” (głównie dla czytelności dla ludzi). Alternatywnie, znakami tła mogą być cokolwiek, co wygląda jak puste miejsce.

(Solver może wybrać, czy wejście jest pojedynczym ciągiem wieloliniowym, czy tablicą ciągów jednowierszowych.)

Na przykład dane wejściowe

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

reprezentuje wektor o współrzędnych (3,1) o wadze 2 i wektor o współrzędnych (2, -1) o wadze 3.

Dane wyjściowe powinny być prawie takie same jak dane wejściowe, z następującymi zmianami:

  • „znak wyniku” wybrany przez solver, który ma zostać dodany w pozycji określonej przez ważoną sumę wektorów wejściowych (równoważnie w pozycji, która jest odpowiednią liniową kombinacją wektorów wejściowych);
  • tyle znaków tła, ile potrzeba, aby dopasować początek, dwa wektory wejściowe i wektor wyjściowy na tym samym obrazie. W razie potrzeby można dołączyć dodatkowe znaki tła; jedynym ograniczeniem jest to, że jeśli znak tła jest znakiem widocznym, wówczas cały wynik musi mieć kształt prostokątny, a każdy znak nie reprezentujący wektora musi być znakiem tła. (Jeśli jako znaki tła używane jest puste miejsce, ograniczenia te nie muszą być egzekwowane.)

(Na ogół, jeśli mamy jeden wektor (v, w) o wadze a i drugi wektor (x, y) o wadze b, ich ważona suma to a (v, w) + b (x, y) = (av + bx, aw + by).)

W poprzednim przykładzie odpowiednią kombinacją liniową jest 2 * (3,1) + 3 * (2, -1) = (12, -1). Jeśli użyjemy „X” jako znaku wynikowego, wynik może wyglądać następująco

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

lub

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

Zwykle punktowanie w : wygrywa najkrótsza odpowiedź w bajtach.

Przykładowe wejście i wyjście

Jeśli zostanie użyte puste miejsce, powyższe dane wejściowe będą wyglądać

    2
 0
   3

i wyglądałby wynik

    2
 0
   3         X

Wiodące / końcowe białe znaki / linie są nieistotne; jeśli są niewidoczne dla czytelnika, jest w porządku. (Biorąc to pod uwagę, w pozostałych przykładach wrócę do używania „.” Jako znaku tła, aby ułatwić czytanie.)

Jeśli oba wektory mają wagę 1, wynik będzie wyglądał jak równoległobok: dane wejściowe

.1.
...
1.0

prowadzi do wyjścia

X.1.
....
.1.0

Zauważ, że ten równoległobok może zostać zdegenerowany, jeśli wektory wejściowe są współliniowe: wejście

0.1..1

prowadzi do wyjścia

0.1..1.X

Wektor wynikowy może być równy jednemu wektorowi wejściowemu lub źródłu; w takim przypadku po prostu nadpisuje znak wejściowy. Na przykład dane wejściowe

..2.0.1...

daje wynik

..X.0.1...

(w przypadku wejścia i / lub wyjścia można usunąć początkowe i końcowe okresy). Dane wejściowe

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

daje wynik

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

Wreszcie dane wejściowe

90
.8

daje wynik

........90
.........8
..........
..........
..........
..........
..........
..........
X.........
Greg Martin
źródło
1
Witamy w PPCG! Ładne pierwsze wyzwanie.
AdmBorkBork
@TimmyD Dziękuję za powitanie i zachętę :)
Greg Martin
1
Wreszcie, ponieważ jestem pewien, że inni to poruszą, jest to flirtowanie blisko wyzwania kameleona, ponieważ spora część kodu będzie po prostu analizować dane wejściowe, gdy nie jest to tak naprawdę głównym celem wyzwania.
AdmBorkBork
czy jest jakiś limit liczby wierszy / kolumn na wejściu lub prawidłowe wyjście?
Sparr
@ TimmyD Dodałem ogólną formułę sumy ważonej, a także wyjaśniłem, że każdy format wejściowy jest w porządku. Zgadzam się, że jest to zbliżone do wyzwania kameleona (chociaż miałem nadzieję, że niektóre języki mogą mieć zdolność „chodzenia” bezpośrednio po planszy, aby rozwiązać problem); jednak opinie na temat Sandbox były nieco bardziej pozytywne niż negatywne, więc zdecydowałem się na to.
Greg Martin

Odpowiedzi:

7

MATL , 48 bajtów

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

Znakiem tła jest spacja. Dane wejściowe to tablica znaków 2D z wierszami oddzielonymi średnikami. Tak więc przypadki testowe mają odpowiednie dane wejściowe:

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

Dane wyjściowe zawierają znaczną ilość białych znaków wypełniających.

Wypróbuj online!

Luis Mendo
źródło
2

Python 3, 374 355 bajtów

Niezbyt wyrafinowane rozwiązanie Pythona, które jest bardzo hojne z wypełnieniem (wykorzystuje maksymalną odległość od szachownicy). Dane wejściowe to pojedynczy wiersz, w którym wiersze są oddzielone rurami | (chociaż algorytm może z łatwością użyć wszystkiego, co nie jest alfanumeryczne, co nie jest znakiem nowej linii ani EOF). Wszystko inne niż alfanumeryczne lub | działa na dopełnienie wejściowe, dopełnienie wyjściowe wykorzystuje kropki. Doceniamy opinie i ulepszenia od bardziej doświadczonych golfistów python.

Edycja: Kilka ulepszeń dzięki @TheBikingViking. Dodałem także jeszcze więcej marginesów, ponieważ nie byłem dość hojny z paddingiem.

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
źródło
Niezła odpowiedź! Spójrz na wskazówki Python . Kilka wskazówek: 1. Dobrym pomysłem jest określenie, czy korzystasz z Pythona 2/3, ponieważ niektóre funkcje są różne. 2. Możesz zrobić [a,b][condition]zamiast b if condition else cw wierszu 2. sortedbierze dowolny iterator, w tym instrukcję generatora, więc możesz upuścić zewnętrzną parę nawiasów kwadratowych. 3. zip(p)powinien działać zamiast p[0] for p in P.
TheBikingViking
4. Możesz zrobić P+=[stuff]zamiast P.append([stuff])w linii 7. 5. Zrób ["."]zamiast list("."). (3. powinno być zip(p)[0].)
TheBikingViking
Niestety, powinien być kapitał Pw zip.
TheBikingViking
5. Powinieneś być w stanie zrobić to S=[stuff]*2*Lna linii 10.
TheBikingViking
[1] Dobra uwaga, doda wersję Pythona. [2] Dobry wzór, ale nie działa index(błąd nie został znaleziony). Będzie jednak działać find. [Re. posortowane] Dziękujemy, przegapiłem ich usunięcie podczas dodawania sorted. [3] zip (* P) ​​[0] nie działa w Pythonie 3 (obiekt zip nie jest indeksowany). [4] P + = [rzeczy] nie będzie działać, chociaż P + = [[rzeczy]] zadziała. [5] Dziękuję. [pozostałe 5] Nie działa. Potrzebuję nowych list, a nie referencji.
algmyr
2

JavaScript, 534 528 502 bajtów

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

Pamiętaj, że wypełnienie jest optymalne. Ten program zakłada, że ​​i zawiera nieprzetworzony ciąg znaków, z wierszami oddzielonymi \nznakami. Wypełnianie odbywa się spacjami, a wynikowy znak jest małymi literami x.

To moja pierwsza próba gry w golfa.

Techniczne rzeczy: - Rozmiar programu z grubsza podwoił się (a jego złożoność dramatycznie wzrosła), aby wziąć pod uwagę wynikowy wynik, głównie dlatego, że ciągi JavaScript są niezmienne.


Objaśnienie linia po linii:

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

Często ich używam, więc przechowywanie ich w sznurkach pozwoliło mi zaoszczędzić trochę miejsca. Możesz zobaczyć poniżej, że dla splitfunkcji po prostu utworzyłem alias; to dlatego, że potrzebowałem tylko jednego argumentu, drugi był stały. Dla indexOfi join, byłoby jednak być dłuższy.

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

Nic skomplikowanego, czytam szerokość i wysokość początkowej tablicy. Zwróć uwagę na użycie, i[n]aby uzyskać dostęp indexOf, podczas gdy splitjest obsługiwane inaczej.

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

To robi się interesujące. Ta funkcja w zasadzie tworzy konkatenaty J-1 razy łańcuch X i zwraca go. Służy do generowania ciągów odstępów dla wypełnienia.

C=[0,0,0]

Ta tablica będzie zawierać liczbę linii i kolumn dodanych przez wypełnienie (w pierwszym przypadku wyłączone przez współczynnik h). Ostatnia komórka jest śmieciowa i nie pozwala mi na dodatkowy argument w funkcji poniżej.

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

Ta funkcja sama obsługuje dopełnienie (zarówno linie, jak i kolumny); określa, w oparciu o współrzędną wektora wynikowego (X) i liczbę linii / kolumn do wygenerowania (E), czy konieczne jest jego utworzenie. X+E+1+Tto tylko podstęp, aby zaoszczędzić trochę miejsca, Uto ciąg napełniania (przestrzeń dla kolumn, a cała linia do linii), i będziemy wracać do R. Ta funkcja zasadniczo zwraca, w przypadku linii, wypełnienie wymagane na początku lub na końcu wspomnianej linii, a w przypadku kolumny zwraca wymagane linie wypełnienia przed lub po oryginalnych liniach.

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

Tutaj czytamy pozycję początku i pobieramy jego współrzędne. L to funkcja służąca do konwersji indeksu na numer linii.

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

Dodałem trochę białych znaków, aby ułatwić czytanie. Tutaj dzieje się tak, że dla każdej możliwej liczby szukamy jej w oryginalnym ciągu. Ta ~sztuczka jest stosunkowo powszechna w Javascript; jest to bitowy operator NOT, ale najważniejsze jest tutaj to ~-1==0, co pozwala mi przetestować koniec pętli. Następnie usuwam znak z łańcucha (dlatego zrobiłem kopię), co pozwala mi kontynuować wyszukiwanie tak długo, jak to konieczne. Następnie dodaję współrzędne wektora (x, y), używając prostej odejmowania.

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

Tutaj podzieliłem oryginalny ciąg na linie i dla każdej linii wywołuję, Gktóra wygeneruje dopełnienie przed i po liniach. l-w+2I tak dalej pochodzą z prostego obliczenia indeksu, który pozwala mi sprawdzić, czy muszę dodać dopełnienie czy nie. Na przykład, jeśli x>0i x+l-w+1>0, to (x+l-w+1)+1po wierszu należy dodać spacje. +xJest usuwany ze względu na to jest pierwszy parametr i X+E+1+Tstosowane w definicjiG .

Podobna czynność dotyczy pierwszych znaków, a następnie kolumn. Jest tu wiele faktoryzacji, które pozwalają mi korzystać tylko z jednej funkcji. Zanotuj ostatni parametr; w pierwszym przypadku chcę napisać, aby C[0]móc później dowiedzieć się, ile kolumn dodałem na początku każdej linii; pozwala mi to uzyskać ostateczną pozycję postaci wynikowej. Nie dbam jednak o kolumny dodane po oryginalnym wierszu, dlatego drugie wezwanie do Gzapisu do niepotrzebnej komórki C[2]jest nieużywane.

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

Tutaj po prostu czytam nową długość linii i tworzę z niej linię spacji. Zostanie to wykorzystane do utworzenia pionowego wypełnienia.

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

Jest to dokładnie to samo, co dwie linie powyżej. Jedyną różnicą jest pisanie do C[1]tego czasu i używanie separatorów N+Oi O+N. Pamiętaj, że Oto nowa linia i Nlinia spacji. Następnie aplikuję Bna wynik, aby go ponownie podzielić (muszę edytować wiersz zawierający znak wynikowy, aby go edytować).

M=y+c+C[1]

Jest to indeks pionowy wynikowego znaku.

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

Tutaj jestem zmuszony zmodyfikować, Oaby móc podzielić odpowiednią linię na tablicę znaków. Jest tak, ponieważ ciągi JavaScript są niezmienne; jedynym sposobem edycji łańcucha jest przekonwertowanie go na tablicę (co tutaj robię), edycja we właściwej pozycji i ponowne dołączenie łańcucha. Zwróć także uwagę na hwspółczynnik, ponieważ Gfunkcja została wywołana raz na linię początkową.

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

W końcu zastępuję nowy ciąg w tablicy i łączę go ponownie w ciąg. Łał!

pie3636
źródło