Внедрить Lazy Drop Sort

26

Эта проблема уже описывает дропсорт. Тем не менее, я немного ленив, и мне действительно нужно, чтобы мой массив был немного более отсортирован, чем раньше, его не нужно сортировать полностью .

В Drop Sort мы отбрасываем каждый элемент меньше, чем любой элемент перед ним. В Lazy Drop Sort мы отбрасываем каждый элемент меньше, чем строго предшествующий ему.

Вот пример. Рассмотрим следующий массив:

8 6 9 9 7 2 3 8 1 3

Давайте отметим каждый элемент меньше, чем предыдущий.

8 6 9 9 7 2 3 8 1 3
  ^     ^ ^     ^

Обратите внимание, как ни 3было отмечено, ни последний 8. Все они больше, чем один элемент слева от них.

Завершив алгоритм, удалив отмеченные элементы, получим:

8 9 9 3 8 3

Это в основном выглядит более сортированным. Своего рода. Мне лень.

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

Ввод - это массив не менее 1 положительного целого числа от 1 до 9, поэтому вы можете также взять строку цифр.

Это код-гольф , побеждает меньше байтов!

Дополнительные тестовые случаи:

1
1

1 2 3
1 2 3

5 3 1
5

1 2 3 2 1
1 2 3

1 1 1 9 9 9 1 1 1 9 9 9 1 1 1
1 1 1 9 9 9 1 1 9 9 9 1 1

9 9
9 9

5 2 4 2 3
5 4 3
code-golf array-manipulation sorting Павел
источник
Это может быть функция или программа?
rafa11111
@ rafa11111 Либо в порядке
Павел
Если это функция, может ли входной массив быть жестко закодирован в основной программе? И можно ли передать длину массива в качестве входных данных для функции?
rafa11111
@ rafa11111 Вход не может быть жестко закодирован в самой функции. Неважно, как функция получает этот вход в вашей тестовой программе. Вы можете взять длину массива, только если вы используете C / C ++ или другой язык, где это единственный способ определить длину массива.
Павел

Ответы:

15

JavaScript (ES6), 28 25 байт

Сохранено 3 байта благодаря @Shaggy

a=>a.filter(n=>~-a<(a=n))

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

Arnauld
источник
2
n=>p<=nвыглядел бы потрясающе ;-)
ETHproductions
4
@ETHproductions Для +4 байта, (n=p)=>p<=(p=n)отлично работает;)
Арно
этот ответ поражает меня, почему он не взрывается при попытке доступа pв первый раз, когда он еще не определен?
Брайан Х.
1
@ Shaggy Это выглядит безопасно. Обновлюсь, когда я вернусь к компьютеру. Благодарность!
Арно,
2
@Pavel aизначально установлен на входной массив и a-1может привести к NaN(если он не содержит единственное целое число, в этом случае он приводится к этому целому числу).
Арно,
6

MATL , 9 8 байт

Сохранено один байт благодаря Джузеппе.

0yd0<h~)

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

Объяснение:

0                 % Push a zero
 y                % Implicitly grab the input and duplicate it.
                  % Stack: [8 6 9 9 7 2 3 8 1 3], 0, [8 6 9 9 7 2 3 8 1 3]
  d               % The difference between each number of the last element:
                  % Stack: [8 6 9 9 7 2 3 8 1 3], 0, [-2, 3, 0, -2, -5, 1, 5, -7, 2]
   0<             % Which are negative?
                  % Stack: [8 6 9 9 7 2 3 8 1 3], 0, [1 0 0 1 1 0 0 1 0]
     h            % Concatenate. Stack: [8 6 9 9 7 2 3 8 1 3], [0 1 0 0 1 1 0 0 1 0] 
      ~           % Negate. Stack: [8 6 9 9 7 2 3 8 1 3], [1 0 1 1 0 0 1 1 0 1]
       )          % Index. Stack: [8 9 9 3 8 3]
Стьюи Гриффин
источник
5

Perl 5 .10.0 + -nl, 16 байт

$f>$_||say;$f=$_

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

Wastl
источник
1
Перевод на Perl 6perl6 -ne '$/>$_||.say;$/=$_'
Брэд Гилберт b2gills
@Brad perl6 - это другой язык (он даже не совместим с предыдущими версиями).
Wastl
Я написал один, который был более идиоматическим Perl 6, но он был длиннее. Также одна из причин, которые я публикую здесь, - показать язык и объяснить его. Публикация этого перевода только показывает, что это немного более многословная версия Perl. В основном это не удовлетворяет ни одной из причин, почему я размещаю на этом сайте.
Брэд Гилберт b2gills
5

Haskell, 29 байт

f s=[b|(a,b)<-zip(0:s)s,a<=b]

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

