Codegolf — Это Перестановка Башни?

Башня состоит из слоев, каждый из которых на одну единицу короче нижнего. Каждый слой полностью находится поверх предыдущего. Например, вот башня и ее карта высот:

 
 
 [1] -> True
[1, 2] -> True
[2, 1] -> True
[1, 2, 3] -> True
[1, 3, 2] -> True
[2, 1, 3] -> False
[2, 3, 1] -> True
[3, 1, 2] -> False
[3, 2, 1] -> True
[1, 2, 3, 4] -> True
[1, 2, 4, 3] -> True
[1, 3, 2, 4] -> False
[1, 3, 4, 2] -> True
[1, 4, 2, 3] -> False
[1, 4, 3, 2] -> True
[2, 1, 3, 4] -> False
[2, 1, 4, 3] -> False
[2, 3, 1, 4] -> False
[2, 3, 4, 1] -> True
[2, 4, 1, 3] -> False
[2, 4, 3, 1] -> True
[3, 1, 2, 4] -> False
[3, 1, 4, 2] -> False
[3, 2, 1, 4] -> False
[3, 2, 4, 1] -> False
[3, 4, 1, 2] -> False
[3, 4, 2, 1] -> True
[4, 1, 2, 3] -> False
[4, 1, 3, 2] -> False
[4, 2, 1, 3] -> False
[4, 2, 3, 1] -> False
[4, 3, 1, 2] -> False
[4, 3, 2, 1] -> True
 
 
 

Поскольку длины слоев представляют собой целые числа от 1 до n, а слои полностью расположены друг над другом, карта высот всегда будет перестановкой целых чисел из n>0 to # ## ### # ### ##### 21354 . (Понимаете, почему? Комментарий ниже)

Обратное неверно. Некоторые перестановки не являются картой высот башни. перестановки башни. Например, [1,4,5,3,2] is not the height map of any tower, meaning that it's not a tower permutation. However, [2,1,3,5,4] это перестановка башни, как вы можете видеть из предыдущего рисунка ascii.

Чтобы внести ясность, следующее нет башня:

n

Потому что каждый слой должен быть непрерывным. Вместо этого это замок :P

Ваша задача — взять перестановку целых чисел от 1 до n (включительно) и решить, является ли это перестановкой башни, как обычно и по правилам. Вы можете предположить, что 1

Тестовые случаи (все перестановки до n=4)

# ## ### #### ##### 14532

#код-гольф #задача-решение #код-гольф #массив #проблема-решение

Питон, 46 байт

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
lambda x:sorted(a:=[*map(int.__gt__,x,x[1:])])==a
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

Использует характеристику

Перестановка башни — это перестановка, в которой ни один элемент не меньше обоих своих соседей.

---

Питон 2, 36 байт

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 ü      # For each overlapping pair of the (implicit) input-list:

›     #  Check if the first is larger than the second

D    # Duplicate this list of checks

