25
\$\begingroup\$

Introduction

Suppose you want to compute the tail maxima of a list of numbers, that is, the maximum of each nonempty suffix. One way to do it is to repeatedly choose one number and replace it by a higher number occurring after it, until this is not possible anymore. In this challenge, your task is to perform one step of this algorithm.

The task

Your input is a list of integers L, which may be empty. Your output shall be the list L where exactly one number Li has been replaced by another Lj, where Li < Lj and i < j.

In other words, you shall replace one number with a higher number that occurs after it.

You can choose i and j freely among all valid pairs, and the choice can be nondeterministic.

If such i and j do not exist (i.e. L is non-increasing), your output shall be L unchanged.

Example

Consider the input L = [ 3, 1, 4, -1, 2 ]. The possible operations are to replace 3 by 4, replace 1 by 4, replace 1 by 2, or replace -1 by 2. Thus the possible outputs are:

 [  3 ,   1 ,   4 ,  -1 ,   2 ]
 ------------------------------
 [( 4),   1 ,(  4),  -1 ,   2 ]
 [  3 ,(  4),(  4),  -1 ,   2 ]
 [  3 ,(  2),   4 ,  -1 ,(  2)]
 [  3 ,   1 ,   4 ,(  2),(  2)]

If you repeat the operation enough times, the end result will be [4,4,4,2,2], which is precisely the list of tail maxima of L.

Rules and scoring

You can write a full program or a function. In the latter case, you can modify the input in place instead of returning a new array, if your language allows that. Input and output formats are flexible within reason.

The lowest byte count wins.

Test cases

All possible outputs are shown.

[] -> []
[1] -> [1]
[1,2] -> [2,2]
[2,1] -> [2,1]
[4,4,4,4] -> [4,4,4,4]
[-1,-3,-10] -> [-1,-3,-10]
[1,3,10] -> [3,3,10] [10,3,10] [1,10,10]
[1,1,2,1] -> [2,1,2,1] [1,2,2,1]
[998,64,2,-94,-789] -> [998,64,2,-94,-789]
[998,2,64,-94,-789] -> [998,64,64,-94,-789]
[3,1,4,-1,2] -> [4,1,4,-1,2] [3,4,4,-1,2] [3,2,4,-1,2] [3,1,4,2,2]
[-1,4,0,4,7,2,3] -> [4,4,0,4,7,2,3] [0,4,0,4,7,2,3] [-1,4,4,4,7,2,3] [7,4,0,4,7,2,3] [-1,7,0,4,7,2,3] [-1,4,7,4,7,2,3] [-1,4,0,7,7,2,3] [2,4,0,4,7,2,3] [-1,4,2,4,7,2,3] [3,4,0,4,7,2,3] [-1,4,3,4,7,2,3] [-1,4,0,4,7,3,3]
[3542,-12311,7662,1672,6081] -> [7662,-12311,7662,1672,6081] [3542,7662,7662,1672,6081] [3542,1672,7662,1672,6081] [6081,-12311,7662,1672,6081] [3542,6081,7662,1672,6081] [3542,-12311,7662,6081,6081]
\$\endgroup\$

24 Answers 24

9
\$\begingroup\$

JavaScript (ES6), 41 40 39 38 bytes

Saved a byte thanks to @Neil, another thanks to @user81655

x=>x.map(c=>c<x[++i]>d?x[d=i]:c,d=i=0)

Just when it seems reduceRight might finally have a chance, .map shows up yet again...

\$\endgroup\$
  • \$\begingroup\$ x=>x.map(c=>c<x[++i]&!d?x[d=i]:c,d=i=0)? \$\endgroup\$ – Neil Mar 24 '17 at 21:43
  • \$\begingroup\$ Conditionals are evaluated left-to-right, which means x=>x.map(c=>c<x[++i]>d?x[d=i]:c,d=i=0) (38 bytes) should work. \$\endgroup\$ – user81655 Mar 25 '17 at 9:29
  • \$\begingroup\$ @user81655 That's amazing :-) \$\endgroup\$ – ETHproductions Mar 28 '17 at 13:05
7
\$\begingroup\$

Mathematica, 37 bytes

#/.{a___,b_,c_,d___}/;b<c:>{a,c,c,d}&

Pure function taking a list of real numbers even, and returning a list of real numbers. Looks for the first pair of consecutive entries in the "wrong" order, and replaces the first of that pair with the second. Nice default behavior of /. means that it returns the input unaltered when appropriate.