гордый хаскеллер
источник
4

Stax , 5 байт

âÿ╠╦░

Запустите и отладьте это онлайн

Распаковывая, распаковывая и комментируя код, мы получаем это.

Z   Push a zero under the input
f   Use the rest of the program as a filter on the input.  Output passing elements.
>   Current element is greater than previous?
_~  Push current element to the input stack; when the main stack is empty, pops fall back to this
!   Logical not; applies to the result of the greater-than

Запустите этот

Упорядочить инструкции неудобно, но есть причина для этого. Упаковка исходного кода Stax не всегда дает один и тот же размер вывода для одного и того же размера ввода. По сути, у вас есть шанс сохранить байт, если последний символ источника имеет более низкий код символа. Ну, !есть один из самых низких кодов, которые вы можете получить для печатного символа. (В частности 33) Многие 6-байтовые программы ASCII Stax не могут упаковать меньше. Но если они заканчиваются на !, то они могут. Таким образом, причина этого конкретного порядка команд состоит в том, чтобы гарантировать, что логическое не заканчивается в конце программы.

рекурсивный
источник
4

J, 12 байт

#~1,2&(<:/\)

Объяснение:

#~1,2&(<:/\)    | Whole function, executed as a hook
       <:/      | Distribute <: (greater or equal) over an array
    2&(   \)    | Apply to each sub array of length 2
  1,            | Append a 1 to the front
#~              | Choose elements from the original array

Примеры:

    2&(<:/\) 8 6 9 9 7 2 3 8 1 3
0 1 1 0 0 1 1 0 1
    1,2&(<:/\) 8 6 9 9 7 2 3 8 1 3
1 0 1 1 0 0 1 1 0 1
    (1 0 1 1 0 0 1 1 0 1) # 8 6 9 9 7 2 3 8 1 3
8 9 9 3 8 3
    f =: #~1,2&(<:/\)
    f 8 6 9 9 7 2 3 8 1 3
8 9 9 3 8 3

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

Bolce Bussiere
источник
Отличное решение! Я добавил ссылку TIO для вашего кода.
Гален Иванов
4

Желе , 6 байт

>Ɲ0;¬×

I / O находится на строках.

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

Деннис
источник
Мне любопытно, почему оперируют со строками, а не с массивами? Мне сказали, что Джелли плохо справляется со своими обязанностями.
Павел
2
Это. ×не должен работать на повторение символов, но это работает.
Деннис
4

Java 8, 66 55 48 байт

l->{for(int i=0;;)if(i>(i=l.next()))l.remove();}

-11 байт после подсказки от @ OlivierGrégoire .
-7 больше байтов благодаря @ OlivierGrégoire .

Объяснение:

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

l->{                     // Method with Integer-ListIterator parameter and no return-type
  for(int i=0;;)         //  Loop over all items
    if(i>(i=l.next()))   //   If the current item is larger than the next
      l.remove();}       //    Remove this next item
Кевин Круйссен
источник
Почему все начинают использовать, ~0когда это в принципе -1. Лично я бы выбрал более интуитивное решение, если бы количество байтов было такой же длины (за исключением while(...)vs for(;...;), в этом случае я предпочитаю for. Хотя, спасибо еще за -7 байт. :)
Кевин Круйссен,
Это потому, что я плохо с 2-мя комплементами ... Я так плох, что хотел иметь в виду Integer.MIN_VALUE(что тогда 1<<31, я думаю ...) ;-)
Оливье Грегуар
4

Октава , 21 байт

@(x)x(~[0,diff(x)<0])

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

Объяснение:

Возьмите вектор в xкачестве входных данных и создайте вектор [0, diff(x)<0], где diff(x)есть вектор с разницей между всеми соседними элементами. Оставьте только те, которые являются отрицательными, сравнивая его с нулем, давая нам список всех элементов, которые мы хотим отбросить.

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

Стьюи Гриффин
источник
4

V , 25 байтов

òjälá k$yl+@"òç-/d
ç /dw

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

HexDump:

00000000: f26a e46c e120 6b24 796c 2b40 2218 f2e7  .j.l. k$yl+@"...
00000010: 2d2f 640a e720 2f64 77                   -/d.. /dw

Худший язык для работы. Но я сделал это за вызов .

DJMcMayhem
источник
6
Примечание стороны: Ойала испанский для мы надеемся .
Деннис
2
@dennis Это круто. Для чего нужен k$yl+@"òç-/dиспанский?
DJMcMayhem
7
k$yl+@"òç-/dможет быть в широком смысле переведено как Ой, кто, черт возьми, оставил эту дверь шкафа открытой?
Луис Мендо
3

Треугольность , 71 байт

