Memecahkan persamaan dengan (hampir) angka apa pun yang Anda suka

27

Diberikan string karakter di +=-mana setidaknya ada satu= , masukkan bilangan bulat positif antara semua simbol dan pada awal dan akhir sehingga persamaan matematika terpenuhi.

Misalnya diberi input

+-=-=

Anda perlu memasukkan bilangan bulat positif A hingga F seperti ini

A+B-C=D-E=F

sedemikian rupa sehingga semua persamaan puas, yaitu A + B - Cdan D - Edan Fsemua angka yang sama.

Ada banyak cara yang mungkin untuk melakukan ini karena, selama persamaan berhasil, setiap himpunan bilangan bulat positif dapat digunakan. Setiap baris di sini adalah kemungkinan input untuk input yang valid +-=-=:

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

Perhatikan bahwa nilai ekspresi tidak perlu menjadi bilangan bulat positif seperti angka yang dimasukkan. Misalnya, input yang diberikan -=-output 1-10=8-17(evals to -9) dan 10-1=17-8(evals to 9) sama-sama valid. Tentu saja untuk beberapa input seperti =tidak mungkin memiliki ekspresi negatif karena hanya angka positif seperti yang 5=5dapat dimasukkan.

Perhatikan juga bahwa nol bukan bilangan bulat positif.

Kode terpendek dalam byte menang.

Anda dapat menampilkan nomor sebagai daftar alih-alih memasukkannya langsung ke dalam string. Jika Anda menghasilkan string, mungkin ada spasi yang memisahkan simbol dan angka. Jadi, untuk input +-=-=, keluaran

2, 3, 4, 6, 5, 1

atau

2 + 3 - 4 = 6 - 5 = 1

setara dengan keluaran

2+3-4=6-5=1

Uji Kasus

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
Hobi Calvin
sumber
Terkait
Martin Ender
Bisakah kita mengasumsikan batas atas pada panjang rumus?
xnor
2
@ xnor Anda dapat mengasumsikan input kurang dari 2 ^ 16 karakter jika itu membantu.
Calvin Hobi

Jawaban:

16

Retina , 58 byte

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

1+
$.&

Cobalah online!

Solusi alternatif pada jumlah byte yang sama:

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

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

Cobalah online!

Penjelasan

Ide dasarnya adalah untuk mengubah semua +s dan -menjadi sederhana +1dan -1operasi dan kemudian menambahkan jumlah yang cukup besar yang membuat semua persamaan bekerja. Untuk membuat persamaan cocok, kita bisa dengan mudah menambahkan angka yang sama ke masing-masing, dan kemudian menguranginya dengan satu untuk masing-masing +1dan menambahnya dengan satu untuk masing-masing -1setelah itu. Karena kita akan bekerja dengan angka unary, satu-satunya tangkapan adalah bahwa angka pertama harus cukup besar sehingga kita bisa menguranginya sebanyak 1 kali.

[-+]
$&1

Kami mulai dengan memasukkan 1setelah setiap -atau +.

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

The \Bmemastikan bahwa pertandingan ini baik di awal input, atau antara =dan +atau -, yaitu semua posisi di mana kita ingin memasukkan jumlah terkemuka ekspresi. Bagian ((\+1)|(-1))*kemudian hanya menghitung jumlah +1s dan -1s dalam kelompok 2dan 3masing - masing. Sekarang mari kita hancurkan string substitusi:

$._$*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_

Jatuh berulang-ulang 1_dari string, menerapkan pembatalan yang diperlukan dari +1s.

1+
$.&

Akhirnya, ganti semua string 1s dengan panjangnya untuk mengkonversi dari unary ke desimal.

Martin Ender
sumber
8

Python 2 , 76 byte

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

Cobalah online!

Tidak
sumber
3
Bisakah Anda menambahkan penjelasan?
Calvin Hobbies
1
@HelkaHomba Idenya cukup sederhana: pertama ambil setiap potongan input dibagi dengan tanda sama. Pilih nomor pertama dari setiap potongan yang akan dibuat eqtn_len + plus_signs + minus_signs - 2 * plus_signs = eqtn_len + minus_signs - plus_signs. Kemudian karena semua angka lain dalam chunk adalah nomor, total untuk chunk berhasil eqtn_len + minus_signs - plus_signs - minus_signs + plus_signs = eqtn_len. Panjang persamaan harus positif, jadi semuanya berjalan lancar.
FryAmTheEggman
6

Python 2, 199 179 178 172 162 158 156 156 152 byte

Terlalu lama, tapi solusinya mudah dibuat.

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

Cobalah online

Ini akan mencoba setiap kemungkinan sampai menemukan solusi. Program ini sangat lambat. Ini juga melakukan penggantian string setiap iterasi. Suntingan "172" membuatnya lebih lambat secara drastis , karena alih-alih dimulai dengan rentang kecil, itu dimulai pada maks. Misalnya input-= atau=+ harus mencoba 2 ** 32 upaya sebelum mencapai solusi.

