Стекируемые последовательности

29

Вы раздаете из колоды карты с метками от 0 до 9, формируя стопки, которые начинаются с 0 и считаются до 1.

  • Когда вы разыгрываете 0, вы кладете его на стол, чтобы начать новый стек.
  • Когда вы сдаете любую другую карту, вы кладете ее на карту, стоимость которой точно на одну ниже, и покрываете ее. Если такой карты нет, колода не складывается.

Для данной колоды определите, может ли она быть сложена, когда раздается в указанном порядке. Эквивалентно, учитывая список цифр, решить, можно ли его разбить на непересекающиеся подпоследовательности в каждой форме0,1,..,k

пример

Возьми колоду 0012312425. Первые две карты есть 0, поэтому они идут на стол:

Stacks: 00

  Deck: 12312425

Далее, мы имеем дело с 1, который идет на 0, не имеет значения, который:

        1
Stacks: 00

  Deck: 2312425

Затем мы разыгрываем 2верхнюю часть только что размещенного 1и 3поверх него.

        3
        2
        1
Stacks: 00

  Deck: 12425

Далее 1, 2и помещают поверх первого стека и на 4вершине второй. 

        4
        3
        22
        11
Stacks: 00

  Deck: 25

Теперь нам нужно разместить a 2, но 1поверх стека нет. Итак, эта колода не была составной.

Входные данные: непустой список цифр 0-9 или их строка. Вы не можете предполагать, что 0 всегда будет на входе.

Вывод : одно из двух различных непротиворечивых значений, одно для суммируемых последовательностей и одно для не стекируемых

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

Составная:

0
01
01234
00011122234567890
012031
0120304511627328390

Не штабелируется:

1
021
0001111
0012312425
012301210
000112223

Для удобства в виде списков:

[0]
[0, 1]
[0, 1, 2, 3, 4]
[0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 4, 5, 6, 7, 8, 9, 0]
[0, 1, 2, 0, 3, 1]
[0, 1, 2, 0, 3, 0, 4, 5, 1, 1, 6, 2, 7, 3, 2, 8, 3, 9, 0]

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

Сгруппированные:

[[0], [0, 1], [0, 1, 2, 3, 4], [0, 0, 0, 1, 1, 1, 2, 2, 2, 3], [0, 1, 2, 0, 3, 1], [0, 1, 2, 0, 3, 0, 4, 5, 1, 1, 6, 2, 7, 3, 2, 8, 3, 9, 0]]
[[1], [0, 2, 1], [0, 0, 0, 1, 1, 1, 1], [0, 0, 1, 2, 3, 1, 2, 4, 2, 5]]

Leaderboard:

Показать фрагмент кода

code-golf sequence decision-problem subsequence XNOR
источник
Можем ли мы принять ограничение на длину списка?
17
@orlp Нет явного ограничения.
xnor
@xnor он, вероятно, просит оправдать написание int a[99]на C
Leaky Nun
@ LuisMendo Вы можете, я говорю "непустой".
xnor
@xnor Ах, прости, я этого не видел. Может ли массив быть основан на 1? То есть числа от 1до10
Луис Мендо

Ответы:

6

Haskell , 55 байтов

Анонимная функция, принимающая список целых чисел и возвращающая Bool.

Использование: (all(<1).foldr(?)[]) [0,1,2,3,4].

all(<1).foldr(?)[]
m?l|(p,r)<-span(/=m+1)l=m:p++drop 1r

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

Как это работает

  • foldr(?)[]сворачивает свой аргумент списка справа налево, используя ?, начиная с пустого списка. В результате получается список чисел в списке, который не помещается поверх предыдущего числа.
  • all(<1) проверяет, являются ли нули только единственными числами, не помещающимися поверх предыдущего числа.
  • m?lдобавляет число mк списку lнеподходящих номеров. Если m+1он уже есть в списке, его можно удалить, если он помещается поверх m.
    • (p,r)<-span(/=m+1)lразбивает список lна две части pи rв первом экземпляре числа m+1. Если их нет, правая часть rбудет пустой.
    • m:p++drop 1rзависит mот разделенных частей. Если rне пусто, то оно должно начинаться с того m+1, что удаляется с помощью drop 1.
Орджан Йохансен
источник
Отличная идея сделать укладку в обратном порядке! Я пытался расширить ваш ?рекурсивно, но получил ту же длину .
xnor
54 байта сData.List.delete
H.PWiz
5

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

Λ¬ḞS:o-→ø

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

Возвращает 1для стекируемых колод и не 0для стекируемых колод.