.....).....
....IEL....
...)rFD)...
..2+)IE)w..
.+h)2_stDO.
={M)IEm}...

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

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

) IEL) rFD) 2+) IE) w + h) 2_stDO = {M) IEm} - полная программа.
) IE - получить 0-й вход I и оценить его.
   L) R - И нажмите диапазон [0 ... длина I).
      F {- Фильтровать целые числа в этом диапазоне, которые удовлетворяют:
       D) 2+) IE) w + h) 2_stDO = - Это условие. Запускает каждый элемент E на отдельном
                                    складывать и отбрасывать те, которые не соответствуют критериям.
       D) 2+ - Дублируйте и добавьте 2 ко второй копии.
           ) IE - Получить я снова.
              ) - Вставьте 0 в стек.
               w - обернуть 0 в списке. [0]
                + - добавить его к I.
                 ч - зав. Обрежьте элементы после индекса E + 2.
                  ) 2_ - буквальный -2.
                     ст - хвост.
                       DO = - Проверить, является ли результат инвариантным по отношению к сортировке.
                           M) IEm} - Последняя часть: индексирование на входе.
                           M} - для каждого индекса, который удовлетворяет условиям:
                            ) IEm - Получить элемент I в этой позиции.
Мистер Xcoder
источник
2
Из любопытства (так как вы являетесь создателем Triangularity): почему бы не сделать что-то похожее на Hexagony / Cubically, где кусок кода автоматически заполняется неактивными точками? Таким образом, эта программа будет )IEL)rFD)2+)IE)w+h)2_stDO={M)IEm}расширена до вашего текущего ответа?
Кевин Круйссен,
@KevinCruijssen Поскольку я фактически планировал сделать Triangularity 2D esolang, но я отказался от этой идеи, поэтому я просто придерживался своего предыдущего шаблона. Я думаю, что вскоре я внесу некоторые важные изменения, когда выпущу Triangularity v2. (Также довольно забавно играть в гольф в его нынешнем виде, потому что простое 1-байтовое встроенное сохранение может вместо этого сэкономить вам 20: D ... Это также применяется задним числом при исправлении
ошибок
Ну, даже если вы планируете выпустить его как 2D esolang, мой комментарий все еще остается (несколько). )IEL)rFD)2+)IE)w+h)2_stDO={M)IEm}будет ваш код, он будет расширяться до вашего текущего шаблона, а затем выполнять 2D-команды на этом расширенном шаблоне. РЕДАКТИРОВАТЬ: .....).....\n....IEL....\n...)rFD)...\n..2+)IE)w..\n.+h)2_stDO.\n={M)IEm}...и .....).........IEL.......)rFD).....2+)IE)w...+h)2_stDO.={M)IEm}...и )IEL)rFD)2+)IE)w+h)2_stDO={M)IEm}все три будут одной и той же программы.
Кевин Круйссен
3

Python , 40 байт

f=lambda h,*t:t and h+f(*t)[h>t[0]:]or h

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

Ввод в виде набора символов.

Python 3 , 41 байт

p=''
for x in input():x<p or print(x);p=x

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

Строковый ввод.

Python 2 , 41 байт

for x in input():
 if x>=id:print x
 id=x

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

Строковый ввод, просто потому что строки больше чем, idа числа меньше.

XNOR
источник
3

Wolfram Language (Mathematica) , 33 байта