Untuk mempercepat program, gunakan versi dengan 178 byte dari riwayat edit.

mbomb007
sumber
Bukankah rangedi python2 membuat seluruh rentang sebagai daftar segera? IIRC Anda bisa mempercepatnya dengan menggunakan xrangesebagai gantinya, karena saya pikir itu adalah versi lazy-loading (Python3 menggunakan lazy sebagai default range)
Delioth
1
@Delioth Itu menggunakan byte lain, meskipun. Tujuannya adalah untuk menghapus byte. Juga, itu tidak akan benar-benar memberikan banyak peningkatan, karena mayoritas perlambatan adalah dari jumlah iterasi, bukan pembuatan daftar, yang hanya terjadi sekali. Saya berlari print range(1,65537)dan selesai dalam 0,034 s.
mbomb007
Yah, tentu saja - lebih dari "ini bisa mempercepatnya dengan metodologi yang persis sama," pada kekhawatiran akan butuh waktu lama. Memori meronta-ronta dapat menyebabkan perlambatan yang signifikan. Anda juga dapat memotong beberapa byte (mungkin hanya 1) dengan tidak menyetel l=..., tetapi menempatkannya di dalam product(range(...),repeat=len(s)+1). Jika Anda membutuhkan tanda kurung, ia hanya menyimpan satu byte (\ n)
Delioth
@Delioth Bahkan jika saya membutuhkan parens di sekitar len(s)+1, saya bisa menggunakannya -~len(s), yang tidak akan memerlukan parens.
mbomb007
Ah benar Saya selalu lupa tentang operasi bitwise dan trik-harus tol bekerja di javascript frontend mengambil keahlian Python saya!
Delioth
5

JavaScript (ES6), 92 82 byte

Golf 8 byte dengan trik dari @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>

Kuncinya di sini adalah untuk memasukkan 1setelah setiap +atau -, lalu tambahkan setiap ekspresi dengan jumlah yang membuat ekspresi sama dengan panjang input. Dengan cara ini kami dapat menjamin bahwa jumlahnya selalu positif; karena selalu ada setidaknya 1 =dalam string, jumlah +s tidak pernah bisa mencapai panjang string, jadi sisanya selalu setidaknya 1. Anda dapat memverifikasi ini dengan mengetikkan angka +s sembarang pada cuplikan di atas.

Produksi ETH
sumber
5

Python 2 , 120 119 byte

-1 byte, terima kasih kepada 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)

Cobalah online! atau Verifikasi semua kasus uji

Pertama saya masukkan 1di setiap posisi, untuk memeriksa nilai tertinggi, lalu menambahkannya sebagai offset pada setiap persamaan. Ini berfungsi karena Anda tidak dapat menambahkan angka negatif, sehingga hasil minimum diberikan oleh jumlah +dalam persamaan yang hanya dimiliki +.

tongkat
sumber
Anda dapat menghapus beberapa spasi.
mbomb007
5

GNU Prolog, 156 byte

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

Penjelasan

Kami punya banyak persamaan untuk dipecahkan, jadi mengapa tidak menggunakan pemecah persamaan yang sebenarnya?

xpada dasarnya adalah evaluator persamaan untuk persamaan bentuk +-+; selain persamaan itu sendiri, ia memiliki dua argumen tambahan (daftar perbedaan L,Ryang berisi nilai-nilai persamaan, dan nilai Vyang dievaluasi oleh persamaan). Seperti biasa dalam Prolog, ini dapat digunakan dengan cara apa saja (misalnya Anda dapat menentukan Vdan mendapatkan L,R, menentukan L,Rdan mendapatkan V, menentukan keduanya dan memverifikasi bahwa nilainya benar, atau tidak menentukan dalam hal mana kendala yang sesuai akan ditempatkan pada keduanya Vdan L,R). "Elemen saat ini" L,Rdinamai E, dan kami juga menyertakan pernyataan bahwaE lebih besar dari 0 (karena pertanyaannya memerlukan penggunaan angka positif). Fungsi ini sedikit lebih verbose daripada yang saya inginkan, misalnya saya harus menulis[E|R]pencocokan pola / tidak cocok dua kali, karena fakta bahwa daftar adalah asosiatif kanan tetapi penambahan dan pengurangan asosiatif kiri. Sayangnya, kita perlu menggunakan daftar aktual, daripada menciptakan tipe daftar asosiatif kiri kita sendiri dari sel kontra, untukfd_labeling agar berfungsi.

qmirip dengan x, tetapi juga termasuk =. Itu pada dasarnya hanya panggilan x, dan itu sendiri secara rekursif. Secara kebetulan, ini adalah demonstrasi yang sangat jelas tentang cara kerja daftar perbedaan, menunjukkan bahwa Anda dapat menggabungkan dua daftar perbedaan L,Tdan T,Rmenjadi daftar perbedaan tunggal L,R. Ide dasarnya adalah bahwa daftar perbedaan adalah fungsi parsial yang mengambil argumen Rdan mengembalikan nilai Lyang ada di Rdalam daftar itu sendiri. Dengan demikian, dengan mengidentifikasi argumen dari satu daftar perbedaan dan nilai pengembalian yang lain, kita dapat menyusun fungsi, dan dengan demikian merangkai daftar tersebut.

