title: Numbers by Position

text:
# Question
Title: Numbers by Position
**Challenge**

Print the numbers:

```
1
22
333
4444
55555
666666
7777777
88888888
999999999

```

In that order.

**I/O**

Takes no input. The numbers can have any delimiters desired (or none). That includes lists, cell arrays, .jpeg, etc.... Example outputs:

```
122333444455555666666777777788888888999999999

[1,22,333,4444,55555,666666,7777777,88888888,999999999]

etc....

```

**Code Example**

This is an un-golfed example that may perhaps act as algorithm guide (or maybe not):

# Turing Machine Code, 535 bytes

```
0 * 1 r L
L * _ r 2
2 * 2 r a
a * 2 r M
M * _ r 3
3 * 3 r b
b * 3 r c
c * 3 r N
N * _ r 4
4 * 4 r d
d * 4 r e
e * 4 r f
f * 4 r O
O * _ r 5
5 * 5 r g
g * 5 r h
h * 5 r i
i * 5 r j
j * 5 r P
P * _ r 6
6 * 6 r k
k * 6 r l
l * 6 r m
m * 6 r n
n * 6 r o
o * 6 r Q
Q * _ r 7
7 * 7 r p
p * 7 r q
q * 7 r r
r * 7 r s
s * 7 r t
t * 7 r u
u * 7 r R
R * _ r 8
8 * 8 r v
v * 8 r w
w * 8 r x
x * 8 r y
y * 8 r z
z * 8 r A
A * 8 r B
B * 8 r S
S * _ r 9
9 * 9 r C
C * 9 r D
D * 9 r E
E * 9 r F
F * 9 r G
G * 9 r H
H * 9 r I
I * 9 r J
J * 9 r halt

```

Try it online!

This prints out the numbers with a space delimiter:

```
1 22 333 4444 55555 666666 7777777 88888888 999999999

```

**Challenge Type**

, so shortest answer in bytes (by language) wins.

*Based on a submission in the sandbox.*

# Answer
# Deadfish~, 194 bytes

```
{{i}ddddd}dc{d}{d}iiic{i}{i}ddcc{d}{d}iic{i}{i}dccc{d}{d}ic{i}{i}cccc{d}{d}c{i}{i}iccccc{d}{d}dc{i}{i}iicccccc{d}{d}ddc{i}{i}iiiccccccc{d}{d}dddc{i}{i}iiiicccccccc{d}{d}ddddc{i}{i}iiiiiccccccccc

```

Try it online!
> 3 votes

# Answer
# Google Sheets, 35 bytes

```
=ArrayFormula(Rept(Row(1:9),Row(1:9

```

Sheets will automatically add three trailing parentheses when you exit the cell. Output is one line per row.
> 29 votes

# Answer
# Bash \+ Core utilities, ~~27~~, 25 bytes

```
seq -f8d%f*7-v1+2/n 45|dc

```

Try it online!

---

*Changed seq formatting from %0.f to %f for a 2-byte savings.*

*Modified to print on one line, with no delimiters, instead of having a newline after each number, just because I like that better. Same number of bytes.*

---

This uses the formula $$\left\lfloor\frac{\big\lfloor\sqrt{8n-7}\big\rfloor+1}2\right\rfloor$$

for the \\$n^{th}\\$ digit, where \\$n\\$ goes from 1 to 45.
> 16 votes

# Answer
# 05AB1E, 3 bytes

```
9L×

```

Try it online!

```
9L    Build a list from 1 to 9 {1, 2, 3, 4, 5, 6, 7, 8, 9}
×     copy each number that many times

```
> 16 votes

# Answer
# Python 2, 28 bytes

```
i=1;exec"print`i`*i;i+=1;"*9

```

Try it online!
> 11 votes

# Answer
# APL (dzaima/APL), 6 bytes

Full program, requiring `⎕IO←0`.

```
⍋⍛⌿⍨⎕D

```

Try it online!

`⎕D` on the string "0123456789",

`⍛⌿⍨` replicate the characters by

their grade (0, 1, 2, …, 9)
> 9 votes

# Answer
# Kotlin, 30 bytes

```
{(1..9).map{"$it".repeat(it)}}

```

Try it online!
> 9 votes

# Answer
# , 18 bytes

```
a=1:9;(10^a-1)/9*a

```

Try it online!

Use the formula \\$\frac{10^n-1}{9}\times n\\$ for the \\$n\\$th number.
> 9 votes

# Answer
# APL (Dyalog Unicode), 4 bytes

```
\⍨⍳9

```

Try it online!

### How it works

```
⍳9        ⍝ Integers 1..9
   ⍨      ⍝ Duplicate argument on each side
     \    ⍝ Replicate each element *n* times

```

### Examples

```
Index Generator:    ⍳5          =  1 2 3 4 5
Expand:             2 3 \ 1 4   =  1 1 4 4 4
Commute:            +⍨4         =  4 + 4 = 8

```
> 7 votes

# Answer
# Perl 5, 18 bytes

```
map{say$_ x$_}1..9

```

Try it online!
> 6 votes

# Answer
# brainfuck, 56 bytes

```
+++++++[>+++++++<-]+++++++++[<+[>>.<<-<+>]<[>+<-]>>>+<-]

```

Try it online!

```
+++++++[>+++++++<-]     49 (ASCII "1")
+++++++++[              do 9 times
  <+                    add 1 to output counter
  [                     do that many times
    >>.<<               print character
    -<+>                move value of output counter to temp
  ]
  <[>+<-]               move value of temp back to output counter
  >>>+                  increment character
  <-                    decrement loop counter
]

```
> 6 votes

# Answer
# Retina, 12 bytes

```

9*

$.`*$.`

```

Try it online! Outputs a leading `_` to each number, which appears to be acceptable (would cost 2 bytes to fix if not). Explanation:

```

9*

```

Insert 9 `_`s.

```

$.`*$.`

```

Around each `_`, insert its position repeated appropriately.
> 6 votes

# Answer
# Haskell, ~~30~~ 29 bytes

```
(<$)<*>g<$>g '9'
g c=['1'..c]

```

Try it online!
> 6 votes

# Answer
# APL (Dyalog Unicode), 7 bytesSBCS

```
⎕D/⍨⍳10

```

Try it online!

Uses `⎕IO←0`.

### How it works

```
⎕D/⍨⍳10
⎕D       ⍝ The string '0123456789'
  /⍨     ⍝ Replicate each of them the following times...
    ⍳10  ⍝ 0..9

```
> 5 votes

# Answer
# Brain-Flak, ~~90~~ 82 bytes

```
([(()()())({}){}]){((({})()<([{}]((((()()()){}){}){}){})>)<{({}()<(({}))>)}{}>)}{}

```

Try it online!

## Explanation:

---

Compare this with the output of JoKing's autogolfer

# Brain-Flak, 142 bytes

```
(((((((((((((((((((((((((((((((((((((((((((((((((()()()){}){}){}){}())()))())))()))))())))))()))))))())))))))()))))))))()))))))))){({}<>)<>}<>

```

Try it online!

---

# Strange delimiters, 78 bytes

```
([(()()())({}){}]){((({})()<([{}]((((()()()){}){}){}){})>)<{({}()<(({}))>)}>)}

```

Try it online!

If we decide to play around with our delimiters a bit, we can shave off 4 bytes. This version outputs the correct stuff but with two leading null bytes and null bytes between the chunks:

This is a tiny bit cheaty but it meets the specs of the challenge.

---

And for posterity here is the old super cheaty version that has been made obsolete by my golfs.
> 5 votes

# Answer
# Husk, 5 bytes

```
d´Ṙḣ9

```

Try it online!

Output: `122333444455555666666777777788888888999999999`.
> 5 votes

# Answer
# , 18 bytes

