Rozwiąż równanie z (prawie) dowolnymi liczbami

27

Biorąc pod uwagę ciąg znaków, w +=-których jest co najmniej jeden =, wstaw dodatnie liczby całkowite między wszystkimi symbolami oraz na początku i na końcu, aby równania matematyczne były spełnione.

Na przykład biorąc pod uwagę dane wejściowe

+-=-=

musisz wstawić dodatnie liczby całkowite od A do F w ten sposób

A+B-C=D-E=F

tak, że wszystkie równania są spełnione, tj. A + B - Ci D - Ei Fwszystkie mają tę samą liczbę.

Istnieje wiele możliwych sposobów, aby to zrobić, dopóki dopóty równania się sprawdzą, można zastosować dowolny zestaw dodatnich liczb całkowitych. Każda linia tutaj jest możliwym prawidłowym wyjściem do wprowadzenia +-=-=:

2+3-4=6-5=1
1+1-1=2-1=1
4+2-4=4-2=2
100+1-10=182-91=91
89+231-77=1024-781=243

Zauważ, że wartość wyrażeń nie musi być dodatnią liczbą całkowitą, jak w przypadku wstawionych liczb. Na przykład, biorąc pod uwagę dane wejściowe, -=-wyjścia 1-10=8-17(evals do -9) i 10-1=17-8(evals do 9) są jednakowo ważne. Oczywiście w przypadku niektórych danych wejściowych, takich jak =wyrażenie ujemne, ponieważ 5=5nie można wstawić tylko liczb dodatnich .

Zauważ też, że zero nie jest dodatnią liczbą całkowitą.

Najkrótszy kod w bajtach wygrywa.

Możesz wyprowadzać liczby jako listę zamiast wstawiać je bezpośrednio w ciągu. Jeśli wypiszesz ciąg znaków, mogą istnieć spacje oddzielające symbole i liczby. Tak więc dla danych wejściowych +-=-=, wyjściowych

2, 3, 4, 6, 5, 1

lub

2 + 3 - 4 = 6 - 5 = 1

jest równoważne z wyjściem

2+3-4=6-5=1

Przypadki testowe

Input | One Possible Output
= | 1=1
== | 2=2=2
+= | 1+3=4
=+ | 2=1+1
-= | 30-10=20
=- | 1=2-1
=-= | 3=7-4=3
=+= | 2=1+1=2
=== | 100=100=100=100
+=- | 3+2=7-2
-=+ | 7-2=3+2
+=+ | 3+3=3+3
-=- | 1-10=8-17
--= | 60-1-1=58
++= | 60+1+1=62
-+= | 60-9+1=52
+-= | 60+9-1=68
+-=-= | 2+3-4=6-5=1
--=-- | 2-1-1=2-1-1
==-== | 47=47=50-3=47=47
=++=+-=-+=--= | 3=1+1+1=3+1-1=1-1+3=5-1-1=3
+--++-=-+-+- | 35+10-16-29+20+107-1000=5-4+3-2+1-876
====== | 8=8=8=8=8=8=8
Hobby Calvina
źródło
Związane z.
Martin Ender,
Czy możemy założyć górną granicę długości formuły?
xnor
2
@ xnor Możesz założyć, że dane wejściowe mają mniej niż 2 ^ 16 znaków, jeśli to pomoże.
Calvin's Hobbies

Odpowiedzi:

16

Siatkówka , 58 bajtów

[-+]
$&1
\B((\+1)|(-1))*
$._$*1$#3$*1$#2$*_$&
+`1_

1+
$.&

Wypróbuj online!

Alternatywne rozwiązanie przy tej samej liczbie bajtów:

((\+)|(-))*
$._$*1$#3$*1$#2$*_$&
+`1_

([+-])1*
$+1
1+
$.&

Wypróbuj online!

Wyjaśnienie

Podstawowym założeniem jest, aby włączyć wszystkie +S i -S na proste +1i -1operacji, a następnie poprzedzić wystarczająco dużą liczbę, która sprawia, że wszystkie prace równań. Aby dopasować równania, możemy po prostu przypisać tę samą liczbę każdemu z nich, a następnie zmniejszyć go o jeden dla każdego +1i zwiększyć o jeden dla każdego -1po nim. Ponieważ będziemy pracować z liczbami jednoargumentowymi, jedynym haczykiem jest to, że pierwsza liczba musi być wystarczająco duża, abyśmy mogli ją zmniejszyć odpowiednio 1 razy.

