Escreva um solucionador de equações de palavras [duplicado]

17

Introdução

Considere o seguinte exemplo:

  CODE
+ GOLF
——————
 GREAT

Esta é uma equação em que cada letra representa um dígito decimal e as palavras representam números naturais (letras semelhantes representam dígitos semelhantes e letras diferentes representam dígitos diferentes). A tarefa é combinar cada letra com seu valor de dígito para que a equação esteja correta. Uma solução para a equação acima é:

  9265
+ 1278
——————
 10543

Sua tarefa

Sua tarefa é escrever um programa ou uma função que possa resolver essas equações, como visto acima.

Entrada

A entrada é uma sequência no seguinte formato:

[A-Z]+\+[A-Z]+=[A-Z]+

Exemplo:

  1. CODE+GOLF=GREAT
  2. AA+BB=CC

Os espaços são omitidos e somente as letras entre maiúsculas A e Z serão usadas (sem letras maiúsculas ou minúsculas).

Essa sequência pode ser lida a partir da entrada padrão, de um arquivo ou como um parâmetro de função.

Resultado

Você tem as duas opções a seguir para o formato de saída:

  1. a equação original com os dígitos substituídos
  2. lista das letras e seus valores

Se houver várias soluções, qualquer (mas apenas uma) delas deve ser retornada. Se não houver soluções, o programa deve retornar uma cadeia vazia ou nula. A saída pode ser retornada como uma sequência, pode ser gravada na saída padrão ou em um arquivo.

Exemplo:

  1. 9265+1278=10543
  2. A=1 B=2 C=3 (você pode usar qualquer delimitador)

Regras

  1. Para facilitar as coisas, os números são aceitos para começar com 0, mas você pode lidar com números com os 0 iniciais como soluções inválidas.
  2. Letras semelhantes representam dígitos semelhantes e letras diferentes representam dígitos diferentes
  3. Você pode usar qualquer idioma e a biblioteca padrão do idioma escolhido (sem bibliotecas externas)
  4. Você não pode se conectar a nenhum recurso na internet (por que você faria assim?)
  5. Esta é uma tarefa de código de golfe, o código mais curto vence. Caracteres consecutivos de espaço em branco contam como um único caractere. (Portanto, qualquer programa escrito em espaço em branco vence automaticamente)

Eu tenho uma solução um pouco hackish usando 179 caracteres. Se algo não estiver claro, pergunte-me nos comentários.

David Frank
fonte
Eu acho que a resposta ideal é "tudo é 0". Você pode querer proibir isso especificamente.
Undergroundmonorail
11
O que você quer dizer com tudo é 0? Letras diferentes devem indicar números diferentes.
David Frank
Perdeu essa, deixa pra lá :)
undergroundmonorail
If there are no solutions, the program should return an empty string or null.Loops infinitos ainda não produzem nada ... posso?
Titus
11
Todas as respostas vencedoras para esse desafio se resumem efetivamente à exploração da regra de pontuação de espaço em branco, com votação tão fechada quanto duplicada.
Pppery

Respostas:

11

Python - 48 caracteres

exec("".join(map(chr,map(len,'                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             '.split("    ")))))

Abusando da regra de espaço em branco.

Primeiro, converti todos os caracteres da resposta da CesiumLifeJacket para o seu valor ASCII (eu poderia ter escrito o meu próprio, mas sou preguiçoso e, de qualquer maneira, não teria afetado a pontuação final). A cadeia longa na minha solução é um espaço para cada um desses valores ASCII e tabulações que os separam. Divida em abas, encontre os comprimentos, converta novamente em caracteres e execute.

O SE converte guias em 4 espaços cada, para que o copypasting não funcione. Você só precisa acreditar em mim :)

undergroundmonorail
fonte
11
Você pode fornecer um link para ideone ou um hex dump do seu código?
n̴̖̋h̷͉a̷̭̿h̸̡̅ẗ̵̨d̷̰ĥ̷̳
11
Também: exec é uma palavra-chave, você pode salvar 2 caracteres removendo o primeiro e o último colchete
#
4

Ruby 2.0, 122 caracteres

Baralhar a força bruta + eval! Isso ainda não atende aos critérios de retornar cadeia nula / vazia quando não há solução; apenas faz um loop infinito. Se não conseguir encontrar um resultado após ~ 300 milhões de iterações, retornará zero. Perto o suficiente?

f=->s{d=*0..9
d.shuffle!&&$.+=1until$.>9**9||z=eval((r=$_.tr(s.scan(/\w/).uniq*'',d*'')).gsub(/\b0/,'').sub ?=,'==')
z&&r}