{   # Sort the copy

Q  # Check if the lists are still the same (thus it was sorted)

# (after which the result is output implicitly)
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

На самом деле пропитана ностальгией по Python 2: ü›D{Q , backticks, D(l)=sign(l-l[2...]) M(l)=1/D(D(l)).max создание списка.

Идея состоит в том, чтобы использовать 0.5 to compare consecutive elements to detect an decrease ( 1 ) с последующим увеличением 0.5 . This is identified by the string representation containing the substring undefined , так что перестановки башен дают 0 and others give undefined .

---

Питон 3 код ошибки, 32 байта

max

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

Отличное короткое решение от Loyy Walt. Принимает входные данные и выходные данные с ошибками или без ошибок, с указанием успешного завершения. нет перестановка башни.

Желе, ⁵ 4 байта

2

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

Объяснение:

0

Это проверяет, увеличивается ли список, а затем снова уменьшается.

Р, 33 байта

Или Р>=4,1, 26 байт заменив слово 2 with a -2 .

0

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

Выходы перевернуты D / M .

Шу, 100 99 байт

1

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

Принимает входные данные в виде списка унарных чисел, разделенных запятыми, с завершающей запятой.

Объяснение

-1

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

Питон 3 алгоритмический эквивалент

l

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

Юля 1.0, 26 23 байта

-1

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

Брахилог, 8 6 байт

1

Выводит false для перестановки башни, true для перестановки без башни. Попробуйте онлайн!

Объяснение

Использует тест «есть ли у него локальный минимум» из ответ xnorа.

l ||answer||

Хаскелл + hgl, 16 13 9 байт

D

Возврат 0.5 when it is a tower permutation and undefined когда это не так.

Для того же результата также работает следующее:

M

Объяснение

Мы хотим найти элемент, который меньше обоих своих соседей.

Для этого начнем с D=sign(l-l[2...]) M(l)=1/max(D-D[2...]) . h->{int b=0,s=1;for(int a:h)s=s*b>s*(b=a)?s>0?-1:0:s;return s;} принимает функцию и применяет ее ко всем последовательным соседям, a->#a<3||prod(i=2,#a-1,a[i]>min(a[i-1],a[i+1])) для перестановки башни или f(a)=#a<3||(a[2]>min(a[1],a[3]))*f(a[^1]) если первый аргумент меньше второго и sub{join('',map$_[-2]>pop?I:D,2..@_)=~/^I*D*$/} из более длинных списков мы инвертируем его, в результате чего

θ Input array Φ Filtered where κ Current index is not zero ? Map over remaining elements and join ι Current element › Is greater than θ Unfiltered array § Indexed by κ Current index ¬№ Does not contain 01 Literal string `01` Implicitly print

Если бы мы начали с перестановки башен, то результатом было бы некоторое количество - s follower by some number of ¬№эΦθκ›ι§θκ01 с. Если бы это было не так, то (⍳∘≢≡⍋)2>/ sub-sequence. This means that we just have to check if the result is monotonically increasing. If it is then it was a tower permutation, if it is not then it wasn't. 2lvƒ>ÞṠ — это функция, проверяющая, монотонно ли увеличивается список.

Отражение

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

Дж, ^{19 14} 12 байт

a=>!a.some((x,i)=>x<a[i-1]&&x<a[i+1])

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

^{-5 после того, как из ответа pxeger понял, что я мог бы использовать сортировку вместо группировки.}

^{еще одна -2 украла идею pxeger, которую можно использовать import Control.SetFunctions f(_++a:b:c:_)|b<a&&b<c=1 -- Helper to run tests helper :: [Int] -> Bool helper a = isEmpty $ set0 $ f a main = [ helper [1,2,3] , helper [3,2,1] , helper [3,1,2] , helper [4, 1, 2, 3] ] instead of PAKCS 2.2.0}

Ключевой вывод заключается в том, что дельты последовательных элементов в перестановке башни имеют не более одного «пика»:

• 1 Sort by...
• f(_++a:b:c:_)|b<a&&b<c=1 Is left greater than right (pairs of 2
• r;f(a,n)int*a;{for(r=0;n-->2;)r|=*a>*++a&*a<a[1];n=r;} Does that equal the original input?

Питон, 49 байт

\d+ $* ^(^1+,|1+\1)*((1+),(?!\3))*(1+)$

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

Порт моего ответа Jelly. (Написание этого вдохновило меня на создание -1-байтового гольфа)

Шелуха, 5 байт

1

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

Выводит ноль для вышек и ненулевое значение для не-башен.

1 ||answer||

Руби, 35 байт

0

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

Java (JDK), 76 байт

\d+ $* (1+),\1,\1

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

Возврат ! { 2 1 3 5 4 } 3 clump ! { { 2 1 3 } { 1 3 5 } { 3 5 4 } } [ ... ] ∃ ! (is there any element that...) ! { 2 1 3 } dup ! { 2 1 3 } { 2 1 3 } infimum ! { 2 1 3 } 1 second= ! t if it's a tower, t если это замок.

Кипу, 64 58 46 байт

f

Принимает входные данные со стандартного ввода, по одному числу в строке. Выводит ошибку для перестановок башни и автоматический выход для перестановок без башни. Попробуйте это онлайн!

Объяснение

Программы в Quipu состоят из нити, которые представляют собой столбцы шириной в два символа. Эта программа имеет шесть потоков, пронумерованных от 0 до 5:

[ 3 clump [ dup infimum second= ] ∃ ]

Потоки 3 и 4 содержат два последовательных числа в списке. (Изначально они оба равны 0.) Выполнение происходит следующим образом:

• Поток 0 принимает значение потока 3 минус значение потока 4 и проверяет, является ли разница положительной, т. е. находятся ли числа в порядке убывания. Если да, перейдите к потоку 2; в противном случае продолжите поток 1.
• Поток 1 проверяет, равен ли поток 2 по-прежнему 0. Если да, он переходит к потоку 3; если нет, он выходит из программы.
• Поток 2, если он достигнут, устанавливает свое значение в 1.
• Поток 3 устанавливает свое значение равным значению потока 4.
• Поток 4 считывает и сохраняет число из стандартного ввода.
• Поток 5 возвращается к потоку 0.

Конечным результатом является то, что любая нисходящая пара устанавливает значение потока 2 в 1, а любая последующая восходящая пара завершает программу. Если этот нисходящий-восходящий шаблон никогда не возникает, программа продолжает работу до тех пор, пока не закончатся входные данные и ошибки.

Поведение, 52 байта

math.unicode

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

Ungolfed и прокомментировал:

t=&![#(t=a)<3(#a-2)*&(v=t%(a+1)v>t%a|v<t%(a+2));>&a|b]

Тест с:

t:{1} t:{1 2 3} t:{3 1 2}

Бонусный (более крупный) ответ, использующий более неясные особенности языка, но по сути ту же логику:

t = &( i=1 // start on the index 1 // repeat the following sequence until failure \~( // either the ith member is bigger than the previous or bigger than the next [ a%i > a%(i+1) a%i > a%(i-1) ] // increment index and check if it still is less than n-1 i += 1 i < #a-1 ) // is a tower if the index stopped incrementing on the last possible index (i.e. passed all the checks) i > #a-2 ) ||answer||

Фактор + t=&(i=1\~([a%i>a%(i+1)a%i>a%(i-1)]i+=1i<#a-1)i>#a-2) , 39 bytes

"0 1 2 3 4 5" 3& 2& 1& 4& \/ 0& [] [] [] ?? 4& 3& [] == -- :: 2& >>

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

Объяснение

Возврат 3&2&1&4&\/0& [][] [] ?? 4&3& []== --:: 2& >> for true and 0 за ложь.

«Есть ли элемент, который меньше обоих своих соседей?»

Спасибо @xnor's отвечать для характеристики. Самый короткий метод «отсортированных знаков различий», который мне удалось получить, составил 44 байта.

1 ||answer||

Ретина 0.8.2, 17 байт

h->{int d=1,i=1;for(;i<h.length-1;)d&=h[i-1]>h[i]&h[i]<h[++i]?0:1;return d;}

Попробуйте онлайн! Ссылка включает тестовые примеры. Выходы f=->l{l==l.sort||l.pop<l[-1]&&f[l]} for a tower permutation, nonzero if not. Explanation: Uses @xnor's observation that each number in a tower permutation is greater than at least one of its neighbours. After unary conversion, the regex simply has to find a run of … # Fill gaps with numeric ranges Ẋ- # Pairwise differences V # Index of first element that is < # less than the next one # (or zero if not found) s, где оба соседних пробега V<Ẋ-… s are at least as long and therefore neither neighbour is lower.

Прямой положительный тест занимает массивные 39 байт:

-:

Попробуйте онлайн! Ссылка включает тестовые примеры. Объяснение: Ищет восходящую последовательность, за которой следует нисходящая последовательность.

С (ГКК), ^{93 \$\cdots\$ 59} 54 байта

2>\0&,

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

Сэкономлено колоссальные 24 байта благодаря Оливье Грегуару!!!

Вводит указатель на массив перестановок целых чисел от \$1\$ до \$n\$ и \$n\$ (поскольку указатели в C не несут информации о длине).
Возвращает \$0\$, если это перестановка башни, или \$1\$ в противном случае.

Карри, 24 байта

Протестировано для работы как в PAKCS, так и в КиКС2

/:

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

Проверяет, меньше ли какое-либо значение, чем оба его соседа, используя мощные сопоставления с шаблонами Карри. Возвращает *@| if it isn't a tower permutation and nothing otherwise.

TIO имеет ограниченные возможности для тестирования подобных вещей. Вставьте следующее в шлепать и вбежать > for better testing abilities:

-:]/:2>/\0&,

Этот обработчик теста не будет работать в KiCS2 или, по крайней мере, в версии, используемой smap. Но сама функция подойдет, если вы захотите протестировать ее вручную.

JavaScript (Node.js), 37 байт

mnI

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

Виксал, 9 7 байт

[B,T]

Попробуйте онлайн! или Запустите все тестовые случаи

-2 байта благодаря Ааронеусу Миллеру

Диалог APL: 10 байт

Здесь особо нечего сказать, обычное решение.

B ||answer||

Древесный уголь, 13 байт

T

Попробуйте онлайн! Ссылка на подробную версию кода. Выводит логическое значение Charcoal, т.е. [1,2,3,5,9,8,7,6,4] [T,T,T,T,B,B,B,B] [1,2,9,5,3,8,7,6,4] [T,T,B,N,T,B,B,B] for a tower permutation, nothing if not. Explanation: Port of @xnor's Python 2 answer.

False ||answer||

Перл 5, 47 байт

True

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

Париж/GP, 41 байт

lt

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

Порт Ответ @xnor на Python.

---

Париж/GP, 47 байт

pa

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

Java (JDK), 71, 63 байта

pa lt

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

возвращает 0, если это замок, и ненулевое значение (1 или -1), если это башня;

Объяснение

Начинается с ожидаемого минимального «наклона» (ов), равного 1,

Проверяет, соответствует ли разница между последовательными значениями ожидаемому «направлению», умножая их на наклон, чтобы нормализовать направление и гарантировать, что следующее значение будет больше. Если эта проверка не удалась, пока наклон равен 1, наклон изменяется на -1 для оставшейся части сравнения. Если это не удается, пока наклон не равен 1, наклон изменяется на 0. В противном случае наклон остается тем же, что и в последней итерации. Наклон 0 означает дельту в неожиданном направлении и, следовательно, не башню, а также гарантирует, что все последовательные вычисления направления равны 0, поэтому вычисленный наклон 0 «застревает». Возвращает наклон 's'

Десмос

, 41 39 байт -2 байта благодаря

mnI<pa cp

Эйден Чоу False takes a list and returns True Функция mnI<pa lt for non-tower permutations.

для перестановок башен или

Попробуй (игра в гольф)

Попробуйте (предварительно)

s For some consecutive sublist of the input Ṫ which has three elements, ⌋ its minimum ∈₁ occurs at index 1 (i.e. the middle element) Ṫ in that sublist is a helper quantity? macro? that takes the pairwise differences of a list sṪ⌋∈₁Ṫ Объяснение !v=issorted(diff(v).<0) s and def f(arr): if arr==[]:return True if 1 in arr[1:-1]:return False if arr[0]==1:return f([e-1 for e in arr[1:]]) if arr[-1]==1:return f([e-1 for e in arr[:-1]]) и получает знак каждого. Результатом будет список =L - Implicit left edge =R - Implicit right edge ,1,R=<,R - Spawn a left triangle on the right, if last element is 1. Remove the last element 1<={ - Triangle decrements element, turns into left curly triangle 1{={1 - Curly triangle passes trough ones ,{=<, - Curly triangle turns into a sharp triangle (to decrement next element) L{=L - After reaching the left edge, curly triangle dissapears L1,=L> - Same stuff but in the other direction >1=} - --||-- }1=1} - --||-- },=,> - --||-- >R=R - --||-- LR - If everything has been reduced, output true ,1,1=e - Or if there is a one not located near the edges, create an error e1=e - Errors propagate 1e=e - --||-- e,=e - --||-- ,e=e - --||-- LeR - Final error state is a tower permutation, all the =L =R ,1,R=<,R 1<={ 1{={1 ,{=<, L{=L L1,=L> >1=} }1=1} },=,> >R=R LR ,1,1=e e1=e 1e=e e,=e ,e=e LeR с. Если FALSE s.

TRUE then takes the result of function(v)is.unsorted(diff(v)<0) это произойдет до того, как и получает его \ s and possibly a function парные различия. Для перестановки башни это будет список (implicit input) [1, 4, 5, 3, 2] Ɲ for each neighouring pair: [(1, 4), (4, 5), (5, 3), (3, 2)] > is left greater than right? [0, 0, 1, 1] ṠƑ is it the same after sorting? (implicit output) somewhere. Thus, the max of the second-level differences will be >ƝṢƑ . Для перестановки без башни будет def f(a,*l):(a,)>l<l[1:]or f(*l) for a non-tower permutation. But there are also inputs of length 1 or 2 to be considered; they are too short for to have any second-level differences, which means that True returns False . To merge this result with the -1, 1 возвращает (+1) for any tower permutation and -1 otherwise.

---

в противном случае. cmp instead of map :

cmp ||answer||

Альтернативное 39-байтовое решение, которое возвращает, 5 05AB1E

lambda l:'-1, 1'in`map(cmp,l[1:],l)`

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

проверить все тестовые случаи

f=lambda l:len(l)<3or min(l[:3])<l[1]*f(l[1:])