Сортировка с потерями (реализация Dropsort)

61

Dropsort , разработанный Дэвидом Морган-Маром, является примером линейного «алгоритма сортировки», который создает список, который фактически отсортирован, но содержит только некоторые из исходных элементов. Любой элемент, который не меньше, чем максимум элементов, предшествующих ему, просто удаляется из списка и удаляется.

В этой задаче вам будет дан список целых чисел в качестве входных данных (STDIN или аргумент функции, вы должны поддерживать как минимум диапазон 8-битных целых чисел со знаком.) Ваша задача - отбросить их, а затем вывести остальные элементы в заказ.

Вы можете предположить, что список не пуст.

Это код гольф, поэтому выигрывает самая короткая программа.

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

Input             Output
1 2 5 4 3 7       1 2 5 7
10 -1 12          10 12
-7 -8 -5 0 -1 1   -7 -5 0 1
9 8 7 6 5         9
10 13 17 21       10 13 17 21
10 10 10 9 10     10 10 10 10

Leaderboard

var QUESTION_ID=61808,OVERRIDE_USER=39022;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

SuperJedi224
источник
1
Это чек highest < current? Или highest <= current?
Морган Трепп
7
Сохранить текущий элемент, если highest (so far)<=current.
SuperJedi224
Можно ли предположить, что в списке будет хотя бы один элемент?
Lirtosiast
@ThomasKwa: Да.
SuperJedi224
19
Повышение эффективности Dropsorts может сэкономить компании много денег, если использовать ее в системе начисления заработной платы.
PyRulez

Ответы:

42

APL, 9 байт

⊢(/⍨)⊢=⌈\

Это монадическая последовательность функций со схемой:

┌─┼───┐  
⊢ ⍨ ┌─┼─┐
┌─┘ ⊢ = \
/     ┌─┘
      ⌈  

Версия без поезда

{⍵/⍨⍵=⌈\⍵}

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

Обратите внимание, что J-решение Мартина Бюттнера имеет такую ​​же длину и было опубликовано первым.

lirtosiast
источник
41
Бонусные баллы, потому что это выглядит мило.
Саммитч
22
Код выглядит как недовольный чувак, стреляющий в лоскут кота
slebetman
2
Я не знаю много о подсчете байтов и о том, какая кодировка предназначена для использования, но в соответствии с mothereff.in/byte-counter и meta.codegolf.stackexchange.com/questions/4944/… это 17 байтов и bytesizematters. com это 13
DLeh
3
@DLeh Это в UTF-8. APL имеет свою собственную унаследованную кодировку, которая составляет 1 байт на символ APL, до того, как существовал юникод.
Исаак
3
@DLeh bytesizematters использует составленный алгоритм для подсчета байтов, который не соответствует (и не может ) соответствовать фактической кодировке.
Деннис
21

J 10 9 байт

#~(=>./\)

Рабочая версия моей идеи CJam (меньше байтов). Например:

   f =: #~(=>./\)
   f 10 10 10 9 10
10 10 10 10
   f 1 2 5 4 3 7
1 2 5 7

объяснение

Сначала мы получаем максимум каждого префикса:

    >./\

(Здесь >.это оператор максимума, /складывает этот оператор в список и \получает все префиксы ввода.)

Затем мы сравниваем исходный список с этими максимумами на равенство:

  (=>./\)

И, наконец, мы выбираем все элементы, для которых этот список логических результатов дал 1:

#~(=>./\)
Мартин Эндер
источник
16

Хаскелл, 28

foldr(\x l->x:filter(x<)l)[] 

Анонимная функция. Назови это как

foldr(\x l->x:filter(x<)l)[] [-7, -8, -5, 0, -1, 1] 
[-7,-5,0,1]

Эквивалент рекурсии

f[]=[]
f(x:l)=x:filter(x<)(f l)