```
echo u:(#48+])i.10

```

Try it online!

# K (oK), ~~11~~ 10 bytes

-1 byte thanks to ngn!

```
,/${x}#!10

```

Try it online!
> 4 votes

# Answer
# Jelly, 5 bytes

```
9ẋ`€Ḍ

```

Try it online!

A niladic link returning a list of integers. If a program printing the numbers is preferred, subsitute `Y` for .

## Explanation

```
9     | Literal 9
 ẋ`€  | Repeat each that many times
    Ḍ | Convert from decimal digits to integer

```
> 4 votes

# Answer
# Perl 6, 13 bytes

```
{1..9 Zx^9+1}

```

Try it online!

Anonymous code block that returns a list of strings by zip string multiplying the range 1 to 9 with itself.
> 4 votes

# Answer
# Java 11 (JDK), ~~60~~ 59 bytes

Not sure if thats the shortest approach but couldn\`t make it shorter even without System.out.print. Output is without delimiters.

*-1 byte thanks to Kevin Cruijssen*

```
v->{for(int i=0;i++<9;System.out.print((i+"").repeat(i)));}

```

Try it online!
> 4 votes

# Answer
# C (gcc), 46 bytes

```
s;main(n){n>9||main(puts(memset(&s,n+48,n)));}

```

Try it online!
> 4 votes

# Answer
# Haskell, 21 bytes

```
[c<$[1..c]|c<-[1..9]]

```

Try it online!

A list of lists of numbers.

**23 bytes**

```
replicate<*>id=<<[1..9]

```

Try it online!

A flat list of numbers.
> 4 votes

# Answer
# , 15 bytes

```
strrep(1:9,1:9)

```

Try it online!
> 4 votes

# Answer
# x86-16 machine code, IBM PC DOS, ~~18~~ 16 bytes

**Binary**:

```
00000000: b839 0ab2 09b1 2dcd 1048 2aca 4a75 f8c3  .9....-..H*.Ju..

```

**Listing**:

```
B8 0A39     MOV  AX, 0A39H              ; AH = 0AH, AL = '9'
B2 0A       MOV  DL, 10                 ; DL as counter value
B1 2D       MOV  CL, 1+2+3+4+5+6+7+8+9  ; start digit repeat 45 times
        NLOOP:
CD 10       INT  10H                    ; call BIOS - write digit * CX times
48          DEC  AX                     ; decrement ASCII digit
4A          DEC  DX                     ; decrement counter value
2A CA       SUB  CL, DL                 ; reduce digit repeat value by counter
75 F8       JNZ  NLOOP                  ; loop until 0
C3          RET                         ; return to DOS

```

Try it online!

**Explanation**:

This uses the PC BIOS API's `INT 10H` / `0AH` function to write the ASCII char in `AL` to the screen `CX` number of times. However, this function does not update the cursor position to the end of the output -- it just stays where it started. In other words, the next call simply overstrikes existing characters writing over them. Making a BIOS call to advance the cursor is expensive byte-wise.

Since going forward isn't going to work, we go backwards starting from `'9'`. It writes `'9'` 45 times, then `'8'` 36 times, `'7'` 28 times, etc -- each time starting from the first column overwriting like so:

```
999999999999999999999999999999999999999999999
888888888888888888888888888888888888999999999
777777777777777777777777777788888888999999999
666666666666666666666777777788888888999999999
555555555555555666666777777788888888999999999
444444444455555666666777777788888888999999999
333333444455555666666777777788888888999999999
222333444455555666666777777788888888999999999
122333444455555666666777777788888888999999999

```

**Output**:
> 4 votes

# Answer
# Fig, \\$6\log\_{256}(96)\approx\\$ 4.939 bytes

```
Mcd'*_

```

Try it online!

Lyxal tried to outgolf me in my own language again.

```
Mcd'*_ # Full program
 cd    # Digits
M  '   # Map each digit string
    *  # Repeat the digit
     _ # By the number form of it

```
> 4 votes

# Answer
# Julia, 22 bytes

```
1:9 .|>i->show("$i"^i)

```

Attempt This Online!

prints

```
"1""22""333""4444""55555""666666""7777777""88888888""999999999"

```

Relying on the repl for printing output we can get to 17 bytes

```
~i="$i"^i;.~(1:9)

```
> 4 votes

# Answer
# PowerShell, 15 bytes

```
1..9|%{"$_"*$_}

```

Try it online!
> 3 votes

# Answer
# Icon, 27 bytes

```
write(1(i:=1to 9,1to i))&\z

```

Try it online!
> 3 votes

# Answer
# JavaScript (ES8), 33 bytes

```
f=n=>n>9?'':''.padEnd(n,n)+f(-~n)

```

Try it online!

### Commented

```
f = n =>            // n = counter, initially undefined
  n > 9 ?           // if n is greater than 9:
    ''              //   stop recursion
  :                 // else:
    ''.padEnd(n, n) //   pad an empty string with n digits n
                    //   this leaves the empty string unchanged for n undefined
    + f(-~n)        //   add the result of a recursive call with n + 1

```

### Building in reverse order (38 bytes)

A somewhat funny alternate method is to build the string from \\$n=9\\$ to \\$n=1\\$ and pad the recursive call instead of an empty string.

By doing it this way, the required padding length is:

$$L\_n=\left\lfloor\frac{n^2}{2}+1\right\rfloor$$

```
f=(n=9)=>n?f(n-1).padEnd(n*n/2+1,n):''

```

Try it online!
> 3 votes

# Answer
# T-SQL, 69 bytes

```
SELECT top 9replicate(1+number,1+number)FROM spt_values WHERE'p'=type

```

**Try it online**
> 3 votes

# Answer
# jq (`-nr`), ~~20~~ 19 characters

```
range(9)+1|"\(.)"*.

```

Thanks to:

* 2x-1 for pointing out that `range()` does *not* produce array, so operators will see separate numbers.

Sample run:

```
bash-5.0$ jq -nr 'range(9)+1|"\(.)"*.'
1
22
333
4444
55555
666666
7777777
88888888
999999999

```

Try it online!
> 3 votes

# Answer
# Charcoal, 5 bytes

```
⭆χ⭆ιι

```

Try it online! Link is to verbose version of code. Outputs without separators. The first `StringMap` could be changed into a `for` statement for the same byte count. Explanation:

```
 χ       Predefined variable 10
⭆        Map over implicit range and join
   ι     Current index
  ⭆      Map over implicit range and join
    ι    Outer index
         Implicitly print

```
> 3 votes

# Answer
# C (gcc), ~~54~~ 53 bytes

```
i;j;f(){for(i=0;9/++i;)for(j=0;j++<i;)putchar(48+i);}

```

Try it online!

No delimiters between the numbers.
> 3 votes

# Answer
# ~~5~~ ~~4~~ 3 bytes

```
@π┐

```

Uncompressed:

```
$*9N

```

Repeat 1..9 N times.

# Explanation

```
     M % Map in the range
9      % From 1 to 9
  a$   % Stringify the current counter
 a  *  % Repeat that string by the current counter

```
> 3 votes

# Answer
# Japt `-P`, ~~5~~ 4 bytes

```
AÇçZ

```

Test it
> 3 votes

# Answer
# Erlang (escript), 49 bytes

```
f()->[X*(math:pow(10,X)-1)/9||X<-lists:seq(1,9)].

```

Try it online!
> 3 votes

# Answer
# C (gcc), 50 bytes

```
n;f(i){for(i=0;i++<9;)for(n=i;n--;)putchar(48+i);}

```

Try it online!
> 3 votes

# Answer
# Japt, 4 bytes

```
AÇîZ

```

Try it

```
NaN

```
> 3 votes

# Answer
This is my dumbest code golf submission ever, but here it goes

# SQLite, 53 bytes

```
SELECT'122333444455555666666777777788888888999999999'

