Введение

Предположим, у вас есть линейка с номерами от 0 до r-1 . Вы помещаете муравья между любыми двумя числами, и он начинает беспорядочно ползать по линейке. Правитель настолько узок, что муравей не может ходить из одной позиции в другую, не пройдя все промежуточные числа. Когда муравей ходит по числу впервые, вы записываете его, и это дает вам перестановку r чисел. Мы говорим, что перестановка является беспокойной, если она может быть сгенерирована муравьем таким образом. В качестве альтернативы, перестановка p является беспокойной, если каждая запись p [i], кроме первой, находится на расстоянии 1 от некоторой предыдущей записи.

Примеры

Длина-6 перестановок

4, 3, 5, 2, 1, 0

является беспокойным, потому что 3 находится на расстоянии 1 от 4 , 5 находится на расстоянии 1 от 4 , 2 находится на расстоянии 1 от 3 , 1 находится на расстоянии 1 от 2 , и 0 находится на расстоянии 1 от 1 . Перестановка

3, 2, 5, 4, 1, 0

не беспокойный, потому что 5 не находится на расстоянии 1 от 3 или 2 ; муравей должен пройти через 4, чтобы добраться до 5 .

Задание

Учитывая перестановку чисел от 0 до r-1 для некоторого 1 ≤ r ≤ 100 в любом приемлемом формате, выведите истинное значение, если перестановка является беспокойной, и ложное значение, если нет.

Контрольные примеры

[0] -> True
[0, 1] -> True
[1, 0] -> True
[0, 1, 2] -> True
[0, 2, 1] -> False
[2, 1, 3, 0] -> True
[3, 1, 0, 2] -> False
[1, 2, 0, 3] -> True
[2, 3, 1, 4, 0] -> True
[2, 3, 0, 4, 1] -> False
[0, 5, 1, 3, 2, 4] -> False
[6, 5, 4, 7, 3, 8, 9, 2, 1, 0] -> True
[4, 3, 5, 6, 7, 2, 9, 1, 0, 8] -> False
[5, 2, 7, 9, 6, 8, 0, 4, 1, 3] -> False
[20, 13, 7, 0, 14, 16, 10, 24, 21, 1, 8, 23, 17, 18, 11, 2, 6, 22, 4, 5, 9, 12, 3, 15, 19] -> False
[34, 36, 99, 94, 77, 93, 31, 90, 21, 88, 30, 66, 92, 83, 42, 5, 86, 11, 15, 78, 40, 48, 22, 29, 95, 64, 97, 43, 14, 33, 69, 49, 50, 35, 74, 46, 26, 51, 75, 87, 23, 85, 41, 98, 82, 79, 59, 56, 37, 96, 45, 17, 32, 91, 62, 20, 4, 9, 2, 18, 27, 60, 63, 25, 61, 76, 1, 55, 16, 8, 6, 38, 54, 47, 73, 67, 53, 57, 7, 72, 84, 39, 52, 58, 0, 89, 12, 68, 70, 24, 80, 3, 44, 13, 28, 10, 71, 65, 81, 19] -> False
[47, 48, 46, 45, 44, 49, 43, 42, 41, 50, 40, 39, 38, 51, 37, 36, 52, 35, 34, 33, 32, 53, 54, 31, 30, 55, 56, 29, 28, 57, 58, 59, 60, 27, 26, 61, 25, 62, 63, 64, 65, 66, 67, 24, 23, 22, 21, 68, 69, 20, 19, 18, 17, 70, 71, 16, 15, 72, 73, 74, 75, 76, 14, 13, 12, 77, 11, 10, 9, 8, 78, 7, 79, 80, 6, 81, 5, 4, 3, 82, 2, 83, 84, 1, 85, 86, 87, 0, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99] -> True

Интересный факт: для r ≥ 1 существует ровно 2 ^r-1 перестановки antsy длины r .

Pyth, 7 байт

/y+_QQS

Попробуйте онлайн. (Из-за экспоненциального времени выполнения включены только небольшие тестовые случаи.) Выходы 2 для Truthy, 0 для Falsey.

/          Count the number of occurences of
      S     the sorted input (implicit Q)
 y          in the order-preserved power set
  +_QQ       of the input prepended by its reverse