Итеративно переведенный, мы перебираем элементы, и для каждого видимого мы удаляем те, которые меньше его, из остальной части списка, который мы перебираем. Спасибо Антисфену за сохраненный байт (x<).

XNOR
источник
Почему бы не карри лямбда? Если сохранить несколько символов ...
MathematicalOrchid
@MaturgicalOrchid Если вы имеете в виду foldr(\x->(x:).filter(>=x))[], это оказывается одинаковой длины.
xnor
Ах. Я только что увидел фильтр в конце и подумал: "Эй, ты можешь это сделать!" Мне не приходило в голову, что x:заставляет вас добавлять оператор точки. Ну да ладно ...
Математический
1
это все O(n^2)же. много ненужных сравнений. ;-(
гордый haskeller
Почему бы не изменить (> = x) на (x <)? Это спасет 1 байт
Антисфен
10

Python 2, 49

f=lambda a:a and f(a[:-1])+a[-1:]*(a[-1]==max(a))
feersum
источник
1
Это потрясающе.
Морган Трепп
1
@ThomasKwa Проблема в том, как прекратить рекурсивные вызовы. Вам нужен пустой регистр, даже если входные данные исключают этот регистр.
Бакуриу
проблема в том, что он не является линейным из-заmax(a)
njzk2
1
@ njzk2 Задача не требует выполнения реализаций за линейное время.
feersum
3
@ njzk2 Хорошие коды заканчиваются последними!
feersum
10

JavaScript (ES6), 29

Злоупотребление стандартным преобразованием типов в javascript, массив в число:

  • массив всего 1 число => это число
  • любой другой массив => NaN

d=l=>l.filter(v=>l>v?0:[l=v])

// TEST
console.log=x=>O.innerHTML+=x+'\n'

;[
  [[1,2,5,4,3,7], [1,2,5,7]]
, [[10,-1,12], [10,12]]
, [[-7,-8,-5,0,-1,1], [-7,-5,0,1]]
, [[9,8,7,6,5], [9]]
, [[10,13,17,21], [10,13,17,21]]
, [[10,10,10,9,10], [10,10,10,10]]
].forEach(t=>( i=t[0],r=d(i),x=t[1],              
  console.log('Test '+i+' -> '+r+(r+''==x+''?' OK':' Fail (expected '+x+')')))
)
<pre id=O></pre>

edc65
источник
Ух ты. Я думал, что 38 байтов были приблизительно лучшими из возможных; видимо я был очень неправ. +1
ETHproductions
Настольные тесты. Приятно!
Slebetman
8

Октава, 27 19 байт

@(a)a(cummax(a)==a)
alephalpha
источник
7

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

⊇ᶠ↔ᵒt

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

Желе , 5 байт

ŒPUÞṪ

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

объяснение

⊇ᶠ↔ᵒt    ŒPUÞṪ
⊇ᶠ       ŒP       On all subsequences of {the input}
   ᵒ        Þ     sort by
  ↔        U      their reverse
    t        Ṫ    then take the last element (i.e. the maximum as given by the sort)

Это редкая ситуация: я использую алгоритм, который (насколько я могу судить по быстрому отбору) пока что никто не использует, и он каким-то образом заканчивается одинаковой длиной в двух совершенно разных языках игры в гольф с очень разным синтаксисом и встроенные наборы, с соответствием между программами 1: 1 (команды даже в том же порядке!). Таким образом, казалось, что было бы более целесообразно объединить их - в некотором смысле, это одна и та же программа, и я написал ее на обоих языках, чтобы увидеть, какой из них был короче, - чем представлять их отдельно.

Основная идея здесь заключается в том, что дропсорт списка - это его подпоследовательность с лексикографически максимальным обратным. Как ни странно, ни Brachylog, ни Jelly не имеют встроенной функции для поиска максимума по определенной функции (Jelly имеет встроенную функцию, которая возвращает все максимумы по определенной функции, но при этом возвращался бы одноэлементный список, содержащий результат, а не сам результат, и и даже не короче, чем делать это так). Таким образом, вместо этого мы генерируем все возможные подпоследовательности, сортируем по обратному, принимаем последнее.

Причина, по которой работает «лексикографически максимальное обратное направление», заключается в том, что выбранный выход должен заканчиваться (поэтому его обратный ход должен начинаться) с наибольшего числа в списке входных данных (легко видеть, что выход с дропсортированием всегда будет заканчиваться этим), и, таким образом, может ничего после этого не содержит (потому что принятие подпоследовательностей сохраняет порядок). Повторите индуктивно, и мы получим определение DropSort.

ais523
источник
6

Mathematica, 26 байт

DeleteDuplicates[#,#>#2&]&
celtschk
источник
2
Я не знаю Mathematica, но что-то, что вызывает DeleteDuplicates, не похоже на возвращение {10, 10, 10, 10}для ввода{10, 10, 10, 9, 10}
Деннис
2
@ Денис: Да, я проверял это. Хитрость в том, что я прохожу "больше, чем" в качестве теста "эквивалентности". Да, это неправильное использование этой функции, но она работает, и в любом случае Code Golf - это не совсем лучшие практики программирования.
celtschk
2
Хорошо, несмотря на то, что предполагает название, DeleteDuplicatesс двумя аргументами кажется простым фильтром.
Деннис
5

R, 29 26 байт

function(x)x[x>=cummax(x)]

Это создает функциональный объект, который принимает вектор xи возвращает xпосле удаления все элементы, по крайней мере, такие же, как кумулятивный максимум x.

Сохранено 3 байта благодаря flodel!

Алекс А.
источник
Форма функции будет короче.
Flodel
@flodel Ты абсолютно прав. Спасибо!
Алекс А.
4

К, 11 байт

{x@&~x<|\x}

В бою:

  f: {x@&~x<|\x}
  f'(1 2 5 4 3 7
     10 -1 12
     -7 -8 -5 0 -1 1
     9 8 7 6 5
     10 13 17 21
     10 10 10 9 10)

(1 2 5 7
 10 12
 -7 -5 0 1
 ,9
 10 13 17 21
 10 10 10 10)
Johne
источник
{x@&~<':x}на байт короче.
kirbyfan64sos
@ kirbyfan64sos: использование каждого приоритета не дает правильного результата. Рассмотрим входной случай 3 4 2 2 5.
JohnE
Ах я вижу. Исправление было бы {x@&~<':x}/, но это та же длина.
kirbyfan64sos
3

Java, 82 байта

void f(int[]a){int m=a[0];for(int n:a){System.out.print(m>n?"":n+" ");m=n>m?n:m;}}

Вот простой цикл вывода. Он просто сохраняет максимум mи сравнивает каждый элемент.

Geobits
источник
1
Вы можете сократить это, используя лямбду:a->{int m=a[0]...
Даниэль М.
Да, вы обычно можете. Я не люблю лямбда-язевские гольфы.
Geobits
3

Perl, 33 байта

Код 32 байта + -p

$p=$_;s/\S+ ?/$&>=$p&&($p=$&)/ge

Если в выводе допустимы дополнительные пробелы, можно удалить 31 байт, удалив и ?. Принимает строку (или число разделенных новой строкой) строк через STDIN:

perl -pe'$p=$_;s/\S+ ?/$&>=$p&&($p=$&)/ge' <<< '-7 -8 -5 0 -1 1'
-7 -5 0 1
perl -pe'$p=$_;s/\S+ ?/$&>=$p&&($p=$&)/ge' <<< '10 10 10 9 10'
10 10 10 10
Дом Гастингс
источник
3

Python 3, 67

Довольно грубая сила. Изменил это на функцию, потому что я упустил, что это был правильный ответ.

def f(i):
 s=[i[0]]
 for n in i[1:]:
  if s[-1]<=n:s+=[n]
 return s

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

input_numbers = input().split()
sorted_numbers = []
previous_number = int(input_numbers[0])
for number in map(int, input_numbers):
    if previous_number <= number:
        sorted_numbers.append(number)
        previous_number = number
print(sorted_numbers)
Морган Трепп
источник
62 байта
movatica
3

Haskell, 38 37 байт

Сохранено 1 байт благодаря JArkinstall .

f(x:y:s)|x>y=f$x:s|1>0=x:f(y:s)
f s=s
alephalpha
источник
1
Вы можете заменить один из своих наборов скобок на a, $чтобы сократить один целый байт! f(x:y:s)|x>y=f$x:s|1>0=x:f(y:s);f s=s (Точка с запятой используется, потому что комментарии не позволяют переводить новые строки)
Джейк
3

C # - 6864 или 132127 персонажей

int[]f(int[]b){return b.Where((v,i)=>i<1||b[i-1]<=v).ToArray();}

Whereв этом случае выполняет итерацию по списку, и для каждого элемента vпо индексу iв списке вычисляется логическое выражение. Если выражение оценивается как true, то элемент добавляется к результату. Единственный реальный трюк с логическим выражением состоит в том, что короткое замыкание или оценка C #, как только условие оценивается как истинное. Это предотвращает IndexOutOfRangeExceptionисключение и сохраняет первый элемент в списке.

Если входные и выходные данные должны быть строками (я не могу сказать наверняка, поэтому я оставлю это на усмотрение ОП, а остальным вам решать).

string t(string b){var c=b.Split(' ').Select(d=>int.Parse(d)).ToList();return String.Join(" ",c.Where((v,i)=>i<1||c[i-1]<=v));}

Распаковка немного дает:

string t(string b) 
{
    var c=b.Split(' ').Select(d=>int.Parse(d)).ToList();
    return String.Join(" ",c.Where((v, i)=>i<1||c[i-1]<=v));
}

В этом случае вторая строка функции использует ту же логику, что и выше. В Selectвыхватывает элементы списка и преобразует их int. Вызов ToList1 вызывает выбор, который должен быть оценен, и превращается varв a List<int>во время компиляции, так что Whereон работает с коллекцией целых чисел.

Попробуйте это на C # Pad

Спасибо VisualMelon за помощь в обрезке 4 и 5 байтов соответственно. :)

1 лист пачки?

Theb
источник
Если я ошибся или если мое объяснение нуждается в пояснении, пожалуйста, дайте мне знать. :)
theB
1
Хорошая работа - вы можете сэкономить несколько байтов с помощью некоторых распространенных приемов - вам не нужны пробелы после того, как объявления массива int[]f(int[]b)в порядке, и вы можете использовать i<1вместо того, i==0чтобы немного сократить эту проверку. Для строковой версии вы также (d)=>int.Parse(d)можете заключить скобки вокруг одного аргумента в лямбде (например, может быть d=>int.Parse(d). Я также считаю только 67 байтов, а не 68, в вашем оригинале;)
VisualMelon
@VisualMelon - Спасибо! Я полагал, что любое неправильное подсчет в конечном итоге увеличит общую сумму. ;)
theB
3

CJam, 15 байтов

q~{_2$<{;}&}*]p

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