Похоже, что Орджан Йохансен в своем ответе на Haskell уже придумал тот же алгоритм, но в Husk это, очевидно, гораздо более лаконично.

объяснение

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

Λ¬ḞS:(-→)ø
         ø    Starting with the empty list (each element of this list will be the top card
              of a stack)
  ḞS          Traverse the input from right to left. For each card:
      -→        Remove the successor of this card from our list (if present)
    :           Add this card to our list
Λ¬            At the end, check if all the cards in our list are zeroes (falsy)
Лео
источник
4

Желе , 15 11 байт

‘Ṭ€+\I>0FS¬

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

Дрянная Монахиня
источник
О, очень мило. Будет ‘Ṭ€+\I>0FṀработать всегда?
Джонатан Аллан
@JonathanAllan Хорошо, учитывая правило 2 последовательных значений, оно должно.
Эрик Outgolfer
4

C (gcc), 74 73 байта

f(int*l){int s[10]={},r=1;for(;~*l;s[*l++]++)r*=!*l||s[*l-1]--;return r;}

Требуется, чтобы входной массив отмечал конец -1. Пример использования:

int main(int argc, char** argv) {
    int a[] = {0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 4, 5, 6, 7, 8, 9, 0, -1};
    printf("%d\n",  f(a));
    return 0;
}
orlp
источник
Что не так с равниной return r?
Утренняя монахиня
4

Сетчатка , 42 байта

O$#`(.)(?<=(\1.*?)*)
$#2
.
$*1,
^(,|1\1)+$

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

объяснение

O$#`(.)(?<=(\1.*?)*)
$#2

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

Проще всего определить, имеет ли вход такой тип паттерна в унарном формате.

.
$*1,

Мы заменяем каждую цифру n на n 1 s, после которой ставим запятую для разделения отдельных цифр.

^(,|1\1)+$

Наконец, мы используем прямую ссылку для сопоставления последовательно увеличивающихся серий цифр. Мы пытаемся сопоставить всю строку либо путем сопоставления одной запятой (представляющей 0 , которая запускает новый прогон), либо путем сопоставления предыдущей вещи, которой предшествует дополнительная 1, которая работает, только если текущая цифра является преемницей предыдущей.

Мартин Эндер
источник
3

TI-Basic (серия 83), 25 байтов (49 символов)

:min(seq(min(cumSum(Ans=I)≤cumSum(Ans=I-1)),I,1,9

Как это работает

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

Для каждого I, cumSum(Ans=I)вычисляет список того , сколько раз Iпроизошли в каждом начальном сегменте, так min(cumSum(Ans=I)≤cumSum(Ans=I-1))только 1 , если в любом положении, мы видели , по I-1крайней мере , столько раз , сколько I. Общее выражение 1всякий раз, когда это верно для каждого I.

Миша лавров
источник
3

JavaScript (ES6), 61 45 40 байт

Принимает ввод в виде списка.

a=>a.every(k=>a[~k]=!k|a[-k]--&&-~a[~k])

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

Показать фрагмент кода

Как?

Для каждого значения 0 ... 9 мы отслеживаем количество доступных стеков с предыдущей картой сверху. Эти счетчики хранятся от [-9] до [0] , где a [] - исходный входной массив. Единственный счетчик, который сталкивается с входными данными, это [0] , но нас это не волнует, потому что 1) карты с меткой 0 всегда разрешены и в любом случае должны обрабатываться отдельно и 2) входное значение a [0 ] обрабатывается до того, как появится возможность его обновления.

a => a.every(k =>  // given the input array a, for each card k in a:
  a[~k] =          // the card is valid if:
    !k |           //   - it's a 0 or
    a[-k]-- &&     //   - there's at least one stack with the card k-1 atop
    -~a[~k]        // in which case we allow a new card k+1 and go on with the next card
)                  // otherwise, every() fails immediately
Arnauld
источник
Ты быстрее меня: o
Leaky Nun
@LeakyNun Вы, должно быть, отсутствовали в течение 20 минут ...;)
Арно
2

MATL , 16 байт

0*GQ"@yQy=f1)(]a

Ввод представляет собой массив чисел.

Код выводится 1в STDOUT, если ввод является наращиваемым, или завершается с ошибкой, и пустой вывод в STDOUT, если ввод не является наращиваемым.

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

Луис Мендо
источник
2

Mathematica, 80 байт