Ele encontra todas as letras exclusivas na entrada, depois embaralha repetidamente os dígitos de 0 a 9 e tenta combiná-los com as letras até encontrar uma configuração que funcione.

O código é apresentado como uma função chamada fque retorna uma sequência com os números substituídos, como na Opção de Saída 1 acima. Exemplo de uso:

puts f["AA+BB=CC"]
 #=> 22+44=66
puts f["CODE+GOLF=GREAT"]
 #=> 8673+0642=09315

O tempo de execução do CODE+GOLF=GREATexemplo na minha máquina varia de instantâneo a cerca de 6 segundos - depende da sorte que você tem com os shuffles!

Estou particularmente insatisfeito com a parte gsub(/\b0/,'')para remover os zeros à esquerda, mas foi a única coisa que consegui impedir evalde interpretar os números como entradas octais.

( BÔNUS : Como usa eval, funciona para expressões arbitrárias em Ruby e não apenas para adição!)

Paul Prestidge
fonte
Eu tive a mesma idéia quando li isso, mas obtive ~ 170 caracteres de código, muito bem feito. 0..9 são dez dígitos, então o limite não deve ser 10 ** 10? Você pode usar a permutação Array # para fazer um loop em todos os mapeamentos possíveis, mas isso pode tornar o código mais longo.
blutorange
@blutorange Acabei de escolher 9 ** 9 porque era um número grande que você poderia escrever com poucos caracteres. Deve ser mais do que suficiente para qualquer caso de teste razoável, eu acho! Eu não tentei uma versão com base permutation, mas como você diz, eu estava principalmente preocupado com o comprimento do código.
Paul Prestidge
4

LiveScript (179 caracteres)

Possui tempo de execução determinístico e relativamente rápido e funciona com outros operadores (+, -, *).

f=(s)->                     # define function that takes parameter s
  c=s.replace /[^A-Z]/g ''  # remove all the non-letters
  if c                      # if any letters remain
    for i from 0 to 9       # loop from 0 to 9
       if s.indexOf(i)<0&&a=f s.split(c.0).join i  # if i is not present in the number, replace the first letter with i and call the function recursively
         return a           # if there is a solution, return it
  else                      # if there are no letters left
    if eval s.replace(/(^|\D)0+(\d)/g,'$1$2').replace \= \==  # if the expression is correct (we need to remove leading 0, because javascript interprets numbers with leading 0 as octal)
       return s  # return solution



f("CODE+GOLF=GREAT")
David Frank
fonte
2

Python, 256 213 caracteres

Tempo de execução horrível, tentará melhorar ainda mais:

q='='
e=input()
v=set(e)-set([q,'+'])
for x in __import__('itertools').permutations(range(10),len(v)):
    t=e
    for l,n in zip(v,x):t=t.replace(l,str(n))
    try: 
        if eval(t.replace(q,q*2)):print(t);break
    except:pass
CesiumLifeJacket
fonte
2

JavaScript 138

for(s=prompt(p='1');eval(p.replace('=','!='));)for(p=s,i=64;i++<90;)p=p.replace(new RegExp(String.fromCharCode(i),'g'),10*Math.random()|0)

Força bruta aleatória.
Pode demorar um pouco (minha melhor chance CODE+GOLF=GREATé de 3 segundos, meus piores 3 minutos).
Experimente com uma expressão simples comoA+B=C

Michael M.
fonte
2

Haskell, 222

import Data.List
z=(\(b,(_:c))->b:z c).span Data.Char.isUpper
j(Just g)=g
main=interact$(\d@[a,b,c]->show$take 1[e|e<-map(zip$nub$d>>=id)$permutations['0'..'9'],(\f->f a+f b==(f c::Int))(read.map(j.(`lookup`e)))]).take 3.z

Força bruta. Tenta todas as correspondências possíveis até encontrar uma ou depois de concluir todas as tentativas. Estiquei as regras de saída: imprime algo parecido [[('C','3'),('O','8'),('D','6'),('E','7'),('G','0'),('L','5'),('F','2'),('R','4'),('A','1'),('T','9')]]com a solução e, se não houver, imprime []. Deixe-me saber se eu preciso mudar isso.

YawarRaza7349
fonte
Eu acho que essa saída é aceitável.
David Frank
2

CJam - 17

"





























































































































































































































































































































    ""  
"f#3b127b:c~