Pick[#,Arg[#-{0}~Join~Most@#],0]&

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

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

Код # - {0}~Join~Most@#превращает массив {a,b,c,d,e,f}в {a,b-a,c-b,d-c,e-d,f-e}. Применение Argк этому устанавливает отрицательные числа к Piи неотрицательные числа к 0.

Pick[#, ..., 0]&выбирает записи #where ...has a 0: в нашем случае, именно те элементы, которые дают неотрицательное число, когда вы вычитаете предыдущий элемент. Другими словами, это именно те записи, которые мы хотим сохранить при lazydropsorting.

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

Чудо , 27 байт

-> ':1.!> 'sS#<=.cns2.++[0]

Пример использования:

(-> ':1.!> 'sS#<=.cns2.++[0])[8 6 9 9 7 2 3 8 1 3]

объяснение

Безголовая версия:

(map get 1).(fltr sS <=).(cns 2).(++ [0])

Prepend 0, получить список последовательных пар, сохранить элементы списка, где первое число <= второе число, получить второе число каждой пары.

Mama Fun Roll
источник
3

Wolfram Language (Mathematica) , 20 байтов

#&@@@Split[#,##>0&]&
(* or *)
Max/@Split[#,##>0&]&

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

объяснение

Input = {8, 6, 9, 9, 7, 2, 3, 8, 1, 3}

Split[#,##>0&]

Группируйте последовательные элементы, которые строго уменьшаются: {{8, 6}, {9}, {9, 7, 2}, {3}, {8, 1}, {3}}

#&@@@

Возьмите первый элемент каждого: {8, 9, 9, 3, 8, 3}

Юнг Хван Мин
источник
##>0причудливо и все такое, но здесь ничего не сохраняется #>#2;) (что заставит вашу программу работать с произвольными целыми числами, хотя это и не требуется).
Мартин Эндер
3

SWI-Пролог, 44 байта

[A,B|C]-[A|E]:-B<A,[B|C]-[B|E];[B|C]-E. L-L.

Использование: Вызовите « List -X», где List - заключенный в скобки список, разделенный запятыми, например [1,4,5,1,11,6,7].

ashtraypettingzoo
источник
1
Добро пожаловать на сайт! :)
DJMcMayhem
2

APL + WIN, 14 байтов

Запрашивает ввод на экран вектора целых чисел.

(1,1>2-/v)/v←⎕
Грэхем
источник
2

05AB1E , 6 байтов

ĆÁü›_Ï

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

объяснение

Ć        # append the head of the list
 Á       # rotate right
  ü›     # apply pair-wise greater-than
    _    # logical negate each
     Ï   # keep elements of input that are true in this list
Emigna
источник
2

Котлин , 39 байт

a->a.filterIndexed{i,v->i<1||v>=a[i-1]}

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

Отфильтруйте элементы, которые являются либо первым элементом (индекс == 0, либо даже более короткий индекс <1) ИЛИ текущее значение больше или равно предыдущему элементу (a [i-1]).

Makotosan
источник
2

К4 , 10 байт

Решение:

x_/|&<':x:

Пример:

q)k)x_/|&<':x:8 6 9 9 7 2 3 8 1 3
8 9 9 3 8 3

Объяснение:

Найти индексы, где элемент меньше, чем предыдущий, удалить эти индексы из ввода

x_/|&<':x: / the solution
        x: / store input as x
     <':   / less-than each-previous
    &      / indices where true
   |       / reverse
 _/        / drop-over
x          / the input
streetster
источник
2

Атташе , 24 байта

{Mask[1'(Delta!_>=0),_]}

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

объяснение

Maskвыбирает все элементы из второго аргумента, которые соответствуют истинным элементам в первом аргументе. 1'(Delta!_>=0)вычисляет индексы, которые соответствуют элементам, которые должны быть в конечном массиве.

Другие попытки

28 байт (без точек): ~Mask#(1&`'##Delta#`>=#C[0])

32 байта: {Mask[1'(&`<= =>Slices[_,2]),_]}

Конор О'Брайен
источник
2

C # (.NET Core) , 33 + 18 = 51 байт

x=>x.Where((a,n)=>n<1||x[n-1]<=a)

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

в основном это утверждение, где x - это первое целое в массиве, или оно больше или равно предыдущему числу, сохраните его. Остальное брось.

Dennis.Verweij
источник
1
Вы можете вернуть IEnumerable. Нет ToArray()необходимости
Павел
@Pavel Мне нужно добавить дополнительную ссылку System.Collections, и это сведет на нет все байты, сохраненные для удаления ToArray().
Dennis.Verweij
Нет, поскольку IEnumerableв ответе вы не будете ссылаться , просто используйте его в качестве типа возвращаемого значения.
Павел
@Pavel хорошо, спасибо, иногда я немного не уверен, когда считать байты или нет ... извините
Dennis.Verweij
1

Swift 4 , 56 55 байт

{var l=0;print($0.filter{($0>=l,l=$0).0})}as([Int])->()

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

объяснение

{var l=0;           // Declare variable l
print($0.filter{(   // Print every element e in the input
  $0>=l,            //   where e >= l
  l=$0).0})         //   And set l to e
}as([Int])->()      // Set the input type to integer array
Герман Л
источник
1

Желе , 9 байт

0;>ƝżµḢÐṂ

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

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

0;>ƝżµḢÐṂ
   Ɲ       For each adjacent pair in the input...
  >        ...is the first element greater than the second? (yields a list of 0/1)
0;         prepend a zero to this list (always keep the first element)
    ż      zip with the input
     µ     new monadic link
       ÐṂ  keep elements of the list with minimal value of... (Ðḟ would have worked here and been slightly more clear but I'll leave it as it is)
      Ḣ    ...their first element
dylnan
источник
1

Brain-Flak , 136 , 120 байт

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

Здесь он отформатирован и «читабелен» .

((()))
{
    {}

    ([{}]({}))

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

    {
        {}(({})<>)(())(<>)
    }

    {}

    ([][()])

}{}{}<>

{
    {}
    ({}<>)<>
}<>

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

DJMcMayhem
источник