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>
code-golf
array-manipulation
sorting
SuperJedi224
источник
источник
highest < current
? Илиhighest <= current
?highest (so far)<=current
.Ответы:
APL, 9 байт
Это монадическая последовательность функций со схемой:
Версия без поезда
Это в основном проверяет, равен ли каждый элемент рабочему максимуму.
Обратите внимание, что J-решение Мартина Бюттнера имеет такую же длину и было опубликовано первым.
источник
J
109 байтРабочая версия моей идеи CJam (меньше байтов). Например:
объяснение
Сначала мы получаем максимум каждого префикса:
(Здесь
>.
это оператор максимума,/
складывает этот оператор в список и\
получает все префиксы ввода.)Затем мы сравниваем исходный список с этими максимумами на равенство:
И, наконец, мы выбираем все элементы, для которых этот список логических результатов дал
1
:источник
Хаскелл, 28
Анонимная функция. Назови это как
Эквивалент рекурсии
Итеративно переведенный, мы перебираем элементы, и для каждого видимого мы удаляем те, которые меньше его, из остальной части списка, который мы перебираем. Спасибо Антисфену за сохраненный байт
(x<)
.источник
foldr(\x->(x:).filter(>=x))[]
, это оказывается одинаковой длины.x:
заставляет вас добавлять оператор точки. Ну да ладно ...O(n^2)
же. много ненужных сравнений. ;-(Python 2, 49
источник
max(a)
JavaScript (ES6), 29
Злоупотребление стандартным преобразованием типов в javascript, массив в число:
источник
Октава,
2719 байтисточник
Pyth, 12 байт
Проверьте все тестовые случаи одновременно.
Как это устроено
источник
Брахилог , 5 байт
Попробуйте онлайн!
Желе , 5 байт
Попробуйте онлайн!
объяснение
Это редкая ситуация: я использую алгоритм, который (насколько я могу судить по быстрому отбору) пока что никто не использует, и он каким-то образом заканчивается одинаковой длиной в двух совершенно разных языках игры в гольф с очень разным синтаксисом и встроенные наборы, с соответствием между программами 1: 1 (команды даже в том же порядке!). Таким образом, казалось, что было бы более целесообразно объединить их - в некотором смысле, это одна и та же программа, и я написал ее на обоих языках, чтобы увидеть, какой из них был короче, - чем представлять их отдельно.
Основная идея здесь заключается в том, что дропсорт списка - это его подпоследовательность с лексикографически максимальным обратным. Как ни странно, ни Brachylog, ни Jelly не имеют встроенной функции для поиска максимума по определенной функции (Jelly имеет встроенную функцию, которая возвращает все максимумы по определенной функции, но при этом возвращался бы одноэлементный список, содержащий результат, а не сам результат, и и даже не короче, чем делать это так). Таким образом, вместо этого мы генерируем все возможные подпоследовательности, сортируем по обратному, принимаем последнее.
Причина, по которой работает «лексикографически максимальное обратное направление», заключается в том, что выбранный выход должен заканчиваться (поэтому его обратный ход должен начинаться) с наибольшего числа в списке входных данных (легко видеть, что выход с дропсортированием всегда будет заканчиваться этим), и, таким образом, может ничего после этого не содержит (потому что принятие подпоследовательностей сохраняет порядок). Повторите индуктивно, и мы получим определение DropSort.
источник
Mathematica, 26 байт
источник
DeleteDuplicates
, не похоже на возвращение{10, 10, 10, 10}
для ввода{10, 10, 10, 9, 10}
DeleteDuplicates
с двумя аргументами кажется простым фильтром.R,
2926 байтЭто создает функциональный объект, который принимает вектор
x
и возвращаетx
после удаления все элементы, по крайней мере, такие же, как кумулятивный максимумx
.Сохранено 3 байта благодаря flodel!
источник
К, 11 байт
В бою:
источник
{x@&~<':x}
на байт короче.3 4 2 2 5
.{x@&~<':x}/
, но это та же длина.Java, 82 байта
Вот простой цикл вывода. Он просто сохраняет максимум
m
и сравнивает каждый элемент.источник
a->{int m=a[0]...
Perl, 33 байта
Код 32 байта +
-p
Если в выводе допустимы дополнительные пробелы, можно удалить 31 байт, удалив
и
?
. Принимает строку (или число разделенных новой строкой) строк черезSTDIN
:источник
Python 3, 67
Довольно грубая сила. Изменил это на функцию, потому что я упустил, что это был правильный ответ.
Безголовая версия:
источник
Haskell,
3837 байтСохранено 1 байт благодаря JArkinstall .
источник
$
чтобы сократить один целый байт!f(x:y:s)|x>y=f$x:s|1>0=x:f(y:s);f s=s
(Точка с запятой используется, потому что комментарии не позволяют переводить новые строки)C # -
6864 или132127 персонажейWhere
в этом случае выполняет итерацию по списку, и для каждого элементаv
по индексуi
в списке вычисляется логическое выражение. Если выражение оценивается как true, то элемент добавляется к результату. Единственный реальный трюк с логическим выражением состоит в том, что короткое замыкание или оценка C #, как только условие оценивается как истинное. Это предотвращаетIndexOutOfRangeException
исключение и сохраняет первый элемент в списке.Если входные и выходные данные должны быть строками (я не могу сказать наверняка, поэтому я оставлю это на усмотрение ОП, а остальным вам решать).
Распаковка немного дает:
В этом случае вторая строка функции использует ту же логику, что и выше. В
Select
выхватывает элементы списка и преобразует ихint
. ВызовToList
1 вызывает выбор, который должен быть оценен, и превращаетсяvar
в aList<int>
во время компиляции, так чтоWhere
он работает с коллекцией целых чисел.Попробуйте это на C # Pad
Спасибо VisualMelon за помощь в обрезке 4 и 5 байтов соответственно. :)
1 лист пачки?
источник
int[]f(int[]b)
в порядке, и вы можете использоватьi<1
вместо того,i==0
чтобы немного сократить эту проверку. Для строковой версии вы также(d)=>int.Parse(d)
можете заключить скобки вокруг одного аргумента в лямбде (например, может бытьd=>int.Parse(d)
. Я также считаю только 67 байтов, а не 68, в вашем оригинале;)CJam, 15 байтов
Попробуйте онлайн в интерпретаторе CJam .
Как это устроено
источник
PowerShell , 32 байта
Попробуйте онлайн!
Менее гольф:
источник
C: 73 байта
или же
C: 49 байтов
(Если разрешен таможенный заголовок для соревнований по кодгольфу)
Все еще не может победить CJam, но, по крайней мере, это позволяет обыграть несколько других языков.
источник
Бурлеск, 13 байт
11-байтовое решение, которое проходит тест-кейсы:
Попробуйте онлайн здесь .
Объяснение:
Однако эта версия работает только благодаря тому факту, что между двумя числами нет двух меньших чисел. В противном случае используйте версию ниже (которая 13B):
Старые версии:
Попробуйте онлайн здесь. Объяснение:
Если бы вы также сбросили равные числа, вы могли бы использовать только
.>
вместо использованияcm
. Кроме того, если списки содержат только положительные числа, вы можете использовать либо вместо,0
либо .-1
J-]
источник
Минколанг 0,9 , 18 байт
Попробуй это здесь.
объяснение
источник
Рубин,
4137 символовОбразец прогона:
источник
-[p]
Короче.compact
NARS2000 APL, 13 байтов
NARS2000 - бесплатный интерпретатор APL для Windows; он включает в себя функции мультимножества, доступные
⍦
оператору.Это монадическая ветвь, которая принимает многосетевое пересечение (
⍦∩
) для input (+
) * и список работающих максимумов (⌈\
).Поскольку
⍦
это не стандартный символ APL в устаревших однобайтовых кодировках APL, мы должны использовать UTF-8, создавая⍦∩⌈
символы по три байта каждый. Я выбрал+
вместо того,⊢
чтобы сохранить два байта.NARS2000 поддерживает вилки, которые могут быть встроены в поезда без скобок, но в отличие от Dyalog он не позволяет присваивать функции без заключения функции в скобках.
*
+
является технически сложным сопряженным, но вход является реальным.источник
> <> с флагом -v,
3631 + 2 = 33 байтаВведите список в стек с помощью -v, чтобы первый элемент списка находился на вершине стека. Он напечатает отсортированный список с завершающим пробелом.
Тестовый забег :
Редактировать: 5 байтов сохранено благодаря Fongoid
источник
:&\o" "&n:~& <
и строки 2 as~ >l?!;:&:&(?!^
Python,
1029994 +56 не-финальных строк новой строки =107105100 байт(Я использовал вкладки для отступа)
Не самый лучший, но это мой первый шанс сыграть в гольф. Не удалось найти способ сортировки списка в строке, не сталкиваясь с ошибками, связанными с удалением, поэтому я переместил упорядоченные элементы во временный список.
РЕДАКТИРОВАТЬ: list.append () короче, чем делать это уродливым способом
r + = [i] был короче, чем list.append (); спасибо njzk2 !
источник
Scala:
232126120 байтисточник
List[Int]
не удовлетворяет требованиям, вы должны получить ввод через STDIN или в качестве аргумента. Плюс, это раздутый твой ответ ... Почему бы просто не иметьdef dropSort(s:Seq[Int]):Seq[Int]
?Scala, 54 байта
Ungolfed:
источник
Крошечный Лисп, 107 байт
( Этот язык был опубликован только после того, как этот вопрос, так что этот ответ работает вне конкуренции. Не то , чтобы он имел все шансы на победу. Язык позже эволюционировали дальше , чтобы иметь больше buildins , чем те , которые я использовал здесь, но я остаюсь с версия, которую я первоначально реализовал в 2015 году. Этот ответ по-прежнему работает с более новым официальным интерпретатором , хотя он дает некоторые предупреждения, потому что я определяю параметр, который скрывает новое построение (для добавления). Спасибо DLosc за ссылку TIO. )
a
a
(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:
Вот несколько примеров, как это использовать (с тестовыми примерами из вопроса):
(Да,
-7
это не целочисленный литерал, поэтому мы должны определить функцию для их представления.) Вывод:источник
r
, я думаю ..)ds
? Я думаю, это можно было бы сделать, сохранил бы еще один байт. Думаю, я выбралds
аббревиатуру для сортировки по каплям.(d ds
и сопоставив их)
в конце. Возможны и другие игры в гольф, если вы хотите использовать моего текущего переводчика , но если вы хотите придерживаться спецификации в исходном вопросе, это тоже хорошо. :)Желе, 5 байт
Обратите внимание, что задача предшествует созданию желе.
Попробуйте онлайн!
Как это устроено
источник
Mathematica, 27 байт
источник