Amusing side note: if we replace b<c with !OrderedQ[{c,b}], then the function works on strings (and really any data type once the appropriate ordering is described). For example, #/.{a___,b_,c_,d___}/;!OrderedQ[{c,b}]:>{a,c,c,d}& on input {"programming", "puzzles", "code", "golf"} returns {"puzzles", "puzzles", "code", "golf"}.

\$\endgroup\$
  • \$\begingroup\$ A caveat for the side note: Mathematica's canonical ordering of strings is weird. \$\endgroup\$ – Martin Ender Mar 24 '17 at 21:00
  • \$\begingroup\$ How so, Martin Ender? \$\endgroup\$ – Greg Martin Mar 24 '17 at 21:09
  • \$\begingroup\$ Just try Sort[FromCharacterCode /@ Range[32, 127]]. It gets weird once you have strings with multiple words, because then it ignores spaces and stuff. \$\endgroup\$ – Martin Ender Mar 24 '17 at 21:19
6
\$\begingroup\$

JavaScript (ES6), 43 39 38 bytes

a=>a[a.some(e=>e<a[++i],i=0)*i-1]=a[i]

Outputs by modifying the array in-place. Edit: Saved 4 bytes thanks to @ETHproductions. Saved 1 byte thanks to @user81655.

\$\endgroup\$
  • \$\begingroup\$ I think you can do with a=>a[i=0,a.findIndex(e=>e<a[++i])]=a[i] for 39. \$\endgroup\$ – ETHproductions Mar 24 '17 at 22:44
  • \$\begingroup\$ Another approach for 40B: a=>a.map((_,b)=>Math.max(...a.slice(b))) \$\endgroup\$ – Luke Mar 24 '17 at 23:38
  • \$\begingroup\$ @Luke I think you're misunderstanding the challenge; the point is to only make one of the integers in the array larger. \$\endgroup\$ – ETHproductions Mar 24 '17 at 23:52
  • \$\begingroup\$ @ETHproductions Thanks for returning the favour, now the honours are even! \$\endgroup\$ – Neil Mar 25 '17 at 0:30
  • \$\begingroup\$ I think you might be able to replace findIndex with some (38 bytes): a=>a[i=0,a.some(e=>e<a[++i])*i-1]=a[i] \$\endgroup\$ – user81655 Mar 25 '17 at 9:20
5
\$\begingroup\$

Haskell, 36 bytes

f(a:r@(b:_))|a<b=b:r|1>0=a:f r
f e=e

Try it online!

Look through the list for consecutive elements a,b with a<b and changes them to b,b.

Improved from 37 bytes:

f(a:b:t)|a<b=b:b:t
f(a:t)=a:f t
f e=e
\$\endgroup\$
  • \$\begingroup\$ I think f(a:r@(b:_))=max(b:r)(a:f r) works and is two bytes shorter. \$\endgroup\$ – Ørjan Johansen Mar 26 '17 at 0:42
  • \$\begingroup\$ @ØrjanJohansen That's a beautiful method! I think you should post it as your own answer. I wasn't sure at first it would handle ties correctly, but I see now it works because f r >= r. \$\endgroup\$ – xnor Mar 28 '17 at 0:04
  • \$\begingroup\$ Thanks, I've done so! \$\endgroup\$ – Ørjan Johansen Mar 28 '17 at 1:22
4
\$\begingroup\$

Jelly, 13 11 bytes

ṫJṀ€ż¹ŒpQ-ị

Replaces the rightmost of all possible numbers.

Try it online!

How it works

ṫJṀ€ż¹ŒpQ-ị  Main link. Argument: A (array)

 J           Yield all indices of A, i.e., the array [1, ..., len(A)].
ṫ            Dyadic tail; for index k, take all elements starting with the k-th.
             This constructs the array of suffixes.
  Ṁ€         Maximum each; map the monadic maximum atom over the suffixes.
     ¹       Identity; yield A.
    ż        Zip; construct all pairs of elements of the result to the left and the
             corresponding elements of the result to the right.
      Œp     Cartesian product. Construct all arrays that, for each index, take
             either the left or the right element.
        Q    Unique; deduplicate the resulting arrays.
         -ị  At-index -1; select the second to last result.
             The last result is A itself, the first maxima of suffixes.
\$\endgroup\$
3
\$\begingroup\$

MATL, 15 bytes

tdt0>0whY>d*0h+

Try it online!

I'm not a huge fan of this solution. It seems horribly inefficient to me. Particularly the whY>d* and 0h+ sections.