Другими словами,

lambda l: subseq(sorted(l), concat(reverse(l), l))

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

Почему это работает? Чтобы перестановка была сложной, переход от 0 к n-1 должен состоять в том, чтобы идти только влево, а затем идти только вправо. Это потому, что элементы больше первого элемента должны увеличиваться слева направо, а элементы меньше, чем должны уменьшаться слева направо.

[2, 3, 1, 4, 0]
             ^
       ^     0
 ^     1      
 2  ^        
    3     ^
          4

Если мы зеркально отобразим список, поместив перевернутую копию слева от него, теперь этот обход идет только вправо.

[0, 4, 1, 3, 2, 2, 3, 1, 4, 0]
 ^            |             
 0     ^      |             
       1      | ^           
              | 2  ^        
              |    3     ^  
              |          4                                  

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

Haskell, 46 байтов

(%)=scanl1
f l=zipWith(+)(min%l)[0..]==max%l

Проверяет, равна ли разность векторов бегущих максимумов и бегущих минимумов [0,1,2,3 ...].

l =             [2, 3, 1, 4, 0]

scanl1 max l =  [2, 3, 3, 4, 0]
scanl1 min l =  [2, 2, 1, 1, 0]  
difference =    [0, 1, 2, 3, 4]

Згарб сохранил 2 байта с (%)=scanl1.

JavaScript (ES6), 45

a=>a.every((v,i)=>a[v]=!i|a[v-1]|a[v+1],a=[])

Я думал, что это слишком просто, чтобы объяснять, но есть хитрость, и на всякий случай, вот моя первая версия, pre-golf

a => {
  k = []; // I'll put a 1 in this array at position of each value 
          // that I find scanning the input list
  return a.every((v,i) => { // execute for each element v at position i
    // the index i is needed to manage the first iteration
    // return 1/true if ok, 0/false if not valid
    // .every will stop and return false if any iteration return falsy
    k[v] = 1; // mark the current position
    if ( i == 0 )
    {  // the first element is always valid
       return true;
    }
    else
    {
       return k[v-1] == 1 // valid if near a lesser value
              || k[v+1] == 1; // or valid if near a greater value
    }
  })
}

Примечание: в гольфе aиспользуется код вместо k, так как мне не нужна ссылка на исходный массив внутри everyвызова. Поэтому я избегаю загрязнять глобальное пространство имен, повторно используя параметр

Тест

antsy=
a=>a.every((v,i)=>a[v]=!i|a[v-1]|a[v+1],a=[])

var OkAll=true
;`[0] -> True
[0, 1] -> True
[1, 0] -> True
[0, 1, 2] -> True
[0, 2, 1] -> False
[2, 1, 3, 0] -> True
[3, 1, 0, 2] -> False
[1, 2, 0, 3] -> True
[2, 3, 1, 4, 0] -> True
[2, 3, 0, 4, 1] -> False
[0, 5, 1, 3, 2, 4] -> False
[6, 5, 4, 7, 3, 8, 9, 2, 1, 0] -> True
[4, 3, 5, 6, 7, 2, 9, 1, 0, 8] -> False
[5, 2, 7, 9, 6, 8, 0, 4, 1, 3] -> False
[20, 13, 7, 0, 14, 16, 10, 24, 21, 1, 8, 23, 17, 18, 11, 2, 6, 22, 4, 5, 9, 12, 3, 15, 19] -> False
[34, 36, 99, 94, 77, 93, 31, 90, 21, 88, 30, 66, 92, 83, 42, 5, 86, 11, 15, 78, 40, 48, 22, 29, 95, 64, 97, 43, 14, 33, 69, 49, 50, 35, 74, 46, 26, 51, 75, 87, 23, 85, 41, 98, 82, 79, 59, 56, 37, 96, 45, 17, 32, 91, 62, 20, 4, 9, 2, 18, 27, 60, 63, 25, 61, 76, 1, 55, 16, 8, 6, 38, 54, 47, 73, 67, 53, 57, 7, 72, 84, 39, 52, 58, 0, 89, 12, 68, 70, 24, 80, 3, 44, 13, 28, 10, 71, 65, 81, 19] -> False
[47, 48, 46, 45, 44, 49, 43, 42, 41, 50, 40, 39, 38, 51, 37, 36, 52, 35, 34, 33, 32, 53, 54, 31, 30, 55, 56, 29, 28, 57, 58, 59, 60, 27, 26, 61, 25, 62, 63, 64, 65, 66, 67, 24, 23, 22, 21, 68, 69, 20, 19, 18, 17, 70, 71, 16, 15, 72, 73, 74, 75, 76, 14, 13, 12, 77, 11, 10, 9, 8, 78, 7, 79, 80, 6, 81, 5, 4, 3, 82, 2, 83, 84, 1, 85, 86, 87, 0, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99] -> True`
.split`\n`.forEach(row => {
  var rowElements = row.match(/\w+/g), 
      expected = rowElements.pop()=='True',
      input = rowElements.map(x => +x),
      result = antsy(input),
      ok = result == expected;
  OkAll = OkAll && ok;
  console.log(ok?'OK':'KO', input+' -> '+result)
})
console.log(OkAll ? 'All passed' : 'Failed')

