Решить математические задачи

14

Представьте, что у меня есть бесконечное количество домашних заданий (!), Каждому из которых дано целое число.

Math Problem Notation - это нотация для описания подмножеств проблемы с использованием спецификаторов проблемы.

Выражение MPN может состоять из нескольких вещей:

  • Единственное значение. Это представляет собой набор , содержащий номер: 99 -> {99}.
  • Простой ассортимент. Это представляет собой набор , содержащий все цифры от начала до конца диапазона: 10~13 -> {10, 11, 12, 13}. Если левые или правые части отсутствуют, то они считаются -Infinity или бесконечность соответственно: ~10 -> {x|x ≤ 10}; ~ -> ℤ,
  • Выражение MPN, за которым следует «пропуск» и другое выражение MPN. Это представляет собой разность двух множеств: 10~20 skip 12~14 -> {10, 11, 15, 16, 17, 18, 19, 20}.
  • Два выражения MPN, разделенные запятой. Это представляет собой объединение двух множеств: 1,8~9,15~17 -> {1,8,9,15,16,17}.

Оператор «пропустить» связывает более тесно, чем оператор запятой, поэтому 16,110~112 skip 16 -> {16,110,111,112}(16 не входит в набор {110,111,112}, поэтому исключение 16 не имеет значения.)

Вы также можете поместить выражения в скобки для устранения неоднозначности: 1~9 skip (2~8 skip (3~7 skip (4~6 skip 5))) -> {1,3,5,7,9}

Это грамматика:

<expr>  ::= "(" <expr> ")"
         || <number>
         || [<number>] "~" [<number>]
         || <expr> "skip" <expr>
         || <expr> "," <expr>

Ваша задача - написать программу, которая принимает два входа:

  • Выражение MPN
  • Число

и выводит некоторое истинное или ложное значение в зависимости от того, находится ли эта проблема в наборе, описанном выражением MPN.

Характеристики

  • Вы можете предположить, что первый вход является правильно сформированным выражением MPN (то есть соответствует грамматике выше)
  • Числа в выражении MPN всегда являются целыми числами. Они могут быть отрицательными или нулевыми, но никогда не будут иметь дробной части.
  • Это , поэтому выигрывает самое короткое действительное представление (измеряется в байтах).
  • Вы можете использовать разные символы для ~и ,, если хотите.

Тестовые случаи

10~20             14 -> True
10~20             20 -> True
10~20 skip 14~18  17 -> False
~ skip 6          8  -> True
16,17 skip 16     16 -> True
(16,17) skip 16   16 -> False
~10,5~            8  -> True
~10,5~            4  -> True
6 skip 6,~        6  -> True
Esolanging Fruit
источник
Можно ли использовать другие символы для представления операторов? Например, используя # вместо ~
rahnema1
1
@ rahnema1 Для ~и ,, но не для skip.
Esolanging Fruit
3
Почему ~ 10,5 ~ ложно для 4? Потому что это союз-бесконечности к 10 и 5 к бесконечности, первый из которых включает в себя 4
ev3commander
@ ev3commander Отредактировано. Я всегда путаюсь на своих тестах. Могу поспорить, что мои проблемы были бы яснее, если бы я их не добавил: P
Esolanging Fruit
1
@ Challenger5 Я добавил тестовый пример, 6 skip 6,~который, как мне кажется, я правильно интерпретировал. Другие 2 ответа пока не удовлетворяют его (опять же, при условии, что я правильно интерпретирую). Если я неправильно понял, пожалуйста, исправьте это и уточнить, но, насколько я понимаю, оно должно соответствовать чему угодно (это объединение набора, который ничего не соответствует, с набором, который соответствует всем). Это те случаи, о которых я говорил ранее, которые, как мне кажется, могут очень помочь при тестировании наших решений.
Бриантист

Ответы:

3

PowerShell , 189 195 байт

param($m,$q)('$m',"'(\d*)~(\d*)','($q-ge(`$1)-and$q-le(`$2))'","'\(\)',$q","'((?<=,|skip )\d+|\d+(?=,| skip))','($q-eq`$1)'","'skip','-and!'"-join'-replace'|iex|% Sp* ','|%{"($_)"})-join'-or'|iex