```

Try it online!
> 3 votes

# Answer
# Stax, 5 bytes

```
╜├ìíy

```

Try it online or try it online unpacked (6 bytes).

**Explanation (of the unpacked version):**

```
Vd      # Push constant "0123456789"
  A     # Push 10
   r    # Pop and push a list in the range [0, 10)
    :B  # Repeat the characters in the string the integer amount of times:
        #  "122333444455555666666777777788888888999999999"
        # (after which the top of the stack is output implicitly as result)

```
> 3 votes

# Answer
# \[VBA\] 58 bytes

```
i=1:While i<0:For x=1 to i:Debug.Print i:Next x:i=i+1:wend

```

Can be ran in Immediate
> 3 votes

# Answer
# C (gcc), 47 bytes

```
k;main(i){for(;9>printf("%d",i*++k);i=i*10+1);}

```

Try it online!

# C (gcc), 49 bytes

```
main(i){for(;9>printf("%lX",(i*1L<<4*i++)/15););}

```

Try it online!
> 3 votes

# Answer
# COW, 75 bytes

```
MoOMoOMoOMoOMoOMoOMoOMoOMoOMOOmoOMoOMMMmoOMMMMOOmOoOOMmoOMOomoomOomOoMOomoo

```

Try it online!

# Uncowed

```
moo ]    mOo <    MOo -    oom o
MOO [    moO >    MoO +    MMM =

+++++++++[>+=>=[<o>-]<<-]

```
> 3 votes

# Answer
# Brainetry, 451 bytes

This is the golfed version, ungolfed version below.

```
a b c d
a b c d e f g h
a b c d e f g h
a b c
a b c d
a b
a b c d e
a b
a b c d
a b c d
a b c d
a b c d
a b c d
a b c
a b c d e f g h i
a b
a b c d
a b c d e f g h i
a b c
a b c
a b c d e
a b c d e
a b c
a b c d e
a b c d e f g h
a b
a b
a b c d
a b c d e f g h
a b c
a b c d e f g
a b
a b c d e
a b
a b c d
a b c
a b c d e f g h i
a b
a b c d e f g h
a b c
a b c d
a b
a b c d e
a b c d e f g h i
a b c
a b c
a b c d
a b c
a b c d e
a b c d e f g h i

```

To try this online, follow this link and paste the code in the `btry/replit.btry` file, then hit the green "Run" button.

Golfed version of the program below:

```
Let me explain what
is going on with this brainetry program: this
program will print the digits one to nine
and each of
those is going to
be repeated
as many times as its
own value.
Makes sense, doesn't it?
To achieve such result
we have to play
around with some nice
values in our tape.
That, and we
also have to play smart with our program pointer.
Of course
I would be delighted
to actually explain the algorithm used by this program.
The only problem
is I really
have no idea whatsoever about
what is actually going on.
Let me explain:
brainetry's instructions are a superset
of brainfuck, which means any brainfuck program can
be translated
to brainetry
and it will work.
So this is what I did, I found
a brainfuck program
that completed this task I described and
I just
translated it from brainfuck to
brainetry. Probably
there are simpler approaches
if we take
into consideration the extended operations that brainetry provides ...
However, brainetry
is still in its early stages of development
and I am
still trying to figure
out exactly
what operations to add to
brainetry. Once that set of operations becomes more well-defined
it will be
easier to harness
brainetry's power to write
computer programs. And
once that is finally done,
I will not have to steal random brainfuck programs.

```

This brainetry answer built on top of this answer
> 3 votes

# Answer
# Scala, ~~35~~ 26 bytes

*-9 bytes thanks to user!*

```
()=>1 to 9 map(i=>s"$i"*i)

```

Try it online!
> 3 votes

# Answer
# Vyxal `j`, 3 bytes

```
9ƛẋ

```

Try it Online!

-1 thanks to lyxal
> 3 votes

# Answer
# Add++ `-i`, ~~14~~ 13 bytes

```
L,9Rdz£XbUBvn

```

Try it online!

This is making me cry. A fun feature of like 99% of stack commands is that it applies to the *whole* stack rather than the top of the stack. Very very helpful.

*-1 thanks to caird which kinda makes up for the suffering of this*

## Explained

```
L,9Rdz£XbUBvn
L,              # Start a lambda which is called implicitly by the -i flag
  9R            # Push the range [1...9]
    dz          # and zip it with itself, giving [[1, 1], [2, 2] ... [9, 9]]
      £X        # repeat x[0] by x[1] times for each x in that
        bU      # dump the contents of that onto the stack. This is a very important part because as I said, 99% of lambda stack commands map over to the whole stack, even when using quicks and stuff.
          Bv    # join each item (on the stack...) into a single integer
            n   # and join (the stack...) on newlines

```
> 3 votes

# Answer
# Malbolge, 175 bytes

```
(C%;_#"~[}43WVxwuRt+*NMLmlljGig}CBAc?=vNtLr[v64m321/RzP+Ncha&&Gc#EDBX|{zx=vv:bs6p^]nllk/iVgfdvD'`N#?\\6YY3WUwvvQtPOqLo,JIHGihfCddcx>=<;:9[Y6XVl210/.-O+MLJ`&HG\[!~}|{z>=wv998rp

```

Try it online!
> 3 votes

# Answer
# Julia, 24/21 bytes

w/o

```
(a=1:9).*(10 .^a.-1).÷9

```

and w/ macro:

```
a=1:9;@.a*(10^a-1)÷9

```
* array of numbers, nothing new
> 3 votes

# Answer
# Regenerate `-a`, 15 bytes

```
([1-9])$1{$1-1}

```

Outputs `1` through `999999999` on separate lines. Attempt This Online!

### Explanation

The `-a` flag outputs all possible matches on separate lines.

```
([1-9])$1{$1-1}
 [1-9]           Pick a digit 1 thru 9
(     )          Store it in group 1
       $1        Match group 1 again
         {    }  this many times:
          $1       Group 1 contents
            -1     minus 1

```

---

Alternate `-a` solution, also **15 bytes**:

```
([1-9])(){1,$1}

```

Outputs digits on separate lines. Attempt This Online!

```
([1-9])(){1,$1}
 [1-9]           Pick a digit 1 thru 9
(     )          Store it in group 1
       ()        Match empty string
         {    }  this many times:
          1,       Minimum of once
            $1     Maximum of (group 1 contents) times

```
> 3 votes

# Answer
# Deadfish~, ~~61~~ 54 bytes

```
ioiooioooiooooioooooiooooooioooooooiooooooooiooooooooo

```

Try it online!

-7 bytes thanks to Bubbler.

Separating by zeros:

# Deadfish~, 128 bytes

```
{iiiii}dcdciiccddciiicccdddciiiiccccddddciiiiicccccdddddciiiiiiccccccddddddc{i}dddccccccc{d}iiic{i}ddcccccccc{d}iic{i}dccccccccc

```

Try it online!

By spaces:

# Deadfish~, 159 bytes

```
{iiiii}dc{dd}iiic{ii}ddcc{dd}iic{ii}dccc{dd}ic{ii}cccc{dd}c{ii}iccccc{dd}dc{ii}iicccccc{dd}ddc{ii}iiiccccccc{dd}dddc{ii}iiiicccccccc{dd}ddddc{ii}iiiiiccccccccc

```

Try it online!
> 3 votes

# Answer
# Nibbles, 4 bytes (8 nibbles)

```
,9^$`p

```

```
,9^$`p
        # implicitly map over
,9      # integers from 1 to 9
  ^     # replicating
   `p   # the character of each
        # by itself times

```
> 3 votes

# Answer
# Knight (v2.0-alpha), 21 bytes

```
;=i@W>10=i+1iO*+""i i

```

Try it online!
> 3 votes

# Answer
# Labyrinth, 21 bytes

```
" }*!@
9 : {
:(1""
""

```

Try it online!

```
Intro
9    Push 9

Loop 1
:(""    Duplicate and decrement; exit when top is 0

[9 8 7 6 5 4 3 2 1 0]
Loop 2
1:}     Use the 0 as the basis for repunit;
        append 1, copy to aux.stack  [... i "1"*i | "1"*i]
*!      Multiply i and "1"*i and print; exit when the stack is empty
{       Pull the repunit back  [... i+1 "1"*i]

@       Halt

```

# Labyrinth, 21 bytes

```
1:#
: (*
;  !
%9_:@
"

```

Try it online!

```
Loop: [... "1"*i] -> [... "1"*i "1"*(i+1)]
1     Append 1 (multiply by 10 and add 1)
:     Dup
#(    Stack size - 1 (== i+1)
*!    Multiply and print
:_9%  Test if the current repunit % 9 is 0 and exit loop if so
;:    Discard the test value and dup to increase the stack size by 1

9_:@  Halt

```
> 3 votes

# Answer
# Keg, ~~45~~ ~~11~~ ~~9~~ 8 bytes

```
9Ï^⑷:⅍*⑸

```

Try it online!
> 2 votes

# Answer
# Pure Bash, ~~41~~ 37 bytes

```
for k in {1..9};{ echo $[10**k/9*k];}

```

Try it online!
> 2 votes

# Answer
# Io, 38 bytes

```
Range 1 to(9)map(i,i*(10**i-1)/9)print

```

Try it online!

# Io, 47 bytes

```
Range 1 to(9)map(i,i asString repeated(i))print

```

Try it online!
> 2 votes

# Answer
# Python 3.8, 34 bytes

```
i=0
while i<9:print(str(i:=i+1)*i)

```

Try it online!
> 2 votes

# Answer
# Wolfram Language (Mathematica), 17 bytes

```
Table[,{,9},{a,}]

```

Try it online!

thanks @att
> 2 votes

# Answer
# Bubblegum, 23 bytes

```
00000000: 3334 3232 3636 3601 0253 1030 0303 7308  3422666..S.0..s.
00000010: b080 024b 1800 00                        ...K...

```

Try it online!
> 2 votes

# Answer
# PHP, ~~37~~ ~~36~~ 35 bytes

```
for(;10>$j=++$i;)for(;$j--;)echo$i;

```

Try it online!

-1 byte thanks to @Night2
> 2 votes

# Answer
# Python 2, 32 bytes

```
print[i*`i`for i in range(1,10)]

```

Try it online!
> 2 votes

# Answer
## Batch, 74 bytes

```
@set s=
@for /l %%i in (1,1,9)do @call set s=%%s%%0&call echo %%s:0=%%i%%

```

Outputs on separate lines. Extends the string length by 1 and replaces the character with the current digit for each output.

The `call` commands are required so that the variable `s` is processed inside the loop instead of before parsing the loop.
> 2 votes

# Answer
# Ruby, ~~30~~ 25 bytes

```
1.upto(9){|i|p 10**i/9*i}

```

Try it online!

`10**i/9` gives a number with `i` digits, all `1`s. Multiply by `i` for the required output.
> 2 votes

# Answer
# naz, 36 bytes

```
1a1o1a2o1a3o1a4o1a5o1a6o1a7o1a8o1a9o

```

Outputs all the numbers with no extra delimiter, using the same functionality described in this answer.
> 2 votes

# Answer
# Zsh, 30 bytes

```
repeat 9 echo ${(pl[++i][$i])}

```

Try it online!

The `(l[width][fill])` flag does the heavy lifting.
> 2 votes

# Answer
# Red, 30 bytes

```
repeat a 9[repeat b a[prin a]]

```

Try it online!

Well, the most obvious way to do it is the shortest in Red.
> 2 votes

# Answer
# Factor, ~~42~~ 39 bytes

```
9 [1,b] [ dup 1array swap cycle ] map .

```

Try it online!

Displays a list ot lists
> 2 votes

# Answer
# IBM/Lotus Notes Formula Language, 56 bytes

```
@For(x:=1;x<10;x:=x+1;@Set("o";o:@Repeat(@Text(x);x)));o

```

Formula in a multi value form field, once again showing that the only *real* use for `@For` in Notes is Code Golf!
> 2 votes

# Answer
# SNOBOL4 (CSNOBOL4), 47 bytes

```
O OUTPUT =DUPL(X,X)
 X =LT(X,9) X + 1 :S(O)
END

```

Try it online!

Prints with a leading newline.
> 2 votes

# Answer
# MathGolf, ~~6~~ 5 bytes

```
9{îÄí

```

-1 byte thanks to *@maxb*.

Try it online.

**Explanation:**

```
9{     # Loop 9 times:
  î    #  Push the 1-based loop index
   Ä   #  Do an inner loop that many times, using a single command:
    í  #   Push the total number iterations of the outer loop
       # (after the loops, the entire stack is joined together and output implicitly)

```
> 2 votes

# Answer
# Whitespace, 109 bytes

```
[S S S T    S S T   N
_Push_9][N
S S N
_Create_Label_LOOP][S N
S _Duplicate_top][N
S S S N
_Create_Label_INNER_LOOP][S S S T   N
_Push_1][T  S S T   _Subtract][S N
S _Duplicate_top][N
T   S T N
_If_0_Jump_to_Label_DONE_INNER_LOOP][S T    S S T   N
_Copy_0-based_1st][S N
T   _Swap_top_two][N
S N
S N
_Jump_to_Label_INNER_LOOP][N
S S T   N
_Create_Label_DONE_INNER_LOOP][S N
N
_Discard_top][S N
S _Duplicate_top][S S S T   N
_Push_1][T  S S T   _Subtract][S N
S _Duplicate_top][N
T   S S S N
_If_0_Jump_to_Label_DONE_LOOP][N
S N
N
_Jump_to_Label_LOOP][N
S S S S N
_Create_Label_DONE_LOOP][S N
N
_Discard_top][N
S S S T N
_Create_Label_PRINT_LOOP][T N
S T _Print_top_as_integer][N
S N
S T N
_Jump_to_Label_PRINT_LOOP]

```

Letters `S` (space), `T` (tab), and `N` (new-line) added as highlighting only.
`[..._some_action]` added as explanation only.

Try it online (with raw spaces, tabs and new-lines only).

**Explanation in pseudo-code:**

```
Push n=9
Start LOOP:
  Duplicate top (Integer i = n)
  Start INNER_LOOP
    i = i - 1
    if(i == 0):
      Jump to DONE_INNER_LOOP
    Copy n (0-based index 1)
    Swap
    Go to next iteration of INNER_LOOP
  DONE_INNER_LOOP:
    Discard i
    n = n - 1
    if(n == 0):
      Jump to DONE_LOOP
    Go to next iteration of LOOP
DONE_LOOP:
  Discard n
  Start PRINT_LOOP:
    Print top as integer
    Go to next iteration of PRINT_LOOP

```

Funny thing is, is that outputting with the additional single leading `0` as the challenge in the Sandbox initially had, this could have been 11 bytes shorter: try it online. xD
> 2 votes

# Answer
# Batch, 85 Bytes

`@for /L %%A in (1 1 9)do @For /L %%B in (1 1 %%A)do @Call Set O=%%O%%%%A
@Echo(%O%`

TIO not available.
> 2 votes

# Answer
# Fortran (GFortran), ~~38~~ 28 bytes

```
print*,(10**i/9*i,i=1,9)
end

```

Try it online!

Edit: Turns out the `program` statement is optional, saving 10 bytes!
> 2 votes

# Answer
# Gol\>\<\>, 8 bytes

```
aFLRL|D;

```

Try it online!

```
aF   |   For Loop, from 0 to 10 excluding 10
  L      Push the current loop iteration to the stack
   RL    Pop the current iteration and repeat pushing the loopiterator value so many times
      D; Print the entire stack content as numeric values with the debug operation and halt

```
> 2 votes

# Answer
# Python 3, 38 bytes

```
print([str(x)*x for x in range(1,10)])

```

Try it online!

# C++ (gcc), 59 bytes

```
for(int i=1;i<10;++i){for(int x=1;x<=i;++x){std::cout<<i;}}

```

Try it online!

Started learning c++ an hour ago, tried codegolf :)
> 2 votes

# Answer
## vJASS, 126 bytes

```
//! zinc
library q{function onInit(){integer x,y;string s="";for(1<=x<10){for(0<=y<x){s+=I2S(x);}}BJDebugMsg(s);}}
//! endzinc

```
> 2 votes

# Answer
# Javascript, 48 bytes

```
for(x=1;x<=9;x++){console.log((x+'').repeat(x))}

```

Try it online!
> 2 votes

# Answer
# C++ (gcc), ~~93~~, 65 bytes

```
int a;void n(){int b=a;while(b){std::cout<<a;b--;}if(a++!=9)n();}

```

Try it online!

The loop work is essentially the same as the previous version, but instead its own function.

It sets the starting `digit -> 1 -> counter` then it prints digits until the counter reaches `0`. At that point it increments the digit and recalls the function until `9`.

# C++ (gcc), 93 bytes

```
int main(int n){static int a=1;int b=a;if(b>9)return 0;while(b){std::cout<<a;b--;}main(a++);}

```

Try it online!

Don't mind the main...
> 2 votes

# Answer
# dc, ~~25~~ ~~24~~ 22 bytes

```
1[ddIr^9/*n1+dA>m]dsmx

```

Try it online!
> 2 votes

# Answer
# Common Lisp, 50 bytes

```
(loop for x from 1 to 9 do(dotimes(n x)(write x)))

```

Try it online!
> 2 votes

# Answer
# cQuents, 6 bytes

```
#9&$D$

```

Try it online!

Oh cool, another way to use cQuents!
> 2 votes

# Answer
# MAWP 0.1, ~~22~~ 20 bytes

```
[![~!:~1A]%!9A?.%1M]

```

Explanation:

```
[      start of loop
!      duplicates top of stack
[      start of loop
~!:~   prints bottom stack value
1A     subtracts 1
]      end of loop
%      removes top of stack (0 from the counter in the previous loop)
!9A    diffeence between top value and 9
?.     if top 0, then terminate program
%      removes top value
1M     adds 1 to top value
]      end of loop

```
> 2 votes

# Answer
# C# (Visual C# Interactive Compiler), 45 bytes

```
for(int j,i=0;i++<9;)for(j=i;j-->0;Write(i));

```

Try it online!
> 2 votes

# Answer
## Clojure, 32 bytes

```
(for[i(range 1 10)](repeat i i))

```

This results in a lists of numbers:

```
((1) (2 2) (3 3 3) (4 4 4 4) (5 5 5 5 5) (6 6 6 6 6 6) (7 7 7 7 7 7 7) (8 8 8 8 8 8 8 8) (9 9 9 9 9 9 9 9 9))

```
> 2 votes

# Answer
# International Phonetic Esoteric Language, 21 bytes

```
{A}1ɑee0ɑbue1søɒe1søɒ

```

Prints `122333444455555666666777777788888888999999999`.

Explanation:

```
{A}1ɑee0ɑbue1søɒe1søɒ
{A}1                  (push loop bounds, 1 to 10)
    ɑ                 (start loop)
     e                (push the current index)
      e0              (push loop bounds for current digit, 0 to index)
        ɑ             (start loop)
         bu           (DUP and CPRINT current digit)
           e1sø       (increment index)
               ɒ      (end loop)
                e1sø  (increment index)
                    ɒ (end loop)

```
> 2 votes

# Answer
# Python 3, 34 bytes

```
for i in range(10):print(str(i)*i)

```

Try it online!
> 2 votes

# Answer
# Rust, ~~77~~ ~~75~~ ~~73~~ ~~72~~ ~~57~~ 56 bytes

```
fn main(){for k in 1..10{for j in 0..k{print!("{}",k)}}}

```

Try it online!

And I thought Lua was verbose!

*Thanks to ovs for saving 15 bytes.*
> 2 votes

# Answer
# brainfuck, 50 bytes

```
+[>+<+++++]+++++++++[>-->+[<.>>+<-]>[<+>-]<<+++<-]

```

Try it online!

Assumes byte cells; does not go out of bounds to left.
> 2 votes

# Answer
# Poetic, 222 bytes

```
THE NUMERICAL I/O RULES
i saw a digit,o yes
o,again,i saw a number;too many
i do the I/O rules,i get a repeat
i now count to zeros
o,from one right to nine,i do digits,e.t.c
seldom a newline,since i know i am swayed not to

```

Try it online!
> 2 votes

# Answer
# Husk, 7 bytes

```
mod´Rḣ9

```

Try it online!

# Husk, 7 bytes

```
mdg´Ṙḣ9

```

Try it online!
> 2 votes

# Answer
# Canvas, 6 bytes

```
９｛：ŗ×］

```

Try it here!
> 2 votes

# Answer
# Excel, ~~29~~ 24 bytes

Saved 5 bytes thanks to Taylor Raine

```
=REPT(ROW(1:9),ROW(1:9))

```

`ROW(1:9)` returns an array of the numbers 1 through 9 so the `REPT()` function repeats each of those numbers itself-many times.
> 2 votes

# Answer
# APOL, 21 bytes

`ⅎ(9 p(*(t(∈) ∈)))`
> 2 votes

# Answer
# Pip, 5 bytes

```
,tX,t

```

Attempt This Online!

### Explanation

```
,t     Range(10)
  X    String-repeat (itemwise)
   ,t  Range(10)

```

That is, for each number in `[0; 1; 2; 3; 4; 5; 6; 7; 8; 9]`, repeat it a number of times equal to itself. The result is the list `[""; 1; 22; 333; 4444; 55555; 666666; 7777777; 88888888; 999999999]`, which is by default concatenated together and printed.
> 2 votes

# Answer
# Desmos, 21 bytes

```
l=[1...9]
l10^l/9-l/9

```

Try It On Desmos!

Try It On Desmos! - Prettified

Uses the following formula for the \\$n\\$th number: $$\frac{10^n-1}9\times n$$ `[1,22,333,4444,55555,666666,7777777,88888888,999999999]` is the value of the list in the second line.

Made it look "obfuscated" for fun but it's really just the same as:

```
l=[1...9]
l(10^l-1)/9

```

which is also 21 bytes.
> 2 votes

# Answer
# Fig, \\$7\log\_{256}(96)\approx\\$ 5.762 bytes

```
Ma9'*+D

```

Try it online!

## Explained

```
Ma9'*+D
Ma9'    # To each item n in the range [1, 9]
    *+D # Repeat the stringified n, n times

```
> 2 votes

# Answer
# Regenerate, 15 bytes

```
(#1{#1} ! ){10}

```

Outputs space-separated runs of digits, with a leading and a trailing space. Attempt This Online!

### Explanation

Spaces are replaced with underscores for clarity.

```
(#1{#1}_!_){10}
           {10}  Repeat 10 times
(         )      and store as group 1 after each match:
 #1                Length of previous match of group 1
   {#1}            repeated (length of previous match of group 1) times
       _           followed by a space
        !          Or, if that failed because there was no previous match of group 1,
         _         just a space

```

The first match of group 1 is a space, which has length 1, so the second match is one 1 followed by a space, which has length 2, so the third match is two 2's followed by a space, and so forth.
> 2 votes

# Answer
# Headass, 31 bytes

```
+^{{D^(]<)PN][}:(+++[]]]>)N^-[}

```

Try It Online!

Beats the naive solution (`+P+PP+PPP`... and so on for 54 bytes) by 23 bytes.

Outputs individual digits separated by newlines

Breakdown:

```
+^{{D^(]<)PN][}:(+++[]]]>)N^-[}  full program

+^                               initialize r1 to be 1
                                 r2 is already initialized to 0
  {                           }  repeat
    D^(  )     :(        )       until r1
                 +++[]]]>        fails to be less than 9
   {          }                    repeat
    D^(  )                         until r1
       ]<                          fails to be more than r2
    D     P                          print r1
           N][                       increment r2
                                   end repeat
                          N^       increment r1
                          N -[     set r2 to 0
                                 end repeat

```
> 2 votes

# Answer
# Prolog (SWI), 43 bytes

```
:-between(1,9,N),between(1,N,_),\+write(N).

```

Try it online!
> 2 votes

# Answer
# yup, ~~43~~ 41 bytes

```
0e:{~:{~:#~0e-}0e--:0ee00e--|00e--e0e-~-}

```

Try it online.

**Explanation:**

```
0e           # Push 1 (push 0; pop and push exp(0))
  :          # Duplicate it
   {         # Loop while the top of the stack is >0 (without popping):
    ~        #  Swap the top two values on the stack
     :       #  Duplicate the top
      {      #  Inner loop while the top of the stack is >0 (without popping):
       ~     #   Swap the top two values on the stack
        :    #   Duplicate the top
         #   #   Pop and print it as number
       ~     #   Swap the top two values on the stack back
        0e-  #   Decrease it by 1 (push 0; pop and push exp(0); subtract)
      }      #  Stop the inner loop if the top of the stack is <=0 (without popping)
       0e--  #  Increase the current value by 1 (using the 0 that was still on the
             #  stack as: push 0 → exp(0)=1 → 0-1=-1 → --1=+1)
       :     #  Duplicate the top again
        0ee00e--|00e--e0e-
             #  Push 9.107... (see below)
         ~   #  Swap the top two values again
          -  #  Subtract the current value from the 9.107...
   }         # Stop the outer loop if the top of the stack is <=0 (without popping)
             # (which it will be once we've reached 10)

0ee00e--|00e--e0e- # Push 9.107...:
0                  #  Push 0        - STACK: 0
 e                 #  exp(0)        - STACK: 1
  e                #  exp(1)        - STACK: 2.718...
   0               #  Push 0        - STACK: 2.718...,0
    0              #  Push 0        - STACK: 2.718...,0,0
     e             #  exp(0)        - STACK: 2.718...,0,1
      -            #  Subtract      - STACK: 2.718...,-1
       -           #  Subtract      - STACK: 3.718...
        |          #  ln(3.718...)  - STACK: 1.313...
         0         #  Push 0        - STACK: 1.313...,0
          0        #  Push 0        - STACK: 1.313...,0,0
           e       #  exp(0)        - STACK: 1.313...,0,1
            -      #  Subtract      - STACK: 1.313...,-1
             -     #  Subtract      - STACK: 2.313...
              e    #  exp(2.313...) - STACK: 10.107...
               0   #  Push 0        - STACK: 10.107...,0
                e  #  exp(0)        - STACK: 10.107...,1
                 - #  Subtract      - STACK: 9.107...

```
> 2 votes

# Answer
# F# (.NET Core), ~~59~~ ~~58~~ 57 bytes (thanks ouflak!)

```
for i=1 to 9 do String.replicate i (string i)|>printf"%s"

```

or

```
for i=1 to 9 do printf"%s"(String.replicate i (string i))

```

Try it online!
> 2 votes

# Answer
# Vyxal 3, 3 bytes

```
9ƛY

```

Try it Online!

Edit, the three byter is valid
> 2 votes

# Answer
# Uiua SBCS, 9 bytes

```
▽:+@0.⇡10

```

Try it!
> 2 votes

# Answer
# mlochbaum/BQN, 7 bytes

```
⥊˜¨1+↕9

```

Try it!

## Explanation

```
⥊˜¨1+↕9
     ↕9 range from 0 to 8
   1+   add 1 to each
  ¨     for each element n,
⥊˜      replicate n times

```
> 1 votes

# Answer
# AWK, 32 or 37 bytes

This code needs an `EOF` at the prompt, or a file with an empty line.

```
{for(;++i<10;)print(10^i-1)/9*i}

```

Try it online!

To substitute the input, one can use the `BEGIN` pattern, adding 5 more bytes to the code.

```
BEGIN{for(;++i<10;)print(10^i-1)/9*i}

```
> 1 votes

# Answer
# JavaScript, 50 bytes

```
_=>{for(i=0;++i<10;)console.log((''+i).repeat(i))}

```
> 1 votes

# Answer
# Factor, 29 bytes

```
9 [1,b] [ dup <array> ] map .

```

Try it online!
> 1 votes

# Answer
# A0A0, 46 bytes

```
O122333444455555666666777777788888888999999999

```

Literally prints the example output. I'd be very surprised if you can get something smaller in A0A0. The first `O` outputs the number following it and the number following it is the output. The language specification does not state any restriction on the size of the number, just "signed integer", so this works. (Although an interpreter may not handle this correctly, because this is a 147 bit number and not every language may support numbers that large.)
> 1 votes

# Answer
# TI-Basic, 17 bytes

```
seq(I(₁₀^(I)-1)/9,I,1,9

```

Output is stored in `Ans` as a list and displayed.
> 1 votes

# Answer
# Lua, 37 bytes

```
for i=1,9 do print((""..i):rep(i))end

```

Try it online!
> 1 votes

# Answer
# Pure Zsh, 27 bytes

```
eval ';s+=1;<<<$[s*'{1..9}]
```

Attempt This Online!
> 1 votes

# Answer
# GolfScript, 9 bytes

```
10,{.`*}/

