Reverse Range Successors

Question

Given a positive integer n, do the following (and output every stage):

start with a list containing n copies of n.
do the following n times:
at the ith step, gradually decrement the ith entry of the list until it reaches i

So, for example, if the given n is 4, then you start with [4,4,4,4], and then at the first step you have [3,4,4,4], [2,4,4,4], [1,4,4,4]. At the second step, you have [1,3,4,4], [1,2,4,4]. At the third step you have [1,2,3,4]. Nothing is done on the fourth step.

So your output is [[4,4,4,4],[3,4,4,4],[2,4,4,4],[1,4,4,4],[1,3,4,4],[1,2,4,4],[1,2,3,4]].

Any reasonable input/output format is permitted.

Standard loopholes apply. This is code-golf: the answer with the smallest byte-count wins.

Python implementation for checking purposes.

You might want to explicitly state that ith is always 1-indexed. — Kevin Cruijssen, Commented Mar 28, 2018 at 10:01
Do we really have to manipulate array? I get to a shorter answer without manipulating any array, producing an acceptable output. — Olivier Grégoire, Commented Mar 28, 2018 at 14:20
@OlivierGrégoire You do not have to follow the steps, you just need to produce the output in a reasonable format. (i.e. go ahead) — Leaky Nun, Commented Mar 28, 2018 at 14:21

Jonathan Allan · Accepted Answer · 2018-03-28 21:10:37Z

Jelly, 9 bytes

r€⁸Œp»\QṚ

Try it online!

How?

r€⁸Œp»\QṚ - Link: integer, N    e.g. 4
 €        - for €ach of implicit range of N (i.e. for i in [1,2,3,...N])
  ⁸       -   with the chain's left argument, N on the right:
