Двигаясь скромный минимум

40

Вдохновленный вопросом о переполнении стека. Название здесь полностью моя вина.


Соревнование

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

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

[4 3 2 5]    ->  [2 2 3 2]
[4 2 2 5]    ->  [2 2 2 2]
[6 3 5 5 8]  ->  [3 5 3 3 3]
[7 1]        ->  [1 7]
[9 9]        ->  [9 9]
[9 8 9]      ->  [8 9 8]

правила

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

Программы или функции разрешены на любом языке программирования . Стандартные лазейки запрещены.

Вклад может быть сделан любым разумным способом ; и с любым форматом. То же самое для вывода. Форматы ввода и вывода могут быть разными.

Самый короткий код в байтах побеждает.

Луис Мендо
источник
Что должен [4 3 2 2 5]выводить?
Kritixi Lithos
@KritixiLithos разве второй тестовый пример не охватывал это?
Утренняя монахиня
@KritixiLithos Для ввода [4 3 2 2 5]вывод будет [2 2 2 2 2](это похоже на второй контрольный пример)
Луис Мендо
О, я пропустил второй контрольный пример. Но теперь я понимаю, как это работает
Kritixi Lithos
@LuisMendo Вы изменили "integer" на "любой размер и значения ввода". Значит ли это, что нам нужно учитывать все действительные числа?
Утренняя монахиня

Ответы:

19

Желе , 9 6 5 байт