```

## Explanation

```
     /  # for each element in...
     10,{ # 0-9
     . # duplicate it
     ` # stringify it
     * # push to the stack the stringified version of the number, repeated that many times
    }  # end block
       # implicitly output the stack

```

Try it online!
> 1 votes

# Answer
# \>\<\>, 28 bytes

```
1:\   >~1+:a=?;!
n$>:?!v1-$:

```

Try it online!
> 1 votes

# Answer
# Pyt, 6 bytes

```
ɳąĐƖ*ǰ

```

Try it online!

```
ɳ           pushes string containing all digits ("0123456789")
 ą          converts to ąrray of characters
  Đ         Đuplicates on stack
   Ɩ        casts top of stack to array of Ɩntegers
    *       string multiplication
     ǰ      ǰoin with no delimiter; implicit print

```
> 1 votes

# Answer
# Thunno `N`, \\$ 8 \log\_{256}(96) \approx \\$ 6.58 bytes

```
9R1+eDJ*

```

Attempt This Online!

#### Explanation

```
9R        # Push range(0, 9)
  1+      # Add one to each
    e     # To each number:
     D    #  Duplicate
      J   #  Cast to string
       *  #  Repeat that many times
          # N flag joins by newlines
          # Implicit output

```
> 1 votes

# Answer
# JavaScript, 50 bytes

```
_=>'122333444455555666666777777788888888999999999' // 50
_=>eval("for(s='',i=0;i<11;s+=''.padEnd(++i,i))s") // 50
n=>eval("for(s='';(n=-~n)<11;s+=''.padEnd(n,n))s") // 50
_=>'123456789'.replace(/(\d)/g,(d,i)=>d.repeat(i)) // 50

```

Try it:

```
f1=_=>'122333444455555666666777777788888888999999999' // 50
f2=_=>eval("for(s='',i=0;i<10;s+=''.padEnd(++i,i))s") // 50
f3=n=>eval("for(s='';(n=-~n)<11;s+=''.padEnd(n,n))s") // 50
f4=_=>'123456789'.replace(/(\d)/g,(d,i)=>d.repeat(i)) // 50

console.log(f1());
console.log(f2());
console.log(f3());
console.log(f4());
```
> 1 votes

# Answer
# Uiua, 15 bytes

```
∵(⋕/⊂∵°⋕↯).+1⇡9

```

Pad
> 1 votes

# Answer
# TypeScript’s type system, 94 bytes

```
type F<N extends 1[]=[1],L=N["length"]>=L extends 10?[]:[...{[_ in keyof N]:L},...F<[...N,1]>]

```

Try it at the TS Playground
> 1 votes

# Answer
# YASEPL, 24 bytes

```
=a$`1=b)""ſa;b,a<!+}4,9