\$\endgroup\$
3
\$\begingroup\$

Python 2, 139 134 93 bytes

a=input()
for i in range(len(a)):
 for j in a[i+1:]:
    if a[i]<j:a[i]=j;print a;exit()
print a

Terribly long, but it's a first attempt.

-5 bytes thanks to TemporalWolf
-41 (!!) bytes thanks to Value Ink

\$\endgroup\$
  • \$\begingroup\$ [1,2] gives [2,1] instead of [2,2] \$\endgroup\$ – TemporalWolf Mar 24 '17 at 21:37
  • 1
    \$\begingroup\$ @TemporalWolf Yeah, I misread the challenge. No bytes saved or lost, will fix. \$\endgroup\$ – HyperNeutrino Mar 24 '17 at 21:37
  • \$\begingroup\$ You can remove the return before your inner print and use a \t tab instead of extra space for the inner loop. Also, you can drop the 0 in exit() for an extra one. Should bring you down to 132. \$\endgroup\$ – TemporalWolf Mar 24 '17 at 21:52
  • \$\begingroup\$ @TemporalWolf Okay, thanks! \$\endgroup\$ – HyperNeutrino Mar 24 '17 at 21:56
  • 1
    \$\begingroup\$ if a[i]<a[j]:a[i]=a[j];print a;exit() is even shorter. Heck, it's better to do for j in a[i+1:]:\n\tif a[i]<j:a[i]=j;print a;exit() \$\endgroup\$ – Value Ink Mar 24 '17 at 23:00
3
\$\begingroup\$

MATL, 13 bytes

ttd0>fX>Q)2M(

Try it online!

Explanation

The following two conditions are equivalent:

  1. There is a number that has a higher number to its right
  2. There is a number that has a higher number immediately to its right

The code uses condition 2, which is simpler. It computes consecutive increments and finds the last positive one, if any. For the two involved entries, it writes the value of the second entry into the first.

This trick is used to handle the case when no substitution can be done. Note also that MATL indexing is 1-based.

Let's use input [3,1,4,-1,2] as an example.

tt    % Get input implicitly and duplicate it twice
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], [3,1,4,-1,2]
d     % Consecutive differences
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], [-2  3 -5  3]
0>    % Are they positive?
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], [0 1 0 1]
f     % Find indices of all positive differences. Result may be empty
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], [2 4]
X>    % Maximum index with a positive difference. Empty input remains as empty
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], 4
Q     % Add 1. Since the addition is elementwise, empty input remains as empty
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], 5
)     % Get the entry of the input at that position
      % STACK: [3,1,4,-1,2], 2
2M    % Push maximum index with a positive difference, again
      % STACK: [3,1,4,-1,2], 2, 4