Python 2, 49 байт

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

Проверяет, содержит ли каждый префикс списка все числа между его min и max включительно. Это делается путем проверки, если разность max и min меньше его длины.

54 байта:

f=lambda l:1/len(l)or-~l.pop()in[min(l),max(l)+2]*f(l)

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

Это также можно проверить с помощью забавного, но более длинного понимания списка.

lambda l:all(l.pop()in[min(l)-1,max(l)+1]for _ in l[1:])

Я хотел бы использовать неравенство min(l)-2<l.pop()<max(l)+2, но popсначала должно произойти. Использование программы для вывода через код ошибки, скорее всего, будет короче.

Mathematica, 42 байта

!MatchQ[#,{a__,b_,___}/;Min@Abs[{a}-b]>1]&

Использует сопоставление с шаблоном, чтобы попытаться найти префикс a, максимальное отличие которого от следующего элемента bбольше 1(и сводит на нет результат MatchQ).

Perl, 39 38 35 байт

Включает +1 для -p

Приведите последовательность на STDIN:

antsy.pl <<< "2 1 3 0"

antsy.pl:

#!/usr/bin/perl -p
s%\d+%--$a[$&]x"@a"=~/1  /%eg;$_++

MATL , 11 байт

&-|R1=a4L)A

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

объяснение

Это вычисляет матрицу всех попарных абсолютных разностей и сохраняет верхнюю треугольную часть. Результат верен, если во всех столбцах, кроме первого, есть хотя бы 1 значение.

&-     % All pairwise differences
|      % Absolute value
R      % Upper triangular part
1=     % Does each entry equal 1?
a      % Logical "or" along each column
4L)    % Remove first value
A      % Logical "and" of all results

R, 72 64 60 байт

v=scan();for(i in seq(v))T=c(T,diff(sort(v[1:i])));all(T==1)

Перестановка является беспокойной тогда и только тогда, когда все ее левые подстановки являются непрерывными (т.е. имеют разность один при сортировке).

Если длина входных данных гарантированно превышает один, то мы можем заменить 1:sum(1|v)на seq(v), что экономит четыре байта.

seq(v)В состояние , если ведет себя по- другому , когда входной имеет длину один --- он генерирует последовательность 1:vвместо seq_along(v). Однако, к счастью, TRUEв этом случае получается результат, который является желаемым поведением. То же самое происходит и для ввода нулевой длины.

В R Tзаданная переменная равна TRUE(но R позволяет вам переопределить ее). TRUEтакже считается равным1 .

Спасибо @Billywob за некоторые полезные улучшения оригинального решения.

05AB1E , 7 байтов

