Представьте, что у меня есть бесконечное количество домашних заданий (!), Каждому из которых дано целое число.
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
источник
~
и,
, но не дляskip
.6 skip 6,~
который, как мне кажется, я правильно интерпретировал. Другие 2 ответа пока не удовлетворяют его (опять же, при условии, что я правильно интерпретирую). Если я неправильно понял, пожалуйста, исправьте это и уточнить, но, насколько я понимаю, оно должно соответствовать чему угодно (это объединение набора, который ничего не соответствует, с набором, который соответствует всем). Это те случаи, о которых я говорил ранее, которые, как мне кажется, могут очень помочь при тестировании наших решений.Ответы:
PowerShell ,
189195 байт-100..100
значениямиобъяснение
Я рано понял, что бесконечности делают это несостоятельным для генерации массивов и проверки значений.
Я посмотрел на диапазоны, но в .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))
, по существу, сводя на нет эту часть диапазона.,
списках, разделенных запятыми , и отдельные числа до или после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
источник
Perl,
99130 байтПопробуйте это на Ideone.
Ungolfed:
источник
JavaScript (ES6),
221292287309274277278 байт(-5 байт благодаря Okx)
Вау. Это было непросто из-за всех крайних случаев, но я думаю, что сделал это. Я просто надеюсь, что нет особых случаев, которые могли бы нарушить используемые регулярные выражения. Я буду играть в гольф больше, когда смогу.
Тестовый фрагмент
источник
1/0
дляInfinity
.6
с выражением,6 skip 6,~
которое, как я считаю, должно быть,true
но оно возвращаетсяfalse
.false
какskip
и ко всему, что следует за ним (6,~
в данном случае), если оно не заключено в круглые скобки. Поэтому, я считаю , что должен вернутьсяtrue
на ,(6 skip 6),~
а не6 skip 6,~
с целым входом6
.6 skip 6,~
должно совпадать, поскольку оно представляет разницу между множеством и множеством .{6}
{6,-Infinity...Infinity}
Röda + bc, 183 байта
Это похоже на ответ PowerShell (или я так думаю, я не понимаю PowerShell). Он принимает число в качестве аргумента , и код в качестве значения во входном потоке, как это:
main { push("1~9") | f(5) }
.Я думаю, что это работает, по крайней мере, это решает все контрольные примеры. Сценарий ниже может быть использован для проверки этого.
И тесты:
источник