[-+]
$&1

Zaczynamy od wstawienia 1po każdym -lub +.

\B((\+1)|(-1))*
$._$*1$#3$*1$#2$*_$&

W \Bgwarantuje, że te mecze są albo na początku wejścia lub między =a +lub -, czyli wszystkie pozycje gdzie chcemy wstawić wiodącą liczbę wyrażenia. ((\+1)|(-1))*Część po prostu zlicza liczbę +1S i -1S w grupach 2i 3odpowiednio. Teraz podzielmy łańcuch podstawienia:

$._$*1   # For each character in the current string, insert a 1. This is
         # an offset which is the same for each expression and is guaranteed
         # to be large enough that all subsequent +1s can be cancelled.
$#3$*1   # For each -1, insert a 1.
$#2$*_   # For each +1, insert a _.
$&       # Re-insert the string of +1s and -1s.
+`1_

Wielokrotnie zrzucaj 1_z łańcucha, stosując wymagane anulowanie z +1s.

1+
$.&

Na koniec zamień wszystkie ciągi 1s ich długościami, aby przekonwertować z jedności na dziesiętne.

Martin Ender
źródło
8

Python 2 , 76 bajtów

lambda e:sum([[len(e+s)-2*s.count('+')]+[1]*len(s)for s in e.split('=')],[])

Wypróbuj online!

xnor
źródło
3
Czy możesz dodać wyjaśnienie?
Calvin's Hobbies
1
@HelkaHomba Pomysł jest dość prosty: najpierw weź każdy fragment wejściowy podzielony znakami równości. Wybierz pierwszą liczbę każdego fragmentu eqtn_len + plus_signs + minus_signs - 2 * plus_signs = eqtn_len + minus_signs - plus_signs. Następnie, ponieważ wszystkie inne liczby w porcji są jednymi, suma dla porcji działa eqtn_len + minus_signs - plus_signs - minus_signs + plus_signs = eqtn_len. Długość równania musi być dodatnia, więc wszystko się ułoży.
FryAmTheEggman,
6

Python 2, 199 179 178 172 162 158 156 152 151 bajtów

Zbyt długo, ale rozwiązanie było łatwe do stworzenia.

from itertools import*
i=input()
k='%s'
s=k+k.join(i)+k
for p in product(*[range(1,65537)]*-~len(i)):
    if eval((s%p).replace('=','==')):print s%p;break

Wypróbuj online

Spróbuje każdej możliwości, dopóki nie znajdzie rozwiązania. Program jest bardzo wolny. Wykonuje również zamianę łańcucha w każdej iteracji. Edycja „172” drastycznie spowolniła, ponieważ zamiast zaczynać od małego zakresu, zaczyna się od maksimum. Na przykład dane wejściowe -=lub =+trzeba spróbować 2 ** 32 prób przed osiągnięciem rozwiązania.

Aby przyspieszyć program, użyj wersji z 178 bajtami z historii edycji.

mbomb007
źródło
Czy rangew Python2 nie tworzy od razu całego zakresu jako listy? IIRC można przyspieszyć, używając xrangezamiast tego, ponieważ myślę, że jest to wersja leniwa ładująca (Python3 używa domyślnie lazy range)
Delioth
1
@Delioth Wykorzystuje jednak inny bajt. Celem jest usunięcie bajtów. Ponadto nie zapewniłoby to zbytnio przyspieszenia, ponieważ większość spowolnienia wynika z liczby iteracji, a nie ze stworzenia listy, która występuje tylko raz. Pobiegłem print range(1,65537)i zakończył się w 0,034 s.
mbomb007
Cóż, oczywiście - bardziej „to może przyspieszyć przy użyciu dokładnie tej samej metodologii”, pod warunkiem, że zajmie to tak dużo czasu. Przeładowanie pamięci może spowodować znaczne spowolnienie. Ponadto, możesz wyciąć niektóre bajty (może tylko 1), nie ustawiając l=..., ale umieszczając to bezpośrednio w product(range(...),repeat=len(s)+1). Jeśli potrzebujesz nawiasów, zapisuje tylko jeden bajt (\ n)
Delioth
@Delioth Nawet gdybym potrzebował parens len(s)+1, mógłbym użyć -~len(s)zamiast tego, co nie wymagałoby parens.
mbomb007
Ah, tak. Zawsze zapominam o bitowych operacjach i trikach - to musi być opłata za pracę nad frontendem javascript, który wykorzystuje moją wiedzę Python!
Delioth,
5

JavaScript (ES6), 92 82 bajty

Grał w golfa 8 bajtów lewą z @xnor

let f =
x=>x.split`=`.map(q=>(x+q).length-2*~-q.split`+`.length+[...q,''].join(1)).join`=`
<input oninput="if(/^[+=-]+$/.test(value))O.innerHTML=f(value)" value="="><br>
<pre id=O>1=1</pre>

Sztuczka polega na tym, aby wstawić 1po każdym +lub -, a następnie wstawić do każdego wyrażenia liczbę, która sprawia, że ​​wyrażenie jest równe długości danych wejściowych. W ten sposób możemy zagwarantować, że liczba będzie zawsze dodatnia; ponieważ =w łańcuchu zawsze znajduje się co najmniej 1 , liczba +s nigdy nie może osiągnąć długości łańcucha, więc reszta zawsze wynosi co najmniej 1. Możesz to sprawdzić, wpisując dowolną liczbę +s we fragmencie powyżej.

ETHprodukcje
źródło
5

Python 2 , 120 119 bajtów

-1 bajt dzięki mbomb007

a=['1'+(n and('1'.join(n)+'1'))for n in input().split('=')]
print'='.join(`max(map(eval,a))-eval(c)+1`+c[1:]for c in a)

Wypróbuj online! lub Zweryfikuj wszystkie przypadki testowe

Najpierw wstawiam 1w każdej pozycji, aby sprawdzić najwyższą wartość, a następnie dodaj ją jako przesunięcie przy każdym równaniu. Działa to, ponieważ nie można dodawać liczb ujemnych, więc minimalny wynik jest podawany przez liczbę +w równaniu, które mają tylko +.

Pręt
źródło
Możesz usunąć kilka spacji.
mbomb007
5

GNU Prolog, 156 bajtów

x(L,R,V)-->{E#>0},({L=[E|R],E=V};x(L,[E|R],X),("+",{V#=X+E};"-",{V#=X-E})).
q(L,R,V)-->x(L,T,V),({T=R};"=",q(T,R,V)).
s(Q,L):-q(L,[],_,Q,[]),fd_labeling(L).

Wyjaśnienie

Mamy kilka równań do rozwiązania, więc dlaczego nie skorzystać z rzeczywistego rozwiązania równań?

xjest w zasadzie ewaluatorem równań dla równań formy +-+; oprócz samego równania ma dwa dodatkowe argumenty (lista różnic, L,Rktóra zawiera wartości równania i wartość V, na którą równanie się ocenia). Jak zwykle w Prologu, może być stosowany dowolny odwrotnie (np można określić Vi uzyskać L,R, należy określić L,Ri uzyskać V, należy podać oba i sprawdzić, czy wartość jest poprawna, lub określić ani w tym przypadku odpowiednie ograniczenia zostaną umieszczone na obu Vi L,R). „Bieżący element” L,Rjest nazwany E, a my również uwzględniamy to twierdzenieEjest większa niż 0 (ponieważ pytanie wymaga użycia liczb dodatnich). Ta funkcja jest nieco bardziej szczegółowa, niż bym chciał, np. [E|R]Musiałem dwukrotnie napisać wzór dopasowania / anulować dopasowanie, ponieważ listy są prawostronne, ale dodawanie i odejmowanie jest lewostronne. Niestety, do pracy musimy użyć rzeczywistej listy, zamiast wynaleźć własny typ listy lewostronnie skojarzonej z komórek przeciw fd_labeling.

qjest podobny x, ale obejmuje również =. Zasadniczo po prostu wywołuje xi sam się rekurencyjnie. Nawiasem mówiąc, jest to bardzo wyraźnie pokazuje, jak działają listy różnica, pokazując, że można łączyć dwie listy różnicy L,Ti T,Rna jednej liście różnicy L,R. Podstawową ideą jest to, że lista różnic jest funkcją częściową, która przyjmuje argument Ri zwraca wartość, do Lktórej Rdołączona jest sama lista. Tak więc, identyfikując argument jednej listy różnic i wartość zwracaną innej, możemy skomponować funkcje, a tym samym połączyć listy.

Wreszcie, sktóra jest funkcją, która faktycznie rozwiązuje zadanie w pytaniu, jest funkcją otoki, która wywołuje qargumenty. Przekształcamy listę różnic w zwykłą listę, podając []jako jej argument i używamy fd_labelingdo znalezienia rozwiązania zbudowanego równania. (Domyślnie wydaje się, że lubi ustawiać wartości na 1, jeśli nie ma powodu, aby ustawiać je na coś innego. Jednak można to skonfigurować; value_method(random)daje więcej „interesujących” rozwiązań niż umieszczanie wszędzie 1, na przykład, i wciąż jest bardzo szybkie. )

Próbka wyjściowa

Z programem jak napisano:

| ?- s("=++=+-=-+=--=", V).

V = [3,1,1,1,3,1,1,3,1,1,5,1,1,3] ?

Jeśli sprawię, że program trochę dłużej doda value_method(random), a wynik będzie różny, ale wygląda mniej więcej tak:

| ?- s("=++=+-=-+=--=", V).

V = [68,6,12,50,85,114,131,45,3,26,71,1,2,68] ? 

W obu przypadkach ?koniec danych wyjściowych oznacza, że ​​może istnieć więcej niż jedno rozwiązanie. (Oczywiście w tym przypadku wiemy, że istnieje o wiele więcej niż jedno rozwiązanie!)


źródło
4

Mathematica, 116 bajtów

Join@@(Prepend[#^2,1-Min[Tr/@c]+Tr@#]&/@(c=Characters@StringSplit["0"<>#<>"0","="]/."+"->-1/."-"->1/."0"->Nothing))&

Czysta funkcja przyjmująca ciąg wejściowy i zwracająca listę liczb całkowitych dodatnich. Podstawowa strategia: zawsze dodajemy 1 i odejmujemy 1 oraz wybieramy liczby początkowe w każdym wyrażeniu, aby wszystko było równe.

c=Characters@StringSplit[#,"="]/."+"->-1/."-"->1dzieliłby wejściowy ciąg znaków przy każdym znaku równości, a następnie zamieniałby każdy +przez -1i każdy -przez 1. Jeśli jednak na początku lub na końcu jest znak równości, zostanie zignorowany. Dlatego sztucznie dodajemy nowy znak na każdym końcu ( "0"<>#<>"0") i odsuwamy go po zakończeniu dzielenia łańcucha ( /."0"->Nothing).

Suma każdej podlisty jest teraz równa liczbie całkowitej, którą możemy umieścić przed +s i -s, aby każde wyrażenie było równe. 1-Min[Tr/@c]jest najmniejszą liczbą całkowitą, którą możemy dodać do każdej sumy, aby wszystkie były dodatnie. Więc Prepend[#^2,1-Min[Tr/@c]+Tr@#]&bierze każdą podlistę ( ^2odwraca wszystkie ich wpisy 1) i przenosi całkowitą przesunięcie o tę najmniejszą liczbę całkowitą kompensacji. Powstałe listy są Joinedytowane razem, aby uzyskać wynik.

Greg Martin
źródło
3

Ruby, 76

->s{(?1+s.gsub(/./){|a|a+?1}).split(?=).map{|e|e[0]="#{5**8-eval(e)}";e}*?=}

Wartość docelowa wyrażeń jest ustalona na 5**8minus 1 z powodów golfowych! Pierwotnie używałem s.size+1minus 1.

Niegolfowany w programie testowym

f=->s{(?1+s.gsub(/./){|a|a+?1}).           #add a 1 at the beginning and after every symbol
       split(?=).                          #split into an array of expressions at = signs
       map{|e|                             #for each expression string
         e[0]="#{5**8-eval(e)}";e          #change the first number to 5**8-eval(e)
       }*?=                                #and rejoin the strings
}


puts f["="] 
puts f["=="] 
puts f["+="] 
puts f["=+"]
puts f["-="]
puts f["=-"]
puts f["=-="]
puts f["=+="]
puts f["==="]
puts f["+=-"]
puts f["-=+"]
puts f["+=+"]
puts f["-=-"]
puts f["--="]
puts f["++="]
puts f["-+="]
puts f["+-="]
puts f["+-=-="]
puts f["--=--"]
puts f["==-=="]
puts f["=++=+-=-+=--="]
puts f["+--++-=-+-+-"]
puts f["======"]

Wydajność

390624=390624
390624=390624=390624
390623+1=390624
390624=390623+1
390625-1=390624
390624=390625-1
390624=390625-1=390624
390624=390623+1=390624
390624=390624=390624=390624
390623+1=390625-1
390625-1=390623+1
390623+1=390623+1
390625-1=390625-1
390626-1-1=390624
390622+1+1=390624
390624-1+1=390624
390624+1-1=390624
390624+1-1=390625-1=390624
390626-1-1=390626-1-1
390624=390624=390625-1=390624=390624
390624=390622+1+1=390624+1-1=390624-1+1=390626-1-1=390624
390624+1-1-1+1+1-1=390625-1+1-1+1-1
390624=390624=390624=390624=390624=390624=390624
Level River St
źródło
2

PHP, 207 204 197 114 bajtów

bezpośrednie podejście: znacznie krótsze i szybsze

foreach(explode("=",$argn)as$t)echo"="[!$c],strlen($argn)+($c=count_chars($t))[45]-$c[43],@chunk_split($t,!!$t,1);

Uruchom go echo '<input>' | php -nR '<code>'lub przetestuj online .

awaria

foreach(explode("=",$argn)as$t) // loop through terms
    echo                            // print ...
        "="[!$c],                       // 1. "=" if not first term
        strlen($argn)                   // 2. maximum number
            +($c=count_chars($t))[45]   //    + number of "-"
            -$c[43],                    //    - number of "+"
        @chunk_split($t,!!$t,1);        // 3. each operator followed by "1"
  • !$cjest prawdziwe w pierwszej iteracji, rzutowanej 1na indeksowanie ciągów; "="[1]jest pusty.
    Następnie $cjest ustawiany i !$cfałsz, rzucany na 0i "="[0]jest pierwszą postacią.
  • Maksymalna wartość dla dowolnego terminu nie musi przekraczać liczby plusów +1;
    więc jesteśmy zdecydowanie bezpieczni z długością wejścia. Wszystkie warunki zostaną ocenione zgodnie z tym.
  • chunk_split($s,$n,$i)wstawia $ipo każdym $nznaku $s- i na końcu.
    Aby zapobiec zamianie pustych terminów 1, wymuszany jest błąd poprzez ustawienie długości porcji na 0.
Tytus
źródło
1

Röda , 112 110 109 bajtów

f x{[(`:$x:`/"=")()|{|p|p~=":",""a=p;a~=`\+`,""b=p;b~="-","";["=",#x-#b+#a];{(p/"")|{|o|[o,"1"*#o]}_}}_][1:]}

Wypróbuj online!

Funkcja podziału nie działała tak, jak zamierzałem z tym programem. Na przykład split("", sep="")zwraca jeden pusty ciąg zamiast niczego. Jak to jest logiczne? Z tego powodu program jest prawie 20 bajtów większy niż mógłby być, gdyby semantyka podziału była idealna.

Ideą tej odpowiedzi jest to, że wiemy, że długość łańcucha wejściowego musi być większa lub równa wartości równania, więc definiujemy wartość równania jako długość łańcucha. Dla każdej części równania uważamy, że każdy operator jest +1lub -1odejmuje i dodaje je do wartości równania.

Nie golfowany:

function f(x) {
    /* Adds ":"s around the string to prevent "=" being split wrong. */
    [split(`:$x:`, sep="=") | for p do
        p ~= ":", ""          /* Removes colons. */
        a := p; b := p        /* Initializes a and b to be p. */
        a ~= "\\+", ""        /* The lengths of a and are now equal to the */
        b ~= "-", ""          /* numbers of "-" and "+" characters in x. */
        push("=", #x-#b+#a)   /* Prints "=" and the value of the equation */
                              /* minus number of "+"s plus number of "-"s. */
        split(p, sep="") | for o do /* For each operator: */
            push(o)                 /* Prints the operator. */
            push(1) if [o != ""]    /* Prints 1 unless the operator is "". */
        done
    done][1:] /* Removes the first character of the output ("="). */
}
fergusq
źródło