Âìæ¹{¢O

Попробуйте онлайн! или как модифицированный набор тестов .

объяснение

Использует процесс, описанный xnor в его блестящем ответе Pyth .
Возвращает 2 для истинных случаев и 0 для ложных.

Âì        # prepend a reversed copy of input to input
  æ       # take powerset
   ¹{     # push a sorted copy of input
     ¢    # count occurances of sorted input in powerset
      O   # sum occurances (which for some reason is needed, feels like a bug)

Perl, 63 байта

Обратите внимание, что @Gabriel Banamy предложил более короткий (55 байт) ответ . Но я думаю, что это решение все еще интересно, поэтому я публикую его.

Количество байтов включает в себя 62 байта кода и -nфлага.

s/\d+/1x($&+1)/ge;/ 1(1*)\b(?{$.&=$`=~m%\b(11)?$1\b%})^/;say$.

Чтобы запустить это:

perl -nE 's/\d+/1x($&+1)/ge;/ 1(1*)\b(?{$.&=$`=~m%\b(11)?$1\b%})^/;say$.' <<< "3 2 5 4 1 0"

Краткие пояснения : преобразует каждое число kв унарное представление k+1(это +1необходимо, чтобы 0s не игнорировалось). Затем для каждого числа k+1(выраженного в унарном виде как 1(1*)) мы смотрим, присутствуют ли k( $1содержит k) или k+2(что тогда 11$1) в предыдущей строке (на которую ссылается $-backtick). Если нет, то мы устанавливаем $.на ноль. В конце мы печатаем, $.что будет, 1если мы никогда не установим его на ноль или ноль в противном случае.

Brain-Flak 302 264 256 Bytes

Спасибо Wheat Wizard за сохранение 46 байт

([]){{}({}<>)<>([])}{}<>(({}))([]){{}({}<>)<>([])}{}<>(({}<>))<>(()){{}(({})<(({})<>[({})]<>(())){((<{}{}>))}{}{{}({}<><{}>)(<>)}{}<>({}<<>(({})<>[({})<>(())]){((<{}{}>))}{}{{}({}<><{}>)(<>)}{}<>>)<>>[({})](<()>)){{}{}(<(())>)}{}}([][()(())]){((<{}{}>))}{}

Вершина стека будет 1 для правды и 0 для фальши.

Правда: попробуйте онлайн!
Ложь: попробуйте онлайн!

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

Краткое объяснение:

([])                             # duplicate the bottom element by
{{}({}<>)<>([])}{}<>             # reversing everything onto the other stack 
(({}))([])                       # duplicating the top element
{{}({}<>)<>([])}{}<>             # and reversing everything back

(({}<>))<>                       # copy the top element to the other stack (push twice)
(()){{}                          # push a 1 so the loop starts, and repeat until the top
                                 # two elements are equal
(({})<                           # hold onto the top element to compare later
(({})<>[({})]<>(()))             # push a 0 if diff with the top of the other stack is +1
{{}({}<><{}>)(<>)}{}             # logical not (the previous line pushed a 1 as the second
                                 # element already)
{{}({}<><{}>)<>(<()>)}{}         # replace the top of the other stack with this element if
                                 # the logical not gave us 1
<>({}<<>                         # take the minimum off the other stack temporarily 
(({})<>[({})<>(())])             # push a 0 if diff with the top of the other stack is -1
{((<{}{}>))}{}                   # logical not (the previous line pushed a 1 as the second
                                 # element already)
{{}({}<><{}>)(<>)}{}             # replace the top of the other stack with this element if
                                 # the logical not gave us 1
<>>)<>                           # put the minimum on back on
>)                               # put the element you were comparing back on
[({})](<()>)){{}{}(<(())>)}{}    # push 1 or 0 for not equal to the element we held earlier
                                 # (push the second number back on)
}                                # repeat the loop if the top 2 weren't equal
([][()(())]){((<{}{}>))}{}       # logical not of the height of the stack

Желе , 9 8 7 байт

;@UŒPċṢ

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

Jelly перевод ответа xnor.

Старые решения:

;\Ṣ€IỊȦ
;\Ṣ€IE€P

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

Работает очень похоже на мой ответ Pyth ниже:

;\          All prefixes (Accumulate (\) over concatenation (;))
  Ṣ€        (Ṣ)ort each (€) prefix
    I       (I)ncrements of each prefix (differences between consecutive elements).  Implicit vectorization.
     E€     Check if all elements are (E)qual (they will be iff the permutation is antsy,
               and all elements will be 1) for each (€) prefix
       P    Is this true for all prefixes?
     ỊȦ     For the other answer, are (Ȧ)ll elements 1 or less (Ị)?

CJam ( 21 20 байт)

{:A,{_)A<$2*)@-#},!}

Набор онлайн-тестов

рассечение

Это использует наблюдение xnor в его ответе на Haskell, что разница между максимумом и минимумом первых nэлементов должна бытьn-1 .

{         e# Define a block. Stack: array
  :A,     e#   Store the array in A and get its length
  {       e#   Filter (with implicit , so over the array [0 ... len-1])
    _)A<  e#     Get the first i+1 elements of A (so we iterate over prefixes)
    $2*)  e#     Extract the last element without leaving an empty array if the
          e#     prefix is of length 1 by first duplicating the contents of the
          e#     prefix and then popping the last element
    @-#   e#     Search the prefix for max(prefix)-i, which should be min(prefix)
          e#     giving index 0
  },      e#   So the filter finds values of i for which the prefix of length i+1
          e#   doesn't have max(prefix) - min(prefix) = i
  !       e#   Negate, giving truthy iff there was no i matching the filter
}