Как это устроено

q~               Read an evaluate all input.
  {        }*    Reduce; push the first element; or each remaining element:
   _2$           Copy the topmost and second topmost element from the stack.
      <          Check if the topmost is smaller than the second topmost.
       {;}&      If it is, remove it from the stack.
             ]   Wrap the stack i an array.
              p  Print.
Деннис
источник
2

C: 73 байта

int i,j;i=j=INT_MIN;while(scanf("%d",&j)!=EOF)if(j>=i)printf("%d",j),i=j;

или же

C: 49 байтов

(Если разрешен таможенный заголовок для соревнований по кодгольфу)

I z,y;z=y=INT_MIN;w(s(D,&y)!=E)i(y>z)p(D,y),z=y;}

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

Разработчик игр
источник
4
Извините, пользовательский заголовок не разрешен; это будет считаться другим языком.
lirtosiast
4
Основная проблема с вашими пользовательскими заголовками заключается в том, что вы опубликовали их после начала этого конкурса.
Деннис
Конечно, я понимаю, но тогда я не могу использовать это ни в будущих соревнованиях?
GameDeveloper
@DarioOO Вы можете, но вы должны будете включить оператор импорта в число байтов.
SuperJedi224
Или просто назовите это новым языком.
CalculatorFeline
2

Бурлеск, 13 байт