r         -     inclusive range (for i<=N this yields [i, i+1, ..., N]
          - ...leaving us with a list of lists like the post-fixes of [1,2,3,....,N]
          -                     e.g. [[1,2,3,4],[2,3,4],[3,4],[4]]
   Œp     - Cartesian product* of these N lists
          -                     e.g. [[1,2,3,4],[1,2,4,4],[1,3,3,4],[1,3,4,4],[1,4,3,4],[1,4,4,4],[2,2,3,4],[2,2,4,4],[2,3,3,4],[2,3,4,4],[2,4,3,4],[2,4,4,4],[3,2,3,4],[3,2,4,4],[3,3,3,4],[3,3,4,4],[3,4,3,4],[3,4,4,4],[4,2,3,4],[4,2,4,4],[4,3,3,4],[4,3,4,4],[4,4,3,4],[4,4,4,4]]
      \   - cumulative reduce with:
     »    -   maximum (vectorises)
          -                     e.g. [[1,2,3,4],[1,2,4,4],[1,3,4,4],[1,3,4,4],[1,4,4,4],[1,4,4,4],[2,4,4,4],[2,4,4,4],[2,4,4,4],[2,4,4,4],[2,4,4,4],[2,4,4,4],[3,4,4,4],[3,4,4,4],[3,4,4,4],[3,4,4,4],[3,4,4,4],[3,4,4,4],[4,4,4,4],[4,4,4,4],[4,4,4,4],[4,4,4,4],[4,4,4,4],[4,4,4,4]]
       Q  - de-duplicate        e.g. [[1,2,3,4],[1,2,4,4],[1,3,4,4],[1,4,4,4],[2,4,4,4],[3,4,4,4],[4,4,4,4]]
        Ṛ - reverse             e.g. [[4,4,4,4],[3,4,4,4],[2,4,4,4],[1,4,4,4],[1,3,4,4],[1,2,4,4],[1,2,3,4]]

* It may be easier to see what's going on with the Cartesian product used above with a different input:

the Cartesian product of [[0,1,2],[3,4],[5]]
is [[0,3,5],[0,4,5],[1,3,5],[1,4,5],[2,3,5],[2,4,5]]

\$\begingroup\$ You outgolfed the un-outgolf-able. \$\endgroup\$
– Leaky Nun
Commented Mar 29, 2018 at 0:58 — Leaky Nun, Commented Mar 29, 2018 at 0:58

Giuseppe · Accepted Answer · 2018-03-28 21:39:39Z

5

R, 83 82 74 bytes

N=rep(n<-scan(),n);while({print(N);any(K<-N>1:n)})N[x]=N[x<-which(K)[1]]-1

Try it online!

Instead of a double for-loop, a while loop is sufficient here: we find the first index where the list is greater than the index, and decrement there.

K has TRUE wherever N[i]>i, which(K) returns the true indices, and we take the first with [1].

edited Mar 28, 2018 at 21:39

answered Mar 28, 2018 at 11:55

Giuseppe

28.8k3 gold badges31 silver badges104 bronze badges

Add a comment |

DELETE_ME · Accepted Answer · 2018-03-28 05:32:32Z

3

Jelly, 12 bytes

R‘®¦<³S©$Ð¿Ṛ

Try it online!

answered Mar 28, 2018 at 5:32

DELETE_ME

17.3k2 gold badges37 silver badges70 bronze badges

\$\begingroup\$ 13 bytes without register: Try it online! \$\endgroup\$
– DELETE_ME
Commented Mar 28, 2018 at 5:37

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

2

JavaScript (ES6), 75 bytes

f=(n,a=Array(n).fill(n))=>[[...a],...a.some(v=>v>++j,j=0)?f(a[j-1]--,a):[]]

Try it online!

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Mar 28, 2018 at 8:53

Arnauld

195k20 gold badges179 silver badges644 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

2

APL+WIN, 54 bytes

Prompts for screen input of integer

((⍴m)⍴n)-+⍀m←0⍪(-0,+\⌽⍳n-1)⊖((+/+/m),n)↑m←⊖(⍳n)∘.>⍳n←⎕

Outputs a matrix with each row representing the result of each step e.g. for 4:

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Mar 28, 2018 at 11:25

Graham

6,5861 gold badge14 silver badges11 bronze badges

Add a comment |

Dennis · Accepted Answer · 2018-03-28 15:33:02Z

Jelly, 11 bytes

x`’Jḟḣ1Ʋ¦ÐĿ

Try it online!

How it works

x`’Jḟḣ1Ʋ¦ÐĿ  Main link. Argument: n

x`           Repeat self; yield an array of n copies of n.
         ÐĿ  While the results are unique, repeatedly call the link to the left.
             Return the array of all unique results, including the initial value.
  ’     ¦      Decrement the return value at all indices specified by the chain
               in between.
       Ʋ         Combine the four links to the left into a monadic chain.
   J               Indices; yield [1, ..., n].
    ḟ              Filterfalse; remove all indices that belong to the return value.
     ḣ1            Head 1; truncate the result to length 1.

Dat · Accepted Answer · 2018-03-28 16:56:47Z

2

Python 3, 91 bytes

n=int(input())
x=[n]*n;print(x)
for i in range(n):
    for j in[0]*(n-i-1):x[i]-=1;print(x)

Try it online!

answered Mar 28, 2018 at 16:56

Dat

9271 gold badge5 silver badges15 bronze badges

\$\begingroup\$ 1 space is enough to indent code in python. Removing unnecessary spaces and switching to python 2 saves 10 bytes: check it out \$\endgroup\$
– Dead Possum
Commented Mar 29, 2018 at 9:56
\$\begingroup\$ @DeadPossum, even though I know I could do better in Python 2, its soon going to be obsolete so I wanted to practice my Python 3 skills as most as possible. \$\endgroup\$
– Dat
Commented Mar 29, 2018 at 14:22

Add a comment |

X1M4L · Accepted Answer · 2018-03-29 11:46:42Z

2

Java (OpenJDK 8), 135 bytes

a->{int r[]=new int[a],i=0;java.util.Arrays x=null;x.fill(r,a);for(r[0]++;i<a;r[i++]++)for(;--r[i]>i;System.out.print(x.toString(r)));}

Try it online!

Explanation:

int r[]=new int[a],i=0;    //Initialize array and loop counter
java.util.Arrays x=null;    //reduces the number of of “Arrays” needed from 3 to 1
x.fill(r,a);    //Sets each value in array length n to int n
for(r[0]++;i<a;r[i++]++)    //Increment everything!
  for(;--r[i]>i;    //If decremented array element is larger than element number:
     System.out.print(x.toString(r)));}    //Print the array

Credit:

-8 bytes thanks to Jonathan Frech!

-16 bytes thanks to Kevin Cruijssen!

-1 byte thanks to Okx!

edited Mar 29, 2018 at 11:46

answered Mar 28, 2018 at 11:47

X1M4L

1,83611 silver badges17 bronze badges

4

\$\begingroup\$ The import java.util.*; is part of the byte-count I'm afraid. And @JonathanFrech's code can be golfed by 4 more bytes by putting the ,i=0 after the r[], and changing <-~a to <=a. (Try it online. 144 bytes) (and I changed ~-i to i-1 to make it more readable..) \$\endgroup\$
– Kevin Cruijssen
Commented Mar 28, 2018 at 12:09
1

\$\begingroup\$ 139 bytes by getting rid of the import java.util.*; by using java.util.Arrays x=null; and x.fill and x.toString. (Note that your current solution is 155 bytes with the required import java.util.*;.) \$\endgroup\$
– Kevin Cruijssen
Commented Mar 28, 2018 at 12:16
1

\$\begingroup\$ Golf a byte by using for(;r[i-1]>i; rather than for(;r[i-1]!=i;. \$\endgroup\$
– Okx
Commented Mar 28, 2018 at 12:24
2

\$\begingroup\$ @KevinCruijssen Another byte could be saved by golfing ++i<=a to i++<a. \$\endgroup\$
– Jonathan Frech
Commented Mar 28, 2018 at 12:55
1

\$\begingroup\$ Another -2 byte changing the last part to for(r[0]++;i<a;r[i++]++)for(;--r[i]>i;System.out.print(x.toString(r)));. :) Try it online 135 bytes \$\endgroup\$
– Kevin Cruijssen
Commented Mar 29, 2018 at 9:16

| Show 1 more comment

Angs · Accepted Answer · 2018-03-29 12:42:16Z

2

Haskell, 69 67 65 63 bytes

Recursive definition:

f 0=[[]]
f a=map(:(a<$[2..a]))[a,a-1..2]++[1:map(+1)x|x<-f$a-1]

Thanks to Laikoni for 2 bytes!

edited Mar 29, 2018 at 12:42

answered Mar 28, 2018 at 14:53

Angs

4,9872 gold badges15 silver badges36 bronze badges

\$\begingroup\$ The second map is two bytes shorter with a list comprehension: Try it online! \$\endgroup\$
– Laikoni
Commented Mar 29, 2018 at 9:22

Add a comment |

Francisco Hahn · Accepted Answer · 2018-04-04 20:32:34Z

2

PHP, 153 Bytes

Try it online!

Code

function f($n){
$a=array_fill(0,$n,$n);$r=json_encode($a)."\n";$p=0;while($p<$n)
{if($a[$p]!=$p+1){$a[$p]--;$r.=json_encode($a)."\n";}else{$p++;}}echo$r;}

Gonna try to lower the bytes, or finish the recursive function

Explanation

function f($n){
  $a=array_fill(0,$n,$n);          #start with $nlength array filled with $n
  $r=json_encode($a)."\n";         #pushed to the string to output
  $p=0;                            #first position
  while($p<$n){                    #on position $n ($n-1) we do nothing
    if($a[$p]!=$p+1){              #comparing the position+1 to the value
     $a[$p]--;                     #it gets decreased by 1
     $r.= json_encode($a)."\n";    #and pushed
   } else {
     $p++;                       #when position+1 = the value,
   }                               #position is changed ++
  }
   echo $r;
  }

edited Apr 4, 2018 at 20:32

answered Apr 4, 2018 at 17:02

Francisco Hahn

6013 silver badges10 bronze badges

\$\begingroup\$ seems like you have some unnecessary whitespace so this should be 153 bytes -- note that I don't know PHP. \$\endgroup\$
– Giuseppe
Commented Apr 4, 2018 at 20:28
\$\begingroup\$ yep, just realize, thank you, editing now. \$\endgroup\$
– Francisco Hahn
Commented Apr 4, 2018 at 20:30

Add a comment |

ElPedro · Accepted Answer · 2018-03-28 12:03:00Z

1

Python 2, 80 76 bytes

i=input();l=[i]*i;print l
for x in range(i):
 while l[x]>x+1:l[x]-=1;print l

Try it online!

Bit wasteful having two print statements but I can't think of a better way at the moment.

edited Mar 28, 2018 at 12:03

answered Mar 28, 2018 at 11:10

ElPedro

6,4692 gold badges24 silver badges38 bronze badges

\$\begingroup\$ 75 bytes. \$\endgroup\$
– Jonathan Frech
Commented Mar 28, 2018 at 11:45

Add a comment |

Dead Possum · Accepted Answer · 2018-03-28 14:07:07Z

1

Python 2, 70 bytes

-2 bytes thanks to @LeakyNun
-2 bytes thanks to @JonathanFrech

i=I=input()
l=[I]*I
exec"exec'print l;l[-i]-=1;'*max(~-i,2);i-=1;"*~-I

Try it online!

edited Mar 28, 2018 at 14:07

answered Mar 28, 2018 at 13:50

Dead Possum

3,43413 silver badges25 bronze badges

1

\$\begingroup\$ (I-1) --> ~-I \$\endgroup\$
– Leaky Nun
Commented Mar 28, 2018 at 13:50
1

\$\begingroup\$ 70 bytes, initializing i=I and decrementing. \$\endgroup\$
– Jonathan Frech
Commented Mar 28, 2018 at 13:58

Add a comment |

Olivier Grégoire · Accepted Answer · 2018-03-28 14:42:38Z

1

Java (JDK 10), 112 bytes

n->{var s="";for(int i=1,k=n,j;i<=n;k=--k>i?k:n-++i+i)for(j=0;j++<n;)s+=(j<i?j:j>i?n:k)+(j<n?",":";");return s;}

Try it online!

edited Mar 28, 2018 at 14:42

answered Mar 28, 2018 at 14:13

Olivier Grégoire

14.4k3 gold badges32 silver badges56 bronze badges

Add a comment |

miles · Accepted Answer · 2018-03-29 00:02:33Z

1

J, 17 15 bytes

+/\@,(#=)@i.&.-

Try it online!

Explanation

+/\@,(#=)@i.&.-  Input: n
              -  Negate n
          i.     Reverse of range [0, n)
       =           Identity matrix of order n
      #            Copy each row by the reverse range
              -  Negate
    ,            Prepend n
+/\              Cumulative sum of rows

edited Mar 29, 2018 at 0:02

answered Mar 28, 2018 at 23:48

miles

17k2 gold badges29 silver badges94 bronze badges

Add a comment |

Neil · Accepted Answer · 2018-03-30 00:36:33Z

Retina, 49 bytes

.+
*
_
$`_,$= 
.{*\`_+,(_+)
$.1
0`(\b(_+),\2)_
$1

Try it online! Explanation:

.+
*

Convert the input to unary.

_
$`_,$=

Create a list of n copies of i,n where i is the index of the copy.

Don't print anything (when the loop finishes).

Loop until the pattern does not change.

*\`_+,(_+)
$.1

Temporarily delete the is and convert the ns to decimal and output.

0`(\b(_+),\2)_
$1

Take the first list entry whose value exceeds its index and decrement it.

xbarbie · Accepted Answer · 2018-04-11 08:08:12Z

Python 3, 70 67 65 bytes

def f(n):
 k=0;a=[n]*n
 while k<n-1:print(a);k+=a[k]==k+1;a[k]-=1

Try it online!

(67) Converting to function: -3 bytes
(65) Removing unneeded parentheses: -2 bytes

Ungolfed version:

def f(n):
    k = 0
    a = [n] * n             # create n-item list with all n's
    while k < n - 1:        # iterate through columns 0..n-1
        print(a)            # print whole list
        if a[k] == k + 1:   # move to the next column when current item reaches k+1
            k += 1
        a[k] -= 1           # decrement current item

GPS · Accepted Answer · 2018-03-29 09:01:55Z

0

C (clang), 131 141 bytes

i,j,k,m[99];p(){for(k=0;m[k];printf("%d ",m[k++]));puts("");}f(n){for(j=k=m[n]=0;k<n;m[k++]=n);p();for(;j<n;j++)for(i=1;i++<n-j;m[j]--,p());}

Try it online!

This will work for all n upto 99. TIO truncates output. It can support arbitrarily larger n by changing size of array m as memory permits.

Following is limited to n=1..9 but is significantly shorter

C (clang), 89 92 bytes

i,j;char m[12];f(n){j=!puts(memset(m,n+48,n));for(;j<n;j++)for(i=1;i++<n-j;m[j]--,puts(m));}

Try it online!

Updated: Modified to avoid dependence on static initialization

edited Mar 29, 2018 at 9:01

answered Mar 28, 2018 at 13:59

GPS

3611 silver badge6 bronze badges

\$\begingroup\$ Your static/global initialization because multiple test cases is not allowed, as functions have to be callable more than once. \$\endgroup\$
– Jonathan Frech
Commented Mar 28, 2018 at 19:07
\$\begingroup\$ @Jonathan Updated answers. I always wondered if this should be allowed, and couldn't make up my mind. \$\endgroup\$
– GPS
Commented Mar 29, 2018 at 9:05
1

\$\begingroup\$ Here is the relevant meta post: codegolf.meta.stackexchange.com/a/4940/73111 \$\endgroup\$
– Jonathan Frech
Commented Mar 29, 2018 at 10:33
\$\begingroup\$ You could golf m[j]--,p() to p(m[j]--) and save a byte. \$\endgroup\$
– Jonathan Frech
Commented Mar 29, 2018 at 10:36
\$\begingroup\$ 128 bytes \$\endgroup\$
– ceilingcat
Commented Oct 6, 2018 at 5:05

Add a comment |

NikoNyrh · Accepted Answer · 2018-03-29 09:40:30Z

0

Clojure, 132 bytes

#(loop[R[(vec(repeat % %))]j(- % 2)i 0](if(> i j)R(recur(conj R(update(last R)i dec))(if(= i j)(- % 2)(dec j))(if(= i j)(inc i)i))))

I was hoping this to be shorter...

Less stateful but longer at 141 bytes:

#(apply map list(for[i(range %)](concat(repeat(nth(cons 0(reductions +(reverse(range %))))i)%)(range % i -1)(if(>(dec %)i)(repeat(inc i))))))

edited Mar 29, 2018 at 9:40

answered Mar 29, 2018 at 8:50

NikoNyrh

2,6819 silver badges8 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

Python 3, 101 bytes

def f(n):
 p=print;m=[n for_ in range(n)];p(m)
 for i in range(n):
    while m[i]>1+i:m[i]-=1;p(m)

I could probably golf more with the print, but I'm away from my computer and am not entirely sure of python 2's rules on setting a variable to print. I'll update later when I get to a computer or if someone clarifies in the comments.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Mar 29, 2018 at 22:04

AvahW

5434 silver badges7 bronze badges

Add a comment |

ngn · Accepted Answer · 2018-12-15 19:38:56Z

0

K (ngn/k), 34 32 bytes

{{x[y]-:1;x}\(,x#x),,/(|!x)#'!x}

Try it online!

edited Dec 15, 2018 at 19:38

answered Mar 28, 2018 at 21:30

ngn

15.3k2 gold badges43 silver badges87 bronze badges

Add a comment |

Stack Exchange Network

Reverse Range Successors

20 Answers 20

Jelly, 9 bytes

How?

R, 83 82 74 bytes

Jelly, 12 bytes

JavaScript (ES6), 75 bytes

APL+WIN, 54 bytes

Jelly, 11 bytes

How it works

Python 3, 91 bytes

Java (OpenJDK 8), 135 bytes

Haskell, 69 67 65 63 bytes

PHP, 153 Bytes

Python 2, 80 76 bytes

Python 2, 70 bytes

Java (JDK 10), 112 bytes

J, 17 15 bytes

Explanation

Retina, 49 bytes

Python 3, 70 67 65 bytes

C (clang), 131 141 bytes

C (clang), 89 92 bytes

Clojure, 132 bytes

Python 3, 101 bytes

K (ngn/k), 34 32 bytes

Your Answer

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

Hot Network Questions

Reverse Range Successors

20 Answers 20

Jelly, 9 bytes

How?

R, 83 82 74 bytes

Jelly, 12 bytes

JavaScript (ES6), 75 bytes

APL+WIN, 54 bytes

Jelly, 11 bytes

How it works

Python 3, 91 bytes

Java (OpenJDK 8), 135 bytes

Haskell, 69 67 65 63 bytes

PHP, 153 Bytes

Python 2, 80 76 bytes

Python 2, 70 bytes

Java (JDK 10), 112 bytes

J, 17 15 bytes

Explanation

Retina, 49 bytes

Python 3, 70 67 65 bytes

C (clang), 131 141 bytes

C (clang), 89 92 bytes

Clojure, 132 bytes

Python 3, 101 bytes

K (ngn/k), 34 32 bytes

Your Answer

Sign up or log in

Post as a guest

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

Related

Hot Network Questions

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