Эта задача - поднять настроение нашему моду Алексу А. , который обычно ошибается .
Предположим, у вас есть друг по имени Алекс, которому нужна помощь по базовой логике и математике, в частности, по математической эквивалентности .
Он дает вам список уравнений вида, [variable] = [variable]
где a [variable]
- это всегда одна заглавная буква от A до Z (ни строчная буква, ни число, ни что-либо еще). В списке есть одно уравнение на строку, за исключением одной строки, которая говорит только therefore
.
Все уравнения выше therefore
являются предпосылками , фактами, которые считаются правдой. Все уравнения ниже therefore
являются непроверенными утверждениями, фактами, которые Алекс пытается вывести из помещения, и они могут быть или не быть правдой.
Например, в этом списке уравнений единственное заключительное утверждение A = C
оказывается верным:
A = B
B = C
therefore
A = C
Это ваша работа, чтобы сказать Алексу, если все его предложения логически вытекают из данной посылки. То есть вам нужно сказать Алексу, ошибся он или нет в своих выводах.
Напишите программу / функцию, которая принимает строку списка уравнений, как описано, и печатает / возвращает
Alex is right
если все выводы логически вытекают из помещения, а в противном случае выводятся
Alex is wrong
если какой-либо вывод логически не вытекает из помещения.
Самый короткий код в байтах побеждает.
Обязательно следите за этими случаями:
Переменная всегда равна себе. например
B = A therefore A = A X = X
результаты в
Alex is right
.Переменные с неизвестными отношениями нельзя считать равными. например
P = Q therefore E = R
результаты в
Alex is wrong
.Когда после этого нет уравнений,
therefore
то выводы оказываются бессмысленными . напримерD = C therefore
а также
therefore
оба результата в
Alex is right
.Когда нет уравнений до этого,
therefore
то можно сделать вывод только о равенстве. напримерtherefore R = R
результаты
Alex is right
, ноtherefore R = W
результаты в
Alex is wrong
.
Больше примеров
Алекс не в том случае: (разделены пустыми строками)
A = B
C = D
therefore
A = C
A = L
E = X
A = I
S = W
R = O
N = G
therefore
G = N
L = I
R = O
S = A
X = X
X = E
D = K
D = Q
L = P
O = L
M = O
therefore
K = L
A = B
therefore
B = C
Z = A
S = S
therefore
A = Z
A = A
S = A
A = S
Z = A
Z = A
K = L
K = X
therefore
X = P
L = X
L = P
therefore
A = B
B = C
A = C
therefore
A = A
B = B
C = C
D = D
E = E
F = F
G = G
H = H
I = I
J = J
K = K
T = I
L = L
M = M
N = N
O = O
P = P
Q = Q
R = R
S = S
T = T
U = U
V = V
W = W
X = X
Y = Y
Z = Z
A = B
B = C
C = D
D = E
E = F
F = G
G = H
H = I
I = J
J = K
K = L
L = M
M = N
N = O
O = P
P = O
Q = R
R = S
S = T
T = U
U = V
V = W
W = X
X = Y
Y = Z
therefore
A = Z
therefore
C = D
T = Y
A = Z
P = Q
therefore
E = R
therefore
R = W
Алекс прав:
H = J
therefore
J = H
K = L
K = X
therefore
L = X
C = B
B = A
therefore
A = B
K = L
K = X
K = P
therefore
L = X
L = P
X = P
A = Y
Y = Q
Q = O
therefore
O = Y
O = A
C = C
therefore
C = C
A = B
B = A
therefore
A = B
B = A
A = B
B = C
C = D
therefore
A = A
A = B
A = C
A = D
B = A
B = B
B = C
B = D
C = A
C = B
C = C
C = D
D = A
D = B
D = C
D = D
therefore
A = A
B = B
C = C
D = D
E = E
F = F
G = G
H = H
I = I
J = J
K = K
L = L
M = M
N = N
O = O
P = P
Q = Q
R = R
S = S
T = T
U = U
V = V
W = W
X = X
Y = Y
Z = Z
D = I
F = H
J = M
therefore
M = J
D = I
H = F
A = B
B = C
C = D
D = E
E = F
F = G
G = H
H = I
I = J
J = K
K = L
L = M
M = N
N = O
O = P
P = Q
Q = R
R = S
S = T
T = U
U = V
V = W
W = X
X = Y
Y = Z
therefore
Z = A
F = R
G = I
W = L
A = B
B = C
therefore
A = C
B = A
therefore
A = A
X = X
P = P
C = G
M = C
therefore
D = C
therefore
therefore
therefore
R = R
Alex is wrong
Проверяет все тесты.therefore\nTABS < SPACES
->Alex is right
Ответы:
CJam, 49
Вдохновлен гистократским решением Ruby. Попробуйте онлайн
3 байта уничтожены благодаря jimmy23013 :)
Объяснение:
Для каждой предпосылки программа заменяет первую переменную второй переменной в остальной части текста. Затем он проверяет, есть ли какой-либо вывод с разными переменными.
Старая версия, 85
Это использует алгоритм поиска объединения. Попробуйте онлайн
источник
"Alex is "qN%S{f{)er}(_el-}h;{)#},"wrong""right"?
,Alex is * wrong * right * ?
Рубин,
8076 + 2 = 78С флагами командной строки
p0
запуститеОбъяснение:
Это использует чистые манипуляции со строками.
p0
читает полный ввод как одну строку в переменную$_
. Затем мы неоднократно сопоставляем эту строку с регулярным выражением/(.) = (?!\1)(.)/
, которое находит все строки в форме «X = Y», где X и Y не являются одной и той же буквой, и присваивает X значение $ 1, а Y - значение $ 2. Когда такое совпадение найдено,gsub$1,$2
заменяет все экземпляры X на Y в строке. Мы также проверяем, произошло ли это совпадение до или после «следовательно» сЕсли это произошло после, это необоснованное требование, и Алекс не прав. Мы отслеживаем, имели ли место такие случаи с использованием
p=
. Использованиеp
в качестве переменной отслеживания предотвращает прерывание работы, если цикл никогда не срабатывает ни разу, посколькуp
вернет nil, если он никогда не был назначен.На данный момент решение CJam длиннее. Гордый, если без сомнения, мимолетный момент.
Редактировать: Да, быстро свергнут. Кроме того, чтобы завершить объяснение, с
p
флагом$_
выводится окончательное значение в конце выполнения, поэтому последняя строка является выходной.источник
String#format
получением вызова и присваивания gsub в одном выражении - довольно интересная идея, +1!CJam,
8375686764 байтаСпасибо Деннису за сохранение 1 байта.
Тестирование. Тестовые случаи слишком длинные для постоянной ссылки, поэтому просто скопируйте их из вопроса. Обратите внимание, что это довольно медленно - это займет минуту или две в онлайн-переводчике. Вы можете сделать это гораздо быстрее за счет изменения
5*
в2*
в этом случае он будет закончить почти мгновенно и решить все , но один тест.объяснение
(Немного устарела.)
Идея состоит в том, чтобы сделать своего рода «заливку» возможных равенств, а затем удалить все равенства, которые мы получили из списка выводов. Можно показать, что нам нужно не более 5 шагов заполнения паводка, потому что они будут покрывать расстояние (в начальном графике неравенств), но максимальное расстояние составляет 25.
25 = 32
источник
R
183192 байтаЯ изменил свой ответ, чтобы устранить ограничение, указанное пользователем user2357112. По-прежнему крайне мала вероятность вызова Алекса, когда он на самом деле прав (что само по себе, похоже, случается не очень часто, если я понимаю контекст задачи :-). Надеюсь, он не будет возражать.
Мне нужно немного де-гольф это:
Например, если вход
сначала он оценит
setup
:тогда
premises
будет запущен 1000 раз каждый в случайном порядке. Это делается для того, чтобы убедиться («почти наверняка»), что все равенства распространяются. Наконец, он оценит
propositions
:источник
A = B, B = C, C = A
, то значения просто вращаются вечно. 26 раундов оценки недостаточно.Haskell, 208 байт
Я перекладываю работу на
Data.Equivalence.Persistent
модуль, который предоставляет функции для управления классами эквивалентности. Осталось только проанализировать функции ввода и вызова, которые иногда имеют слишком длинные имена для правильной игры в гольф.Пример использования:
источник
Математика, 182
Работает на ввод строки, в соответствии с задачей.
источник
f
как чистую функцию, заменивSimplify[#2,#1]
на#2~Simplify~#
и заменивStringSplit[s,"\n"]
на#~StringSplit~"<actual newline>"
.q=StringSplit;
и затем s / StringSplit / q / для еще 6 байтов или около того сохранены. Но, в конце концов, это не очень хорошая задача для Mathematica, я боюсь, хотя логический персонаж казался идеально подходящим.a___
и,b___
вероятно, может быть изменено наa__
иb__
, иs=Symbol;
.a__
иb__
не будет работать, если помещения, предложения или оба пустые, хотяСетчатка, 90 байт
Для запуска разместите следующие 12 строк кода в 12 отдельных файлах (+11 байт для каждого файла после первого).
<empty>
обозначает пустой файл;\n
обозначает буквальный перевод строки. В качестве альтернативы, оставьте\n
s как есть, поместите все строки в один файл и используйте-s
опцию. Убедитесь, что все файлы используют буквальные символы новой строки, а не Windows\r\n
, и запишите пробел в конце последней строки.Как это устроено
Первая замена соответствует первой предпосылке во входных данных всякий раз, когда lhs предпосылки появляется позже в файле. Это заменяет это более позднее вхождение на rhs предпосылки. В
+
Модификатор гарантирует , что замена повторяется до тех пор, пока не соответствует больше. Таким образом, если первая предпосылка естьA = B
, все последующиеA
s в файле преобразуются вB
s.Вторая замена удаляет первую предпосылку из ввода, так как мы закончили с этим сейчас. Затем
)
модификатор возвращается к первой замене и повторяется до тех пор, пока не произойдет никаких изменений за весь проход цикла. Это происходит, когда все помещения были заменены и удалены, а ввод начинается сtherefore
.Третья замена соответствует первой строке ввода (которая есть
therefore
) или чему-либо в формеA = A
и удаляет ее. Если все предложения поддерживаются посылками, все они будут соответствовать этой форме, поэтому то, что остается, должно состоять исключительно из новых строк. Четвертая замена меняет это наright
. В противном случае пятая замена заменяет все оставшееся (которое не содержит,r
посколькуtherefore
было удалено) вwrong
. Наконец, последняя замена добавляетAlex is
в начале.источник
Python 2, 264 байта
Там уже замечательный ответ Python 3 от mbomb007 . Этот ответ вопиюще ворует из этого (в частности, уловка «Алекс неправда»).
И этот ответ также значительно длиннее, чем этот ...
Ну, в любом случае, идея в этом ответе состоит в том, чтобы поддерживать словарь пар ключ-значение, где ключи - это 26 заглавных букв, а соответствующее значение каждого ключа - это набор букв, эквивалентных ключу. (Если бы все 26 букв были эквивалентны, то каждый ключ имел бы набор из 26 букв для своего соответствующего значения.)
(Чтобы сохранить байты, этот ответ смешивает пробелы и табуляции , что допустимо в Python 2.)
Этот код действительно довольно эффективен, потому что словарь ограничен максимально возможным размером (26 на 26, как описано выше), который не зависит от количества строк ввода.
Теперь, когда я занимался этим решением, я понял, что могу сохранить четыре байта , используя строки вместо наборов для значений словаря, заменив
с участием
Конечно, тогда вы также должны заменить (ПРИМЕЧАНИЕ: НЕ ДЕЛАЙТЕ ЭТОГО) три экземпляра операции set union
|
на конкатенацию строк+
, но это не меняет длину кода. В результате все должно работать точно так же, за исключением того, что оно не будет устранять дубликаты, как вы делаете с наборами (оно будет просто добавлять в конец строки). Звучит хорошо - немного менее эффективно, конечно, но 260 байтов вместо 264.Что ж, получается, что 260-байтовая версия настолько неэффективна, что это вызвало,
MemoryError
когда я тестировал ее сЭто было удивительно для меня. Давайте исследуем 260-байтовую версию «конкатенации строк»!
Конечно, это началось бы с пар ключ-значение
A:A
иB:B
(плюс 24 других, которые не имеют значения). Мы напишем,d[A]
чтобы означать значение словаря, соответствующее ключуA
, поэтому в начале мы бы получилиd[A] = A
. Теперь, учитывая предпосылкуA = B
, все началось бы с объединения значенийd[A]=A
иd[B]=B
полученияy = AB
. Тогда он будет дважды зацикливаться на этой строке:for v in AB: for w in AB:
...Итак, первый раз через цикл мы имеем
v=A
иw=A
. Применяемd[v] += d[w]
иd[w] += d[v]
приводим следующую последовательность словарей:Далее с
v=A
иw=B
:Далее
v=B, w=A
:И
v=B, w=B
:Приведенная выше последовательность шагов будет реализовывать единственную предпосылку
A = B
с выводом, которыйA
равен каждой букве в строкеAAAABBAAAABAAAAB
, аB
равен каждой букве вBAAAABAAAABBAAAABAAAABBAAAABAAAABBAAAABAAAAB
.Теперь предположим, что следующая предпосылка
A = B
снова . Вы сначала рассчитываетеy = d[A] + d[B] = AAAABBAAAABAAAABBAAAABAAAABBAAAABAAAABBAAAABAAAABBAAAABAAAAB
.Затем вы дважды зацикливаетесь на этой строке:
for v in y: for w in y:
...Да уж. Возможно, это не будет очень эффективной реализацией.
источник
ES6, 128 байт
Свободно основанный на версии Ruby.
Ищет любое несобственное равенство перед «следовательно» и рекурсивно заменяет переменную по всей строке каждый раз (это сохраняет байты в цикле while).
источник
C 240 байт
Это работает путем объединения значений в заданные деревья, поэтому любые эквивалентные значения приводят к одному и тому же установленному корню. Ungolfed, с неявными типами, сделанными явными.
180 байт
Эта более короткая версия работает для всех случаев из OP, но для некоторых других входных данных неправильно утверждает, что Алекс неправ. Он использует аналогичный подход, но для каждой предпосылки просто устанавливает вторую запись в текущее значение первой записи. При сравнении он смотрит только на точные значения вместо поиска по дереву.
Пример ввода, для которого это не удается:
источник
05AB1E , 32 байта
Вдохновленный ответом Cadam @aditsu .
Попробуйте онлайн или проверьте все контрольные примеры .
Объяснение:
Посмотрите эту подсказку 05AB1E (раздел Как пользоваться словарем? ), Чтобы понять, почему
…±º€ˆ
есть"alex is "
и„–Ñƒ©
есть"wrong right"
.источник
bash + awk + SWI-Prolog , 167 байт
Попробуйте онлайн!
Первоначально это был просто ответ на вопрос Пролога, но инструменты, которые я смог найти для преобразования входного формата во что-то пригодное для использования, были достаточно ограничены, и я решил сделать эту часть в bash, хотя у меня почти не было опыта делать что-то в bash, и никогда не трогал awk. В итоге я потратил на это достаточно часов, чтобы захотеть опубликовать его, даже после того, как он превратился в этот 167-байт, едва играющий в гольф на всех монстрах.
По сути, то, что делает awk-программа, это взять ввод из stdin, стереть строку
therefore
, заменить каждыйA = B
после нее на?=(A,B)
и добавитьwrite(\"Alex is right\");write(\"Alex is wrong\"). halt.
. Затемpaste -sd ,
заменяет каждую новую строку, кроме последней, запятой, превращая ее в действительные два запроса к оболочке SWI-Prolog, которые затем выполняются с усеченным выводимым результатом до одной строкиhead -n1
, которая требует<(...)
вместо конвейера по причинам, выходящим за рамки Мое понимание. Все это, просто чтобы использовать встроенный !источник