(     % Assign to that position. Implicitly display
      % STACK: [3,1,4,2,2]
\$\endgroup\$
3
\$\begingroup\$

Haskell, 34 33 bytes

This is based on the answer by xnor, who suggested I post it myself.

EDIT: xnor found a byte to save.

f(a:r@(b:_))=max(b:r)$a:f r
f e=e

Try it online!

Basically, I observed that the branching of xnor's method always ends up choosing whichever of the branch expressions is largest, since Haskell uses lexicographic ordering for lists. (The case when a==b also works because f r>=r, which can be proved separately by induction.)

Put differently, whenever b:r > a:f r, then b:r is a correct answer, and otherwise we can recurse to a:f r.

So instead of checking a<b in advance, I just calculate both expressions and take the maximum. This could give an exponential blowup, although Haskell's laziness avoids that unless a and b are equal.

\$\endgroup\$
  • 1
    \$\begingroup\$ Looks like max(b:r)$a:f r saves a byte. \$\endgroup\$ – xnor Mar 28 '17 at 1:28
2
\$\begingroup\$

Python 3, 79 bytes

def f(x):
 for i,a in enumerate(x):
  m=max(x[i+1:])
  if m>a:x[i]=m;break

Mutates the original array (list) given to it. I'm unhappy that this isn't a lambda and I'm sure there are better optimizations; I'll hopefully address those later.

Brief explanation

It takes the max of the array past the current element (starting with the zeroth). It then compares this to the element itself: if the max is greater, replace the current element with it and stop, otherwise, increment by one and keep trying that.

\$\endgroup\$
2
\$\begingroup\$

Ruby, 66 61 bytes

->a{i=r=-1;a.map{|e|m=a[i+=1,a.size].max;r&&m>e ?(r=!r;m):e}}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

C, 47 bytes

f(p,n)int*p;{n>1?*p<p[1]?*p=p[1]:f(p+1,n-1):0;}

Recursive implementation taking as its input a pointer to the first element of an array, and the length of the array. Modifies the array in place.

\$\endgroup\$
  • \$\begingroup\$ Your code return seems invalid ideone.com/83HJqN \$\endgroup\$ – Khaled.K Apr 2 '17 at 6:40
  • \$\begingroup\$ @Khaled.K It shows the output "3 4 4 -1 2", which is one of the allowed outputs given in the question. What do you think is wrong with it? \$\endgroup\$ – hvd Apr 2 '17 at 7:11
  • \$\begingroup\$ I see, the question is quite unclear about that though \$\endgroup\$ – Khaled.K Apr 2 '17 at 7:48
2
\$\begingroup\$

SWI-Prolog, 70 bytes

f([H|T],[S|T]):-max_list(T,S),S>H,!.
f([H|T],[H|R]):-f(T,R),!.
f(I,I).

First clause replaces the first element of the list with the maximum value of the rest of the list, but only if this max is bigger. The second clause recursively calls the predicate for the tail of the list. If none of these clauses succeed, the third clause simply returns the input.

This return just one of the possible solutions. It's trivial to find all of them with very similar code, but then the case where no change is possible takes a lot more bytes to handle.

Example:

?- f([-1,4,0,4,7,2,3], O).
O = [7, 4, 0, 4, 7, 2, 3]
\$\endgroup\$
1
\$\begingroup\$

R, 71 bytes

a=scan()
l=length(a) 
lapply(1:l,function(x){
  a[x]=max(a[x:l])
  a
})
\$\endgroup\$
1
\$\begingroup\$

C, 80 bytes

i,j;f(l,n)int*l;{for(i=0;i<n;++i)for(j=i;++j<n;)if(l[i]<l[j]){l[i]=l[j];j=i=n;}}

Call with:

int main()
{
    int a[5]={3,1,4,-1,2};
    f(a,5);
    for(int k=0;k<5;++k)
        printf("%d ", a[k]);
}
\$\endgroup\$
1
\$\begingroup\$

Python 2, 89 bytes

Try it online -1 byte thanks to @TemporalWolf
-25 bytes thanks to @ValueInk
-7 bytes thanks to @Cole

Function that mutates input array

def F(A):
 for i in range(len(A)):
    r=[y for y in A[i+1:]if y>A[i]]
    if r:A[i]=r[0];break

If there was no need to stop after first iteration, it would be a bit prettier

\$\endgroup\$
  • \$\begingroup\$ This appears not to work. Try [1, 3, 5, 7]; it returns [3, 3, 5, 7]. \$\endgroup\$ – HyperNeutrino Mar 24 '17 at 21:31
  • 1
    \$\begingroup\$ A[i]<y and => y>A[i]and saves 1 \$\endgroup\$ – TemporalWolf Mar 24 '17 at 21:31
  • \$\begingroup\$ @HyperNeutrino If I inderstand task right, that is valid outut \$\endgroup\$ – Dead Possum Mar 24 '17 at 21:36
  • 1
    \$\begingroup\$ Consider r=[y for y in A[i+1:]if y>A[i]]\n if r:A[i]=r[0];break to drop your score to 96! \$\endgroup\$ – Value Ink Mar 24 '17 at 23:12
  • 1
    \$\begingroup\$ Might I suggest what I suggested for one of the other Python answers: convert what you have to a function which mutates the original array so that you can avoid printing and input(). \$\endgroup\$ – cole Mar 25 '17 at 7:35
1
\$\begingroup\$

Python 2, 60 bytes

f=lambda x:x and[x[:1]+f(x[1:]),[max(x)]+x[1:]][x[0]<max(x)]

Try it Online!

Explanation: Recursively checks if a given element is less than the max element in the rest of the list. If so, returns the list with max replacing the first element.

\$\endgroup\$
1
\$\begingroup\$

TI-Basic, 72 bytes

Prompt L1
If 2≤dim(L1
Then
For(A,1,dim(L1)-1
For(B,A,dim(L1
If L1(A)<L1(B
Then
L1(B→L1(A
Goto E
End
End
End
End
Lbl E
L1

Explanation:

Prompt L1          # 4 bytes, input list
If 2≤dim(L1        # 7 bytes, if the list has 2 or 1 element(s), skip this part and return it
Then               # 2 bytes
For(A,1,dim(L1)-1  # 12 bytes, for each element in the list other than the last
For(B,A,dim(L1     # 9 bytes, for each element after that one
If L1(A)<L1(B      # 12 bytes, if the second is larger than the first
Then               # 2 bytes
L1(B→L1(A          # 10 bytes, replace the first with the second
Goto E             # 3 bytes, and exit
End                # 2 bytes
End                # 2 bytes
End                # 2 bytes
End                # 2 bytes
Lbl E              # 3 bytes
L1                 # 2 bytes, implicitly return L1
\$\endgroup\$
1
\$\begingroup\$

sh, 118 bytes

Input integers are passed as arguments to the script.

l=("$@");for i in "$@";{ for j in "$@";{(($i<$j))&&{ l[$x]=$j;echo ${l[@]};exit;};};shift;x=`expr $x+1`;};echo ${l[@]}

Breakdown:

l=("$@");                      #copy original list
for i in "$@";{ for j in "$@"; #check all elements j that follow element i in list
{(($i<$j))&&{ l[$x]=$j;echo ${l[@]};exit;};};   #if i<j, make i=j; print list, done
shift;                         #makes sure that i is compared only to j that occur after it
x=`expr $x+1`;};               #keeps track of i'th position in the list
echo ${l[@]}                   #prints list if it was unchanged
\$\endgroup\$
0
\$\begingroup\$

PHP, 88 Bytes

<?for(;$i+1<$c=count($a=$_GET)&&$a[+$i]>=$a[++$i];);$i>=$c?:$a[$i-1]=$a[$i];print_r($a);

Breakdown

for(;
$i+1<($c=count($a=$_GET))  # first condition end loop if the item before the last is reach 
&&$a[+$i]>=$a[++$i] # second condition end loop if item is greater then before 
;);
$i>=$c?:$a[$i-1]=$a[$i]; # replace if a greater item is found
print_r($a); #Output
\$\endgroup\$
0
\$\begingroup\$

Haskell, 48 bytes

f(b:l)|l>[],m<-maximum l,b<m=m:l|1<2=b:f l
f x=x

Usage example: f [1,1,2,1] -> [2,1,2,1]. Try it online!.

If the input list has at least one element, bind b to the first element and l to the rest of the list. If l is not empty and b less than the maximum of l, return the maximum followed by l, else return b followed by a recursive call of f l. If the input list is empty, return it.

\$\endgroup\$
0
\$\begingroup\$

Racket 202 bytes

(let((g(λ(L i n)(for/list((c(in-naturals))(l L))(if(= c i)n l))))(ol'()))
(for((c(in-naturals))(i L))(for((d(in-range c(length L)))#:when(>(list-ref L d)i))
(set! ol(cons(g L c(list-ref L d))ol))))ol)

Ungolfed:

(define (f L)
  (let ((replace (λ (L i n)   ; sub-function to replace i-th item in list L with n;
                   (for/list ((c (in-naturals))
                              (l L))
                     (if (= c i) n l))))
        (ol '()))             ; outlist initially empty; 
    (for ((c (in-naturals))               ; for each item in list
          (i L))
      (for ((d (in-range c (length L)))   ; check each subsequent item in list
            #:when (> (list-ref L d) i))  ; if greater, replace it in list
        (set! ol (cons (replace L c (list-ref L d)) ol)))) ; and add to outlist.
    ol))          ; return outlist.

Testing:

(f '(3 1 4 -1 2))

Output:

'((3 1 4 2 2) (3 2 4 -1 2) (3 4 4 -1 2) (4 1 4 -1 2))
\$\endgroup\$
0
\$\begingroup\$

C, 67 bytes

Single Run, 67 bytes Live

j;f(l,i)int*l;{j=i-1;while(i-->0)while(j-->0)l[j]=fmax(l[i],l[j]);}

Single Step, 78 bytes Live

j;f(l,i)int*l;{j=i-1;while(i-->0)while(j-->0)if(l[j]<l[i]){l[j]=l[i];return;}}

Tail Maxima, 96 bytes Live

x;i;j;f(l,n)int*l;{do{x=0;for(i=0;i<n;i++)for(j=0;j<i;j++)if(l[j]<l[i])l[j]=l[i],x=1;}while(x);}
\$\endgroup\$
0
\$\begingroup\$

Python 3, 103 102 bytes

lambda a:([a[:i]+[max(a[i:])]+a[i+1:]for i in range(len(a))if-~i==len(a)or max(a[i+1:])>a[i]]+[[]])[0]

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.