32
\$\begingroup\$

A lexicographically increasing number is an integer whose digits are in strictly increasing order. Print all lexicographically increasing numbers under 10000.

Here are lines of the expected output:

0
1
2
3
4
5
6
7
8
9
12
13
14
15
16
17
18
19
23
24
25
26
27
28
29
34
35
36
37
38
39
45
46
47
48
49
56
57
58
59
67
68
69
78
79
89
123
124
125
126
127
128
129
134
135
136
137
138
139
145
146
147
148
149
156
157
158
159
167
168
169
178
179
189
234
235
236
237
238
239
245
246
247
248
249
256
257
258
259
267
268
269
278
279
289
345
346
347
348
349
356
357
358
359
367
368
369
378
379
389
456
457
458
459
467
468
469
478
479
489
567
568
569
578
579
589
678
679
689
789
1234
1235
1236
1237
1238
1239
1245
1246
1247
1248
1249
1256
1257
1258
1259
1267
1268
1269
1278
1279
1289
1345
1346
1347
1348
1349
1356
1357
1358
1359
1367
1368
1369
1378
1379
1389
1456
1457
1458
1459
1467
1468
1469
1478
1479
1489
1567
1568
1569
1578
1579
1589
1678
1679
1689
1789
2345
2346
2347
2348
2349
2356
2357
2358
2359
2367
2368
2369
2378
2379
2389
2456
2457
2458
2459
2467
2468
2469
2478
2479
2489
2567
2568
2569
2578
2579
2589
2678
2679
2689
2789
3456
3457
3458
3459
3467
3468
3469
3478
3479
3489
3567
3568
3569
3578
3579
3589
3678
3679
3689
3789
4567
4568
4569
4578
4579
4589
4678
4679
4689
4789
5678
5679
5689
5789
6789

This is a code golf challenge! Shortest answer wins!

(P.S. looking for a python solution)

