21
\$\begingroup\$

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

  1. start with a list containing n copies of n.
  2. do the following n times:
  3. 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 : the answer with the smallest byte-count wins.


Python implementation for checking purposes.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ You might want to explicitly state that ith is always 1-indexed. \$\endgroup\$ Mar 28, 2018 at 10:01
  • \$\begingroup\$ Do we really have to manipulate array? I get to a shorter answer without manipulating any array, producing an acceptable output. \$\endgroup\$ Mar 28, 2018 at 14:20
  • 2
    \$\begingroup\$ @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) \$\endgroup\$
    – Leaky Nun
    Mar 28, 2018 at 14:21

20 Answers 20

6
\$\begingroup\$

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]]
\$\endgroup\$
1
  • \$\begingroup\$ You outgolfed the un-outgolf-able. \$\endgroup\$
    – Leaky Nun
    Mar 29, 2018 at 0:58
5
\$\begingroup\$

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

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

Jelly, 12 bytes

R‘®¦<³S©$пṚ

Try it online!

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

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!

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

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:

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
\$\endgroup\$
2
\$\begingroup\$

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.
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\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\$ 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
    Mar 29, 2018 at 14:22
2
\$\begingroup\$

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!

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

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!

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

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;
  }
\$\endgroup\$
2
  • \$\begingroup\$ seems like you have some unnecessary whitespace so this should be 153 bytes -- note that I don't know PHP. \$\endgroup\$
    – Giuseppe
    Apr 4, 2018 at 20:28
  • \$\begingroup\$ yep, just realize, thank you, editing now. \$\endgroup\$ Apr 4, 2018 at 20:30
1
\$\begingroup\$

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.

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

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!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ (I-1) --> ~-I \$\endgroup\$
    – Leaky Nun
    Mar 28, 2018 at 13:50
  • 1
    \$\begingroup\$ 70 bytes, initializing i=I and decrementing. \$\endgroup\$ Mar 28, 2018 at 13:58
1
\$\begingroup\$

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!

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

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
\$\endgroup\$
1
\$\begingroup\$

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.

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

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
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
5
  • \$\begingroup\$ Your static/global initialization because multiple test cases is not allowed, as functions have to be callable more than once. \$\endgroup\$ 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
    Mar 29, 2018 at 9:05
  • 1
    \$\begingroup\$ Here is the relevant meta post: codegolf.meta.stackexchange.com/a/4940/73111 \$\endgroup\$ Mar 29, 2018 at 10:33
  • \$\begingroup\$ You could golf m[j]--,p() to p(m[j]--) and save a byte. \$\endgroup\$ Mar 29, 2018 at 10:36
  • \$\begingroup\$ 128 bytes \$\endgroup\$
    – ceilingcat
    Oct 6, 2018 at 5:05
0
\$\begingroup\$

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))))))
\$\endgroup\$
0
\$\begingroup\$

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.

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

K (ngn/k), 34 32 bytes

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

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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