Total de 975 caracteres, mas 960 deles são espaços em branco em 2 sequências; portanto, eles contam como 2 caracteres e, junto com os outros 15, obtemos 17.
975 podem parecer muito, mas observe que a solução python do undergroundmonorail tem 18862 caracteres, eles está apenas em uma única linha :)

Você pode executá-lo em http://cjam.aditsu.net/ para palavras curtas, mas provavelmente deve usar o interpretador java para palavras mais longas. Com o java no meu laptop, SEND+MORE=MONEYé executado em 30 a 40 segundos e CODE+GOLF=GREATem quase 3 minutos. Ele não aceita números começando com 0 (porque isso não é legal).

Aqui está um programa que gera o programa acima (também ajuda se o StackExchange não mostrar o espaço em branco corretamente):

"{L__&=}:U;
{L!!{L))_9>{;:L;I}{+:L;}?}*}:I;
{{U!_{I}*}g}:M;
{L,N<L,g&}:K;
{I{K{L0+:L;}*MK}g}:G;
{{C#L=}%si}:R;
{XRYR+ZR=PRAb0#0<&}:F;
l'+/~'=/~:Z;:Y;:X;
[X0=Y0=Z0=]:P;
XYZ++_&:C,:NB<{0a:L;{F0{GL}?}g}*
L{XR'+YR'=ZR}{L}?"
127b3b[32 9 A]:cf='"\'"_32c9cAc"\"f#3b127b:c~"

As 11 primeiras linhas contêm o programa original (não jogado de verdade) em uma seqüência de caracteres, e a última linha faz a conversão e adiciona a parte de decodificação.

aditsu
fonte
0

Powershell, 137 bytes

porta do LiveScript

$f={param($s)if($c=$s-replace'[^A-Z]'){0..9|?{$s-notmatch$_}|%{&$f ($s-replace$c[0],$_)}|Select -f 1}elseif($s-replace'=','-eq'|iex){$s}}

Script de teste não destruído:

$f={

param($s)                           # parameter string
$c=$s-replace'[^A-Z]'               # remove all the non-letters
if($c){                             # if any letters remain
    0..9|?{                         # loop from 0 to 9
        $s-notmatch$_               # if $s is not contains current number
    }|%{
        &$f ($s-replace$c[0],$_)    # replace the first letter with current number and call the function recursively
    }|Select -f 1                   # seelct first non-null value (break if found)
}
elseif($s-replace'=','-eq'|iex){    # else if evaluated value if the expression is $true
    $s                              # return $s as solution
}

}

&$f "AA+BB=CC"
&$f "A+AB=A"            # empty because it has no solution
&$f "CODE+GOLF=GREAT"

Resultado:

11+22=33
2846+0851=03697
confuso
fonte
0

PHP, 118 113 bytes

for(;;)eval(strtr($argn,"=".$w=substr(count_chars($argn,3),2),"-".$n=str_shuffle(1234567890))."||die('$w
$n');");

imprime dígitos abaixo das letras e sai do programa; loop infinitamente se insolúvel. Corra como cano com -nr.

demolir

for(;;)
    eval(                               # 6. evaluate
        strtr($argn,                    # 4. translate letters to digits, "=" to "-"
            "=".$w=substr(              # 2. remove non-letters
                count_chars($argn,3)    # 1. get characters used in the argument
                ,2),
            "-".$n=str_shuffle(1234567890)  # 3. shuffle digits
        )."||die('$w\n$n');"            # 5. if falsy (`A+B-C==0`), print translation and exit
    )
;
Titus
fonte
0

PHP, 145 bytes

function f($s){for(;$i<10*preg_match("/[A-Z]/",$s,$m);)strpos(_.$s,++$i+47)||f(strtr($s,$m[0],$i-1));$i||eval(strtr($s,"=","-")."||die('$s');");}

função recursiva, imprime a equação resolvida e sai do programa; retorna NULLquando insolúvel.

Experimente online

demolir

function f($s)
{
    for(;
        $i<10                   # loop $i from 0 to 9
        *preg_match("/[A-Z]/",$s,$m)    # find a letter; if not found: $i<10*0 == falsy
        ;
    )
        strpos(_.$s,++$i+47)            # find $i in string
        ||f(strtr($s,$m[0],$i-1));      # if not found, replace letter with $i, recurse
    $i||                        # no letter found ($i is unset):
        eval(                   # evaluate:
            strtr($s,"=","-")       # replace "=" with "-"
            ."||die('$s');"         # if falsy (A+B-C==0), print equation, exit program
        );
    # else implicitly return NULL
}
Titus
fonte