Akhirnya, syang merupakan fungsi yang benar-benar menyelesaikan tugas dalam pertanyaan, adalah fungsi pembungkus yang memanggil qdengan argumen. Kami mengonversi daftar perbedaan ke daftar reguler dengan memberikan []argumennya, dan gunakan fd_labelinguntuk menemukan solusi persamaan yang kami buat. (Secara default, sepertinya menetapkan nilai ke 1 jika tidak ada alasan untuk mengaturnya ke sesuatu yang lain. Namun, itu dapat dikonfigurasi; value_method(random)memberikan lebih banyak solusi "menarik" daripada menempatkan 1s di mana-mana, misalnya, dan masih sangat cepat. )

Output sampel

Dengan program seperti yang tertulis:

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

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

Jika saya membuat program sedikit lebih lama untuk ditambahkan value_method(random), hasilnya bervariasi, tetapi terlihat seperti ini:

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

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

Dalam kedua kasus, ?pada akhir output berarti mungkin ada lebih dari satu solusi. (Tentu saja, dalam hal ini, kita tahu bahwa ada banyak lebih dari satu solusi!)


sumber
4

Mathematica, 116 byte

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

Fungsi murni mengambil string sebagai input dan mengembalikan daftar bilangan bulat positif. Strategi dasar: kami hanya pernah menambah 1 dan mengurangi 1, dan kami memilih angka awal dalam setiap ungkapan untuk membuat semuanya sama.

c=Characters@StringSplit[#,"="]/."+"->-1/."-"->1akan membagi string input pada setiap tanda sama dengan, lalu ganti masing-masing +dengan -1dan setiap -oleh 1. Namun, jika ada tanda sama dengan di awal atau akhir, maka itu akan diabaikan. Oleh karena itu kami menambahkan karakter baru secara artifisial di setiap ujung ( "0"<>#<>"0") dan membuatnya hilang setelah pemisahan-string selesai ( /."0"->Nothing).

Total setiap sublist sekarang sama dengan integer yang dapat kita tempatkan di depan +s dan -s untuk membuat setiap persamaan sama. 1-Min[Tr/@c]adalah bilangan bulat terkecil yang dapat kita tambahkan ke setiap total untuk membuat semuanya positif. Jadi, Prepend[#^2,1-Min[Tr/@c]+Tr@#]&bawa setiap sublist ( ^2giliran semua entri mereka 1) dan tambahkan totalnya digeser oleh bilangan bulat kompensasi terkecil ini. Daftar yang dihasilkan Joindiedit bersama untuk menghasilkan output.

Greg Martin
sumber
3

Ruby, 76

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

Nilai target untuk ekspresi ditetapkan pada 5**8minus 1 untuk alasan bermain golf! Awalnya saya menggunakan s.size+1minus 1.

Tidak digabungkan dalam program uji

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["======"]

Keluaran

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
sumber
2

PHP, 207 204 197 114 byte

pendekatan langsung: jauh lebih pendek dan lebih cepat

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

Jalankan dengan echo '<input>' | php -nR '<code>'atau coba online .

kerusakan

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"
  • !$cbenar di iterasi pertama, dilemparkan ke 1untuk pengindeksan string; "="[1]kosong.
    Setelah itu, $cdiatur dan !$csalah, masukkan ke 0dan"="[0] adalah karakter pertama.
  • Nilai maksimum untuk persyaratan apa pun tidak boleh melebihi jumlah plus +1;
    jadi kami pasti aman dengan panjang input. Semua persyaratan akan dievaluasi untuk itu.
  • chunk_split($s,$n,$i)menyisipkan $isetelah setiap $nkarakter $s- dan pada akhirnya.
    Untuk mencegah istilah kosong beralih ke 1, kesalahan terpaksa dengan mengatur panjang chunk ke 0.
Titus
sumber
1

Röda , 112 110 109 byte

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

Cobalah online!

Fungsi pemisahan tidak berfungsi seperti yang saya maksudkan dengan program ini. Misalnya, split("", sep="")mengembalikan satu string kosong, bukan apa-apa. Bagaimana itu logis? Karena ini program ini hampir 20 byte lebih besar dari apa yang bisa terjadi jika semantik yang terbelah itu ideal.

Gagasan dari jawaban ini adalah bahwa kita tahu bahwa panjang string input harus lebih besar atau sama dengan nilai persamaan, jadi kami mendefinisikan nilai persamaan menjadi panjang string. Untuk setiap bagian dari persamaan, kami pikir setiap operator menjadi +1dan -1dan mengurangi dan menambahkannya ke nilai persamaan.

Tidak Disatukan:

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
sumber