Альтернативный подход (также 20 байтов)

{_{a+_)f-:z1&,*}*^!}

Набор онлайн-тестов

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

рассечение

{_{a+_)f-:z1&,*}*^!}

{         e# Declare a block. Stack: array
  _       e#   Work with a copy of the array
  {       e#   Fold...
    a+    e#     Add to the accumulator.
    _)f-  e#     Dup, pop last, map subtraction to get distance of this element from
          e#     each of the previous ones
    :z1&, e#     Check whether the absolute values include 1
    *     e#     If not, replace the accumulator with an empty array
  }*
  ^!      e#   Test whether the accumulator is equal to the original array
          e#   Note that this can't just be = because if the array is of length 1
          e#   the accumulator will be 0 rather than [0]
}

Ява, 100 98 79 75 байт

a->{int n=a[0],m=n-1;for(int i:a)n-=i==m+1?m-m++:i==n-1?1:n+1;return n==0;}

Ранее:

a->{int m,n;m=n=a[0];--m;for(int i:a)if(i==m+1)m=i;else if(i==n-1)n=i;else return 0>1;return 1>0;}

Сохранено 3 байта путем замены trueи falseна 1>0и 0>1.

Сохранено 23 байта благодаря отличным предложениям от Питера Тейлора!

Ungolfed:

a -> {
    int n = a[0], m = n - 1;
    for (int i : a)
        n -= i == m + 1? m - m++ : i == n - 1? 1 : n + 1;
    return n == 0;
}

Следите за самыми высокими и самыми низкими значениями, видимыми до mи n; принимать новое значение только в том случае, если оно есть m + 1или n - 1т. е. следующее большее или меньшее значение; инициализировать высокое значение,m на единицу меньше, чем первый элемент, чтобы он «совпадал» с первым циклом. Примечание: это онлайн-алгоритм с линейным временем. Требуется только три слова памяти для текущих, самых высоких и самых низких значений, в отличие от многих других решений.

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

(К сожалению, это менее эффективно, потому что мы всегда должны смотреть на всю последовательность, а не спасаться после первого неправильного числа, но трудно спорить с 23-байтовой экономией (!), Когда другие решения используют O (n ^ 2) ) и экспоненциальное время приближается.)

Использование:

import java.util.function.Predicate;

public class Antsy {
    public static void main(String[] args) {
        int[] values = { 6, 5, 4, 7, 3, 8, 9, 2, 1, 0 };
        System.out.println(test(values,
            a -> {
                int n = a[0], m = n - 1;
                for (int i : a)
                    n -= i == m + 1? m - m++ : i == n - 1? 1 : n + 1;
                return n == 0;
            }
        ));
    }

    public static boolean test(int[] values, Predicate<int[]> pred) {
        return pred.test(values);
    }
}

Примечание: это также может быть написано без использования лямбд Java 8:

Java 7, 89 байт

boolean c(int[]a){int n=a[0],m=n-1;for(int i:a)n-=i==m+1?m-m++:i==n-1?1:n+1;return n==0;}

Pyth ( вилка ), 13 байт

!sstMM.+MSM._

Нет Попробуйте онлайн Ссылка для этого форка Pyth. Вилка включает функцию deltas .+, которая не является частью стандартной библиотеки Pyth.

Объяснение:

           ._  For each of the prefixes:
         SM    Sort it
      .+M      Get deltas (differences between consecutive elements), which for antsy
                 permutations would all be 1s
   tMM         Decrement each of the elements (all 0s for antsy permutations)
 ss            Sum all the results from the above together, 0 for antsy and >0 for non-antsy
