Напишите решатель уравнений в словах [дубликаты]

17

Вступление

Рассмотрим следующий пример:

  CODE
+ GOLF
——————
 GREAT

Это уравнение, в котором каждая буква представляет собой десятичную цифру, а слова представляют собой натуральные числа (похожие буквы представляют одинаковые цифры, а разные буквы представляют разные цифры). Задача состоит в том, чтобы сопоставить каждую букву с ее цифровым значением, чтобы уравнение было правильным. Одно решение для уравнения выше:

  9265
+ 1278
——————
 10543

Твое задание

Ваша задача - написать программу или функцию, которая может решать такие уравнения, как показано выше.

вход

Входные данные представляют собой строку в следующем формате:

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

Пример:

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

Пробелы опущены, и будут использоваться только буквы между заглавными буквами A и Z (без специальных или строчных букв).

Эта строка может быть прочитана из стандартного ввода, из файла или как параметр функции.

Выход

У вас есть следующие две опции для выходного формата:

  1. исходное уравнение с заменой цифр
  2. список букв и их значений

Если существует несколько решений, любое (но только одно) из них должно быть возвращено. Если решений нет, программа должна вернуть пустую строку или ноль. Вывод может быть возвращен в виде строки, может быть записан в стандартный вывод или файл.

Пример:

  1. 9265+1278=10543
  2. A=1 B=2 C=3 (вы можете использовать любой разделитель)

правила

  1. Чтобы упростить задачу, числа принимаются начинаться с 0, но вы можете обрабатывать числа, начинающиеся с 0, как недействительные решения, решать вам
  2. Одинаковые буквы обозначают одинаковые цифры, а разные буквы обозначают разные цифры.
  3. Вы можете использовать любой язык и стандартную библиотеку выбранного языка (без внешних библиотек)
  4. Вы не можете подключиться к каким-либо ресурсам в Интернете (почему бы вам все равно?)
  5. Это кодовое задание по гольфу, выигрывает самый короткий код. Последовательные пробельные символы считаются одним символом. (Так что любая программа, написанная в пробеле, автоматически побеждает)

У меня есть несколько хакерских решений с использованием 179 символов. Если что-то не понятно, пожалуйста, спросите меня в комментариях.

Дэвид Франк
источник
Я думаю, что оптимальный ответ "все равно 0". Вы можете специально запретить это.
подземный
1
Что вы подразумеваете под всем 0? Разные буквы должны обозначать разные цифры.
Дэвид Франк
Пропустил это, неважно :)
подземный
If there are no solutions, the program should return an empty string or null.Бесконечные циклы по-прежнему ничего не выводят ... можно?
Тит
1
Все выигрышные ответы на этот вызов фактически сводятся к использованию правила подсчета пробелов, поэтому закрытое голосование является дубликатом.
pppery

Ответы:

11

Python - 48 символов

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

Злоупотребление правилом пробелов.

Сначала я преобразовал каждый символ в ответе CaesiumLifeJacket в его значение ASCII (я мог бы написать свой собственный, но я ленивый, и это не повлияло бы на окончательный счет в любом случае). Длинная строка в моем решении - это один пробел для каждого из этих значений ASCII и вкладок, разделяющих их. Разделить на вкладки, найти длину, преобразовать обратно в символы и выполнить.

SE преобразует вкладки в 4 пробела каждая, поэтому копирование не будет работать. Вы просто должны верить мне :)

undergroundmonorail
источник
1
Можете ли вы предоставить ссылку на ideone или шестнадцатеричный дамп вашего кода?
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳
1
Кроме того: exec является ключевым словом, вы можете сохранить 2 символа, удалив первую и последнюю скобки
ɐɔıʇǝɥʇuʎs
4

Ruby 2.0, 122 символа

Грубая сила перетасовки + Eval! Это еще не соответствует критерию возврата пустой / пустой строки, когда нет решения; это просто бесконечно. Если он не может найти результат после ~ 300 миллионов итераций, он вернет ноль. Достаточно близко?

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

