вступление
В стене 3 гвоздя. У вас есть кусок строки, который прикреплен к рамке с обоих концов. Чтобы повесить картину, вы запутали гвозди в струну. Но прежде чем позволить изображению исчезнуть: можете ли вы предсказать, упадет ли изображение, просто взглянув на то, как веревка обвивается вокруг ногтей?
В первом примере картинка не упадет. Во втором примере картина будет падать.
Вызов
Учитывая путь струны вокруг N
ногтей, определите, будет ли картина падать или нет. Верните истинное значение, если картина будет падать, и ложное значение в противном случае.
Детали
- Вы можете предположить, что ногти и рисунок расположены в правильном положении
N+1
, с рисунком внизу. - Можно предположить, что в веревке нет узлов, т. Е. Веревку можно непрерывно разворачивать с одного из двух концов.
- Каждый гвоздь нумеруется по часовой стрелке буквой алфавита. Вы можете предположить, что есть максимум 26 гвоздей (AZ).
- Оборачивание вокруг ногтя по часовой стрелке обозначается буквой в нижнем регистре, а завершение против часовой стрелки - буквой в верхнем регистре.
Первый пример сверху будет закодирован как BcA
, второй пример закодирован как CAbBac
.
Для склонного читателя: эта проблема эквивалентна определению, является ли элемент свободной группы - порожденный набором гвоздей - идентичностью или нет. Это означает, что достаточно многократно отменять подстроки, такие как aA
или Aa
до тех пор, пока вы не достигнете фиксированной точки. Если фиксированная точка - пустая строка, это нейтральный элемент, в противном случае это не так.
Примеры
Picture will fall:
Aa
CAbBac
aBbA
DAacAaCdCaAcBCBbcaAb
ARrQqRrUuVHhvTtYyDdYyEKRrkeUWwua
AKkQqEeVvBESWwseYQqyXBbxVvPpWwTtKkVHLlWwNBbAanYYyyhWwEJZUuNnzjYyBLQqQqlEGgebeEPLlTtZzpUuevZzSsbXSGgsUuLlHhUQquPpHUuFfhTZzIitGgFAaBRrBbbYXxOoDZTDdtzVvXxUudHhOVvoUuXKkxyBEeLlbFfKkHhfVAaQqHAaJjODdoVvhSsZzMZzmPpXNBbnxBbUuSSsUuDRrdNnUusJDIiUuIidCEGgeMmcLlDPOopdTEeQqCAETtNnYyeGUuPEFfSsWwHheAaBbpgCcOHUuhAaCcoEFBbfeaFHhfcCFFffNncGFfgtjMVUuKAakvKkXxLlTMmtmOFfoUuXSsYZzLXxlyxUuRPZzTtprSsWwRrPLlpGgMmKRrDHhdRCcUurYNnKCckykXJjxWwUSsJjKkLlKkuBbBbOoWwWwIiUuPDdBbCcWHBbCFfcDdYBbLlyVvSsWGgEewCchDdYywAaJjEepPpPpQXxZzFfLGXxglNnZzYDdyqCcKWXxwXxQqXTtxkFfBSSAasTFftZzsXGgxSsLlLlbZzAaCCccXVvYyxTIiOoBbFftCVQqDdBbGgAavQqKkDPpKTCctRrkdcvAaQWOowLOolqVMmvZAaHCBbcPphIiRKkrLlzFMOomDIiXJjIixMmdNnMHhmfNTtIiKkSDdTtsVvHhnAaNSVvTUutNnXxsGIiXxPpPHhUupgNnAaAAOoaaIiHJjhVvLlnYyXxQqSsTtKJjkBbNnVvEYCcFfMHGghBbmNnEeJTtjJjWYywyeNWwDIiZYyzOodnMQqmVvCcQqxVvGNnEeNBbngVvUGgYyBbDdVvIiAAaauPpQKDdEekNnVLlvHhGSDIidPZzpsPCcpgQqKkQqNOonLlIiLlJjqPAaPXxTtppYyCPpHhCIicARBbracXxWwXEVUuUuGgZHhzBSsbvGgFfeVvxLlNKknWwBLlIibWOowNnRSsrSEeKAakOosLZzZRrHhzTtTFfUuNnOKkotXxTtla
Picture will not fall:
A
BcA
ABCD
aBaA
bAaBcbBCBcAaCdCaAcaCAD
ARrQqRrUatuVHhvTYyDdYyEKRrkeUAua
AEEeQqNneHhLlAIiGgaECXxcJjZzeJFfVWwDdKkvYWwyTJjtCXxANIinaXWwxcTWwtUuWwMmTBbVWIiFLlWwZzfwPLlEepvWZzwKkEYEeWXxwySXTtEexRIiNBbnWAaTtQqNnBMSsWwOombwWwPVPpGPpgYyvDdpBbrQqHhUusKRrDAVvadLlWwOZzokGJCXSSssXxxJPpGIigZzjJjLlOoNRrnPpcMZzmjgJjNDEeQqWKkNTtnSswIidCcnYBGgbyJSsjPpIiMmMmMmSNnWVvwZzIQqLXHhxTPptlisOoeTtTtYMmVvPpyKNnMFfmkXxSVvsCGJjXxgXYJPpjWwQIiXxqyDdxFfDdAaRNnJjrctHBbZzhEQqMmeCcRBbrGgAaAaJNnRrYyWwSDdVvsJOojQGgWWwIBbiwRrqJjjWwOoFPMmDdRrQOoqNnRrDPJjpMmdPpGFfVvWUuwgpWCcNnPpwfUXCcZzJjUSsuXxxUuuRGgHhrSQqJjOosMMTtmHhmKkXxDdLlWwjSUuAaMmKYyksZzVvPZzVEeVvvHhZZOozBbzMmZCczYyGgISsiQqpXxMmXxEMmeRrAGgaGgMOGgomZFfDdzSSssBGPpgbTtBbOoRWWwGgLJjlEeGgLDdRrUulNnZzJjJjUKkuXxFfwATtaZzLVvlWwSsMmrBAaELleGBLFflbgHhbIFfiBbPpTWZzwKkKLASsaTJYyjtBbBbWwIiZCcWwzIiZLlUTtuBbYyBbIizTJjtLTtDOOoBbodBbllSsUGgLlAKkauYykUuUNnPpuDFfAaLNVvnVvlHhdMmBAaBbIiVRrGWOoPpwgWXwKkvJjOoTtYCUucVGgYyLlVvFfvRrMmySsDdbtICZzcNnINSOosDQAaXoxRGgKkrqdZznDdXxZzMGgmiJjNnACcMQqmaNnWZzUOuwTVvAJjSsaRrGgSsTtOMmRroVvRrtAVGgvMmaINniDGCcOogRrWwMVvYFfyTtmTtVvOoOIiodRrGgAxaSsGgiJja
Ответы:
Сетчатка , 21 байт
Попробуйте онлайн!
Как и в случае решения flawr, он просто многократно удаляет соседние пары верхнего и нижнего регистров, а затем проверяет, является ли результат пустым или нет.
Что касается того, как каждый соответствует заглавной / строчной пары:
источник
MATLAB, 76 байт,
октава,827977 байтЭто может быть первый раз, когда я увидел, что MATLAB на самом деле короче, чем Octave (на целый байт)!
Новый ответ в MATLAB:
Ответ в октаве:
Сохранено
трипять байтов благодаря flawr.~nnz(c)
корочеisempty(c)
, и'Aa'
на два байта короче, чем[0,32]
.Попробуйте Octave-версию онлайн!
Объяснение:
c=input('')
просит пользователя для ввода. Мы определяемk='Aa'
как массив символов.while k++<1e5
: В то время как цикл , в котором оба элемента вk
увеличиваются каждой итерации,Aa
,Bb
,Cc
и так далее. Цикл будет продолжаться до тех пор, пока не появится самый большой элемент1e5
, который должен быть достаточно высоким для большинства строк. Это может быть увеличено до9e9
без увеличения количества байтов.Мы рассмотрим
strrep
функцию поэтапно, начиная с середины.Используя,
mod(k,64)
мы получим следующее, когда достигнем конца алфавита (если мы преобразуемk
обратно в символы):Как вы можете видеть, между ними будет несколько символов, но затем они будут повторяться и начинаться с алфавита, а теперь сначала с букв нижнего регистра. Это очень короткий способ проверить и то,
Aa
и другоеaA
.['',65+mod(k,64)]
объединяет числовые значения изmod
-call с пустой строкой, преобразуя числа в символы.strrep
используется для удаления элементов из строкиc
и ее возврата. Он будет искать все вхожденияk
в строке и заменять ее пустой строкой.После
1e5
итераций у нас будет либо пустая строка, либо непустая строка. Мы проверяем, есть ли какие-либо элементы вc
использованииnnz(c)
. Мы возвращаемсяnot(nnz(c))
, таким образом,1
если он пуст, и0
если в нем остались символыc
источник
Минколанг 0,15 , 30 байт
Попробуй это здесь!
объяснение
Тороидальная природа Минколанга используется здесь, чтобы устранить необходимость во внешней петле. Общая идея здесь состоит в том, чтобы проверить, находятся ли два верхних элемента стека на расстоянии 32 единицы (это означает, что они состоят из прописных / строчных букв), и, если они есть, вытолкнуть оба из них. Так как это делается, так сказать, в реальном времени, вложение пар обрабатывается правильно.
источник
Haskell, 62 байта
Попробуйте онлайн
Кредит flawr для
abs
и Laikoni дляfromEnum
карты .Вспомогательная функция
%
берет уже упрощенную строкуl
и добавляет символa
перед упрощением результата. Еслиl
начинается с обратного символаa
, они отменяются. В противном случаеa
просто добавляется. Обратите внимание, что на данном этапе дальнейшее упрощение не требуется.Основная функция
f
добавляет и упрощает каждый символ по очереди черезfoldr
. Затем он проверяет, является ли результат пустым.Чтобы проверить, являются ли два символа противоположными, и поэтому следует их отменить, посмотрите, отличаются ли их значения ASCII на 32. Каждый элемент обрабатывается
fromEnum
перед передачей в%
.источник
05AB1E , 17 байт
Попробуйте онлайн!
объяснение
источник
Haskell ,
98 97 8581 байтЭто просто наивная реализация, которая неоднократно пытается отменить прилагательные буквы до тех пор, пока не останется никаких изменений, а затем определяет результат из этого.
Спасибо @nimi за -12 байтов и @xnor за еще -4 байта!
Попробуйте онлайн! или проверьте все примеры!
источник
f=null.until(\a->r a==a)r.map fromEnum
должен сохранить два байта.(\a->r a==a)
может быть((==)=<<r)
.=r l
кl
, идея состоит в том, что достаточно сделать только одну замену за цикл.=<<
, похоже, волшебство XD=<<
как,>>=
но с аргументами поменялись местами. Выражение часто появляется в форме,((==)=<<r)
чтобы означать «инвариантен подr
».Mathematica, 102 байта
Безымянная функция, принимающая буквенную строку в качестве ввода и возвращающая
True
илиFalse
.Сердцем реализации является создание функции, которая удаляет любую строку отмены, например
"Pp"
или"gG"
, из строки. Выражение{Join[a=Alphabet[],A=ToUpperCase@a],A~Join~a}
создает упорядоченную пару списков символов, причем первый список является{"a","b",...,"Z"}
вторым{"A","B",...,"z"}
. Затем#<>#2&~MapThread~
создает список, в котором соответствующие элементы этих двух списков были объединены, то есть{"aA","bB",...,"Zz"}
. Тогда забавное выражение""|##&@@
(посредством магии последовательности аргументов##
) создает список альтернатив"" | "aA" | "bB" | ... | "Zz"
; наконец,StringDelete[...]
это функция, которая удаляет любое вхождение любой из этих альтернатив из строки.Теперь достаточно многократно применять эту функцию к входной строке до тех пор, пока результат не изменится, что и выполняется
~FixedPoint~#
, и затем проверить, является ли результат пустой строкой""==
.источник
JavaScript (ES6), 73 байта
В отличие от .NET, JavaScript не имеет возможности отключить чувствительность к регистру в середине совпадения, поэтому вместо этого мы должны найти все подстроки повторяющихся букв без учета регистра, а затем удалить любую несоответствующую пару соседних символов, что к этому моменту должно быть верхняя / строчная пара.
источник
Perl, 28 байт
Объяснение:
Perl позволяет включать динамически генерируемое регулярное выражение в стандартное регулярное выражение.
.
Матчи ничего.Это
(??{
начало сгенерированного регулярного выражения.До
$&
сих пор переменная будет содержать всю совпадающую строку, которая в данном случае будет.
соответствовать.^
Оператор делает либо числовой XOR или строку XOR, в зависимости от значений операндов. В этом случае это будет строка xor.Это
' '
просто строка, содержащая пробел, который обычно имеет значение ascii (или unicode!) 32. Когда пробел записывается с помощью символа в диапазоне az или AZ, он изменяется с верхнего на нижний регистр или тиски наоборот.Это
})
конец сгенерированного регулярного выражения.1 while s/whatever//
будет многократно искать шаблон и заменять его пустой строкой.$_
переменная по умолчанию. Эта переменная - это то, что perl делает весело и увлекательно, когда вы не указываете другую переменную. Здесь я использую его для возврата истинного или ложного значения, поскольку строка нулевой длины равна false, а строка ненулевой длины, которая не равна,"0"
- true. Я также предполагаю, что входная строка была первоначально помещена в нее.Попробуй здесь
источник
!
перед финалом$_
. Если с этим способом все в порядке, вы можете сохранить 4 байта, изменив его наs/.(??{$&^' '})//&&redo
+1 байт для-p
флага. Это не будет работать в подпрограмме, как у вас сейчас, потому что на{ code }
самом деле это не цикл (следовательно&&redo
, не будет работать), но-p
он помещает его вwhile
цикл.' '
на$"
. Посмотрите на это, чтобы увидеть, как выглядит код.Пролог (SWI) , 151 байт
Требуется много времени, чтобы работать на более длинных ложных делах из-за возврата.
Попробуйте онлайн!
Ungolfed
источник
MATL , 20 байтов
Попробуйте онлайн! Или проверьте все тестовые случаи (это займет некоторое время).
объяснение
источник
Mathematica, 65 байт
источник
JavaScript (Node.js) , 47 байт
Попробуйте онлайн!
источник
Python 3 , 71 байт
Попробуйте онлайн!
источник