```

## explanation (in pseudocode)

```
=a$`1=b)""ſa;b,a<!+}4,9          packed
=a$                              a = 1
   `1            !+}4,9          for(i = 0; i < 9; i++)
     =b)""ſa;b,a<                  print(str(a).repeat(a))

```
> 0 votes

---
Tags: code-golf, kolmogorov-complexity
---


# Question
Title: Find the best staircase to maximize the sum
Given an \\$n \times n\\$ matrix of integers, The task is to find the optimal dividing line that maximizes the sum of the integers on the same side as the top left corner. The dividing line should be connected and made up of only vertical and horizontal lines. For an example with a non-optimal dividing line:

```
[[ 3,  0,  2, -3, -3, -1, -2,  1, -1,  0, -1,  0,  0,  0, -2, -3, -2,  2, -2, -3],
 [ 1,  3,  3,  1,  1, -3, -1, -1,  3,  0,  0,  0, -2,  0,  2,  1, 2,  2, -1, -1],
 [-1,  0,  3,  1,  1,  3, -2,  0,  0, -1, -1, -1,  1,  2, -3, -2, 1, -2,  0,  0],
 [-3,  2,  2,  3, -2,  0, -1, -1,  3, -2, -2,  0,  2,  1,  2,  2, 1, -1, -3, -3],
 [-2, -2,  1, -3, -2, -1,  3,  2,  3, -3,  2,  3,  1, -1,  0,  1, -1,  3, -2, -1],
 [ 0,  0, -2, -3,  2,  3,  2,  2, -3,  0, -1, -1,  1, -2, -1,  3, 3,  0,  1,  0],
 [ 1,  2,  2, -1,  2,  0,  1, -2,  1,  2, -1, -3, -3,  2,  0,  0, -3, -1, -2,  2],
 [-1,  2,  2,  2,  0,  1, -3,  0,  0,  1, -2,  3,  3, -1,  2,  0, -1,  0, -1, -2],
 [ 3,  2,  0, -1, -2, -3, -2,  2, -1, -3, -3,  2, -3,  3,  1, -3, 0,  0, -2,  2],
 [ 2,  2, -1, -2,  2,  0, -2,  1,  0, -3, -2,  2, -2,  1, -1, -3, 3, -3, -3, -1],
 [ 2, -1, -2, -1, -3,  0, -3,  3, -3,  0,  1,  2, -3, -1, -3,  0, 3, -1, -2,  1],
 [ 0, -1, -2,  1,  0,  2,  0,  1, -1,  0,  1, -2, -2,  3,  2,  1, -2, -3,  0,  3],
 [-1,  1, -2, -1,  3,  1, -2,  1,  1,  3, -2, -3,  2, -2, -2,  2, 3, -3,  0, -3],
 [ 3, -1,  1,  1, -3,  0, -1, -2,  3, -3, -3, -2, -2,  2,  1,  1, 0,  2, -3, -3],
 [-2, -2, -1, -2,  1, -1,  2,  3,  3, -3, -2,  2, -1,  2, -2, -3, 1, -3, -2,  3],
 [-2,  2,  3, -3, -3,  3,  0,  2, -3, -3,  2, -3,  0, -1, -3,  3, -2, -2,  2, -3],
 [-3,  1, -1, -2,  1, -3,  0,  0,  1,  0,  3,  0, -2,  0,  0, -2, -1,  1,  1,  2],
 [-1, -1,  0,  1, -2,  2, -3,  2, -2, -2,  3, -2,  2,  0, -3, -1, -3, -2, -3, -2],
 [ 2,  0,  2,  3,  0,  2, -1, -2,  2, -2,  3,  1,  3,  0,  3, -2, -3, -3,  0,  2],
 [-3, -3,  3, -3,  0,  0, -1,  0,  1,  0, -3,  2,  2, -1,  0, -3, 1, -3,  1,  1]]

