Resolva uma equação com (quase) qualquer número que você quiser

27

Dada uma sequência de caracteres em +=-que há pelo menos um =, insira números inteiros positivos entre todos os símbolos e no início e no final, de modo que as equações matemáticas sejam atendidas.

Por exemplo, dada a entrada

+-=-=

você precisa inserir números inteiros positivos A a F como este

A+B-C=D-E=F

de tal modo que as equações são satisfeitas, isto é, A + B - Ce D - Ee Fsão todos o mesmo número.

Existem muitas maneiras possíveis de fazer isso, pois, desde que as equações funcionem, qualquer conjunto de números inteiros positivos pode ser usado. Cada linha aqui é uma saída válida possível para entrada +-=-=:

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

Observe que o valor das expressões não precisa ser um número inteiro positivo como os números inseridos. Por exemplo, dada a entrada, -=-as saídas 1-10=8-17(avaliações para -9) e 10-1=17-8(avaliações para 9) são igualmente válidas. Obviamente, para algumas entradas, como =é impossível ter uma expressão negativa, uma vez que apenas números positivos como 5=5podem ser inseridos.

Observe também que zero não é um número inteiro positivo.

O código mais curto em bytes vence.

Você pode exibir os números como uma lista em vez de inseri-los diretamente na string. Se você imprimir a sequência, poderá haver espaços separando símbolos e números. Então, para entrada +-=-=, saída

2, 3, 4, 6, 5, 1

ou

2 + 3 - 4 = 6 - 5 = 1

é equivalente a saída

2+3-4=6-5=1

Casos de teste

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
Passatempos de Calvin
fonte
Relacionado.
Martin Ender
Podemos assumir qualquer limite superior no comprimento da fórmula?
Xnor
2
@xnor Você pode supor que a entrada tenha menos de 2 ^ 16 caracteres, se isso ajudar.
Calvin Hobbies

Respostas:

16

Retina , 58 bytes

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

1+
$.&

Experimente online!

Solução alternativa na mesma contagem de bytes:

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

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

Experimente online!

Explicação

A idéia básica é transformar todos os +s e -s em simples +1e -1operações e, em seguida, para preceder um número suficientemente grande que faz toda a equações trabalho. Para fazer com que as equações correspondam, podemos simplesmente acrescentar o mesmo número a cada uma delas e, em seguida, reduzi-lo em um para cada um +1e aumentá-lo em um para cada -1depois. Como trabalharemos com números unários, o único problema é que o primeiro número precisa ser grande o suficiente para que possamos reduzi-lo em 1 vezes o suficiente.

[-+]
$&1

Começamos inserindo um 1depois de cada -ou +.

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

Os \Bgarante que estes jogos são, quer no início da entrada, ou entre uma =e uma +ou -, ou seja, todas as posições onde se deseja inserir o número inicial de uma expressão. A ((\+1)|(-1))*parte em seguida, simplesmente conta o número de +1s e -1s em grupos 2e 3respectivamente. Agora vamos dividir a string de substituição:

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

Solte repetidamente 1_da string, aplicando o cancelamento necessário do +1s.

1+
$.&

Por fim, substitua todas as cadeias de caracteres de 1s pelos seus comprimentos para converter de unário para decimal.

Martin Ender
fonte
8

Python 2 , 76 bytes

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

Experimente online!

xnor
fonte
3
Você pode adicionar uma explicação?
Hobbies de Calvin
1
@HelkaHomba A idéia é bastante simples: primeiro pegue cada pedaço da entrada dividido por sinais de igual. Escolha o primeiro número de cada pedaço a ser eqtn_len + plus_signs + minus_signs - 2 * plus_signs = eqtn_len + minus_signs - plus_signs. Então, como todos os outros números no bloco são iguais, o total do bloco é calculado em eqtn_len + minus_signs - plus_signs - minus_signs + plus_signs = eqtn_len. O comprimento da equação deve ser positivo, para que tudo dê certo.
FryAmTheEggman
6

Python 2, 199 179 178 172 162 158 158 152 152 151 bytes

Muito tempo, mas a solução foi fácil de criar.

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

Experimente online