JḟÐ € `ị⁸Ṃ € 
ṙJṖ € Ṃ €
ṙJṖ «/ аргумент: 1D массив (z)

 J [1,2,3, ..., len (z)]
z повернуть z на каждую из указанных выше величин (текущий массив 2D)
  Ṗ удалить последний массив
   «/ Уменьшить на [имплицитно векторизованный] минимум

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

Проверьте все из них сразу! (слегка модифицированный)

Я почти уверен, что Деннис может обыграть это.

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

Алгоритм довольно запутанный. Давайте посмотрим, что это значит [4,2,2,5].

Во-первых, мы используем Jдля получения [1,2,3,4]. Обратите внимание, что Jelly использует 1-индексирование.

Затем мы видим . Он принимает два аргумента: массив и целое число. Он поворачивает массив влево на величину, указанную целым числом. Здесь можно было бы увидеть [4,2,2,5]его слева и [1,2,3,4]справа (больше о том, как это работает, можно найти в руководстве ). В Jelly команды неявно векторизуются. Следовательно, эта команда будет выполняться над каждым отдельным элементом справа, поэтому мы должны создать двумерный массив:

Следовательно, [4,2,2,5]ṙ[1,2,3,4]становится [[4,2,2,5]ṙ1,[4,2,2,5]ṙ2,[4,2,2,5]ṙ3,[4,2,2,5]ṙ4], что становится:

[[2,2,5,4],
 [2,5,4,2],
 [5,4,2,2],
 [4,2,2,5]]

Обратите внимание, что исходные элементы находятся в последней строке, поскольку в этой строке мы повернули влево на величину, равную длине массива, поэтому мы используем next для удаления этой строки, чтобы столбцы были коллекциями элементы массива, которых нет в текущем индексе:

[[2,2,5,4],
 [2,5,4,2],
 [5,4,2,2]]

Следующая операция, «/также довольно запутанная. Во-первых, «возвращает минимум двух чисел, которые он видит слева и справа. Например, 5«3возвращает 3. Теперь, если два аргумента являются массивами, то он будет векторизован, как я сказал выше. Что это значит, [1,5,2,3]«[4,1,5,2]что станет тем, [1«4,5«1,2«5,3«2]что есть [1,1,2,2]. Теперь, /это reduceозначает, что мы делаем операцию над каждой строкой до конца. Например, [1,2,3,4]+/стал бы ((1+2)+3)+4, который является суммой массива [1,2,3,4].

Итак, если мы применим «/к только что полученному 2D-массиву, мы получим:

([2,2,5,4]«[2,5,4,2])«[5,4,2,2]

который из-за векторизации будет эквивалентен:

[2«2«5,2«5«4,5«4«2,4«2«2]

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

Дрянная Монахиня
источник
1
О, твоя редакция ... ты первым пришел.
Джонатан Аллан
1
@JonathanAllan Извини.
Утренняя монахиня
40

Python 2 , 41 байт

lambda l:[sorted(l)[x==min(l)]for x in l]

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

Для каждого элемента xмы проверяем, есть ли x==min(l). Если нет, то это так False, как 0если бы он использовался как индекс списка sorted(l), давая наименьший элемент. В противном случае это, Trueиначе говоря 1, дает второй наименьший элемент, так как сам этот элемент наименьший и должен игнорироваться.

XNOR
источник
2
Мне трудно поверить, что это работает.
Утренняя монахиня
2
Отличный подход!
Луис Мендо
Не могли бы вы добавить объяснение? Это не было бы очень сложно, но уловка «каждое число будет минимальным, за исключением того, которое является минимумом, который будет вторым наименьшим», и тот факт, что Falseпреобразуется в 0и Trueпреобразуется в 1действительно круто и стоит похвастаться ^ W ^ Wexplained
Фонда Моники
18

Желе , 5 байт

=Ṃ‘ịṢ

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

Как?

=Ṃ‘ịṢ - Main link: list a     e.g.  [4,3,2,5]
 Ṃ    - minimum of a                2
=     - equals? (vectorises)        [0,0,1,0]
  ‘   - increment                   [1,1,2,1]
    Ṣ - sort a                      [2,3,4,5]
   ị  - index into                  [2,2,3,2]
Джонатан Аллан
источник
4
@LeakyNun Это не порт, это просто тот же метод, я все еще ищу меньше ... Я тоже проголосовал за этот ответ :)
Джонатан Аллан
5
@ LeakyNun Я новичок здесь, но ты всегда такой враждебный? Не то чтобы существует множество уникальных способов подойти к этому. Даже если он это сделал, у него все равно есть более короткий ответ.
Грейсон Кент
3
@GraysonKent Я прошу прощения за мою предполагаемую враждебность.
Утренняя монахиня
1
@GraysonKent Добро пожаловать в PPCG!
Луис Мендо
1
@LeakyNun Это часто случается в более простых задачах, вы не можете сказать, что каждый ответ является портом любого другого
только ASCII
12

Haskell , 42 41 39 байт

РЕДАКТИРОВАТЬ:

  • -1 байт благодаря Ними!
  • -2 байта. Одно спасибо xnor! И один сам.

fберет список целых чисел (или любого Ordтипа) и возвращает список.

f(x:y)=minimum y:(fst<$>zip(f$y++[x])y)

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

fповторяется при вращении списка. xэто первый элемент списка, а yостальные. Поскольку рекурсия бесконечна, список результатов должен быть обрезан: fst<$>zip...yэто более короткий способ сказать take(length y)....

Орджан Йохансен
источник
1
Вы можете сохранить один байт, называя список весь ввод с помощью @и переворачивать списки быть Молнии: f l@(x:y)=fst<$>zip(minimum...)l.
Ними
1
f(h:t)=minimum t:(fst<$>zip(f(t++[h]))t)
xnor
9

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

@(x)sort(x)((x==min(x))+1)

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

Я на самом деле не фанат портирования других ответов, поэтому я хотел бы отметить, что у меня была похожая идея, прежде чем я увидел другие.

Объяснение:

Джонатан Аллан уже предоставил хорошее объяснение Jelly-кода, поэтому он охватывает октавный бит и почему он работает (и не будет работать в MATLAB).

@(x)                       % An unnamed anonymous function taking a vector x as input
    sort(x)                % Gives a sorted version of x
            (x==min(x))    % Checks if each element is equal to the minimum value
           ((x==min(x))+1) % Adds 1 to the boolean vector, to use as indices
@(x)sort(x)((x==min(x))+1) % Complete function

Это не работает в MATLAB, так как встроенные назначения и прямая индексация не работают. sort(x)(1)выдает ошибку в MATLAB, а не первый элемент в отсортированном векторе.

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

Haskell, 41 байт

a#(b:c)=minimum(a++c):(b:a)#c
a#b=b 
([]#)

Пример использования: ([]#) [4,3,2,5]-> [2,2,3,2]. Попробуйте онлайн!

Начните с пустого аккумулятора aи запустите список ввода. Следующим элементом в списке вывода является минимум аккумулятора aи все, кроме первого элемента списка ввода (-> c), за которым следует рекурсивный вызов с первым элементом, bдобавленным в аккумулятор и c. Остановитесь, когда достигнете конца списка ввода.

Ними
источник
7

JavaScript (ES6), 50 46 байт

a=>a.map((_,i)=>Math.min(...a.filter(_=>i--)))

Редактировать: 4 байта сохранены благодаря @Arnauld.

Нил
источник
a=>a.map(x=>Math.min(...a.filter(y=>x!=y)))для 43 байтов.
Лохматый
@ Shaggy Я не думаю, что это работает для входа, такого как3,3,3,3
Арно
D'о! Нет, это не будет работать, если есть 2 или более вхождения минимального значения.
Лохматый
1
Тем не менее, вы можете сделать a=>a.map((_,i)=>Math.min(...a.filter(_=>i--)))для 46.
Arnauld
@Arnauld Очень умно, спасибо!
Нил
7

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

l+₁:?⊇ᶠ⁽⌋ᵐb↔

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

Сохранено один байт благодаря @ ais523.

объяснение

l+₁:?            The list [length(Input) + 1, Input]
     ⊇ᶠ⁽         Find the length(Input) + 1 first subsets of the Input
        ⌋ᵐ       Get the min of each subset 
           b↔    Remove the first element and reverse

Мы используем тот факт, что объединяет подмножества от самых больших до самых маленьких. Например , для [1,2,3], подмножества , которые мы получаем в следующем порядке: [1,2,3], [1,2], [1,3], [2,3], [1], [2], [3], [].

Мы можем видеть, что подмножества [1,2], [1,3], [2,3]- это те, от которых мы хотим получить минимум, но в обратном порядке по сравнению со списком ввода (отсюда и ). Мы можем выбрать эти подмножества только найдя первые length(Input) + 1подмножества, которые будут содержать все из них + весь список в первую очередь. Мы отбрасываем весь этот список с b.

Fatalize
источник
1
Вы можете сохранить байт, разделив «подмножество findall + минимум» на «подмножество findall» и «минимум карты». (Мне нужно добавить это в
1
@ ais523 Спасибо, я всегда забываю об этом трюке ...
Fatalize
6

На самом деле , 13 байтов

;;S╝m╗⌠╜=╛E⌡M

Использует ту же технику, что и xnor .

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

Объяснение:

;;S╝m╗⌠╜=╛E⌡M
;;             make two extra copies of input list
  S╝           sort one and save it in register 1
    m╗         save the minimum of the other in register 0
      ⌠╜=╛E⌡M  for each value in list:
       ╜=╛E      return the minimum element of the input list if the value is not equal to the minimum, else return the second-smallest element
Мего
источник
1
Вы до сих пор не позволили нам взглянуть на глобальный стек внутри временного стека?
Утренняя монахиня
1
@LeakyNun Еще нет. В текущем состоянии, в котором находится код интерпретатора, это будет очень сложно. После того, как я закончу большой рефакторинг, над которым я работаю, я посмотрю, как добавить эту функциональность.
Mego
1
Когда вы начали большой рефакторинг?
Утренняя монахиня
6

R, 46 31 байт

l=scan();sort(l)[(min(l)==l)+1]

реализует решение Stewie Griffin в R, увы, моя оригинальная идея на 50% длиннее! все еще читает список из стандартного ввода, но теперь возвращает гораздо более читаемый числовой вектор.

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

старая реализация:

l=scan();Map(function(x)min(l[-x]),match(l,l))

читает в списке со стандартного ввода. Отрицательный индекс l[-x]исключает элемент из списка и match(l,l)возвращает индекс первого вхождения каждого элемента списка. Возвращает список.

Giuseppe
источник
5

Python 2, 51 байт

Я знаю, что уже есть лучшее решение Python, но я все еще хочу опубликовать мое.

lambda L:[min(L[:i]+L[i+1:])for i in range(len(L))]

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

mbomb007
источник
5

Mathematica 34 байта

Min[#~Drop~{i}]~Table~{i,Tr[1^#]}&
Келли Лоудер
источник
5

PowerShell , 68 59 байт

($a=$args)|%{$b+=@((($c=$a|sort)[0],$c[1])[$_-eq$c[0]])};$b

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

Я довольно уверен, что это может быть сокращено, я буду продолжать смотреть на это

Синусоида
источник
4

C 85 байт

i,j,m;f(d,o,n)int*d,*o;{for(i=n;i--;)for(m=d[!i],j=n;j;o[i]=m=--j^i&&d[j]<m?d[j]:m);}

Первый аргумент - это входной целочисленный массив. Второй аргумент - это выходной целочисленный массив. Третий аргумент - это количество элементов для обоих массивов.

Посмотрите, как это работает онлайн .

2501
источник
3

Perl 6 ,  26 24  19 байт

26

{.map: (.Bag∖*).min.key}

Обратите внимание, что это U + 2216, а не \U + 5C

Попытайся

{.map: (.Bag⊖*).min.key}

Попытайся

24

{(.min X%$_)X||.sort[1]}

Попытайся

19

{.sort[.min X==$_]}

Попытайся


26

{           # bare block lambda with implicit parameter 「$_」

  .map:     # for each of the values in the input (implicit method call on 「$_」)
  (
    .Bag    # turn the block's input into a Bag
           # set-difference           「∖」 U+2216 aka 「(-)」
    # ⊖     # symmetric-set-difference 「⊖」 U+2296 aka 「(^)」
    *       # turn expression into a WhateverCode lambda (this is the parameter)
  ).min.key # get the minimum pair from the Bag, and return its key
}

Я использовал "причудливые" операторы Юникода а не эквиваленты ascii, потому что им потребовался бы пробел перед ними, чтобы они не анализировались как часть .Bagвызова метода.

24

{
  (.min X% $_) # the minimum cross modulus-ed with the input
  X||          # cross or-ed 
  .sort[1]     # with the second minimum
}

19

{
  .sort\        # sort the values
  [             # index into that
    .min X== $_ # the minimum cross compared with the input
  ]
}

(24- и 19-байтовые гольфы были вдохновлены реализацией Jelly )

Брэд Гилберт b2gills
источник
3

Clojure, 36 81 62 71 байт

Новейшие (не следует отправлять их на скорую руку):

#(for[c[(zipmap(range)%)]i(sort(keys c))](apply min(vals(dissoc c i))))

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

Кроме того, у этого есть ошибка (62 байта), zipmap создает неупорядоченную карту, поэтому это не даст правильную последовательность на больших входах.

#(for[c[(zipmap(range)%)][i v]c](apply min(vals(dissoc c i))))

vна самом деле не используется ни для чего, но это короче, чем i (keys c).

Предыдущая на 81 байт:

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

#(let[r(range(count %))](for[i r](apply min(for[j r :when(not= i j)](nth % j)))))

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

О черт, оригинал (36 байт) не работает, когда минимальное число повторяется, в [4 2 2 5]результате [2 4 4 2]оба 2s удаляются :(

#(for[i %](apply min(remove #{i}%)))

#{i}это набор, который содержит только i, он возвращает true iи false для других, что означает, что минимум вычисляется из всех других чисел в списке ввода.

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

NikoNyrh
источник
3

Pyth, 8 7 байтов

mh.-SQ]

-1 байт благодаря @isaacg

Попытайся!

KarlKastor
источник
Вы можете удалить dв конце - это неявно заполнено.
Isaacg
@isaacg спасибо, не знал этого
KarlKastor
2

PHP, 47 байт

while(++$i<$argc)echo@min([z,$i=>z]+$argv),' ';
user63956
источник
2

Скала, 37 байт

l.indices map(i=>l diff Seq(l(i))min)

l это любая коллекция Int.

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

scala> val l = List(4,3,2,5)
l: List[Int] = List(4, 3, 2, 5)

scala> l.indices map(i=>l diff Seq(l(i))min)
res0: scala.collection.immutable.IndexedSeq[Int] = Vector(2, 2, 3, 2)

scala> val l = List(4,2,2,5)
l: List[Int] = List(4, 2, 2, 5)

scala> l.indices map(i=>l diff Seq(l(i))min)
res1: scala.collection.immutable.IndexedSeq[Int] = Vector(2, 2, 2, 2)

scala> val l = List(6,3,5,5,8)
l: List[Int] = List(6, 3, 5, 5, 8)

scala> l.indices map(i=>l diff Seq(l(i))min)
res2: scala.collection.immutable.IndexedSeq[Int] = Vector(3, 5, 3, 3, 3)

scala> val l = List(7,1)
l: List[Int] = List(7, 1)

scala> l.indices map(i=>l diff Seq(l(i))min)
res3: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 7)

scala> val l = List(9,9)
l: List[Int] = List(9, 9)

scala> l.indices map(i=>l diff Seq(l(i))min)
res4: scala.collection.immutable.IndexedSeq[Int] = Vector(9, 9)

scala> val l = List(9,8,9)
l: List[Int] = List(9, 8, 9)

scala> l.indices map(i=>l diff Seq(l(i))min)
res5: scala.collection.immutable.IndexedSeq[Int] = Vector(8, 9, 8)

Это, вероятно, все еще может быть в гольфе, я не мог найти более короткий способ удалить элемент из списка, чем l diff Seq(l(i))

therealfarfetchd
источник
2

C #, 36 байт

i.Select((x,a)=>i.Where((y,b)=>b!=a).Min())

Принимает элементы (i) и ищет в элементах без текущего элемента минимальное значение.

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

MetaColon
источник
2

PowerShell , 49 38 байт

-11 байт благодаря маззи

($a=$args)|%{($c=$a|sort)[$_-eq$c[0]]}

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

Улучшение прекрасного ответа Синусоиды . Сохраняет 10 байтов, используя явный вывод вместо построения массива. Индексирует в отсортированном массиве либо точку 0 (т. Е. Наименьшее значение), либо точку 1, если условие истинно.

Veskah
источник
1
Это умно. Сохранить больше :) Попробуйте онлайн!
Маззи
1
@ mazzy Молодец. Теперь очевидно, что я это вижу, но я бы никогда не соединил это.
Веска
1
Хорошо сделано! Твой любимый :)
Синусоида
1

Perl 5, 43 байта

sub{@x=sort{$a<=>$b}@_;map$x[$_==$x[0]],@_}

Эквивалент решения Python. К sortсожалению, в Perl неверное значение по умолчанию для чисел (требующее явного компаратора), и minоно не является встроенным, но почти компенсирует это тем, subчто оно короче lambda, map$_,короче x for x inи неявностью списков return и args.

Hobbs
источник
1

Рубин, 30 байтов

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

->a{a.map{|e|(a.sort-[e])[0]}}

Это анонимная функция, которую можно использовать так:

f = ->a{a.map{|e|(a.sort-[e])[0]}}
p f[[6, 3, 5, 5, 8]] # => [3, 5, 3, 3, 3]
daniero
источник
1

CJam, 15 байтов

{:S{S:e<=S$=}%}

По сути это перевод алгоритма xnor на CJam.

Это безымянный блок, который берет массив из стека и оставляет результат в стеке.

Объяснение:

{
  :S     e# Save in S
  {      e# For X in S:
    S:e< e#   Push Min(S)
    =    e#   X == Min(S)
    S$=  e#   Sorted(S)[top of stack]
  }%     e# End
}
Esolanging Fruit
источник
1
@ LuisMendo Ой - я забыл на самом деле сортировать массив. Это должно работать сейчас.
Esolanging Fruit
1

05AB1E , 5 байтов

{sWQè

Порт ответа @xnor 's Python 2 .

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

Объяснение:

{        # Sort the (implicit) input-list
         #  i.e. [4,1,3,6] → [1,3,4,6]
 s       # Swap, so the (implicit) input-list is at the top of the stack again
  W      # Get the minimum without popping from the list
         #  i.e. [4,1,3,6] → 1
   Q     # Check for each element if they are equal to this value (1/0 as truthy/falsey)
         #  i.e. [4,1,3,6] and 1 → [0,1,0,0]
    è    # Use these 0s and 1s to index in the sorted list
         #  i.e. [1,3,4,6] and [0,1,0,0] → [1,3,1,1]
Кевин Круйссен
источник
1

Java 8, 119 байт

a->{int t[]=a.clone(),m=a[0],i=a.length;for(int x:a)m=x<m?x:m;for(java.util.Arrays.sort(t);i-->0;)a[i]=t[a[i]==m?1:0];}

Порт @xnor 's Python 2 ответа .

Изменяет массив ввода вместо того, чтобы возвращать новый для сохранения байтов.

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

Объяснение:

a->{                  // Method with integer-array parameter and no return-type
  int t[]=a.clone(),  //  Make a copy of the input-array
      m=a[0],         //  Minimum `m`, starting at the first value of the input-array
      i=a.length;     //  Index-integer, starting at the length of the input-array
  for(int x:a)        //  Loop over the input-array
    m=x<m?            //   If the current item is smaller than the current `m`
       x              //    Replace `m` with this value
      :               //   Else:
       m;             //    Leave `m` the same
  for(java.util.Arrays.sort(t);
                      //  Sort the copy we've made of the input-array
      i-->0;)         //  Loop `i` in the range (length, 0]
    a[i]=             //   Modify the item at index `i` of the input-array to:
      t[              //    The item in the sorted array at index:
        a[i]==m?      //     If the current item and the minimum are equal:
         1            //      Use index 1 in the sorted array
        :             //     Else:
         0];}         //      Use index 0 in the sorted array
Кевин Круйссен
источник
1

APL (Dyalog Extended) , 7 байтов

Порт xnor Python 2 ответ. Требуется ⎕IO←0:

∧⊇⍨⊢=⌊/

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

Объяснение:

∧⊇⍨⊢=⌊/   Monadic function train
      ⌊/   The minimum element of the input
    ⊢=     Element-wise compare the input to the above
           Results in a boolean vector, let's call it "X"
∧         ⍝ Sort the input
 ⊇⍨      ⍝ Index into sorted input by X
voidhawk
источник
1

Haskell , 76 байт

Это значительно дольше, чем в предыдущих записях на Haskell, но это первое, которое выполняет только линейное число сравнений и линейный объем дополнительной работы.

f(x:y)|(z,w)<-x!y=z:w
a![x]=(x,[a])
a!(x:y)|(p,q)<-a#x!y=(x#p,a#p:q)
(#)=min

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

объяснение

!принимает два аргумента: текущий минимум и непустой список. Возвращает минимальное значение в списке и результат обработки данного списка с использованием текущего минимума.

dfeuer
источник
1

MathGolf , 9 7 байт

s_╓?m=§

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

объяснение

В основном это порт ответа Кевина Круйссена на 05AB1E, но я теряю 2 байта из-за необходимости делать что-то явно.

s         sort(array)
 _        duplicate TOS
  ╓       minimum of two elements, min of list, minimum by filter
   ?      rot3 pops input on top of stack again
    m=    explicit map to check equality
      §   get from sorted array for each
maxb
источник