```

**The complication is that the number of horizontal lines is restricted to be at most \\$k\\$, for some integer parameter \\$k\\$.** In the picture above there are 4 horizontal lines within the dividing line. The dividing line can start at any point on the left or bottom edge and end at a different edge.

# Worked examples

Take the example matrix above and \\$k=1\\$. First, the sum of the entire matrix is -76 so we would already do better by including none of it. If we start the horizontal line from the left edge then the optimal has score 26 by including the first 10 rows and 3 columns. We should now consider starting on the bottom edge with a vertical line, then a horizontal line and potentially another vertical line. In this case that turns out not to help and 26 is the optimal sum.

Let us take a smaller example with \\$k=1\\$ again.

```
  [[-3, -2,  3,  2, -2],
   [ 3, -2, -2, -5, -3],
   [ 0,  3,  1,  1, -3],
   [ 1,  1,  2,  1, -1],
   [ 1,  1,  1, -3,  3]]

```

Here the optimal solution is to include the first 3 columns and then only first row for the next column. This gives a sum of 10. The dividing line has one horizontal part and two vertical ones.

> How quickly can this problem be solved when \\$k\\$ is an input parameter along with the matrix?

The winning criterion will be asymptotic time complexity. As there are two parameters, you can assume \\$k \leq \sqrt{n}\\$ when giving your final time complexity. So a complexity of \\$O(n^2+k)\\$ would translate to \\$O(n^2 + \sqrt{n}) = O(n^2)\\$.

# Further details

The dividing line will always go either right or up.

# Answer
> 3 votes
Without the \\$k\\$ constraint, \\$O(n^2)\\$ is possible using a columnwise DP.

Define \\$d\[i,j\]\\$ as the maximum sum of columns \\$0\\$ to \\$j\\$, given some boundary line with a horizontal boundary above cell \\$(i,j)\\$, and \\$c\[i,j\]\\$ to be the column prefix sum up to row \\$i\\$. Then $$d\[i,j\] = \max\_{i \le i' \le n} d\[i',j-1\] + c\[i,j\]$$

This would take linear time, but since max is associative, we can do it with prefix sums too: $$ m\[i,j\] = \max (d\[i,j\], m\[i+1,j\]) = \max\_{i \le i' \le n} d\[i',j\] \\ d\[i,j\] = c\[i,j\] + m\[i,j-1\] \\ $$

As requested, here is python code:

```
import numpy as np
a = np.array(
    [[-3, -2,  3,  2, -2],
     [ 3, -2, -2, -5, -3],
     [ 0,  3,  1,  1, -3],
     [ 1,  1,  2,  1, -1],
     [ 1,  1,  1, -3,  3]])