Он находит все уникальные буквы на входе, затем несколько раз перемешивает цифры 0-9 и пытается сопоставить их с буквами, пока не найдет работающую конфигурацию.

Код представлен в виде вызываемой функции, fкоторая возвращает строку с замещенными числами, как в варианте вывода 1 выше. Пример использования:

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

Время выполнения CODE+GOLF=GREATпримера на моей машине варьируется от мгновенного до примерно 6 секунд - зависит от того, насколько вам повезло с шаффлами!

Я особенно недоволен gsub(/\b0/,'')битом для удаления начальных нулей, но это было единственное, что я мог помешать evalинтерпретировать числа как восьмеричные целые.

( БОНУС : Поскольку он использует eval, он работает для произвольных выражений Ruby, а не только для сложения!)

Пол Престиж
источник
Когда я прочитал это, у меня возникла та же идея, но я получил ~ 170 символов кода, так что хорошо сделано. 0..9 - это десять цифр, поэтому не должно ли быть ограничение 10 ** 10? Вы можете использовать перестановку Array # для циклического перебора всех возможных отображений, но это может сделать код длиннее.
Blutorange
@blutorange Я просто выбрал 9 ** 9, потому что это было большое число, которое вы могли написать с несколькими символами. Это должно быть более чем достаточно для любых разумных тестовых случаев, я думаю! Я не пробовал версию, основанную на permutation, но, как вы говорите, меня в первую очередь интересовала длина кода.
Пол Престиж
4

LiveScript (179 символов)

Он имеет детерминированное и относительно быстрое время работы и работает также с другими операторами (+, -, *).

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")
Дэвид Франк
источник
2

Python, 256 213 символов

Ужасное время работы, постараюсь улучшить еще:

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
источник
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)

Случайный перебор.
Может занять некоторое время (мой лучший выстрел CODE+GOLF=GREAT- 3 секунды, мой худший - 3 минуты).
Попробуйте это с простым выражением, какA+B=C

Майкл М.
источник
2

Хаскелл, 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

Грубая сила. Пробует каждое возможное совпадение, пока не найдет его или не попробует все. Я растянул правила вывода: печатает что-то наподобие [[('C','3'),('O','8'),('D','6'),('E','7'),('G','0'),('L','5'),('F','2'),('R','4'),('A','1'),('T','9')]]решения, а если ничего не существует, печатает []. Дайте мне знать, если мне нужно изменить это.

YawarRaza7349
источник
Я думаю, этот вывод является приемлемым.
Дэвид Франк
2

CJam - 17

"





























































































































































































































































































































    ""  
"f#3b127b:c~

Всего 975 символов, но 960 из них являются пробелами в 2 последовательностях, поэтому они считаются 2 символами, и вместе с другими 15, мы получаем 17.
975 может показаться большим, но обратите внимание, что решение Python подземного монорельса имеет 18862 символа, они всего на одной строчке :)

Вы можете запустить его на http://cjam.aditsu.net/ для коротких слов, но вам, вероятно, следует использовать интерпретатор java для более длинных. С Java на моем ноутбуке, SEND+MORE=MONEYработает в течение 30-40 секунд и CODE+GOLF=GREATпочти 3 минуты. Он не принимает числа, начинающиеся с 0 (потому что это не круто).

Вот программа, которая генерирует программу выше (также помогает, если StackExchange не отображает пробелы правильно):

"{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~"

Первые 11 строк содержат исходную программу (на самом деле не в гольфе) в строке, а последняя строка выполняет преобразование и добавляет часть декодирования.

aditsu
источник
0

Powershell, 137 байт

порт 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}}

Неуправляемый тестовый скрипт:

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

Выход:

11+22=33
2846+0851=03697
Mazzy
источник
0

PHP, 118 113 байт

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

печатает цифры ниже букв и выходит из программы; циклы бесконечно, если они неразрешимы. Беги как труба с -nr.

сломать

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
источник
0

PHP, 145 байт

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');");}

рекурсивная функция, выводит решенное уравнение и выходит из программы; возвращается, NULLкогда неразрешим.

Попробуйте онлайн

сломать

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
источник