объяснение

Я рано понял, что бесконечности делают это несостоятельным для генерации массивов и проверки значений.

Я посмотрел на диапазоны, но в .Net они не имеют необходимого диапазона ( длина диапазона ограничена целым числом со знаком (32 бита), так что даже если бы можно было ограничить диапазон до 32-битного целого числа со знаком) Я бы не смог справиться со всеми диапазонами.

Поэтому я начал думать об этом с точки зрения начала и конца, а в конечном итоге - серии логических тестов и начал создавать набор замен регулярных выражений, чтобы превратить MPN в логическое выражение, понятное PowerShell.

Я в основном разбил это на несколько правил:

  • Сначала с диапазонами было легче работать, потому что они не могли быть выражениями на обоих концах, но открытость была проблемой для реализации в ближайшее время. Посылка 2~8подобна высказыванию n >=2 && n <=8, но когда один из концов отсутствует, пропустите &&и недостающую сторону. Когда оба отсутствуют, я собирался просто заменить его $true. То, что я в конечном итоге сделал, вовсе не проверяло пропущенные стороны, но я удостоверился, что завернул каждое число ().
  • а затем выполните прямую замену, которая заменяет пустые скобки ()входным значением. Таким образом, в случае MPN, подобного ~8входному значению 55, генерируется первая замена (55-ge()-and55-le(8)), затем приходит вторая замена, чтобы сделать это (55-ge55-and55-le(8)), по существу, сводя на нет эту часть диапазона.
  • Затем мне пришлось иметь дело с отдельными номерами в MPN, но нужно было позаботиться о том, чтобы не связываться с теми, которые я вставил ранее. На самом деле это просто числа в ,списках, разделенных запятыми , и отдельные числа до или после skip, так что я использовал, к сожалению, длинные обходные пути.
  • skipв основном то же самое, что -and -notи я делаю прямую замену skipна -and!(используя !как сокращение для -not).
  • Следующей хитрой вещью был низкий порядок приоритета для оставшихся запятых. Первоначально я просто заменил их на, -orно он не учитывал последующие выражения, поэтому 16,17 skip 16генерировал код вроде ($n-eq16)-or($n-eq17) -and! ($n-eq16). Нужно было заключить в скобки, но это казалось неосуществимым с прямой заменой. Поскольку все остальные элементы были заменены, кроме запятых, и они имеют наименьший приоритет, я просто разбил всю сгенерированную строку на оставшиеся запятые, затем заключил каждый элемент в скобки и присоединился к нему -or.

В конечном итоге сгенерированный код просто передается в Invoke-Expression( iex) для выполнения, и затем мы получаем логический результат ( вы можете увидеть код, который сгенерирован вместо результата здесь ).

Это заняло слишком много времени, и я уверен, что есть место, чтобы выжать еще несколько байтов, но я больше не могу смотреть на это :-p

briantist
источник
2

Perl, 99 130 байт

sub f{($_,$n)=@_;s/(-?\d+)?~(-?\d+)?|(-?\d+)/!(defined$3?$n!=$3:length$1&&$1>$n||length$2&&$n>$2)+0/ge;s/skip/&&!/g;s/,/||/g;eval}

Попробуйте это на Ideone.

Ungolfed:

sub f {
    my ($e, $n) = @_;

    $e =~ s/(-?\d+)?~(-?\d+)?|(-?\d+)/ (defined($3) ? $n == $3 : (!length($1) || $n >= $1) && (!length($2) || $n <= $2)) + 0 /ge;
    $e =~ s/skip/ && ! /g;
    $e =~ s/,/ || /g;

    return eval($e);
}
Денис Ибаев
источник
1
Сбой ~ -2 для ввода -2. Также при вставке -? до всех трех \ d *
Кжетил С.
@KjetilS. Исправлено для отрицательных чисел и нуля.
Денис Ибаев
хороший код (полный разбор грамматики часто не требуется, регулярные выражения проще)
Kjetil S.
1

JavaScript (ES6), 221 292 287 309 274 277 278 байт