11-байтовое решение, которое проходит тест-кейсы:

-.2CO:so)[~

Попробуйте онлайн здесь .

Объяснение:

-. -- prepend head of list to list
2CO -- n-grams (sliding window) of size 2
:so -- filter sorted lists
)[~ -- map last

Однако эта версия работает только благодаря тому факту, что между двумя числами нет двух меньших чисел. В противном случае используйте версию ниже (которая 13B):

Старые версии:

J-]{cm-1.>}LO

Попробуйте онлайн здесь. Объяснение:

J -- duplicate
-] -- head
{
  cm -- compare (returning -1,0 or 1)
  -1.> -- greater than -1
}LO -- Loop

Если бы вы также сбросили равные числа, вы могли бы использовать только .>вместо использования cm. Кроме того, если списки содержат только положительные числа, вы можете использовать либо вместо, 0либо .-1J-]

mroman
источник
Да, но тогда я не могу гиперссылку :).
Мроман
исправлено. Я просто добавлю строку "попробовать онлайн здесь".
Мроман
2

Минколанг 0,9 , 18 байт

ndN(nd1R`2&dN$I$).

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

объяснение

ndN                Take first integer from input
(         $I$).    Repeat until the input is empty and then stop.
 nd1R`             Is the next integer less than the previous one?
      2&dN         If not (i.e., it's greater than or equal to), print it.
Эльендия Старман
источник
2

Рубин, 41 37 символов

->a{m=a[0];a.map{|n|m>n ?p: m=n}-[p]}

Образец прогона:

2.1.5 :001 > [
2.1.5 :002 >     [1, 2, 5, 4, 3, 7],
2.1.5 :003 >     [10, -1, 12],
2.1.5 :004 >     [-7, -8, -5, 0, -1, 1],
2.1.5 :005 >     [9, 8, 7, 6, 5],
2.1.5 :006 >     [10, 13, 17, 21],
2.1.5 :007 >     [10, 10, 10, 9, 10],
2.1.5 :008 > ].each{ |test| p ->a{m=a[0];a.map{|n|m>n ?p: m=n}-[p]}[test] }
[1, 2, 5, 7]
[10, 12]
[-7, -5, 0, 1]
[9]
[10, 13, 17, 21]
[10, 10, 10, 10]
manatwork
источник
1
-[p]Короче.compact
Не то, чтобы Чарльз
К сожалению. Конечно. Спасибо. (Примечание для себя: недостаточно просто высказать [link codegolf.stackexchange.com/questions/363/… для игры в гольф в Ruby [/ link], я должен также запомнить их.)
manatwork
2

NARS2000 APL, 13 байтов

NARS2000 - бесплатный интерпретатор APL для Windows; он включает в себя функции мультимножества, доступные оператору.

(+⍦∩⌈\)

Это монадическая ветвь, которая принимает многосетевое пересечение ( ⍦∩) для input ( +) * и список работающих максимумов ( ⌈\).

Поскольку это не стандартный символ APL в устаревших однобайтовых кодировках APL, мы должны использовать UTF-8, создавая ⍦∩⌈символы по три байта каждый. Я выбрал +вместо того, чтобы сохранить два байта.

NARS2000 поддерживает вилки, которые могут быть встроены в поезда без скобок, но в отличие от Dyalog он не позволяет присваивать функции без заключения функции в скобках.

* +является технически сложным сопряженным, но вход является реальным.

lirtosiast
источник
Так почему же codegolf.stackexchange.com/questions/61808/… не применимо и здесь?
кот
NARS2000 не может использовать устаревшие кодировки APL - и даже до того, как правило, что кодировки должны фактически использоваться интерпретаторами, это не может быть 7 байтов, потому что psi не является частью какой-либо устаревшей кодировки APL.
lirtosiast
2

> <> с флагом -v, 36 31 + 2 = 33 байта

:&\o " "&n:~& <
~ >l?!;:&:&(?!^

Введите список в стек с помощью -v, чтобы первый элемент списка находился на вершине стека. Он напечатает отсортированный список с завершающим пробелом.

Тестовый забег :

$ for input in "1 2 5 4 3 7" "10 -1 12" "-7 -8 -5 0 -1 1" "9 8 7 6 5" "10 13 17 21" "10 10 10 9 10"; do echo $input '-> ' $(python fish.py dropsort.fsh -v $(echo $input | tac -s ' ')); done

1 2 5 4 3 7 ->  1 2 5 7

10 -1 12 ->  10 12

-7 -8 -5 0 -1 1 ->  -7 -5 0 1

9 8 7 6 5 ->  9

10 13 17 21 ->  10 13 17 21

10 10 10 9 10 ->  10 10 10 10

Редактировать: 5 байтов сохранено благодаря Fongoid

Аарон
источник
Вы можете сохранить 5 байтов путем рефакторинга строки 1 as :&\o" "&n:~& <и строки 2 as~ >l?!;:&:&(?!^
Fongoid
@ Спасибо, обновлено!
Аарон
2

Python, 102 99 94 + 5 6 не-финальных строк новой строки = 107 105 100 байт

(Я использовал вкладки для отступа)

def d(l):
    j=b=0;m=l[j];r=[]
    for i in l:
        (m,b)=[(m,0),(i,1)][i>=m]
        if b>0:r+=[i]
        j+=1
    l[:]=r

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

РЕДАКТИРОВАТЬ: list.append () короче, чем делать это уродливым способом

r + = [i] был короче, чем list.append (); спасибо njzk2 !

Джеймс Мерфи
источник
r + = [i] закорочена чем r.append
njzk2
Я пытался сделать это раньше, но получил ошибку, потому что я не понимал, что вы должны сделать это с помощью скобок. Спасибо!
Джеймс Мерфи
2

Scala: 232 126 120 байт

def f(x:Int*)=(Seq[Int]()/:x)((r,y)=>r.headOption.filter(y>=).map(_=>y+:r).getOrElse(if(r.isEmpty) y+:r else r)).reverse
Мартин Зилер
источник
2
Добавление «метода расширения» для List[Int]не удовлетворяет требованиям, вы должны получить ввод через STDIN или в качестве аргумента. Плюс, это раздутый твой ответ ... Почему бы просто не иметь def dropSort(s:Seq[Int]):Seq[Int]?
Джейкоб
Я думал, что это будет модно, но вы правы, слишком много байтов ...
Мартин Зилер,
1
Очень хорошее улучшение, используя фолд! Вы все еще можете сбрить некоторые пробелы, а также можете использовать y> = вместо _ <= y, который выдает предупреждение о компиляции без надлежащего импорта, но также демонстрирует, насколько хорош Scala (о, и сбрасывает другой символ).
Джейкоб
Спасибо за отзыв!
Мартин Зилер
2

Scala, 54 байта

def f(x:Int*)=(x:\Seq[Int]())((y,r)=>y+:r.filter(y<=))

Ungolfed:

def dropSort(xs: Seq[Int]): Seq[Int] =
  xs.foldRight(Seq.empty[Int]) { (x, result) =>
    x +: result.filter(r => r >= x)
  }
knutwalker
источник
2

Крошечный Лисп, 107 байт

( Этот язык был опубликован только после того, как этот вопрос, так что этот ответ работает вне конкуренции. Не то , чтобы он имел все шансы на победу. Язык позже эволюционировали дальше , чтобы иметь больше buildins , чем те , которые я использовал здесь, но я остаюсь с версия, которую я первоначально реализовал в 2015 году. Этот ответ по-прежнему работает с более новым официальным интерпретатором , хотя он дает некоторые предупреждения, потому что я определяю параметр, который скрывает новое построение (для добавления). Спасибо DLosc за ссылку TIO. )aa

(d r(q((m a)(i a(i(l(h a)m)(r m(t a))(c(h a)(r(h a)(t a))))()))))(d ds(q((b)(i b(c(h b)(r(h b)(t b)))()))))

Это определяет функцию ds(и ее рекурсивную вспомогательную функцию r), которая сортирует свой аргумент, который должен быть списком целых чисел.

r не является хвостовой рекурсивной функцией, поэтому для очень длинных списков это может привести к переполнению стека.

Ungolfed:

(d r
   (q((m a)
      (i a
         (i (l (h a) m)
            (r m (t a))
            (c (h a)
               (r (h a) (t a))
             )
          )
         ()
       )
   ) )
 )
(d ds
  (q(
      (b)
      (i b
        (c (h b)
           (r (h b) (t b))
         )
        ()
       )
   ) )
 )

Вот несколько примеров, как это использовать (с тестовыми примерами из вопроса):

(d list (q (args args)))
(d -
   (q( (n)
       (s 0 n)
    ) )
 ) 

(ds (list 1 2 5 4 3 7))
(ds (list 10 (- 1) 12))
(ds (list (- 7) (- 8) (- 5) 0 (- 1) 1))
(ds (list 9 8 7 6 5))
(ds (list 10 13 17 21))
(ds (list 10 10 10 9 10))

(Да, -7это не целочисленный литерал, поэтому мы должны определить функцию для их представления.) Вывод:

list
-
(1 2 5 7)
(10 12)
(-7 -5 0 1)
(9)
(10 13 17 21)
(10 10 10 10)
Пауло Эберманн
источник
«-7 - это не целое число» Я все еще смеюсь, +1
кошка
Вы действительно использовали каждый отдельный символ для встроенных функций? (За исключением r, я думаю ..)
CalculatorFeline
@CatsAreFluffy извините, у меня проблемы с пониманием вашего комментария. Tiny Lisp имеет 7 встроенных функций и три встроенных макроса, все из которых имеют отдельные имена персонажей (я думаю, чтобы сделать язык более легким для игры в гольф), с круглыми скобками и пробелом, являющимися специальным синтаксисом. Обратите внимание, что Tiny Lisp - не мое изобретение.
Пажло Эберманн
Ах, я думаю, я понял это сейчас ... Вы предлагаете использовать односимвольное имя вместо ds? Я думаю, это можно было бы сделать, сохранил бы еще один байт. Думаю, я выбрал dsаббревиатуру для сортировки по каплям.
Паŭло Эберманн
Эй, я только что заметил это. Хорошая работа! Согласно мета-консенсусу, неназванные лямбда-функции являются допустимой формой представления, поэтому вы можете сэкономить 6 байтов, избавившись от них (d dsи сопоставив их )в конце. Возможны и другие игры в гольф, если вы хотите использовать моего текущего переводчика , но если вы хотите придерживаться спецификации в исходном вопросе, это тоже хорошо. :)
DLosc
2

Желе, 5 байт

=»\Tị

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

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

Как это устроено

=»\Tị  Main link. Argument: A (list)

 »\    Yield the cumulative maxima of A.
=      Perform element-by-element comparison.
       Yields 1 iff A[n] = max(A[1], ..., A[n]).
   T   Get all indices of truthy elements.
    ị  Retrieve the items of A at those indices.
Деннис
источник
1

Mathematica, 27 байт

Pick[#,#-Max~FoldList~#,0]&
alephalpha
источник