Isso tentará todas as possibilidades até encontrar uma solução. O programa é extremamente lento. Ele também executa a substituição de cadeias a cada iteração. A edição "172" tornou a velocidade drasticamente mais lenta, pois em vez de começar com um pequeno intervalo, ela começa no máximo. Por exemplo, as entradas -=ou =+precisam tentar 2 ** 32 tentativas antes de chegar a uma solução.

Para acelerar o programa, use a versão com 178 bytes do histórico de edição.

mbomb007
fonte
rangeNo python2 não cria todo o intervalo como uma lista imediatamente? IIRC você pode acelerá-lo usando xrangeem vez disso, como eu acho que essa é a versão carregamento lento (Python3 usa preguiçoso como padrão range)
Delioth
1
@ Delioth Isso usa outro byte, no entanto. O objetivo é remover bytes. Além disso, isso não forneceria muita velocidade, pois a maior parte da desaceleração é proveniente do número de iterações, não da criação da lista, que ocorre apenas uma vez. Eu corri print range(1,65537)e terminou em 0.034 s.
mbomb007
Bem, é claro - mais do que "isso poderia acelerar com exatamente a mesma metodologia", com a preocupação de levar tanto tempo. A perda de memória pode causar uma desaceleração significativa. Além disso, você pode cortar alguns bytes (talvez apenas 1) não configurando l=..., mas colocando isso corretamente no product(range(...),repeat=len(s)+1). Se você precisar de parênteses, ele economiza apenas um byte (\ n)
Delioth 9/17/17
@ Delioth Mesmo que eu precisasse de parênteses len(s)+1, eu poderia usá- los -~len(s), o que não exigiria parênteses.
mbomb007
Ah, certo. Eu sempre esqueço operações e truques bit a bit - deve ser o pedágio que o javascript de front-end está assumindo na minha experiência em Python!
Delioth 9/03
5

JavaScript (ES6), 92 82 bytes

Jogou 8 bytes com um truque de @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>

O truque aqui é inserir um 1depois de cada +ou -, em seguida, acrescentar a cada expressão o número que torna a expressão igual ao comprimento da entrada. Dessa forma, podemos garantir que o número seja sempre positivo; como sempre há pelo menos 1 =na string, o número de +s nunca pode atingir o comprimento da string, portanto o restante é sempre pelo menos 1. Você pode verificar isso digitando um número arbitrário de +s no snippet acima.

ETHproductions
fonte
5

Python 2 , 120 119 bytes

-1 byte graças a 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)

Experimente online! ou Verifique todos os casos de teste

Primeiro insiro 1em todas as posições, para verificar o valor mais alto, depois adiciono-o como deslocamento em todas as equações. Isso funciona porque você não pode adicionar números negativos; portanto, o resultado mínimo é dado pela quantidade de +na equação que possui apenas +.

Cajado
fonte
Você pode remover alguns espaços.
mbomb007
5

GNU Prolog, 156 bytes

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

Explicação

Temos várias equações a serem resolvidas. Por que não usar um solucionador de equações real?

xé basicamente um avaliador de equações para equações da forma +-+; além da própria equação, ela possui dois argumentos adicionais (uma lista de diferenças L,Rque contém os valores da equação e um valor Vque a equação avalia). Como de costume no Prolog, ele pode ser usado de qualquer maneira (por exemplo, você pode especificar Ve obter um L,R, especificar L,Re obter um V, especificar ambos e verificar se o valor está correto ou não especificar nem, nesse caso, restrições apropriadas serão impostas a ambos Ve L,R) O "elemento atual" de L,Ré nomeado Ee também incluímos uma afirmação de queEé maior que 0 (porque a pergunta requer o uso de números positivos). Essa função é um pouco mais detalhada do que eu gostaria, por exemplo, tive que escrever a funcionar.[E|R]correspondência de padrão / sem correspondência duas vezes, devido ao fato de que as listas são associativas à direita, mas a adição e subtração são associativas à esquerda. Infelizmente, precisamos usar uma lista real, em vez de inventar nosso próprio tipo de lista associativa à esquerda com células contras, porfd_labeling