n = a.shape[0]

d = np.zeros((n+1, n))
c = np.zeros((n+1, n))
m = np.zeros((n+1, n))

for j in range(n):
    for i in range(n+1):
        c[i,j] = c[i-1,j] + a[i-1,j] if i > 0 else 0
        d[i,j] = c[i,j] + (m[i,j-1] if j > 0 else 0)

    for i in range(n,-1,-1):
        m[i,j] = d[i,j] if i == n else max(d[i,j], m[i+1,j])

print(d, max(d[:,-1]))

```

Finally, the added condition \\$K\\$ is a third parameter of the DP counting down how many new horizontal lines are left to use. This requires keeping track if the horizontal boundary row has changed in the max operation. In your example, you don't count the very bottom \\$i=n\\$ horizontal boundary, so this requires a special case to handle. Since you don't count the very top \\$i=0\\$ boundary either, your final result could look at \\$d\[0,n-1,K\]\\$ for the top row and \\$d\[1:n,n-1,K-1\]\\$ for the rest below. You should verify that this implements your problem correctly.

(This may also work if you modify the problem to allow the boundary line to go up and down.)

$$d\[i,j,k\] = c\[i,j\] + \max(d\[i,j-1,k\], \max\_{i \< i' \< n} d\[i', j-1, k-1\], d\[n,j-1,k\])$$

With max prefix sum: $$ m\[i,j,k\] = \max(d\[i,j,k\], m\[i+1,j,k\]) \\ d\[i,j,k\] = c\[i,j\] + \max(d\[i,j-1,k\], m\[i+1,j-1,k-1\], d\[n,j-1,k\]) $$

```
K = 1
d = np.zeros((n+1, n, K+1))
c = np.zeros((n+1, n))
m = np.zeros((n, n, K+1))

