Moving modest minimum

Question

Inspired by a question over at Stack Overflow. The title here is entirely my fault.

---

The challenge

Given a list of positive integers containing at least two entries, replace each number by the minimum of all entries excluding itself.

Test cases

[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]

Rules

The algorithm should theoretically work for any input size (greater than one) and values (positive integers). It's accepted if the program is limited by time, memory or data types and so only works for numbers up to a given value, or for input size up to a given value.

Programs or functions are allowed, in any programming language. Standard loopholes are forbidden.

Input can be taken by any reasonable means; and with any format. Same for output. Input and output formats may be different.

Shortest code in bytes wins.

Answer 1

Jelly, 9 6 5 bytes

JḟЀ`ị⁸Ṃ€
ṙJṖ€Ṃ€
ṙJṖ«/     argument: 1D array (z)

 J        [1,2,3,...,len(z)]
ṙ         rotate z by each of the above amount (current array is 2D)
  Ṗ       remove the last array
   «/     reduce by [impliclitly vectorized] minimum

Try it online!

Verify all of them at once! (slightly modified)

I'm pretty sure Dennis can out-golf this.

How it works

The algorithm is rather convoluted. Let us observe what this does to [4,2,2,5].

Firstly, we use J to obtain [1,2,3,4]. Note that Jelly uses 1-indexing.

Then, we see ṙ. It takes two arguments: an array and an integer. It rotates the array to the left by an amount specified by the integer. Here, ṙ would see [4,2,2,5] on its left and [1,2,3,4] on its right (more about how this works can be found in the tutorial). In Jelly, commands implicitly vectorize. Therefore, this command will be performed over each individual element on the right, which is why we would create a 2D array:

Therefore, [4,2,2,5]ṙ[1,2,3,4] becomes [[4,2,2,5]ṙ1,[4,2,2,5]ṙ2,[4,2,2,5]ṙ3,[4,2,2,5]ṙ4], which becomes:

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

Notice that the original elements are on the last row, since in that row we rotated to the left by an amount equal to the length of the array, which is why we use Ṗ next to remove that row, so that the columns are the collections of the elements of the array which are not at the current index:

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

The following operation, «/, is also quite convoluted. Firstly, « returns the minimum of the two numbers it sees on its left and on its right. For example, 5«3 returns 3. Now, if the two arguments are arrays, then it would vectorize as I have said above. What this means it that [1,5,2,3]«[4,1,5,2] would become [1«4,5«1,2«5,3«2] which is [1,1,2,2]. Now, / is reduce, which means that we do the operation over each row until the end. For example, [1,2,3,4]+/ would become ((1+2)+3)+4, which is the sum of the array [1,2,3,4].

So, if we apply «/ to the 2D array we just obtained, we would get:

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

which, because of the vectorization, would be equivalent to:

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

which computes the minimum of every array without the element at the index.

Answer 2

Python 2, 41 bytes

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

Try it online!

For each element x we check whether x==min(l). If not, this is False, which is treated as 0 when used as a list index into sorted(l), giving the smallest element. Otherwise, it's True aka 1, giving the second-smallest element, since that element itself is smallest and should be ignored.

Answer 3

Jelly, 5 bytes

=Ṃ‘ịṢ

Try it online!

How?

=Ṃ‘ịṢ - 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]

Answer 4

Haskell, 42 41 39 bytes

EDIT:

• -1 byte thanks to nimi!
• -2 bytes. One thanks to xnor! And one by myself.

f takes a list of integers (or any Ord type) and returns a list.

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

Try it online!

f recurses while rotating the list. x is the first list element and y the remainder. Since the recursion is infinite, the result list needs to be cut off: fst<$>zip...y is a shorter way of saying take(length y)....

Answer 5

Octave, 26 bytes

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

A similar approach as used in this answer, which happens to be the same as this.

I'm not really a fan of just porting other answers, which is why I'd like to note that I had a similar idea before I saw the other ones.

Explanation:

Jonathan Allan has already provided a good explanation for the Jelly-code, so this covers the Octave-bit, and why it works (and wouldn't work in 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

This doesn't work in MATLAB, since inline assignments and direct indexing doesn't work. sort(x)(1) gives an error in MATLAB, not the first element in the sorted vector.

Answer 6

Haskell, 41 bytes

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

Usage example: ([]#) [4,3,2,5]-> [2,2,3,2]. Try it online!

Start with an empty accumulator a and run down the input list. The next element in the output list is the minimum of the accumulator a and all but the first element of the input list (->c) followed by a recursive call with the first element b added to the accumulator and c. Stop when you reach the end of the input list.

Answer 7

JavaScript (ES6), 50 46 bytes

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

Edit: Saved 4 bytes thanks to @Arnauld.

Answer 8

Brachylog, 13 12 bytes

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

Try it online!

Saved one byte thanks to @ais523.

Explanation

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

We exploit the fact that ⊇ unifies subsets from biggest to smallest. For example for [1,2,3], the subsets we get are in this order: [1,2,3], [1,2], [1,3], [2,3], [1], [2], [3], [].

We can see that the subsets [1,2], [1,3], [2,3] are the ones we want the minimum from, but are in the reverse order compared to the input list (hence the ↔). We can select those subsets only by finding the first length(Input) + 1 subsets, which will contain all of them + the entire list first. We discard that entire list with b.

Answer 9

Actually, 13 bytes

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

Uses the same technique that xnor also discovered.

Try it online!

Explanation:

;;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

Answer 10

R, 46 31 bytes

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

implements Stewie Griffin's solution in R, alas, my original idea is 50% longer! still reads the list from stdin, but now returns a much more readable numeric vector.

Try it online!

old implementation:

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

reads in the list from stdin. A negative index l[-x] excludes the element from the list, and match(l,l) returns the index of the first occurrence of each element of the list. Returns a list.

Answer 11

Python 2, 51 bytes

I know there's already a better Python solution, but I still want to post mine.

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

Try it online

Answer 12

Mathematica 34 Bytes

Min[#~Drop~{i}]~Table~{i,Tr[1^#]}&

Answer 13

PowerShell, 68 59 bytes

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

Try it online!

I'm pretty confident it can be shortened, I will continue to look at it

Answer 14

C, 85 bytes

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);}

First argument is the input integer array. The second argument is the output integer array. The third argument is the element count for both arrays.

See it work online.

Answer 15

Clojure, 36 81 62 71 bytes

Newest (shouldn't really submit these in a hurry):

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

Try it online.

Aaaand this one has a bug (62 bytes), zipmap produces an unordered map so this won't produce the correct sequence on larger inputs.

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

v is not actually used for anything but this is shorter than i (keys c).

Previous at 81 bytes:

Try it online.

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

Try it online.

Oh damn the original (36 bytes) does not work when the minimum number is repeated, [4 2 2 5] results in [2 4 4 2] as both 2s are removed :(

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

#{i} is the set which contains only i, it returns truthy for i and falsy for others, meaning that the minimum is calculated from all other numbers within the input list.

Try it online.

Answer 16

Perl 6,  26 24  19 bytes

26

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

Note that is ∖ U+2216 not \ U+5C

Try it

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

Try it

24

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

Try it

19

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

Try it

---

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
}

I used the "fancy" unicode operators rather than the ascii equivalents because they would have required a space before them so that they wouldn't be parsed as part of the .Bag method call.

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
  ]
}

---

(The 24 and 19 byte golfs were inspired by a Jelly implementation)

Answer 17

Pyth, 8 7 bytes

mh.-SQ]

-1 Byte thanks to @isaacg

Try it!

Answer 18

PHP, 72 Bytes

<?$k=$g=$_GET;sort($k);foreach($g as&$v)$v=$k[$v==$k[0]?:0];print_r($g);

Online Version

Answer 19

PHP, 47 bytes

while(++$i<$argc)echo@min([z,$i=>z]+$argv),' ';

Answer 20

Scala, 37 bytes

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

l is any collection of Int.

Test cases:

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)

This can probably still be golfed, I couldn't find a shorter way to remove an element from a list than l diff Seq(l(i))

Answer 21

C#, 36 Bytes

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

Takes the elements (i) and looks in the elements without the current item for the minimal value.

It's kind of sad, that some other attempts don't work, as we work with primitive types, and therefore don't have lists with references to compare the items from.

Answer 22

PowerShell, 49 38 bytes

^{-11 bytes thanks to mazzy}

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

Try it online!

Improvement of Sinusoid's lovely answer. Saves 10 bytes by using explicit output instead of building an array. Indexes into the sorted array to either spot 0 (i.e. smallest value) or spot 1 if the conditional is true.

Answer 23

Perl 5, 43 bytes

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

Equivalent to the Python solution. Perl's sort unfortunately has the wrong default for numbers (requiring an explicit comparator), and min isn't built-in, but it almost makes up for it by sub being shorter than lambda, map$_, being shorter than x for x in, and the implicitness of return and args lists.

Answer 24

CJam, 15 bytes

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

Essentially a translation of xnor's algorithm into CJam.

This is an unnamed block that takes an array from the stack and leaves the result on the stack.

Explanation:

{
  :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
}

Answer 25

Ruby, 30 bytes

For each element, sort the array, remove the current element and grab the first element of the remaining array.

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

It's an anonymous function that can be used like this:

f = ->a{a.map{|e|(a.sort-[e])[0]}}
p f[[6, 3, 5, 5, 8]] # => [3, 5, 3, 3, 3]

Answer 26

05AB1E, 5 bytes

{sWQè

Port of @xnor's Python 2 answer.

Try it online or verify all test cases.

Explanation:

{        # 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]

Answer 27

Java 8, 119 bytes

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];}

Port of @xnor's Python 2 answer.

Modifies the input-array instead of returning a new one to save bytes.

Try it online.

Explanation:

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

Answer 28

APL (Dyalog Extended), 7 bytes

Port of xnor's Python 2 answer. Requires ⎕IO←0:

∧⊇⍨⊢=⌊/

Try it online!

Explanation:

∧⊇⍨⊢=⌊/  ⍝ 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

Answer 29

Haskell, 76 bytes

This is considerably longer than the earlier Haskell entries, but it's the first that only performs a linear number of comparisons and a linear amount of additional work.

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

Try it online!

Explanation

! takes two arguments: a running minimum and a nonempty list. It returns the minimum value in the list and the result of processing the given list using the running minimum.

Answer 30

MathGolf, 9 7 bytes

s_╓?m=§

Try it online!

Explanation

Basically a port of Kevin Cruijssen's 05AB1E answer, but I lose 2 bytes thanks to having to do things explicitly.

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

Answer 31

APL(NARS), 47 chars, 94 bytes

{m←⌊/⍵⋄⍵{⍵>≢⍺:⍬⋄t←⍺∇⍵+1⋄m=⍵⊃⍺:(⌊/⍺∼⍦m),t⋄m,t}1}

∼⍦ it seems is using for remove one element only 1 times; possible it is too much long for you... test:

  f←{m←⌊/⍵⋄⍵{⍵>≢⍺:⍬⋄t←⍺∇⍵+1⋄m=⍵⊃⍺:(⌊/⍺∼⍦m),t⋄m,t}1}
  f 4 3 2 5
2 2 3 2 
  f 4 2 2 5
2 2 2 2 
  f 6 3 5 5 8
3 5 3 3 3 
  f 7 1
1 7 
  f 9 9
9 9 
  f 8 9 8
8 8 8 
  f 9 8 9
8 9 8