qé semelhante a x, mas também inclui =. Basicamente, apenas chama xe recursivamente. Aliás, é uma demonstração muito clara de como as listas de diferenças funcionam, mostrando que você pode concatenar duas listas de diferenças L,Te T,Ruma única lista de diferenças L,R. A idéia básica é que uma lista de diferenças é uma função parcial que pega um argumento Re retorna um valor Lque está Rcom a própria lista anexada a ele. Assim, identificando o argumento de uma lista de diferenças e o valor de retorno de outra, podemos compor as funções e concatenar as listas.

Finalmente, sque é a função que realmente resolve a tarefa na pergunta, é uma função de invólucro que chama qcom argumentos. Convertemos a lista de diferenças em uma lista regular, fornecendo []como argumento e usamos fd_labelingpara encontrar uma solução para a equação que construímos. (Por padrão, parece gostar de definir valores como 1 se não houver motivo para defini-los para outra coisa. No entanto, ele pode ser configurado; value_method(random)fornece soluções mais "interessantes" do que colocar 1s em todos os lugares, por exemplo, e ainda é muito rápido. )

Saída de amostra

Com o programa conforme escrito:

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

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

Se eu demorar um pouco mais para adicionar um programa value_method(random), o resultado varia, mas é algo como isto:

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

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

Nos dois casos, ?no final da saída significa que pode haver mais de uma solução. (Obviamente, nesse caso, sabemos que há muito mais de uma solução!)


fonte
4

Mathematica, 116 bytes

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

Função pura pegando uma string como entrada e retornando uma lista de números inteiros positivos. Estratégia básica: sempre adicionamos 1 e subtraímos 1, e escolhemos os números iniciais em cada expressão para tornar tudo igual.

c=Characters@StringSplit[#,"="]/."+"->-1/."-"->1dividiria a string de entrada em todos os sinais de igual e, em seguida, substituiria cada +por -1e cada -por 1. No entanto, se houver um sinal de igual no início ou no final, ele será ignorado. Portanto, adicionamos artificialmente um novo caractere em cada extremidade ( "0"<>#<>"0") e fazemos com que ele desapareça após a divisão da cadeia de caracteres (/."0"->Nothing ).

O total de cada sub-lista agora é igual a um número inteiro que podemos colocar na frente dos +s e -s para fazer com que cada expressão igual. 1-Min[Tr/@c]é o menor número inteiro que podemos adicionar a cada total para torná-los todos positivos. Então, Prepend[#^2,1-Min[Tr/@c]+Tr@#]&pega cada sub-lista (a qual ^2vira todas as suas entradas 1) e precede seu total deslocado por esse menor número inteiro de compensação. As listas resultantes são Joineditadas juntas para produzir a saída.

Greg Martin
fonte
3

Ruby, 76

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

O valor alvo para as expressões é fixado em 5**8menos 1 por razões de golfe! Originalmente eu estava usandos.size+1 menos 1.

Ungolfed in program program

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

Saída

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

PHP, 207 204 197 114 bytes

abordagem direta: muito mais curta e mais rápida

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

Executar echo '<input>' | php -nR '<code>'ou testá-lo online .

demolir

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"
  • !$cé verdadeiro na primeira iteração, convertida em 1para indexação de string; "="[1]está vazia.
    Depois disso, $cé definido e !$cfalso, convertido para0 e"="[0] é o primeiro caractere.
  • O valor máximo para qualquer termo não precisa exceder o número de vantagens +1;
    então estamos definitivamente seguros com o tamanho da entrada. Todos os termos serão avaliados para isso.
  • chunk_split($s,$n,$i)insere $iapós todos os $ncaracteres de $s- e no final.
    Para evitar que termos vazios se voltem para 1, um erro é forçado configurando o comprimento do pedaço como 0.
Titus
fonte
1

Röda , 112 110 109 bytes

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

Experimente online!

A função de divisão não funcionou como pretendia com este programa. Por exemplo,split("", sep="") retorna uma string vazia em vez de nada. Como isso é lógico? Devido a isso, o programa é quase 20 bytes maior do que poderia ser se a semântica de divisão fosse ideal.

A idéia desta resposta é que sabemos que o comprimento da sequência de entrada deve ser maior ou igual ao valor da equação, portanto, definimos o valor da equação como sendo o comprimento da sequência. Para cada parte da equação, acreditamos que todo operador seja +1ou-1 subtrai e os adiciona ao valor da equação.

Ungolfed:

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
fonte