for j in range(n):
    for i in range(n+1):
        c[i,j] = c[i-1,j] + a[i-1,j] if i > 0 else 0

        for k in range(K+1):
            d[i,j,k] = c[i,j]
            if j > 0:
                d[i,j,k] += max(d[i,j-1,k],
                                d[n,j-1,k],
                                m[i+1,j-1,k-1] if i+1 < n and k > 0
                                else -np.inf)

    for i in range(n-1,-1,-1):
        for k in range(K+1):
            m[i,j,k] = max(d[i,j,k], m[i+1,j,k] if i+1 < n else -np.inf)

for k in range(K+1):
    print(d[:,:,k])

print(max(d[0,-1,K], max(d[1:n,-1,K-1])))

```

The final time complexity is \\$O(n^2 k)\\$.

# Answer
> 2 votes
Pure JavaScript:

```
const _staircase = (rowIndex, colIndex, prevRowIndex, maxRowIndex, k, sum, rowIndices) => {
  result.numIterations += 1;
  if (maxRowIndex === 0 || k === kMax) {
    rowIndices += (',' + prevRowIndex).repeat(width - colIndex);
    for (let j = colIndex; j < width; j++) sum += c[prevRowIndex][j];
    colIndex = width; // skip further iteration
  }
  if (colIndex === width) { // extract result
    if (sum > result.sum) [result.sum, result.rowIndices] = [sum, rowIndices];
    return;
  }
  const kInc = colIndex === 0 && rowIndex === height ? 0 : rowIndex !== prevRowIndex;
  _staircase(0, colIndex + 1, rowIndex, rowIndex, k + kInc, sum + c[rowIndex][colIndex], rowIndices + ',' + rowIndex);
  if (rowIndex < maxRowIndex) _staircase(rowIndex + 1, colIndex, prevRowIndex, maxRowIndex, k, sum, rowIndices);
};

```

Try it online!

The function is a closure that iterates the pre-computed static matrix `c` recursively. The pre-computed matrix holds cumulative column sums and has a row of zeros prepended.

The paths that are followed are stored by concatenating 1-indexed row numbers in `rowIndices` which is a simple delimited text string like `,5,5,5,1,0`.

The function keeps track of how deep to go in each column by observing `maxRowIndex`. The first `if()` is a simple optimization that skips iteration of further columns when we're on the first row (that only contains zeros in `c`) and when we're out of horizontal lines to insert.

The harness is at the TIO link above. It constructs `c`, calls the recursive function, and shows the result.

# Answer
> 1 votes
Given the constraint that the partition line may only move up or right, this corresponds to the number of combination words defined by north-east lattice-paths: https://en.wikipedia.org/wiki/Lattice\_path

For example, for n=3, we would write:

```
NNN
NNE
NEE
ENN
EEN
EEE

```

The total number of paths is: `C(n+n,n) = C(2n,n)`

This is the central binomial coefficient: https://en.wikipedia.org/wiki/Central\_binomial\_coefficient

> This next section may be considered as speculation on a technicality.

By this constraint you can define that the left-side contains no entries while the right-side contains all entries:

```
NNN

```

Or that the left-side contains all entries and the right-side contains no entries.

```
EEE

```

These considers the following sub-cases:

* The maximal left-side partition is the entire matrix, because every entry is positive.
* The maximal left-side partition is empty, because the right-side partition contains negative integers for every entry. Subsequently, the entire matrix contains negative entries.

---

Calculate the total value of the matrix based on the left-hand side of the partition created by the NE path. Words of 'N' and 'E' string movements corresponds from the bottom-left to the top-right corner.

```
def calculate_partition_value(matrix, path):
    n = matrix.shape[0]
    row, col = n - 1, 0  # Start from the bottom-left corner
    total_value = 0

    # Track boundary created by the path
    boundary = [(row, col)]

    for move in path:
        if move == 'N':
            row -= 1  # Move up
        elif move == 'E':
            col += 1  # Move right
        boundary.append((row, col))

    for i in range(n):
        for j in range(n):
            if is_left_of_path((i, j), boundary):
                total_value += matrix[i, j]

    return total_value

```

Determine if a cell is on the left-hand side of the path based on the boundary coordinates by checking if the cell is below any segment, then return True. Otherwise, the cell is either right of the path or above, return False.

```
def is_left_of_path(cell, boundary):
    for k in range(1, len(boundary)):
        if cell[1] < boundary[k][1] and cell[0] > boundary[k][0]:
            return False
    return True

```

Sort matrices based on the partition value:

```
def sort_matrices_by_value(matrices_with_values):
    return sorted(matrices_with_values, key=lambda x: x[1])

```

And to provide a simpler example, create an nxn matrix with random integers between -1 and 1.

```
def randomize_matrix_entries(n):
    return np.random.randint(-1, 1+1, size=(n, n))

```

Ungolfed code:

```
import numpy as np
from itertools import combinations

def generate_ne_paths(n):
    steps = 'N' * n + 'E' * n
    return set([''.join(p) for p in combinations(steps, n)])

def randomize_matrix_entries(n):
    return np.random.randint(-1, 1+1, size=(n, n))

def calculate_partition_value(matrix, path):
    n = matrix.shape[0]
    row, col = n - 1, 0
    total_value = 0
    boundary = [(row, col)]

    for move in path:
        if move == 'N':
            row -= 1
        elif move == 'E':
            col += 1
        boundary.append((row, col))

    for i in range(n):
        for j in range(n):
            if is_left_of_path((i, j), boundary):
                total_value += matrix[i, j]

    return total_value

def is_left_of_path(cell, boundary):
    for k in range(1, len(boundary)):
        if cell[1] < boundary[k][1] and cell[0] > boundary[k][0]:
            return False
    return True

def sort_matrices_by_value(matrices_with_values):
    return sorted(matrices_with_values, key=lambda x: x[1])

n = 3
ne_paths = generate_ne_paths(n)
matrices_with_values = []

for path in ne_paths:
    matrix = randomize_matrix_entries(n)
    value = calculate_partition_value(matrix, path)
    matrices_with_values.append((matrix, value, path))

sorted_matrices = sort_matrices_by_value(matrices_with_values)

print("First sorted matrix (example):")
print("Matrix:\n", sorted_matrices[0][0])
print("Total Value:", sorted_matrices[0][1])
print("Path:", sorted_matrices[0][2])

```

---

---
Tags: fastest-algorithm
---