!              Logical negation.

Perl, 66 54 +1 = 55 байт

+1 байт за -n.

s/\d+/$.&=!@a||1~~[map{abs$_-$&}@a];push@a,$&/eg;say$.

Объяснение:

s/\d+/$.&=!@a||1~~[map{abs$_-$&}@a];push@a,$&/eg;say$.
#input is automatically read into $_.
#regex automatically is performed on $_.
s/   /                                       /eg;
    #Substitution regex.
    #/g means to keep searching after the first match
    #/e evaluates the replacement as code instead of regex.
  \d+  #Match of at least 1 digit.  Match automatically gets stored in $&
      $.&=  #$. is initially 1.  This basically says $. = $. & (code)
           !@a  #Since @a is uninitialized, this returns !0, or 1
                #We don't want to check anything for the first match
              || #logical or
                1~~
                   #~~ is the smartmatch operator.  When RHS is scalar and LHS is array reference,
                   #it returns 1 iff RHS is equal to at least one value in de-referenced LHS.
                   [map{abs$_-$&}@a];
                       #Return an array reference to the array calculated by |$_ - $&|
                       #where $_ iterates over @a.  Remember $& is the stored digit capture.
                                     push@a,$& #pushes $& at the end of @a.
                                                 say$. #output the result

Печатает 0, если false, 1, если true.

-11 байт благодаря @Dada

Brainfuck, 60 байт

,+[>+>+<<-]
,+
[
  [>->->+<<<-]
  >-
  [
    +>+
    [
      <<<
    ]
  ]
  >[>]
  <[<+<+>>-]
  <<<,+
]
>.

Перестановка дается в виде байтов без разделителей и завершающей строки. Поскольку \x00происходит во входных данных, это предназначено для реализаций с EOF = -1. Выход \x00для ложного и \x01истинного.

Если перестановка \x01 до до chr(r)разрешена, то мы можем заменить все экземпляры ,+с ,за счет 57 сEOF = 0 реализацией.

Попробуйте онлайн (57-байтовая версия): входные данные могут быть представлены как перестановка любого непрерывного диапазона байтов, исключая \x00, и выходные данные будут\x00 для ложного и минимального диапазона для истинного.

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

Структура памяти нормального рабочего пространства в начале основного цикла

c a b 0 0

где cтекущий символ, aминимальное и bмаксимальное. (Для 60-байтовой версии все обрабатывается со смещением 1 из-за ,+.)

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