(-5 байт благодаря Okx)

(j,v,m=1/0,Z=/(skip)([^,]+)/g)=>eval(j[M='replace'](/(-?\d*)~(-?\d*)/g,(e,a,b)=>(a[M]('-','#')||-m)+'<='+(T=v[M]('-','#'))+'&&'+T+'<='+(b[M]('-','#')||m))[M](Z,i=o=>o.match(Z)?i(o[M](Z,'&&!($2)')):o)[M](/,/g,'||')[M](/(^|[^=&#\d])(\d+)([^<\d]|$)/g,'$1$2=='+v+'$3')[M](/#/g,'-'))

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

Тестовый фрагмент

D=(j,v,m=1/0,Z=/(skip)([^,]+)/g)=>eval(j[M='replace'](/(-?\d*)~(-?\d*)/g,(e,a,b)=>(a[M]('-','#')||-m)+'<='+(T=v[M]('-','#'))+'&&'+T+'<='+(b[M]('-','#')||m))[M](Z,i=o=>o.match(Z)?i(o[M](Z,'&&!($2)')):o)[M](/,/g,'||')[M](/(^|[^=&#\d])(\d+)([^<\d]|$)/g,'$1$2=='+v+'$3')[M](/#/g,'-'))
MPN Expression:<input type="text" value="1~9 skip (2~8 skip (3~7 skip (4~6 skip 5)))" id="MPN"></input>
<br>
Integer:<input type="number" id="INT" value=6></input>
<input type="button" value="Submit" onclick="T=r=>document.getElementById(r).value;console.log(D(T('MPN'),T('INT')))"></input>

Р. Кап
источник
@AriaAx Это должно работать сейчас.
Р. Кап
@ R.Kap Вы можете использовать 1/0для Infinity.
Okx
@ R.Kap Я попробовал значение 6с выражением, 6 skip 6,~которое, как я считаю, должно быть, trueно оно возвращается false.
Бриантист
@briantist На самом деле, я считаю, что должно возвращаться, falseкак skipи ко всему, что следует за ним ( 6,~в данном случае), если оно не заключено в круглые скобки. Поэтому, я считаю , что должен вернуться trueна , (6 skip 6),~а не 6 skip 6,~с целым входом 6.
Р. Кап
@briantist Другими словами, ничто не6 skip 6,~ должно совпадать, поскольку оно представляет разницу между множеством и множеством . {6}{6,-Infinity...Infinity}
Р. Кап
0

Röda + bc, 183 байта

f x{{["x=",x,"\n"];replace" ","",",","||","skip\\(","&&!","skip([0-9~]+)","&&!($1)","(?<!~|\\d)(\\d+)(?!~|\\d)","x==$1","(\\d*)~(\\d*)","x>=($1)&&x<=($2)","\\(\\)",x;["\n"]}|exec"bc"}

Это похоже на ответ PowerShell (или я так думаю, я не понимаю PowerShell). Он принимает число в качестве аргумента , и код в качестве значения во входном потоке, как это: main { push("1~9") | f(5) }.

Я думаю, что это работает, по крайней мере, это решает все контрольные примеры. Сценарий ниже может быть использован для проверки этого.

main {
    readLines("/tmp/tests.txt") | split(sep=";") | for code, num, ans do
        push(code, " -> ")
        print(code) | replace" ","",",","||","skip\\(","&&!","skip([0-9~]+)","&&!($1)","(?<!~|\\d)(\\d+)(?!~|\\d)","x==$1","(\\d*)~(\\d*)","x>=($1)&&x<=($2)","\\(\\)",num
        a := push(code) | f(num) | head()
        result := push("OK") if [ (a = "0" and ans = "False") or (a = "1" and ans = "True") ] else push("FAIL")
        print code, " ; ", num, " -> ", a, " ", ans, " (", result, ")\n"
    done
}

И тесты:

10~20;14;True
10~20;20;True
10~20 skip 14~18;17;False
~ skip 6;8;True
16,17 skip 16;16;True
(16,17) skip 16;16;False
~10,5~;8;True
~10,5~;4;True
6 skip 6,~;6;True
fergusq
источник