\$\endgroup\$
  • 3
    \$\begingroup\$ do we need to print them on separate lines or is space-separated OK? \$\endgroup\$ – Giuseppe Nov 16 '18 at 19:29
  • 3
    \$\begingroup\$ Welcome to PPCG! Nice first challenge. For future challenges, I can recommend using the Sandbox to refine a challenge and get meaningful feedback before posting it to main. \$\endgroup\$ – AdmBorkBork Nov 16 '18 at 19:38
  • 4
    \$\begingroup\$ To expand on @Giuseppe's question, can we output separated by commas, spaces, in array format [0,1,...], etc. or must we output each number on a separate line? \$\endgroup\$ – ETHproductions Nov 16 '18 at 19:42
  • 10
    \$\begingroup\$ Do the numbers need to be in a specific order, or do they just need to all exist? \$\endgroup\$ – Kamil Drakari Nov 16 '18 at 19:56
  • 14
    \$\begingroup\$ @VarunPatro, please update the challenge to explicitly state that each number by on a separate line (although I'd recommend against that requirement) and make sure to inform any existing solutions that don't do so. \$\endgroup\$ – Shaggy Nov 16 '18 at 20:32

47 Answers 47

1 2
1
\$\begingroup\$

Ruby, 39 bytes

puts (?0..?9*4).grep /^#{[*0..9]*??}?$/

Try it online!

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

JavaScript, 83 bytes

Borrowed some ideas from @Shaggy, but without recursion.

[...Array(1e4)].reduce((s,_,n)=>s+=([...n+''].every(x=>y<(y=x),y=0))?'\n'+n:'','0')

Try it online!

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

T-SQL, 188 185 bytes

WITH a AS(SELECT 0n UNION ALL SELECT n+1FROM a WHERE n<9)
SELECT CONCAT(a.n,b.n,c.n,d.n)+0
FROM a,a b,a c,a d
WHERE(a.n<b.n OR a.n+b.n=0)
AND(b.n<c.n OR b.n+c.n=0)
AND(c.n<d.n OR c.n+d.n=0)

Line breaks are for readability only.

I'm certain there must be more efficient ways to do this in SQL, but this was the first thing I thought of. Explanation:

  1. Declare an in-memory table with values 0 to 9
  2. Cross-join 4 copies of this table for all possible values from 0000 to 9999
  3. Messy WHERE clause to ensure the digits are strictly increasing (or both 0)
  4. Smash the digits together (CONCAT) and convert to integer (+0)
  5. The resulting rows may or may not be sorted, but the challenge doesn't appear to require that.
\$\endgroup\$
  • 1
    \$\begingroup\$ You can convert to number by adding zero x+0 instead of abs(x). \$\endgroup\$ – Dr Y Wit Nov 26 '18 at 17:55
  • \$\begingroup\$ Thanks, @DrYWit, saved 3 bytes. Looks like x*1 works as well. \$\endgroup\$ – BradC Nov 26 '18 at 18:27
1
\$\begingroup\$

MathGolf, 10 bytes

♫rgÆ▒_s▀=n

Try it online!

Explanation

♫            push 10000
 r           range(0, n)
  g          pop a, (b), pop operator from code, filter
   Æ         start block of length 5
    ▒        split to list of chars/digits
     _       duplicate TOS
      s      sort(array)
       ▀     unique elements of string/list
        =    pop(a, b), push(a==b)
         n   newline char, or map array with newlines
\$\endgroup\$
1
\$\begingroup\$

Brachylog, 12 bytes

7jj⟦{ẹ<₁cẉ}ˢ

Try it online!

         ẉ      Write on its own line
    {     }ˢ    every
        c       concatenated
      <₁        strictly increasing
     ẹ          list of digits of
   ⟦            numbers from the range from 0 to
7jj             7777.

7jj⟦{ṫ⊆Ị&ẉ}ˢ also works.

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

Retina 0.8.2, 38 bytes


9999$*
.
$.`¶
.
$*_$&
A`(_*)\d\1\d
_

Try it online! Explanation:


9999$*

Insert 9999 characters.

.
$.`¶

Convert into a list of numbers 0..9998

.
$*_$&

Prefix each digit with its value in _s.

A`(_*)\d\1\d

Delete lines containing nonincreasing digits.

_

Remove the now unnecessary _s.

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

Pyth, 15 bytes

jf.A<V`Tt`TU^T4

Try it here!

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

Bash + GNU Core Utilities, 57 bytes

seq 1e4|grep -vP `seq 0 9|sed 's/./(&[0-&])/'|tr '
' \|`p

Uses some meta-regex-generation shit

\$\endgroup\$
  • \$\begingroup\$ Your output is missing the 0. \$\endgroup\$ – Dennis Nov 18 '18 at 3:07
  • \$\begingroup\$ 47 bytes \$\endgroup\$ – Dennis Nov 18 '18 at 3:21
0
\$\begingroup\$

K4, 19 bytes

Solution:

-1@$&&/'>':'$!9999;

Explanation:

-1@$&&/'>':'$!9999; / the solution
             !9999  / range 0..9998
            $       / string
        >':'        / greater-than (>) each-previous (':) each (')
     &/'            / max (&) over (/)
    &               / indices where true
   $                / string
  @                 / apply
-1                ; / print to stdout and swallow return value (-1)
\$\endgroup\$
0
\$\begingroup\$

Oracle SQL, 163 bytes

Various ways to generate combinations

with a(n)as(select level-1 from dual connect by level<11),r(i,x,s)as(select 1,n,n||''from a union all select i+1,n,s||n from r,a where(x<n or n+x=0)and i<4)select s+0 from r where i=4;

with a(n)as(select level-1 from dual connect by level<11)select a.n||b.n||c.n||d.n+0 from a,a b,a c,a d where(a.n<b.n or a.n+b.n=0)and(b.n<c.n or b.n+c.n=0)and(c.n<d.n or c.n+d.n=0);

with a(n)as(select level from dual connect by level<11)select unique replace(sys_connect_by_path(n-1,'#'),'#')+0 from(a)connect by level<5and prior n<n order by 1;
  1. Rec with (CTE), 184 bytes
  2. Self joins, 182 bytes
  3. Connect by, 163 bytes

Just for fun

with t(c)as(select ku$_vcnt(1,2,3,4,5,6,7,8,9) from dual)
select listagg(value(z)) within group (order by 0) + 0 n
  from (select rownum r, value(r) v
          from t, table(powermultiset(c)) r),
       table(v) z
 where cardinality(v) < 5
group by r union select 0 from dual

.

with a(n)as(select decode(level,10,null,level) from dual connect by level<11)
select nvl(a.n || b.n || c.n || d.n + 0, 0) n
  from a, a b, a c, a d
 where nvl2(b.n, sign(b.n - a.n), 1) = 1
   and nvl2(c.n, sign(c.n - b.n), 1) = 1
   and nvl2(d.n, sign(d.n - c.n), 1) = 1
 order by 1
\$\endgroup\$
0
\$\begingroup\$

PHP, 51 bytes

while($n<1e4)count_chars($n,3)-$n++||print~-$n."
";

Run with -nr or try it online.


count_chars($string,$mode=3) returns a string of all used characters in ascending order.
This equals the input if, and only if, its characters (in this case: digits) are strictly increasing.

$n is NULL in the first iteration; count_chars returns an empty string; NULL-"" is evaluated as 0-0.

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

Kotlin, 132 131 bytes

Edit: -1 Byte thanks to @Giuseppe

fun main(){(0..9999).forEach{it.toString().let{var b=1;it.forEachIndexed{i,c->if(i>0&&it[i-1]<c)b++};if(b==it.length)println(it)}}}

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ I don't know Kotlin, but a trivial golf is replacing 10000 with 9999 \$\endgroup\$ – Giuseppe Nov 26 '18 at 17:35
  • \$\begingroup\$ alternative 131 \$\endgroup\$ – ASCII-only Mar 11 '19 at 1:44
  • \$\begingroup\$ 96 \$\endgroup\$ – ASCII-only Mar 11 '19 at 1:49
  • \$\begingroup\$ 95 \$\endgroup\$ – ASCII-only Mar 11 '19 at 2:59
0
\$\begingroup\$

Tcl, 116 bytes

set i 0
time {set m -1;lmap n [split $i ""] {if $n>$m {set m $n} {set m X;break}}
if \$m!="X" {puts $i}
incr i} 9999

Try it online!

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

APL (Dyalog Extended), 28 bytes

{(⍵≡∪⍵)∧⍵≡∧⍵:⎕←⍵⋄⍬}∘⍕¨⍳10000

Try it online!

Explanation:

{(⍵≡∪⍵)∧⍵≡∧⍵:⎕←⍵⋄⍬}∘⍕¨⍳10000 ⍝ Full program
                          ⍳10000 ⍝ Generate integers from 1 to 10000
                      ∘⍕¨       ⍝ For each number, convert to string and apply left function
         ⍵≡∧⍵                   ⍝ If the string equals itself sorted...
 (⍵≡∪⍵)∧                        ⍝ ...and the string contains only unique elements...
               ⎕←⍵              ⍝ ...print the string to output with trailing newline
                   ⋄⍬            ⍝ Otherwise, do nothing
\$\endgroup\$
0
\$\begingroup\$

C++ (gcc), 113 bytes

bool y(int a){return(a==0||a%10>(a/=10)%10&&y(a))?true:false;}void z(int i){while(++i<7e3)if(y(i))cout<<i<<endl;}

Try it online!

Pretty Layout:

#include<iostream>
using namespace std;

bool y(int a){
    return(a==0||a%10>(a/=10)%10&&y(a))?true:false;
}

void z(int i){
    while(++i<7e3){
        !y(i)?:cout<<i<<endl;
    }
}

int main(){
    z(-1);
}
\$\endgroup\$
0
\$\begingroup\$

Java 8

Full program: 186 bytes

interface M{static void main(String[]a){for(int i=-1;i++<9999;System.out.print((i+"").chars().distinct().sorted().mapToObj(c->(c-48)+"").reduce("",(x,y)->x+y).equals(i+"")?i+"\n":""));}}

Function: 149 bytes

v->{for(int i=-1;i++<9999;System.out.print((i+"").chars().distinct().sorted().mapToObj(c->(c-48)+"").reduce("",(x,y)->x+y).equals(i+"")?i+"\n":""));}
\$\endgroup\$
0
\$\begingroup\$

Burlesque, 11 bytes

1e4qsoFO:U_

Equivalently

1e4ro:so:U_

Try it online!

1e4 # 10000
qso # Boxed is sorted?
FO  # Filter from 1..10000 if sorted
:U_ # Filter for unique digits
\$\endgroup\$
1 2

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.