:@[fb:{oLtT,Lh:T:efL}a

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

объяснение

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

:@[fb                       Take all but the first prefixes of the Input
     :{             }a      This predicate is true for all those prefixes
       oLtT,                Sort the prefix, call it L, its last element is T
            Lh:T            The list [First element of L, T]
                :efL        Find all integers between the First element of L and T. It must
                              result in L

Пакет, 133 байта

@set/au=%1,l=%1-1,a=0
@for %%n in (%*)do @call:l %%n
@exit/b%a%
:l
@if %1==%u% (set/au+=1)else if %1==%l% (set/al-=1)else set a=1

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

J, 14 байт

/:~-:>./\-<./\

Это основано на @ xnor's методе .

объяснение

/:~-:>./\-<./\  Input: array P
        \       For each prefix of P
     >./          Reduce using the maximum
          <./\  Get the minimum of each prefix of p
         -      Subtract between each
   -:           Test if it matches
/:~               P sorted

Java, 170 байт

boolean f(int[]a){int l=a.length,i=0,b=0,e=l-1;int[]x=new int[l];for(;i<l;i++)x[i]=i;for(i--;i>0;i--)if(a[i]==x[b])b++;else if(a[i]==x[e])e--;else return 0>1;return 1>0;}

Массив xимеет значения от 0 до максимального числа по порядку (Python будет намного лучше здесь ...). Цикл идет назад, пытаясь найти совпадение с самым низким ( x[b]) или самым высоким ( x[e]) числом, которое еще не встречалось; если это произойдет, это число может быть достигнуто на этом этапе.

Тестовый код здесь .

Mathematica, 47 байт

Немного дольше, чем решение Мартина Эндера (неожиданный сюрприз!). Но это одно из моих нечитаемых усилий, так что это хорошо: D

#=={}||{Max@#,Min@#}~MemberQ~Last@#&&#0@Most@#&

Объяснение:

#=={}                         empty lists are antsy (function halts with True)
 ||                            or
{Max@#,Min@#}~MemberQ~Last@#  lists where the last number is largest or smallest
                              are possibly antsy (else function halts with False)
 &&                            and
#0@Most@#&                    recursively call this function after dropping the
                              last element of the list

Java 7, 170 169 байт

import java.util.*;Object c(int[]a){List l=new ArrayList();l.add(a[0]);for(int i:a){if(l.indexOf(i)<0&l.indexOf(i-1)<0&l.indexOf(i+1)<0)return 0>1;l.add(i);}return 1>0;}

Ungolfed & тестовый код:

Попробуй это здесь.

import java.util.*;
class M{
  static Object c(int[] a){
    List l = new ArrayList();
    l.add(a[0]);
    for(int i : a){
      if(l.indexOf(i) < 0 & l.indexOf(i-1) < 0 & l.indexOf(i+1) < 0){
        return 0>1; //false
      }
      l.add(i);
    }
    return 1>0; //true
  }

  public static void main(String[] a){
    System.out.println(c(new int[]{ 0 }));
    System.out.println(c(new int[]{ 0, 1 }));
    System.out.println(c(new int[]{ 1, 0 }));
    System.out.println(c(new int[]{ 0, 1, 2 }));
    System.out.println(c(new int[]{ 0, 2, 1 }));
    System.out.println(c(new int[]{ 2, 1, 3, 0 }));
    System.out.println(c(new int[]{ 3, 1, 0, 2 }));
    System.out.println(c(new int[]{ 1, 2, 0, 3 }));
    System.out.println(c(new int[]{ 2, 3, 1, 4, 0 }));
    System.out.println(c(new int[]{ 0, 5, 1, 3, 2, 4 }));
    System.out.println(c(new int[]{ 6, 5, 4, 7, 3, 8, 9, 2, 1, 0 }));
    System.out.println(c(new int[]{ 4, 3, 5, 6, 7, 2, 9, 1, 0, 8 }));
    System.out.println(c(new int[]{ 5, 2, 7, 9, 6, 8, 0, 4, 1, 3 }));
    System.out.println(c(new int[]{ 20, 13, 7, 0, 14, 16, 10, 24, 21, 1, 8, 23, 17, 18, 11, 2, 6, 22, 4, 5, 9, 12, 3, 15, 19 }));
    System.out.println(c(new int[]{ 34, 36, 99, 94, 77, 93, 31, 90, 21, 88, 30, 66, 92, 83, 42, 5, 86, 11, 15, 78, 40, 48, 22, 29, 95, 64, 97, 43, 14, 33, 69, 49, 50, 35, 74, 46, 26, 51, 75, 87, 23, 85, 41, 98, 82, 79, 59, 56, 37, 96, 45, 17, 32, 91, 62, 20, 4, 9, 2, 18, 27, 60, 63, 25, 61, 76, 1, 55, 16, 8, 6, 38, 54, 47, 73, 67, 53, 57, 7, 72, 84, 39, 52, 58, 0, 89, 12, 68, 70, 24, 80, 3, 44, 13, 28, 10, 71, 65, 81, 19 }));
    System.out.println(c(new int[]{ 47, 48, 46, 45, 44, 49, 43, 42, 41, 50, 40, 39, 38, 51, 37, 36, 52, 35, 34, 33, 32, 53, 54, 31, 30, 55, 56, 29, 28, 57, 58, 59, 60, 27, 26, 61, 25, 62, 63, 64, 65, 66, 67, 24, 23, 22, 21, 68, 69, 20, 19, 18, 17, 70, 71, 16, 15, 72, 73, 74, 75, 76, 14, 13, 12, 77, 11, 10, 9, 8, 78, 7, 79, 80, 6, 81, 5, 4, 3, 82, 2, 83, 84, 1, 85, 86, 87, 0, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99 }));
  }
}

Выход:

true
true
true
true
false
true
false
true
true
false
true
false
false
false
false
true