Catch[Fold[#~Join~{-1}/.{{p___,#2-1,q___}:>{p,#2,q},-1:>Throw[1<0]}&,{},#];1>0]&
Юнг Хван Мин
источник
2

R , 88 байт

function(d){s={}
for(e in d)if(!e)s=c(s,0)else{k=match(e,s+1)
if(is.na(k))T=F
s[k]=e}
T}

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

Функция, которая принимает вектор R; возвращает TRUEдля наращиваемых и не FALSEсуммируемых.

Объяснение:

function(d){
 s <- {}              # initialize the stacks as empty
 for(e in d){         # iterate over the deck
  if(!e)              # if e is zero
   s <- c(s,0)        # start a new stack
  else {              # otherwise
   k <- match(e,s+1)  # find where e should go in s, NA if not there
   if(is.na(k))       # if no match (unstackable)
    T <- F            # set T to F (False)
   s[k] <- e          # set s[k] to e
  }
 T                    # return the value of T, which is TRUE by default and only gets changed in the loop to F.
}
Giuseppe
источник
2

Ним, 133 байта

proc s(d:seq[int]):int=
 var
  t= @[0]
  r=1
 for c in d:(t.add(0);var f=0;for i,s in t.pairs:(if s==c:(t[i]=c+1;f=1;break));r*=f)
 r

1если он работает; 0если это не так.

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

Quelklef
источник
1

Haskell , 77 75 байт

import Data.List
g[]=1<3
g(x:r)|s<-r\\[x-1]=g r&&(x<1||s/=r&&g s)
g.reverse

Попробуйте онлайн! Использование: g.reverse $ [0,1,2]. Возвращает Trueдля наращиваемых входов и в Falseпротивном случае.

Это рекурсивное решение, которое пересекает заданный список задом наперед. Он реализует наблюдение, что

  • пустой список является наращиваемым.
  • непустой список с префиксом rи последним элементом xявляется стекируемым, если rон стекируемый и либо xравен нулю, либо оба x-1появляются в rи rс x-1удаленным, также стекируемый.
Laikoni
источник
1

Java 8, 168 150 142 байта

a->{int x[]=new int[a.length],s=0,i;a:for(int n:a){if(n<1){s++;continue;}for(i=0;i<s;i++)if(x[i]==n-1){x[i]=n;continue a;}return 0;}return 1;}

Возвращает 0/ является 1ли он правильно составляемым или нет.

Объяснение:

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

a->{                         // Method with integer-array parameter and integer return-type
  int x[]=new int[a.length], //  Array for the stacks, (max) size equal to input-size
      s=0,                   //  Amount of stacks, starting at 0
      i;                     //  Index integer
  a:for(int n:a){            //  Loop (1) over the input
    if(n<1){                 //   If the current item is a zero:
      s++;                   //    Increase amount of stacks `s` by 1
      continue;}             //    And go to the next iteration
    for(i=0;i<s;i++)         //   Inner loop (2) over the stacks
      if(x[i]==n-1){         //    If a top item of a stack equals the current item - 1:
        x[i]=n;              //     Set this item in the stacks-array
        continue a;}         //     And go to the next iteration of loop (1)
    return 0;                //   If we haven't encountered a `continue`, return 0
  }                          //  End of loop (1)
  return 1;                  //  Return 1 if we were able to correctly stack everything
}                            // End of method
Кевин Круйссен
источник
1

C 248 байт

Примечание. Чтобы напечатать возвращаемый статус, введите «echo $ status» в терминал

Статус возврата 0: не стекируется

Статус возврата 1: наращиваемый

Объяснение: Увеличивает элемент массива с индексом, эквивалентным самой последней цифре в стеке. Затем программа проверяет, больше ли этот только что увеличенный элемент массива, чем предшествующий ему элемент. Если это так, возвращает 0. Иначе, если программа доходит до конца массива, возвращает 1.

 main(int argc, char ** argv)
{
    static int stack[10];

    while ( *++argv != 0x0 )
    {
        stack[**argv - 0x30]++;

        if ( **argv - 0x30 > 0 )
        {
            if ( stack[**argv - 0x30] > stack[**argv - 0x30 - 1] )
            {
                return 0;
            }

        }

    }   

    return 1;
}
Т. Салим
источник
3
Добро пожаловать в Code Golf! Ваш код и ваш счет должны совпадать, поэтому обязательно предоставьте полную версию вашего кода. Версия без присмотра является опциональной.
Стивен
0

Желе , 15 байт

œp@ŒQẎµ0rṀ⁼Qµ¿Ẹ

Монадическая ссылка, берущая список неотрицательных целых чисел и возвращающая, 0если она может быть наращиваемой или 1не складываемой.

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

Как?

œp@ŒQẎµ0rṀ⁼Qµ¿Ẹ - Link: list
             ¿  - while loop:
      µ     µ   - ...condition chain:
       0        -      literal zero
         Ṁ      -      maximum of current list
        r       -      inclusive range = [0,1,2,...,max(list)]
           Q    -      de-duplicate list (unique values in order of appearance)
          ⁼     -      equal?
                - ...do:
   ŒQ           -      distinct sieve (1s at first occurrences 0s elsewhere)
  @             -      use swapped arguments:
œp              -        partition (the list) at truthy values (of the distinct sieve)
     Ẏ          -      tighten (makes the list flat again ready for the next loop)
              Ẹ - any truthy? 1 if the resulting list has any non-zero integers remaining
                -           - effectively isNotEmpty for our purposes since a list of only
                -             zeros gets reduced to an empty list via the loop.
Джонатан Аллан
источник
Ваш ход: P: P
Утренняя монахиня
Хех, ну, я сомневаюсь, что я бы побил 11 (или 10 ?!) и должен был заснуть: D
Джонатан Аллан
0

Japt , 16 байт

£=k_¥T©°T}T=0ÃUd

Проверьте это онлайн! Выходы falseдля стекируемых, trueдля не стекируемых.

объяснение

 £   = k_  ¥ T© ° T}T=0Ã Ud
UmX{U=UkZ{Z==T&&++T}T=0} Ud    Ungolfed
                               Implicit: U = input array
UmX{                   }       For each item X in the array:
                    T=0          Set T to 0.
      UkZ{         }             Remove the items Z where
          Z==T&&++T              Z == T (and if so, increment T).
                                 This has the effect of removing the largest stack.
    U=                           Reset U to the result.
                               This process is repeated U.length times, which is
                               evidently enough to handle any U.
                         Ud    Return whether there are any truthy items in U.
                               Any items not part of a stack are non-zero/truthy,
                               so this works for every possible case.
ETHproductions
источник
0

05AB1E , 25 байтов

ηε[DõQ#ZƒDNåiNõ.;Dëˆ#]¯OĀ

Задача не выглядит такой сложной, но в 05AB1E она довольно сложная (по крайней мере, для меня ...)

Выходы, 0если они могут быть стекируемыми, а 1если нет.

Попробуйте онлайн или проверьте все контрольные примеры .

Объяснение:

η             # Prefixes of the (implicit) input
              #  i.e. '012031' → ['0','01','012','0120','01203','012031']
              #  i.e. `021` → ['0','02','021']
 ε            # Map each to:
  [           # Start an infinite inner loop
   D          # Duplicate the current value
    õQ#       # If it's an empty String, stop the infinite loop
   Z          # Get the maximum (without popping)
              #  i.e. '01203' → 3
              #  i.e. '02' → 2
    ƒ         # Inner loop `N` in the range [0,max]
     D        # Duplicate the current value
      Nåi     # If it contains the current digit `N`
              #  i.e. '01203' and 1 → 1 (truthy)
              #  i.e. '02' and 1 → 0 (falsey)
         Nõ.; # Remove the first one (by replacing the first `N` with an empty string)
              #  i.e. '1203' and 1 → '203'
         D    # And duplicate it again for the next iteration of the inner loop
      ë       # Else (does not contain the digit `N`):
       ˆ      # Push `N` to the global stack
        #     # And break the infinite loop
 ]            # Close the if-else, inner loop, infinite loop, and mapping (short for `}}}}`)
  ¯           # Push the global stack
   O          # Take the sum
              #  i.e. [] → 0
              #  i.e. ['2'] → 2
    Ā         # And get the trutified value of that (which we implicitly output as result)
              #  i.e. 0 → 0
              #  i.e. 2 → 1
Кевин Круйссен
источник
0

Java 8, 87 байт

Вместо того, чтобы строить стеки, я просто вычисляю, является ли элемент стекируемым на предыдущих элементах, и возвращаю 0, когда встречается не стекируемый элемент. Если я достигну конца, вся строка будет наращиваемой и возвращается 1:

s->{int l[]=new int[10];for(int n:s)if(n!=0&&l[n]>=l[n-1]||l[n]++<0)return 0;return 1;}

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

Объяснение:

s->{
  int l[]=new int[10];                # initialise the counts of each digit encountered prefix of element, all initialised to 0
  for(int n:s)                        # Iterate over all entries in input
    if(n!=0&&l[n]>=l[n-1]||++l[n]<0)  # Check if the element is stackable on the previous elements. Last check is always evaluated and false, but the sideeffect is to add the element to the handled, prefixed element og the next element.  
      return 0;                       # Unstackable
  return 1;                           # No unstackable elements, so the result is stackable
}
tfantonsen
источник