title: Sequence and Series

text:
# Question
Title: Sequence and Series
Use any programming language to display numbers divisible by 1000000 that are greater than 1 and less than 10000000. Each number should be displayed in new line. Your program should display exactly:

```
1000000
2000000
3000000
4000000
5000000
6000000
7000000
8000000
9000000

```

# Answer
# Japt `-R`, 5 bytes

```
9õ*L³

```

Test it

---

## Explanation

```
9õ        :Range [1,9]
  *       :Multiply each by
   L      :100
    ³     :Cubed
          :Implicitly join with newlines and output

```
> 3 votes

# Answer
# Python 2, 29 bytes

```
i=0;exec'i+=10**6;print i;'*9

```

Try it online!
> 3 votes

# Answer
# Bash, 13 bytes

```
seq {1,1,9}e6

```

Try it online!

This answer is found out by @manatwork
> 3 votes

# Answer
# Whitespace, 85 bytes

```
[S S S N
_Push_0][N
S S N
_Create_Label_LOOP][S S S T N
_Push_1][T  S S S _Add][S N
S _Duplicate][S S S T   S T S N
_Push_10][T S S T   _Subtract][N
T   S S N
_If_0_Jump_to_Label_EXIT][S N
S _Duplicate][S S S T   T   T   T   T   S T S S S N
_Push_1000][S N
S _Duplicate][T S S N
_Multiply][T    S S N
_Multiply][T    N
S T _Print_number][S S S T  S T S N
_Push_10][T N
S S _Print_character][N
S N
N
_Jump_to_Label_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).

**Pseudo-code:**

```
Integer i = 0
Start LOOP:
  i = i + 1
  If(i == 10):
    Exit with an error
  Integer j = 1000 * 1000 * i
  Print j as number to STDOUT
  Print "\n"
  Go to next iteration of LOOP

```
> 2 votes

# Answer
# PowerShell, 14 bytes

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

```

Try it online!

Simply loops from `1` to `9` and multiplies each by `1e6`, i.e., `1000000`, to give the appropriate numbers. Ho-hum boring. Saved 7 bytes thanks to mazzy.

Previous versions:

---

### PowerShell, 21 bytes

```
1..9|%{"$_"+"000000"}

```

Try it online!

Boring simple loop from `1` to `9` that just string-concatenates the output together.

---

### PowerShell, 21 bytes

```
1e6..9e6|?{!($_%1e6)}

```

Try it online!

Loops from `1e6` to `9e6`, pulls out those entries where they're divisible by `1e6`. Times out on TIO but works offline. Run it with 3 instead of 6 to see the logic better.
> 2 votes

# Answer
# Neim, 8 bytes

```
9Δμ7)_

```

Try it online!
> 1 votes

# Answer
# Java 11, ~~62~~ ~~61~~ ~~56~~ 54 bytes

```
v->{for(int i=0;i++<9;)System.out.println(i*1000000);}

```

-2 bytes thanks to *@ggorlen*.

Try it online.

**Explanation:**

```
v->{                        // Method with empty unused parameter and no return-type
  v->{for(int i=0;i++<9;)   //  Loop `i` in the range (0,9]
    System.out.println(     //   Print without trailing newline:
     i*1000000);}           //    `i` multiplied by 1,000,000

```
> 1 votes

# Answer
# 05AB1E, 6 bytes

```
9L6°*»

```

Try it online.

**Explanation:**

```
9L        # List in the range [1,9]
  6°*     # Multiply each by 10**6
     »    # Join the list by newlines (and output implicitly)

```
> 1 votes

# Answer
# Python 3, 35 bytes

```
for i in range(1,10):print(i*10**6)

```

Try it online!
> 1 votes

# Answer
# Keg, 17 bytes

```
Ϩ²:(
;|:.
,':"+

```

Try it online!

## Explanation

```
Ϩ    # Push 1k
 ²   # Square the value
  :( # Copy the value for the accumulator
;|   # Repeat 10-1 times:
  :. # Print TOS
,    # Print newline
 ':" # Copy 1m to TOS
    + #Add the values

```

# Keg, 8 bytes (SBCS) (Doesn't seem to work online yet)

```
9Ï_⑷ė6Ë*

```

Try it online!

## Explanation

```
9Ï_     #Generate range 1-9 by generating range 0-9 and discarding 0
   ⑷        #Map the following to each element:
    ė6Ë*    #   Multiply each by 10 to the power of 6
#-pn puts newlines between each item, which is printed using -no

```
> 1 votes

# Answer
# `n` `d`, 5 bytes

```
-í╞6\

```

## Explanation

Decompressed:

```
9    M % Map in the range 1..9
 a  *  % Multiply the current item by ...
  6^   % ... 10 to the power of 6

```
> 1 votes

# Answer
# JavaScript (Node.js), 35 bytes

```
for(i=0;i++<9;)console.log(i*10**6)

```

Try it online!
> 0 votes

# Answer
# Attache, 16 bytes

```
Output[1:9*10^6]

```

Try it online!

## Explanation

```
Output[1:9*10^6]
       1:9          the range from 1 to 9
          *10^6     multiplied by 10^6 (1e6)
Output[        ]    output each entry on its own line

```
> 0 votes

# Answer
# ///, 29 bytes

```
/!/000000
/1!2!3!4!5!6!7!8!9!

```

Try it online!

33 bytes for no trailing newline:

```
/"/000//!/""
/1!2!3!4!5!6!7!8!9""

```

Try it online!
> 0 votes

# Answer
# C++ 44 bytes

```
for(int i=1;i<=9;i++){cout<<i*100**6<<endl;}

```
> 0 votes

# Answer
# C# (.NET Core), 48 44 bytes

```
for(int i=0;i++<9;)Console.WriteLine(i*1e6);

```

Try it online!

*-4 bytes: changed* `i*1000000` *to* `i*1e6` *in* `Console.WriteLine()`

Ungolfed:

```
for (int i = 0; i++ < 9;)               // from 1 to 9
    Console.WriteLine(i * 1e6);     // write i times 1,000,000 (1e6 = 1*(10^6) = 1,000,000) to the console

```
> 0 votes

# Answer
# Retina, 16 bytes

```

9*
L$`.
$.>`6*0

```

Try it online! Explanation:

```

9*

```

Insert 9 `_`s.

```
L$`.

```

List a value for each `_`.

```
$.>`6*0

```

Number of characters up to and including the current `_` followed by six zeros.
> 0 votes

# Answer
# APL (Dyalog Unicode), 7 bytesSBCS

Full program.

```
⍪1E6×⍳9

```

Try it online!

`⍳9`**ɩ**ndices one through nine

`1E9×` multiply million by those

columnify
> 0 votes

# Answer
# Ruby, 30 24 bytes

```
(1..9).map{|d|p d*10**6}

```

Try it online!

-6 bytes: use `map` instead of `step`. Use `10**6` instead of `1e6.to_i`
> 0 votes

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

```
00000000: ba10 018b fab1 09b4 09cd 21fe 05e2 fac3  ..........!.....
00000010: 3130 3030 3030 300d 0a24                 1000000..$

```

Listing:

```
BA 0110     MOV  DX, OFFSET O           ; DOS pointer to output string
8B FA       MOV  DI, DX                 ; pointer to defrerence for increment
B1 09       MOV  CL, 9                  ; counter to 9
8A E1       MOV  AH, CL                 ; DOS write string function also to 9
        LOOPY:
CD 21       INT  21H                    ; write string to stdout
FE 05       INC  BYTE PTR[DI]           ; increment first digit
E2 FA       LOOP LOOPY                  ; loop 9 times
C3          RET                         ; return to DOS
        O:  DB  '1000000',0DH,0AH,'$'   ; output string

```

Standalone DOS executable, output to STDOUT.

*TODO: re-do screenshot with old program length!*
> 0 votes

# Answer
# Jelly, 6 bytes

```
9Rȷ6×Y

```

Try it online!

# Explanation

```
9R     [1, 2, ..., 8, 9]
  ȷ6   100000
    ×  Multiply each
     Y Join by newline

```
> 0 votes

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


# Question
Title: Counts Of Orderings Containing At Most K Of The Kth Class
This challenge is about the number of orderings which contain at most \\$n\\$ classes and at most \\$k\\$ of the \\$k^{\text{th}}\\$ class.

One way to represent such an ordering is as a sequence of positive integers with these three restrictions:

1. A number may only appear after all lower numbers have appeared
2. All numbers which appear must be less than or equal to \\$n\\$
3. Any number may only appear up to as many times as its own value

As such the number of such sequences is itself a sequence, \\$a(n)\\$ where:

\\$a(0) = 1\\$, since only the empty sequence, `[]`, works;

\\$a(1) = 2\\$, since `[1]` now also works;

\\$a(2) = 4\\$, since both `[1, 2]` and `[1, 2, 2]` also work\*;

\\$a(3) = 16\\$:

```
[], [1], [1, 2], [1, 2, 2], [1, 2, 3], [1, 2, 2, 3], [1, 2, 3, 2], [1, 2, 3, 3], [1, 2, 2, 3, 3], [1, 2, 3, 2, 3], [1, 2, 3, 3, 2], [1, 2, 3, 3, 3], [1, 2, 2, 3, 3, 3], [1, 2, 3, 2, 3, 3], [1, 2, 3, 3, 2, 3], [1, 2, 3, 3, 3, 2]

```

\\$a(4) = 409\\$:

```
[], [1], [1, 2], [1, 2, 2], [1, 2, 3], [1, 2, 2, 3], [1, 2, 3, 2], [1, 2, 3, 3], [1, 2, 3, 4], [1, 2, 2, 3, 3], [1, 2, 2, 3, 4], [1, 2, 3, 2, 3], [1, 2, 3, 2, 4], [1, 2, 3, 3, 2], [1, 2, 3, 3, 3], [1, 2, 3, 3, 4], [1, 2, 3, 4, 2], [1, 2, 3, 4, 3], [1, 2, 3, 4, 4], [1, 2, 2, 3, 3, 3], [1, 2, 2, 3, 3, 4], [1, 2, 2, 3, 4, 3], [1, 2, 2, 3, 4, 4], [1, 2, 3, 2, 3, 3], [1, 2, 3, 2, 3, 4], [1, 2, 3, 2, 4, 3], [1, 2, 3, 2, 4, 4], [1, 2, 3, 3, 2, 3], [1, 2, 3, 3, 2, 4], [1, 2, 3, 3, 3, 2], [1, 2, 3, 3, 3, 4], [1, 2, 3, 3, 4, 2], [1, 2, 3, 3, 4, 3], [1, 2, 3, 3, 4, 4], [1, 2, 3, 4, 2, 3], [1, 2, 3, 4, 2, 4], [1, 2, 3, 4, 3, 2], [1, 2, 3, 4, 3, 3], [1, 2, 3, 4, 3, 4], [1, 2, 3, 4, 4, 2], [1, 2, 3, 4, 4, 3], [1, 2, 3, 4, 4, 4], [1, 2, 2, 3, 3, 3, 4], [1, 2, 2, 3, 3, 4, 3], [1, 2, 2, 3, 3, 4, 4], [1, 2, 2, 3, 4, 3, 3], [1, 2, 2, 3, 4, 3, 4], [1, 2, 2, 3, 4, 4, 3], [1, 2, 2, 3, 4, 4, 4], [1, 2, 3, 2, 3, 3, 4], [1, 2, 3, 2, 3, 4, 3], [1, 2, 3, 2, 3, 4, 4], [1, 2, 3, 2, 4, 3, 3], [1, 2, 3, 2, 4, 3, 4], [1, 2, 3, 2, 4, 4, 3], [1, 2, 3, 2, 4, 4, 4], [1, 2, 3, 3, 2, 3, 4], [1, 2, 3, 3, 2, 4, 3], [1, 2, 3, 3, 2, 4, 4], [1, 2, 3, 3, 3, 2, 4], [1, 2, 3, 3, 3, 4, 2], [1, 2, 3, 3, 3, 4, 4], [1, 2, 3, 3, 4, 2, 3], [1, 2, 3, 3, 4, 2, 4], [1, 2, 3, 3, 4, 3, 2], [1, 2, 3, 3, 4, 3, 4], [1, 2, 3, 3, 4, 4, 2], [1, 2, 3, 3, 4, 4, 3], [1, 2, 3, 3, 4, 4, 4], [1, 2, 3, 4, 2, 3, 3], [1, 2, 3, 4, 2, 3, 4], [1, 2, 3, 4, 2, 4, 3], [1, 2, 3, 4, 2, 4, 4], [1, 2, 3, 4, 3, 2, 3], [1, 2, 3, 4, 3, 2, 4], [1, 2, 3, 4, 3, 3, 2], [1, 2, 3, 4, 3, 3, 4], [1, 2, 3, 4, 3, 4, 2], [1, 2, 3, 4, 3, 4, 3], [1, 2, 3, 4, 3, 4, 4], [1, 2, 3, 4, 4, 2, 3], [1, 2, 3, 4, 4, 2, 4], [1, 2, 3, 4, 4, 3, 2], [1, 2, 3, 4, 4, 3, 3], [1, 2, 3, 4, 4, 3, 4], [1, 2, 3, 4, 4, 4, 2], [1, 2, 3, 4, 4, 4, 3], [1, 2, 3, 4, 4, 4, 4], [1, 2, 2, 3, 3, 3, 4, 4], [1, 2, 2, 3, 3, 4, 3, 4], [1, 2, 2, 3, 3, 4, 4, 3], [1, 2, 2, 3, 3, 4, 4, 4], [1, 2, 2, 3, 4, 3, 3, 4], [1, 2, 2, 3, 4, 3, 4, 3], [1, 2, 2, 3, 4, 3, 4, 4], [1, 2, 2, 3, 4, 4, 3, 3], [1, 2, 2, 3, 4, 4, 3, 4], [1, 2, 2, 3, 4, 4, 4, 3], [1, 2, 2, 3, 4, 4, 4, 4], [1, 2, 3, 2, 3, 3, 4, 4], [1, 2, 3, 2, 3, 4, 3, 4], [1, 2, 3, 2, 3, 4, 4, 3], [1, 2, 3, 2, 3, 4, 4, 4], [1, 2, 3, 2, 4, 3, 3, 4], [1, 2, 3, 2, 4, 3, 4, 3], [1, 2, 3, 2, 4, 3, 4, 4], [1, 2, 3, 2, 4, 4, 3, 3], [1, 2, 3, 2, 4, 4, 3, 4], [1, 2, 3, 2, 4, 4, 4, 3], [1, 2, 3, 2, 4, 4, 4, 4], [1, 2, 3, 3, 2, 3, 4, 4], [1, 2, 3, 3, 2, 4, 3, 4], [1, 2, 3, 3, 2, 4, 4, 3], [1, 2, 3, 3, 2, 4, 4, 4], [1, 2, 3, 3, 3, 2, 4, 4], [1, 2, 3, 3, 3, 4, 2, 4], [1, 2, 3, 3, 3, 4, 4, 2], [1, 2, 3, 3, 3, 4, 4, 4], [1, 2, 3, 3, 4, 2, 3, 4], [1, 2, 3, 3, 4, 2, 4, 3], [1, 2, 3, 3, 4, 2, 4, 4], [1, 2, 3, 3, 4, 3, 2, 4], [1, 2, 3, 3, 4, 3, 4, 2], [1, 2, 3, 3, 4, 3, 4, 4], [1, 2, 3, 3, 4, 4, 2, 3], [1, 2, 3, 3, 4, 4, 2, 4], [1, 2, 3, 3, 4, 4, 3, 2], [1, 2, 3, 3, 4, 4, 3, 4], [1, 2, 3, 3, 4, 4, 4, 2], [1, 2, 3, 3, 4, 4, 4, 3], [1, 2, 3, 3, 4, 4, 4, 4], [1, 2, 3, 4, 2, 3, 3, 4], [1, 2, 3, 4, 2, 3, 4, 3], [1, 2, 3, 4, 2, 3, 4, 4], [1, 2, 3, 4, 2, 4, 3, 3], [1, 2, 3, 4, 2, 4, 3, 4], [1, 2, 3, 4, 2, 4, 4, 3], [1, 2, 3, 4, 2, 4, 4, 4], [1, 2, 3, 4, 3, 2, 3, 4], [1, 2, 3, 4, 3, 2, 4, 3], [1, 2, 3, 4, 3, 2, 4, 4], [1, 2, 3, 4, 3, 3, 2, 4], [1, 2, 3, 4, 3, 3, 4, 2], [1, 2, 3, 4, 3, 3, 4, 4], [1, 2, 3, 4, 3, 4, 2, 3], [1, 2, 3, 4, 3, 4, 2, 4], [1, 2, 3, 4, 3, 4, 3, 2], [1, 2, 3, 4, 3, 4, 3, 4], [1, 2, 3, 4, 3, 4, 4, 2], [1, 2, 3, 4, 3, 4, 4, 3], [1, 2, 3, 4, 3, 4, 4, 4], [1, 2, 3, 4, 4, 2, 3, 3], [1, 2, 3, 4, 4, 2, 3, 4], [1, 2, 3, 4, 4, 2, 4, 3], [1, 2, 3, 4, 4, 2, 4, 4], [1, 2, 3, 4, 4, 3, 2, 3], [1, 2, 3, 4, 4, 3, 2, 4], [1, 2, 3, 4, 4, 3, 3, 2], [1, 2, 3, 4, 4, 3, 3, 4], [1, 2, 3, 4, 4, 3, 4, 2], [1, 2, 3, 4, 4, 3, 4, 3], [1, 2, 3, 4, 4, 3, 4, 4], [1, 2, 3, 4, 4, 4, 2, 3], [1, 2, 3, 4, 4, 4, 2, 4], [1, 2, 3, 4, 4, 4, 3, 2], [1, 2, 3, 4, 4, 4, 3, 3], [1, 2, 3, 4, 4, 4, 3, 4], [1, 2, 3, 4, 4, 4, 4, 2], [1, 2, 3, 4, 4, 4, 4, 3], [1, 2, 2, 3, 3, 3, 4, 4, 4], [1, 2, 2, 3, 3, 4, 3, 4, 4], [1, 2, 2, 3, 3, 4, 4, 3, 4], [1, 2, 2, 3, 3, 4, 4, 4, 3], [1, 2, 2, 3, 3, 4, 4, 4, 4], [1, 2, 2, 3, 4, 3, 3, 4, 4], [1, 2, 2, 3, 4, 3, 4, 3, 4], [1, 2, 2, 3, 4, 3, 4, 4, 3], [1, 2, 2, 3, 4, 3, 4, 4, 4], [1, 2, 2, 3, 4, 4, 3, 3, 4], [1, 2, 2, 3, 4, 4, 3, 4, 3], [1, 2, 2, 3, 4, 4, 3, 4, 4], [1, 2, 2, 3, 4, 4, 4, 3, 3], [1, 2, 2, 3, 4, 4, 4, 3, 4], [1, 2, 2, 3, 4, 4, 4, 4, 3], [1, 2, 3, 2, 3, 3, 4, 4, 4], [1, 2, 3, 2, 3, 4, 3, 4, 4], [1, 2, 3, 2, 3, 4, 4, 3, 4], [1, 2, 3, 2, 3, 4, 4, 4, 3], [1, 2, 3, 2, 3, 4, 4, 4, 4], [1, 2, 3, 2, 4, 3, 3, 4, 4], [1, 2, 3, 2, 4, 3, 4, 3, 4], [1, 2, 3, 2, 4, 3, 4, 4, 3], [1, 2, 3, 2, 4, 3, 4, 4, 4], [1, 2, 3, 2, 4, 4, 3, 3, 4], [1, 2, 3, 2, 4, 4, 3, 4, 3], [1, 2, 3, 2, 4, 4, 3, 4, 4], [1, 2, 3, 2, 4, 4, 4, 3, 3], [1, 2, 3, 2, 4, 4, 4, 3, 4], [1, 2, 3, 2, 4, 4, 4, 4, 3], [1, 2, 3, 3, 2, 3, 4, 4, 4], [1, 2, 3, 3, 2, 4, 3, 4, 4], [1, 2, 3, 3, 2, 4, 4, 3, 4], [1, 2, 3, 3, 2, 4, 4, 4, 3], [1, 2, 3, 3, 2, 4, 4, 4, 4], [1, 2, 3, 3, 3, 2, 4, 4, 4], [1, 2, 3, 3, 3, 4, 2, 4, 4], [1, 2, 3, 3, 3, 4, 4, 2, 4], [1, 2, 3, 3, 3, 4, 4, 4, 2], [1, 2, 3, 3, 3, 4, 4, 4, 4], [1, 2, 3, 3, 4, 2, 3, 4, 4], [1, 2, 3, 3, 4, 2, 4, 3, 4], [1, 2, 3, 3, 4, 2, 4, 4, 3], [1, 2, 3, 3, 4, 2, 4, 4, 4], [1, 2, 3, 3, 4, 3, 2, 4, 4], [1, 2, 3, 3, 4, 3, 4, 2, 4], [1, 2, 3, 3, 4, 3, 4, 4, 2], [1, 2, 3, 3, 4, 3, 4, 4, 4], [1, 2, 3, 3, 4, 4, 2, 3, 4], [1, 2, 3, 3, 4, 4, 2, 4, 3], [1, 2, 3, 3, 4, 4, 2, 4, 4], [1, 2, 3, 3, 4, 4, 3, 2, 4], [1, 2, 3, 3, 4, 4, 3, 4, 2], [1, 2, 3, 3, 4, 4, 3, 4, 4], [1, 2, 3, 3, 4, 4, 4, 2, 3], [1, 2, 3, 3, 4, 4, 4, 2, 4], [1, 2, 3, 3, 4, 4, 4, 3, 2], [1, 2, 3, 3, 4, 4, 4, 3, 4], [1, 2, 3, 3, 4, 4, 4, 4, 2], [1, 2, 3, 3, 4, 4, 4, 4, 3], [1, 2, 3, 4, 2, 3, 3, 4, 4], [1, 2, 3, 4, 2, 3, 4, 3, 4], [1, 2, 3, 4, 2, 3, 4, 4, 3], [1, 2, 3, 4, 2, 3, 4, 4, 4], [1, 2, 3, 4, 2, 4, 3, 3, 4], [1, 2, 3, 4, 2, 4, 3, 4, 3], [1, 2, 3, 4, 2, 4, 3, 4, 4], [1, 2, 3, 4, 2, 4, 4, 3, 3], [1, 2, 3, 4, 2, 4, 4, 3, 4], [1, 2, 3, 4, 2, 4, 4, 4, 3], [1, 2, 3, 4, 3, 2, 3, 4, 4], [1, 2, 3, 4, 3, 2, 4, 3, 4], [1, 2, 3, 4, 3, 2, 4, 4, 3], [1, 2, 3, 4, 3, 2, 4, 4, 4], [1, 2, 3, 4, 3, 3, 2, 4, 4], [1, 2, 3, 4, 3, 3, 4, 2, 4], [1, 2, 3, 4, 3, 3, 4, 4, 2], [1, 2, 3, 4, 3, 3, 4, 4, 4], [1, 2, 3, 4, 3, 4, 2, 3, 4], [1, 2, 3, 4, 3, 4, 2, 4, 3], [1, 2, 3, 4, 3, 4, 2, 4, 4], [1, 2, 3, 4, 3, 4, 3, 2, 4], [1, 2, 3, 4, 3, 4, 3, 4, 2], [1, 2, 3, 4, 3, 4, 3, 4, 4], [1, 2, 3, 4, 3, 4, 4, 2, 3], [1, 2, 3, 4, 3, 4, 4, 2, 4], [1, 2, 3, 4, 3, 4, 4, 3, 2], [1, 2, 3, 4, 3, 4, 4, 3, 4], [1, 2, 3, 4, 3, 4, 4, 4, 2], [1, 2, 3, 4, 3, 4, 4, 4, 3], [1, 2, 3, 4, 4, 2, 3, 3, 4], [1, 2, 3, 4, 4, 2, 3, 4, 3], [1, 2, 3, 4, 4, 2, 3, 4, 4], [1, 2, 3, 4, 4, 2, 4, 3, 3], [1, 2, 3, 4, 4, 2, 4, 3, 4], [1, 2, 3, 4, 4, 2, 4, 4, 3], [1, 2, 3, 4, 4, 3, 2, 3, 4], [1, 2, 3, 4, 4, 3, 2, 4, 3], [1, 2, 3, 4, 4, 3, 2, 4, 4], [1, 2, 3, 4, 4, 3, 3, 2, 4], [1, 2, 3, 4, 4, 3, 3, 4, 2], [1, 2, 3, 4, 4, 3, 3, 4, 4], [1, 2, 3, 4, 4, 3, 4, 2, 3], [1, 2, 3, 4, 4, 3, 4, 2, 4], [1, 2, 3, 4, 4, 3, 4, 3, 2], [1, 2, 3, 4, 4, 3, 4, 3, 4], [1, 2, 3, 4, 4, 3, 4, 4, 2], [1, 2, 3, 4, 4, 3, 4, 4, 3], [1, 2, 3, 4, 4, 4, 2, 3, 3], [1, 2, 3, 4, 4, 4, 2, 3, 4], [1, 2, 3, 4, 4, 4, 2, 4, 3], [1, 2, 3, 4, 4, 4, 3, 2, 3], [1, 2, 3, 4, 4, 4, 3, 2, 4], [1, 2, 3, 4, 4, 4, 3, 3, 2], [1, 2, 3, 4, 4, 4, 3, 3, 4], [1, 2, 3, 4, 4, 4, 3, 4, 2], [1, 2, 3, 4, 4, 4, 3, 4, 3], [1, 2, 3, 4, 4, 4, 4, 2, 3], [1, 2, 3, 4, 4, 4, 4, 3, 2], [1, 2, 3, 4, 4, 4, 4, 3, 3], [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], [1, 2, 2, 3, 3, 4, 3, 4, 4, 4], [1, 2, 2, 3, 3, 4, 4, 3, 4, 4], [1, 2, 2, 3, 3, 4, 4, 4, 3, 4], [1, 2, 2, 3, 3, 4, 4, 4, 4, 3], [1, 2, 2, 3, 4, 3, 3, 4, 4, 4], [1, 2, 2, 3, 4, 3, 4, 3, 4, 4], [1, 2, 2, 3, 4, 3, 4, 4, 3, 4], [1, 2, 2, 3, 4, 3, 4, 4, 4, 3], [1, 2, 2, 3, 4, 4, 3, 3, 4, 4], [1, 2, 2, 3, 4, 4, 3, 4, 3, 4], [1, 2, 2, 3, 4, 4, 3, 4, 4, 3], [1, 2, 2, 3, 4, 4, 4, 3, 3, 4], [1, 2, 2, 3, 4, 4, 4, 3, 4, 3], [1, 2, 2, 3, 4, 4, 4, 4, 3, 3], [1, 2, 3, 2, 3, 3, 4, 4, 4, 4], [1, 2, 3, 2, 3, 4, 3, 4, 4, 4], [1, 2, 3, 2, 3, 4, 4, 3, 4, 4], [1, 2, 3, 2, 3, 4, 4, 4, 3, 4], [1, 2, 3, 2, 3, 4, 4, 4, 4, 3], [1, 2, 3, 2, 4, 3, 3, 4, 4, 4], [1, 2, 3, 2, 4, 3, 4, 3, 4, 4], [1, 2, 3, 2, 4, 3, 4, 4, 3, 4], [1, 2, 3, 2, 4, 3, 4, 4, 4, 3], [1, 2, 3, 2, 4, 4, 3, 3, 4, 4], [1, 2, 3, 2, 4, 4, 3, 4, 3, 4], [1, 2, 3, 2, 4, 4, 3, 4, 4, 3], [1, 2, 3, 2, 4, 4, 4, 3, 3, 4], [1, 2, 3, 2, 4, 4, 4, 3, 4, 3], [1, 2, 3, 2, 4, 4, 4, 4, 3, 3], [1, 2, 3, 3, 2, 3, 4, 4, 4, 4], [1, 2, 3, 3, 2, 4, 3, 4, 4, 4], [1, 2, 3, 3, 2, 4, 4, 3, 4, 4], [1, 2, 3, 3, 2, 4, 4, 4, 3, 4], [1, 2, 3, 3, 2, 4, 4, 4, 4, 3], [1, 2, 3, 3, 3, 2, 4, 4, 4, 4], [1, 2, 3, 3, 3, 4, 2, 4, 4, 4], [1, 2, 3, 3, 3, 4, 4, 2, 4, 4], [1, 2, 3, 3, 3, 4, 4, 4, 2, 4], [1, 2, 3, 3, 3, 4, 4, 4, 4, 2], [1, 2, 3, 3, 4, 2, 3, 4, 4, 4], [1, 2, 3, 3, 4, 2, 4, 3, 4, 4], [1, 2, 3, 3, 4, 2, 4, 4, 3, 4], [1, 2, 3, 3, 4, 2, 4, 4, 4, 3], [1, 2, 3, 3, 4, 3, 2, 4, 4, 4], [1, 2, 3, 3, 4, 3, 4, 2, 4, 4], [1, 2, 3, 3, 4, 3, 4, 4, 2, 4], [1, 2, 3, 3, 4, 3, 4, 4, 4, 2], [1, 2, 3, 3, 4, 4, 2, 3, 4, 4], [1, 2, 3, 3, 4, 4, 2, 4, 3, 4], [1, 2, 3, 3, 4, 4, 2, 4, 4, 3], [1, 2, 3, 3, 4, 4, 3, 2, 4, 4], [1, 2, 3, 3, 4, 4, 3, 4, 2, 4], [1, 2, 3, 3, 4, 4, 3, 4, 4, 2], [1, 2, 3, 3, 4, 4, 4, 2, 3, 4], [1, 2, 3, 3, 4, 4, 4, 2, 4, 3], [1, 2, 3, 3, 4, 4, 4, 3, 2, 4], [1, 2, 3, 3, 4, 4, 4, 3, 4, 2], [1, 2, 3, 3, 4, 4, 4, 4, 2, 3], [1, 2, 3, 3, 4, 4, 4, 4, 3, 2], [1, 2, 3, 4, 2, 3, 3, 4, 4, 4], [1, 2, 3, 4, 2, 3, 4, 3, 4, 4], [1, 2, 3, 4, 2, 3, 4, 4, 3, 4], [1, 2, 3, 4, 2, 3, 4, 4, 4, 3], [1, 2, 3, 4, 2, 4, 3, 3, 4, 4], [1, 2, 3, 4, 2, 4, 3, 4, 3, 4], [1, 2, 3, 4, 2, 4, 3, 4, 4, 3], [1, 2, 3, 4, 2, 4, 4, 3, 3, 4], [1, 2, 3, 4, 2, 4, 4, 3, 4, 3], [1, 2, 3, 4, 2, 4, 4, 4, 3, 3], [1, 2, 3, 4, 3, 2, 3, 4, 4, 4], [1, 2, 3, 4, 3, 2, 4, 3, 4, 4], [1, 2, 3, 4, 3, 2, 4, 4, 3, 4], [1, 2, 3, 4, 3, 2, 4, 4, 4, 3], [1, 2, 3, 4, 3, 3, 2, 4, 4, 4], [1, 2, 3, 4, 3, 3, 4, 2, 4, 4], [1, 2, 3, 4, 3, 3, 4, 4, 2, 4], [1, 2, 3, 4, 3, 3, 4, 4, 4, 2], [1, 2, 3, 4, 3, 4, 2, 3, 4, 4], [1, 2, 3, 4, 3, 4, 2, 4, 3, 4], [1, 2, 3, 4, 3, 4, 2, 4, 4, 3], [1, 2, 3, 4, 3, 4, 3, 2, 4, 4], [1, 2, 3, 4, 3, 4, 3, 4, 2, 4], [1, 2, 3, 4, 3, 4, 3, 4, 4, 2], [1, 2, 3, 4, 3, 4, 4, 2, 3, 4], [1, 2, 3, 4, 3, 4, 4, 2, 4, 3], [1, 2, 3, 4, 3, 4, 4, 3, 2, 4], [1, 2, 3, 4, 3, 4, 4, 3, 4, 2], [1, 2, 3, 4, 3, 4, 4, 4, 2, 3], [1, 2, 3, 4, 3, 4, 4, 4, 3, 2], [1, 2, 3, 4, 4, 2, 3, 3, 4, 4], [1, 2, 3, 4, 4, 2, 3, 4, 3, 4], [1, 2, 3, 4, 4, 2, 3, 4, 4, 3], [1, 2, 3, 4, 4, 2, 4, 3, 3, 4], [1, 2, 3, 4, 4, 2, 4, 3, 4, 3], [1, 2, 3, 4, 4, 2, 4, 4, 3, 3], [1, 2, 3, 4, 4, 3, 2, 3, 4, 4], [1, 2, 3, 4, 4, 3, 2, 4, 3, 4], [1, 2, 3, 4, 4, 3, 2, 4, 4, 3], [1, 2, 3, 4, 4, 3, 3, 2, 4, 4], [1, 2, 3, 4, 4, 3, 3, 4, 2, 4], [1, 2, 3, 4, 4, 3, 3, 4, 4, 2], [1, 2, 3, 4, 4, 3, 4, 2, 3, 4], [1, 2, 3, 4, 4, 3, 4, 2, 4, 3], [1, 2, 3, 4, 4, 3, 4, 3, 2, 4], [1, 2, 3, 4, 4, 3, 4, 3, 4, 2], [1, 2, 3, 4, 4, 3, 4, 4, 2, 3], [1, 2, 3, 4, 4, 3, 4, 4, 3, 2], [1, 2, 3, 4, 4, 4, 2, 3, 3, 4], [1, 2, 3, 4, 4, 4, 2, 3, 4, 3], [1, 2, 3, 4, 4, 4, 2, 4, 3, 3], [1, 2, 3, 4, 4, 4, 3, 2, 3, 4], [1, 2, 3, 4, 4, 4, 3, 2, 4, 3], [1, 2, 3, 4, 4, 4, 3, 3, 2, 4], [1, 2, 3, 4, 4, 4, 3, 3, 4, 2], [1, 2, 3, 4, 4, 4, 3, 4, 2, 3], [1, 2, 3, 4, 4, 4, 3, 4, 3, 2], [1, 2, 3, 4, 4, 4, 4, 2, 3, 3], [1, 2, 3, 4, 4, 4, 4, 3, 2, 3], [1, 2, 3, 4, 4, 4, 4, 3, 3, 2]

```

\\$a(5) = 128458\\$;

\\$a(6) = 612887198\\$;

...and so on.

* Note, for example, that `[2, 1, 2]` violates (1) while `[1, 1, 2]` violates (3).

(Other interpretations of the underlying objects being counted no doubt exist too, feel free to comment regarding these, or, even better, explain them as part of an answer.)

### The Challenge

Write a program or function which does any of the following:

* Takes a non-negative integer, \\$n\\$ and outputs either:
    + \\$a(n)\\$
    + \\$\[a(0),\cdots ,a(n)\]\\$
* Takes a positive integer, \\$n\\$ and outputs either:
    + \\$a(n-1)\\$
    + \\$\[a(0),\cdots ,a(n-1)\]\\$
* Takes no input and outputs the sequence \\$a\\$ forever

---

This is so try to achieve the shortest solution in your chosen language.

Also insightful answers that are not necessarily the shortest, so long as they are still well golfed, will probably be received well!

---

This sequence is not currently in the OEIS, and as far as I can tell neither is any trivially related sequence (e.g. `[1,1,2,11,393,12442,...]`) - if you spot any do comment.

# Answer
# JavaScript (ES6),  ~~91 ... 76~~  74 bytes

A recursive approach. This is very fast up to \\$n=5\\$. Computing \\$a(6)\\$ takes approximately 2 minutes on my laptop.

```
n=>(g=a=>1+(h=i=>i&&h(i-1)+(a[i]^i&&a[i-1]?g(b=[...a,0],b[i]++):0))(n))`1`

```

Try it online!

### How?

Instead of explicitly building the sequences, we just keep track of how many times each value appears. This gives us enough information to decide which values are allowed to be added at any given time, assuming they're always added at the end of the sequence.

### Commented

```
n => (                     // n = input
  g = a =>                 // g is a recursive function taking an array a[] holding
                           // how many times each value appears in the sequence
  1 + (                    // increment the final result
    h = i =>               // h is a recursive function taking i = next value to try
      i &&                 //   stop if i = 0
      h(i - 1) + (         //   otherwise, do a recursive call to h with i - 1
        a[i] ^ i &&        //   if i does not appear i times (rule #3)
        a[i - 1] ?         //   and i - 1 appears at least once (rule #1):
          g(               //     add the result of a recursive call to g:
            b = [...a, 0], //       define b[] as a copy of a[] with an extra '0'
                           //       so that b[i] is guaranteed to be defined
                           //       (at this point, we know that a[0] to a[i-1] exist)
            b[i]++         //       increment b[i]
          )                //     end of recursive call to g
        :                  //   else:
          0                //     add nothing
      )                    //
  )(n)                     // initial call to h with the maximum value i = n (rule #2)
)`1`                       // initial call to g with a[0] = '1', which is required to
                           // to allow i = 1 to be added as per rule #1

```
> 8 votes

# Answer
# Pyth, 13 bytes

```
lfUI{T{.ysmRh

```

Try it online!

Let's go through this step by step, starting at the end:

* `mRh`: This autoexpands to `mRhdQ`. This means "Map the function `m` with right input `hd` over the input `Q`."

+ `Q` is an integer (e.g. 3) so it gets automatically cast to a range (e.g. \[0, 1, 2\]).
    + The `m` function is the map function.
    + `d` is defined to be the input to the map function.
    + `h` is the `+ 1` function (head).
    + `m` with two numeric inputs just replicates the left input a number of times equal to the right input.
    + As a result, `mRh` outputs a list like this: `[[0], [1, 1], [2, 2, 2]]`.
* `s`: Flatten (sum). Now we have a list like `[0, 1, 1, 2, 2, 2]`.
* `.y`: All permuted subsets.
* `{`: Uniquify (remove duplicates). Now we have a list like `[[], [0], [1], [2], [0, 1], ... ]`
* `fUI{T`: Filter that list on the function `UI{T`.
    + `T` is the input to the filter.
    + `{`: Uniquify the list to be filtered. Uniquify orders the unique elements in the order they first appear.
    + `UI`: Invariant under the function `U`:
        - `U`: Cast to range. So the unique elements must be `[]`, or `[0]`, or `[0, 1]`, etc. to pass this test.
* `l`: Length. The result is implicitly printed.

To see the orderings, just remove the `l`.
> 7 votes

# Answer
# Jelly, 18 bytes

```
x`€FŒ!QJƑ$Ƈ¹Ƥ€ẎQL‘

```

Try it online!

An initial attempt at a Jelly answer. A monadic link taking an integer and returning an integer. Too slow for n\>3 on TIO.

## Explanation

```
x`€                | Repeat each of 1..n itself times
   F               | Flatten
    Œ!             | Permutations
         $Ƈ        | Keep those where the following is true:
      Q            | - Uniquify
       JƑ          | - Check whether invariant when a sequence along the list is generated
           ¹Ƥ€     | Prefixes of each
              Ẏ    | Join outer lists
               Q   | Uniquify
                L  | Length
                 ‘ | Add one (to account for the empty list)

```

# Longer but handles \\$n=5\\$ in under 25 seconds on TIO

## Jelly, 24 bytes

```
ċⱮṀ$;0ḣ³<J$T;€)Ẏ
“”WÇƬẈS

```

Try it online!

Thanks to @JonathanAllan for improving the final bit of the faster version!
> 4 votes

# Answer
# , ~~113~~ ~~106~~ 98 bytes

```
g=function(n,N=1:n,B=N*0){for(e in N[c(1,B)[-n-1]>0&(F=all(B<=N))])F=F+g(n,,'[<-'(B,e,B[e]+1));+F}

```

Try it online!

* -9 bytes thanks to @RobinRyder
* -2 bytes using @Arnauld idea of storing occurrences table only (I just noticed that basically I was using the same approach, but creating the actual list too)
> 4 votes

# Answer
# Ruby, 100 bytes

Relatively simple answer similar to the Jelly solution, but it's able to calculate for n=4 without timing out on TIO (albeit taking 30 seconds to do so), which Jelly can't at time of writing.

```
->n{r=(1..n).flat_map{|j|[j]*j};i=0;r.sum{r.permutation(i+=1).uniq.count{|a|a.uniq==[*1..a.max]}}+1}

```

Try it online!
> 2 votes

# Answer
# Raku, 94 bytes

```
{1+set map ~*,grep {all .unique Z==^$_},.permutations>>[[\,] ^$_][*;*]}o{(^$_ Zxx 1..$_)[*;*]}

```

Try it online!

Times out for \\$n\>3\\$, mostly since it is running the same filter for all prefixes of all permutations of the largest list (i.e. `[1,2,2,3,3,3,...n]`). This results in a lot of duplicates that have to filtered out later.
> 2 votes

# Answer
# 05AB1E, ~~19~~ ~~18~~ 17 bytes

```
ÝDÅΓœ€Œ€`ÙʒÙāQ}g>

```

Pretty slow (\\$n=3\\$ in about ~~5.5~~ 0.5 seconds on TIO), but it works.

Inspired by *@isaacg*'s Pyth answer.
I have the feeling this can definitely be golfed by at least a few bytes, though.
-1 byte thanks to *@ExpiredData*.
-1 byte and sped up by changing the order of some operations thanks to *@Grimmy*.

Try it online or verify a few more test cases.

**Explanation:**

```
Ý                  # Push a list in the range [0, (implicit) input]
                   # (NOTE: `L` cannot be used here, because input=0 would become [1,0])
 D                 # Duplicate this list
  ÅΓ               # Run-length encode the lists, to have each value repeat itself that
                   # many times (i.e. [1,2,3,4] → [1,2,2,3,3,3,4,4,4,4])
    œ              # Take all permutations of this list
     ʒ             # Filter this list of lists by:
      Ù            #  Uniquify it
       ā           #  Push a list in the range [1, length] (without popping the list itself)
        Q          #  Check if both lists are equal
         }€η       # After the filter: take the prefixes of each remaining permutation
            €`     # Flatten one level
              Ù    # Uniquify the list of lists
               g   # After the filter: get the amount of remaining lists by taking the length
                >  # + 1 for the missing `[]`
                   # (after which this is output implicitly)

```

Minor (but even slower) alternative: `$ÝDÅΓœ€Œ€`ÙvyÙāQO`: Try it online or verify a few more test cases.

```
$                  # Push 1 and the input
 ÝDÅΓœ             # Same as above
      €Œ           # Get all sublists of each permutation
        €`Ù        # Same as above
           v       # Loop over each inner list `y`
            y      #  Push list `y`
             ÙāQ   #  Same as above
                O  #  Take the sum of the stack
                   # (after the loop, the result is output implicitly)

```
> 2 votes

# Answer
# Perl 5, 150 bytes

```
sub f{my$n=pop;$n?do{my%e;@f=f($n-1);push@f,map{$f=$_;grep!$e{$_}++,map$f=~s/.{$_}/$&$n/r,$n==1?0:index($f,$n-1)+1||9e9..length$f}@f for 1..$n;@f}:''}

```

Try it online!

Produces the correct output in about two seconds for up to n=5.

Out of memory for n=6. And would not work anyway for n\>9 (two digit numbers).

Thought about using a permutation solution like @Value Ink's Ruby answer, but could'nt find a core perl function or module that generated perm's and including a permutation function would probably add just way too many bytes.

With indentation, comments and test run:

```
sub f {
    my $n = pop;
    $n == 0 ? ('')
  : $n == 1 ? ('',1)
  : do {
      my %e;                                   #keep track of existing elements (strings)
      @f = f($n-1);                            #start with f(n-1) array
      push @f, map{                            #expand f array n times
        $f = $_;                               #f = current @f element
        grep !$e{$_}++,                        #don't add if already exists
          map $f =~ s/.{$_}/$&$n/r,            #insert n char at current position
            index($f,$n-1)+1||9e9 .. length$f  #loop positions from first occurence of n-1 to end
      } @f
        for 1..$n;
      @f                                       #return expanded @f array (string sequences)
    }
}

# test:
for my $n (0..5){
  my @f = f($n);
  my $list = $n<5 ? '['.join(',',map"'$_'",@f).']' : '';
  print "$n: ".@f." $list\n";
}

```

Output:

```
0: 1 ['']
1: 2 ['','1']
2: 4 ['','1','12','122']
3: 16 ['','1','12','122','123','1232','1223','1233','12332','12323','12233','12333','123332','123323','123233','122333']
4: 409 ['','1','12','122','123','1232','1223','1233','12332','12323','12233','12333','123332','123323','123233','122333','1234','12342','12324','12234','12343','12334','123432','123342','123324','123423','123243','123234','122343','122334','123433','123343','123334','1234332','1233432','1233342','1233324','1234323','1233423','1233243','1233234','1234233','1232433','1232343','1232334','1223433','1223343','1223334','12344','123442','123424','123244','122344','123443','123434','123344','1234432','1234342','1234324','1233442','1233424','1233244','1234423','1234243','1234234','1232443','1232434','1232344','1223443','1223434','1223344','1234433','1234343','1234334','1233443','1233434','1233344','12344332','12343432','12343342','12343324','12334432','12334342','12334324','12333442','12333424','12333244','12344323','12343423','12343243','12343234','12334423','12334243','12334234','12332443','12332434','12332344','12344233','12342433','12342343','12342334','12324433','12324343','12324334','12323443','12323434','12323344','12234433','12234343','12234334','12233443','12233434','12233344','123444','1234442','1234424','1234244','1232444','1223444','1234443','1234434','1234344','1233444','12344432','12344342','12344324','12343442','12343424','12343244','12334442','12334424','12334244','12332444','12344423','12344243','12344234','12342443','12342434','12342344','12324443','12324434','12324344','12323444','12234443','12234434','12234344','12233444','12344433','12344343','12344334','12343443','12343434','12343344','12334443','12334434','12334344','12333444','123444332','123443432','123443342','123443324','123434432','123434342','123434324','123433442','123433424','123433244','123344432','123344342','123344324','123343442','123343424','123343244','123334442','123334424','123334244','123332444','123444323','123443423','123443243','123443234','123434423','123434243','123434234','123432443','123432434','123432344','123344423','123344243','123344234','123342443','123342434','123342344','123324443','123324434','123324344','123323444','123444233','123442433','123442343','123442334','123424433','123424343','123424334','123423443','123423434','123423344','123244433','123244343','123244334','123243443','123243434','123243344','123234443','123234434','123234344','123233444','122344433','122344343','122344334','122343443','122343434','122343344','122334443','122334434','122334344','122333444','1234444','12344442','12344424','12344244','12342444','12324444','12234444','12344443','12344434','12344344','12343444','12334444','123444432','123444342','123444324','123443442','123443424','123443244','123434442','123434424','123434244','123432444','123344442','123344424','123344244','123342444','123324444','123444423','123444243','123444234','123442443','123442434','123442344','123424443','123424434','123424344','123423444','123244443','123244434','123244344','123243444','123234444','122344443','122344434','122344344','122343444','122334444','123444433','123444343','123444334','123443443','123443434','123443344','123434443','123434434','123434344','123433444','123344443','123344434','123344344','123343444','123334444','1234444332','1234443432','1234443342','1234443324','1234434432','1234434342','1234434324','1234433442','1234433424','1234433244','1234344432','1234344342','1234344324','1234343442','1234343424','1234343244','1234334442','1234334424','1234334244','1234332444','1233444432','1233444342','1233444324','1233443442','1233443424','1233443244','1233434442','1233434424','1233434244','1233432444','1233344442','1233344424','1233344244','1233342444','1233324444','1234444323','1234443423','1234443243','1234443234','1234434423','1234434243','1234434234','1234432443','1234432434','1234432344','1234344423','1234344243','1234344234','1234342443','1234342434','1234342344','1234324443','1234324434','1234324344','1234323444','1233444423','1233444243','1233444234','1233442443','1233442434','1233442344','1233424443','1233424434','1233424344','1233423444','1233244443','1233244434','1233244344','1233243444','1233234444','1234444233','1234442433','1234442343','1234442334','1234424433','1234424343','1234424334','1234423443','1234423434','1234423344','1234244433','1234244343','1234244334','1234243443','1234243434','1234243344','1234234443','1234234434','1234234344','1234233444','1232444433','1232444343','1232444334','1232443443','1232443434','1232443344','1232434443','1232434434','1232434344','1232433444','1232344443','1232344434','1232344344','1232343444','1232334444','1223444433','1223444343','1223444334','1223443443','1223443434','1223443344','1223434443','1223434434','1223434344','1223433444','1223344443','1223344434','1223344344','1223343444','1223334444']
5: 128458

```
> 1 votes

# Answer
# Charcoal, 34 bytes

```
Ｎθ⊞υυＦυＦθＦ∧∨¬κ№ι⊖κ‹№ικ⊕κ⊞υ⁺ι⟦κ⟧ＩＬυ

```

Try it online! Link is to verbose version of code. Builds up all `a(n)` lists in memory, so TIO will only go up to `n=5`. Explanation:

```
Ｎθ

```

Input `n`.

```
⊞υυ

```

Start with a sequence with no digits. (Alternatively, I could start with a list containing `-1`; this would cost 3 bytes here and then save 3 bytes because I don't need to special case the first digit below.)

```
Ｆυ

```

Loop through each sequence as it is discovered.

```
Ｆθ

```

Loop through each available digit. (These are 0-indexed, so each digit `i` must be less than `n` and can be added if there are no more than `i` digits `i` so far.)

```
Ｆ∧∨¬κ№ι⊖κ‹№ικ⊕κ

```

Check that the digit is legal.

```
⊞υ⁺ι⟦κ⟧

```

If so then append this sequence to the list.

```
ＩＬυ

```

Output the total number of sequences found.
> 1 votes

---
Tags: code-golf, sequence, combinatorics
---


title: Minigolf Solitaire

text:
# Question
Title: Minigolf Solitaire
Inspired by this question on the puzzling stack exchange.

## Rules

Given 5 stacks of 5 cards with numbers from 1 to 7, output the moves needed to empty all stacks. A move is defined as the index of a column to pull the card off of, and a move is only valid if:

1. The stack is non-empty
2. The value of the card at the top of the stack is exactly 1 lower or higher than the value of the last card removed *from any of the stacks*. Note 1 and 7 wrap.

## Input

This challenge has loose input rules. You can use any format as input for the 25 numbers so long as the input is unambiguous among all possible inputs. The same token must be used for every instance of a card's representation. That is, if you use `2` to represent a `2`, you must use that everywhere in your input. But you may use `2` to represent `2` and `532jv4q0fvq!@$$@VQea` to represent `3` if this is somehow beneficial.

## Output

The list of moves needed to empty all stacks without getting stuck. This format is also loose, but it needs to represent a list of indices, where `0` is the leftmost stack.

Your program may assume that the input provided is solvable. That is, you may have undefined behaviour in the case of unsolvable input.

Note: If the input has multiple possible solutions, outputting at least 1 valid solution is acceptable

## Example/Test Case explained

Input: Representing the 5 stacks, where stack one is `5,5,3,2,6` with `5` being the top of the stack. Likewise for the other 4 stacks. Again, as stated in the question, this input format is loose and can be changed to facilitate the answer

```
5 5 3 2 6
2 4 1 7 7
4 2 7 1 3
2 3 3 1 4
4 6 5 5 1

```

Output: List of moves representing the order in which the cards are pulled off the stacks. I'll explain the result of the first 3 moves. The first 3 pops `2` off of the 4th stack (`2 3 3 1 4` stack). The second 3 pops `3` off of the same stack. And then the 1 pops the `2` off of the 2nd stack. If you follow these moves on the input you will end up with empty stacks

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

```

# Answer
> 3 votes
# Jelly,  ~~31~~  28 bytes

# The 31 byte answer:

```
ṖÞZṪs5J€Ƒ
ŒṪŒ!ÇƇðœịIA%5=1ẠðƇḢZḢ

```

Accepts the stacks as a list of lists, `[s1, s2, s3, s4, s5]` where each stack has the first playable card on its left; returns a list of the 1-indexed stacks to from which to play, left to be played first.

Get a list of all ways by replacing `ḢZḢ` with `Ḣ€€`.

Since this is way too inefficient for a 5 by 5...
**Try a 3 by 3 version online!** (`5` replaced by `3` in the code)
\- this still takes ~45s and the code is \\$O(n^2!)\\$.

### How?

```
ṖÞZṪs5J€Ƒ - Link 1: check each stack used in order: list [[stackIndex1, cardIndex1],...]
 Þ        - sort by:
Ṗ         -   pop (i.e. sort by stackIndex values)
  Z       - transpose -> [[1,1,1,1,1,2,2,...,4,4,5,5,5,5,5], cardIndicesSortedByStack]
   Ṫ      - tail -> cardIndicesSortedByStack
    s5    - split into chunks of five - i.e. split up by stacks
        Ƒ - invariant under?:
       €  -   for each:
      J   -     range of length (i.e. equals [[1,2,3,4,5],[1,2,3,4,5],...]?)

ŒṪŒ!ÇƇðœịIA%5=1ẠðƇḢZḢ - Main Link: list of lists of integers, M
ŒṪ                    - truthy multi-dimensional indices
  Œ!                  - all permutations
     Ƈ                - filter keep those for which:
    Ç                 -   call last Link (1) as a monad
                 Ƈ    - filter keep those for which:
      ð         ð     -   the dyadic chain - i.e. checkCardOrder(2d-indices, M)
       œị             -     multidimensional index into M (vectorises)
         I            -     deltas - i.e. [a,b,c,d,...]->[b-a,c-b,d-c,...]
          A           -     absolute values
           %5         -     mod five
             =1       -     equals one
               Ạ      -     all?
                  Ḣ   - head - i.e. first valid 2d-inices pemutation
                   Z  - transpose -> [stackIndices, cardIndices]
                    Ḣ - head -> stackIndices

           ...OR: Ḣ€€ - head each of each -> list of all such stackIndices

```

---

# The 28 byte answer:

Using the rule `You can use any format as input for the 25 numbers so long as the input is unambiguous among all possible inputs` we may choose seven numbers such that a new dyadic function which accepts a list of such numbers and returns a list with `1`s for adjacent neighbouring numbers and `0` for non-adjacent neighbouring numbers replaces the code `IA%5=1`. I chose the following:

```
^ƝẒ - list of numbers from [2,7,12,14,25,28,91] (mapping to [1,2,3,4,5,6,7])
 Ɲ  - neighbours
^   - XOR
  Ẓ - is prime?

```

Here is a table of the XOR results:

```
 ^ |  2  7 12 14 25 28 91
---+----------------------
 2 |  0  5 14 12 27 30 89
 7 |  5  0 11  9 30 27 92
12 | 14 11  0  2 21 16 87
14 | 12  9  2  0 23 18 85
25 | 27 30 21 23  0  5 66
28 | 30 27 16 18  5  0 71
91 | 89 92 87 85 66 71  0

```

And if we check primality:

```
^Ẓ |  2  7 12 14 25 28 91
---+----------------------
 2 |  0  1  0  0  0  0  1
 7 |  1  0  1  0  0  0  0
12 |  0  1  0  1  0  0  0
14 |  0  0  1  0  1  0  0
25 |  0  0  0  1  0  1  0
28 |  0  0  0  0  1  0  1
91 |  1  0  0  0  0  1  0

```

Here is **the equivalent to the 3 by 3 version above**

---

Many other mappings work with this code, e.g.:

```
[1, 2, 3, 4, 5, 6, 7] : [2, 5, 6, 13, 16, 37, 39]

```

or

```
[1, 2, 3, 4, 5, 6, 7] : [7, 12, 17, 18, 21, 32, 34]

```

# Answer
> 7 votes
# JavaScript (V8), 86 bytes

This version is similar to the other one but takes advantage of the loose input format.

The cards are expected as follows:

\\$\[\text{Ace}, 2, 3, 4, 5, 6, 7\] = \[ 16, 37, 31, 91, 44, 41, 1 \]\\$

```
f=(a,p,o='')=>o[24]?print(o):a.map((c,i)=>(v=c.pop())&&c.push((p^v)%3?v|f(a,v,o+i):v))

```

Try it online!

### How?

The numbers \\$a\_n\\$ representing the card values were chosen in such a way that:

* \\$a\_i \bmod 3\neq0\\$ for any \\$i\in\[1..7\]\\$
* \\$(a\_i \operatorname{xor} a\_j)\bmod 3\neq0\\$ for any \\$i,j\in\[1..7\]\\$ iff the \\$i\\$-th and \\$j\\$-th cards are consecutive

*Example:*

Here is what we get for an Ace (\\$v=16\\$):

```
 previous card |     p     | p xor 16 | (p xor 16) mod 3
---------------+-----------+----------+------------------
     none      | undefined |    16    |        1
      ace      |     16    |     0    |        0
       2       |     37    |    53    |        2
       3       |     31    |    15    |        0
       4       |     91    |    75    |        0
       5       |     44    |    60    |        0
       6       |     41    |    57    |        0
       7       |      1    |    17    |        2

```

---

# JavaScript (V8),  ~~105 ... 92~~  91 bytes

Takes input as an array of 5 columns with 1-indexed cards (Ace = 1, Two = 2, etc.). Prints all solutions as strings of 0-indexed columns.

```
f=(a,p,o='')=>o[24]?print(o):a.map((c,i)=>(v=c.pop())&&c.push((p-~v*6)%7%5?v:v|f(a,v,o+i)))

```

Try it online!

### How?

Given the previous card \\$p\\$ and the current card \\$v\\$, we compute:

$$k=((p+(v+1)\times6) \bmod 7) \bmod 5$$

The cards are consecutive iff \\$k=0\\$.

$$ \begin{array}{c|ccccccc} &1&2&3&4&5&6&7\\ \hline 1&1&0&4&3&2&1&0\\ 2&0&1&0&4&3&2&1\\ 3&1&0&1&0&4&3&2\\ 4&2&1&0&1&0&4&3\\ 5&3&2&1&0&1&0&4\\ 6&4&3&2&1&0&1&0\\ 7&0&4&3&2&1&0&1\\ \end{array} $$

We could, in theory, use \\$v+(p+1)\times 6\\$ just as well. But in the JS implementation, we want the result to be *NaN* (falsy) if \\$p\\$ is *undefined* (first iteration), which is why the bitwise operation (`-~v`) may only be applied to \\$v\\$.

### Commented

```
f = (                  // f is a recursive function taking:
  a,                   //   a[] = input
  p,                   //   p = previous card (initially undefined)
  o = ''               //   o = solution
) =>                   //
  o[24] ?              // if o has 25 characters:
    print(o)           //   we have a complete solution: print it
  :                    // else:
    a.map((c, i) =>    //   for each column c at position i in a[]:
      (v = c.pop())    //     pop the last card v from this column
      &&               //     abort if it's undefined
      c.push(          //     otherwise:
        (p - ~v * 6)   //       use our magic formula
        % 7 % 5 ?      //       if it's not equal to 0 or NaN:
          v            //         just push v back
        :              //       else:
          v |          //         because v belongs to the global scope,
                       //         we need to use its current value right away
          f(           //         do a recursive call to f:
            a,         //           pass a[]
            v,         //           set p = v
            o + i      //           append i to o
          )            //         end of recursive call
      )                //     end of push()
    )                  //   end of map()

```

# Answer
> 2 votes
# Jelly, 43 bytes

```
““”;WA;"ị@Ṫ;ɗ¥¥ⱮT>Ƈ2Ɗ$€ẎIḢAfƑʋƇ1,6Ʋ25¡2ịⱮ_3

```

Try it online!

A monadic link taking a list of lists of integers (representing the stacks) and returning a list of lists of integers (representing the possible sequences of moves).

## Explanation (method)

Works iteratively on 1 or more lists, each of which contains the sequence of cards so far at index 1, the sequence of stacks used at index 2 and the current stacks at positions 3 through 7. As such, the stacks are 3-indexed, and get changed to 0-indexing at the end. At each iteration, all possible moves are created, and then the sequence of cards is tested to check that the differences are all either -1, -6, 1 or 6. All valid moves are kept, and the next cycle of the loop is processed.

## Explanation (code)

```
““”;                                        | Prepend two empty lists
    W                                       | Wrap in a further list
                                  Ʋ25¡      | Repeat the following 25 times:
                     $€                     | - For each current working list:
               Ɱ    Ɗ                       |   - Using each of the following as the right argument:
                T                           |     - Truthy indices (effectively here the indices of non-empty lists)
                 >Ƈ2                        |     - Keep only those greater than 2
              ¥                             |   - ... do the following as a dyad:
     A                                      |     - Absolute (used here for the side effect of copying the list)
             ¥                              |     - Following as a dyad:
      ;"    ɗ                               |       - Concatenate to following, using zipped arguments:
        ị@                                  |         - Index into list using reversed arguments
          Ṫ                                 |         - Tail, popping from list
           ;                                |         - Concatenate (to the list index)
                       Ẏ                    | - Join outer lists together
                             ʋƇ             | - Keep those lists where the following is true:
                        I                   |   - Increments (vectorises)
                         Ḣ                  |   - Head
                          A                 |   - Absolute
                           fƑ  1,6          |   - Invariant when filtered to only contain 1s and 6s
                                      2ịⱮ   | 2nd sublist of each (i.e. the sublist containing the list indices used)
                                         _3 | Minus 3

```

# Answer
> 1 votes
# Ruby, ~~140...121~~ 119 bytes

```
->n{w=[*0..4].product;w.find{|x|5.times{|j|((n[j][x.count j]||99)-n[a=x[-1]][~-x.count(a)])**2%35==1&&w<<x+[j]};x[24]}}

```

Try it online!

### How:

Breadth-first search:

* initialize the solution vector with the single cards on top of the stacks. `(w=[[0],[1],[2],[3],[4]])`
* for every solution in the vector, check the possible next step. For example, `[0]` could expand to `[0,2]` or `[0,4]`. Append these new solutions to the vector.
* now check if the solution has 25 elements: if it does, it's complete, and we can stop.

The check could be more efficient, but since I only save the stack numbers, I have to get the cards from the stacks on every iteration. Changing the stack in a non-recursive solution is out of the question, and saving the card numbers would require more code.

---
Tags: code-golf
---


# Question
Title: Approximating the amount of prime numbers below `x`
# Background

We define the prime-counting function, \\$\pi(x)\\$, as the number of prime numbers less than or equal to \\$x\\$. You can read about it here.

For example, \\$\pi(2) = 1\\$ and \\$\pi(6) = 3\\$.

It can be shown, using dark magic, that

\\$ \lim\_{x \to \infty} \frac{\pi(x)}{x/\log x} = 1 \\$

which means we can approximate \\$ \pi(x) \\$ by \\$ x/\log x\\$.

# Your task

Your purpose is to write a function/program that takes `x` as input and outputs the approximation of \\$\pi(x)\\$ as given by the ratio of the input and the logarithm of the input, with **exactly** \\$\pi(x)\\$ decimal places. Either rounding works fine.

# Test cases

```
f(4) = 2.89
f(10) = 4.3429
f(19.3) = 6.52003877
f(60) = 14.6543602005583370
f(173) = 33.570776430488395580723956088340374417691
f(499) = 80.3205598921264941447922062868184315657020413225943243128931714242910058741601601524983152243502
f(1024) = 147.73197218702985291365628733459375487248854570526575965547001926974558404415335218027792618429504967649254587490842053177273361276604002741459580500208428403451262667619517

```

# Scoring

This is so shortest solution wins... With a twist! If the code you wrote gives the right answer for results with up to `p` decimal places and your code has `b` bytes, then your score is

\\$(e^{-p/64} + \frac13)b \\$

which essentially means you get a better score if the precision is really high, as the factor multiplying by `b` decays rapidly as the precision increases until flattening at \\$\frac13\\$.

If you can't tell for sure the precision up to which your code works, you can take `p` to be the number of decimal places of the last test case your code can handle exactly.

For this challenge, the minimum score is `1/3`, which would be attainable by a 1-byte long submission with arbitrary precision.

# Admissible solution

To wrap up, your code is a valid solution if and only if it computes the approximation of \\$\pi(x)\\$ as given by the formula and, when it gives the output, the output has exactly \\$\pi(x)\\$ decimal places. The `p` for the scoring will be how many decimal places you can get right.

Notice the distinction. The code linked outputs square root of 2 with 1000 decimal places BUT python only gets some of the decimal places right.

---

Standard loopholes are forbidden

# Answer
# Python 3, 61 bytes \\$\approx\\$ 77.6375 score

```
import math
def f(x):p=x/math.log(x);print(f"{p:.{int(p)}f}")

```

Try it online!

Correct up to 4 decimals for \\$\pi(10)\\$.

**Original post solution:**

# Python 3, 41 bytes \\$\approx\\$ 54.66 score

```
lambda x:int(x/__import__('math').log(x))

```

Try it online!

Saved 20 bytes thanks to Expired Data!!!

Taking a leaf out of Expired Data's book and going for zero precision so \\$p=0\\$.
> 3 votes

# Answer
# 05AB1E, ~~17~~ 14 bytes - Score = ~~22.6...~~ 18.6...

*-3 bytes/4 score thanks to Kevin Cruijssen*

```
žr.n÷'.0IÅPg×J

```

Try it online!

As far as I'm aware 05ab1e doesn't have arbitrary length decimal precision. You can probably come up with an answer which calculates pi(x) decimal points of x/log(x) in less than 68 bytes and then concats them but frankly I'm not interested in this question any more.

---

# Old answer before the question was revised

# 05AB1E, 6 bytes = 8 score

```
žr.n/ò

```

Try it online!

Does x/ln(x) and then rounds to the nearest integer, hence p = 0
> 3 votes

# Answer
# Bash \+ bc, 89 bytes, arbitrary precision, final score \\${89\over3} \approx 29.67\\$

```
f(){
a=`primes 1 $((${1%.*}+1))|wc -l`
echo "scale=$a+20;a=$1/l($1);scale=$a;a/1"|bc -l
}

```

Try it online!

`${1%.*}` strips off the fraction

`$((` ... `+1)))` adds one, as primes doesn't output the final number if prime.

`primes 1`... outputs the list of primes

`|wc -l` counts them

At this point, a contains \\$\pi(x)\\$.

The `echo` puts together a bc program, which is then piped to bc.

* Set the scale to 20 more than needed (to get the accuracy)
* do the approximation
* set the scale to the exact number of digits
* do a division by 1 so the scale is applied
> 3 votes

# Answer
# bc, 61,51,46,45 bytes +2 for -l, (almost) arbitrary precision, final score \\$\approx{47\over3} \approx 15.6666744835...\\$

```
define f(x){scale=999
return(scale=x/l(x))/1}

```

Try it online!

Unlike the test cases, I don't give too many digits.  I give the number of digits based on the approximation, not the counted value.

Precision degrades with this solution when the result reaches 1000, at f(9119). At that point, one must add another 9 on the first line. A general solution would be possible, but longer. I guess this makes the score for this version 15.6666744835...

It turns out, with initial scale=99 the score is 25.127..., and with initial scale=9999 the score is 16 + 6.75...E-67.

I could write scale=9^9, get 387420489 digits of precision (probably a few less accurate), but it would take too long to run. TIO doesn't even let 9^4 get passed the second test case. This would get a score of 15.6666666666..., but still slightly more the 15⅔.

Edit: Saved 10 bytes by eliminating scale=0 and rounding on scale=a

Edit: saved 5 bytes by eliminating a temporary

Edit: saved 1 byte by eliminating whitespace
> 2 votes

# Answer
# Mathematica, \\$\approx\\$ 7.67 score

## ~~25~~ 23 bytes, arbitrary precision, final score \\$ \frac{23}{3}\\$

```
N[#/Log@#,PrimePi@#+1]&

```

*-2 bytes*, courtesy of @ExpiredData

Here is a benchmarking solution. Try it online!.
> 1 votes

---
Tags: math, code-challenge, floating-point
---


title: Simple Circular Words

text:
# Question
Title: Simple Circular Words
A "simple circular" word is a word whose chords do not intersect. The chords of a word may be seen by laying out the alphabet in a circle, and then connecting the word's consecutive letters.

## Examples of Simple Circular Words

**ROLE**

**LAKE**

**BALMY**

## Failing Example

A word fails to be simple circular if any of its chords intersect:

## The Challenge

Write a program or function that takes a word and returns true if it's simple circular, false otherwise.

* Code golf, fewest bytes wins.
* Standard rules.
* You may assume there are *no repeated letters* in the word.
* You may assume every word has at least 2 letters
* You may assume the word is all uppercase, or all lowercase, whichever you prefer.
* You may output any two consistent values for true and false.

## Test Cases

### True

ROLE, LAKE, BALMY, AEBDC, ABZCYDXE, AZL, ZA

### False

BONES, ACDB, ALBZ, EGDF

# Answer
# Jelly, 12 bytes

```
O_Ṫ$:Ṫ$¬EƲƤẠ

```

Try it online!

A Jelly translation of Grimy’s 05AB1E answer; be sure to upvote that one too! A monadic link taking a Jelly string as its argument and returning a Jelly boolean.

## Explanation

```
O            | Convert to Unicode codepoints
         ƲƤ  | Following applied to each prefix:
 _Ṫ$         | - Subtract tail (after popping tail)
    :Ṫ$      | - Integer divide by tail (after popping tail)
       ¬     | - Not
        E    | - All equal
           Ạ | All

```
> 2 votes

# Answer
# Perl 6, 46 bytes

```
{!/[(.).*]**4<?{[+^] $0 Xeq[...] ~<<$0[^2]}>/}

```

Try it online!

A regex solution that finds if there are four characters in the string such that the two later characters are in different sections of the circle, as defined by the first two characters.

### Explanation

```
{                                           }   # Anonymous code block returning
 !/                                        /    # If the input does not match
   [(.).*]**4                                     # Any 4 characters
             <?{                          }       # Where
                           [...]                    # The range from
                                 ~<<$0[^2]          # The first character to the second
                        Xeq                         # Contains which of
                     $0                             # The four characters
                [+^]                                # Reduce the list of booleans by xor
                 # Effectively, if only one of the 3rd or 4th character is in that range

```
> 12 votes

# Answer
# K (ngn/k), ~~26~~ 24 bytes

```
{&/|/x=&\'x:-:\|26!x-*x}

```

Try it online!

`*x` first letter of the argument `x`

`x-` subtract it from each of `x` as ascii code

`26!` mod 26

`|` reverse

`-:\` make a pair of the list and its negation

`x:` assign to `x`

`&\'` cumulative minima and maxima (max is min under negation)

`|/x=` boolean mask for where `x[i]` is the current minimum or maximum

`&/` all (and-reduce)
> 10 votes

# Answer
# 05AB1E, ~~14~~ 13 bytes

*Fixed a bug thanks to NickKennedy*

```
Ç.sεć-ć/ï_Ë}P

```

Try it online!

```
Ç               # convert each letter to its codepoint
 .s             # suffixes of this list
   ε       }    # for each suffix:
    ć-          #  subtract first from others: [b-a, c-a, d-a, ...]
      ć/        #  divide others by first: [(c-a)/(b-a), (d-a)/(b-a), ...]
        ï       #  round down
         _      #  compare with 0
          Ë     #  all equal?
            P   # after the loop, product (1 iff the list is all 1s)

```
> 8 votes

# Answer
# 05AB1E, ~~21~~ 20 bytes

```
Ask¬-₂%.sD€ß¥s€à¥+ĀP

```

Port of *@ngn*'s K (ngn/k) answer, so make sure to upvote them!!

Input as a lowercase list of characters.

Try it online or verify all test cases.

**Explanation:**

```
A          # Push the lowercase alphabet: "abcdefghijklmnopqrstuvwxyz"
 sk        # Get the (0-based) index of each characters of the input-list in this alphabet
           #  i.e. ["b","a","l","m","y"] → [1,0,11,12,24]
¬          # Push the first index (without popping)
 -         # And subtract it from each index
           #  i.e. [1,0,11,12,24] - 1 → [0,-1,10,11,23]
  ₂%       # Then take modulo-26 to make the negative values positive
           #  i.e [0,-1,10,11,23] → [0,25,10,11,23]
.s         # Take the suffices of this list
           #  i.e. [0,25,10,11,23] → [[23],[11,23],[10,11,23],[25,10,11,23],[0,25,10,11,23]]
  D        # Duplicate it
   €ß      # Take the minimum of each suffix
           #  i.e. [[23],[11,23],[10,11,23],[25,10,11,23],[0,25,10,11,23]]
           #   → [23,11,10,10,0]
     ¥     # And take the deltas (forward differences) of those
           #  i.e. [23,11,10,10,0] → [-12,-1,0,-10]
  s        # Swap to get the suffices again
   €à      # Take the maximum of each suffix this time
           #  i.e. [[23],[11,23],[10,11,23],[25,10,11,23],[0,25,10,11,23]]
           #   → [23,23,23,25,25]
     ¥     # And take the deltas (forward differences) of those as well
           #  i.e. [23,23,23,25,25] → [0,0,2,0]
      +    # Add the values at the same indices in the two lists together
           #  i.e. [-12,-1,0,-10] + [0,0,2,0] → [-12,1,2,-10]
       Ā   # Python-style truthify each (0→0; everything else → 1)
           #  i.e. [-12,1,2,-10] → [1,1,1,1]
        P  # And take the product of that to check if all are truthy
           #  i.e. [1,1,1,1] → 1
           # (after which this is output implicitly as result)

```
> 6 votes

# Answer
# JavaScript (Node.js), 91 bytes

Returns \\$false\\$ for simple circular, or \\$true\\$ for non-simple circular.

```
s=>Buffer(s).some((o,i,a,j=i)=>a.some(_=>((g=i=>x=(a[i]-o%26)%26)(j)-g(i+1))*(x-g(++j))>0))

```

Try it online!

### Commented

```
s =>                            // s = input string
  Buffer(s)                     // turn s into a Buffer
  .some((o, i, a,               // for each ASCII code o at position i in a[]
                  j = i) =>     // and starting with j = i:
    a.some(_ =>                 //   for each entry in a[]:
      (                         //
        ( g = i =>              //     g is a helper function taking a position i
            x = (a[i] - o % 26) //       return (a[i] - (o mod 26)) mod 26
                % 26            //       and assign the result to x
                                //       NB: if a[i] is undefined, this gives NaN
                                //           and forces the forthcoming test to fail
        )(j) -                  //     compute the difference between g(j)
        g(i + 1)                //     and g(i + 1)
      ) * (                     //     multiply it by the difference
        x - g(++j)              //     between g(i + 1) and g(j + 1) (and increment j)
      ) > 0                     //     if it's positive, the chords are intersecting
                                //     inside the circle (i.e. s is not simple circular)
    )                           //   end of inner some()
  )                             // end of outer some()

```
> 6 votes

# Answer
# Charcoal, 29 bytes

```
⬤θ⬤…θκ⬤…θμ⬤…θξ⁼⁼‹ιν‹νλ⁼‹ιπ‹πλ

```

Try it online! Takes input in consistent case and outputs a Charcoal boolean (`-` for true, nothing for false). This has a rare use of the `p` variable. Explanation:

```
 θ                              Input string
⬤                               All characters satisfy
    θ                           Input string
   …                            Truncated to
     κ                          Current index
  ⬤                             All characters satisfy
        θ                       Input string
       …                        Truncated to
         μ                      Current index
      ⬤                         All characters satisfy
            θ                   Input string
           …                    Truncated to
             ξ                  Current index
          ⬤                     All characters satisfy
                 ι              Fourth character
                ‹               Is less than
                  ν             Second character
               ⁼                Equals
                    ν           Second character
                   ‹            Is less than
                     λ          Third character
              ⁼                 Equals
                        ι       Fourth character
                       ‹        Is less than
                         π      First character
                      ⁼         Equals
                           π    First character
                          ‹     Is less than
                            λ   Third character

```

For each subsequence of four characters in the input word, the first two comparisons check whether the second character is between the third and fourth while the other comparisons check whether the first character is between the third and fourth. If the results of these comparisons is different then it means that the chord between the first two characters crosses the chord between the third and fourth characters and the whole expression therefore evaluates to false.
> 4 votes

# Answer
# , ~~40~~ ~~36~~ 33 bytes

```
10(e.,)[:(/:~@,#.@e.])"1/~2]\3&u:

```

Try it online!

Decided to play my own game.

Still golfing...

But the idea is just to try all possible combinations of pairs of points, and check if their lines intersect, which, if the segements are AB and CD, happens when the letters' numerical values are arranged like:

```
      _____
     /     \
A...C...B...D
\______/

```
> 2 votes

# Answer
# Haskell, ~~135~~ 99 bytes

*Thanks @JoKing for saving 36 bytes!*

Almost certain its not the optimal way to go, so please feel free to improve it.

```
x(a:b:c:d:_)|s<- \z->min a b>z||z>max a b=s c/=s d;x _=1<0;y s=or$map(x.concat)$mapM(\a->[[a],[]])s

```

## Explanation

However, I loved doing some propositional calculus. First, `x` tests if a given sequence of four letters form a non-circular word. Let \\$I\\$ be the interval defined by \\$a\\$ and \\$b\\$, so \\$a,b,c\\$ and \\$d\\$ form a circular word only if:

$$ p\equiv(c\in I)\iff q\equiv(d\in I)\\ (p\Rightarrow q)\wedge(q\Rightarrow p)\\ (\neg p\lor q)\wedge(\neg q\lor p)\\ \left\[(\neg p\lor q)\wedge \neg q\right\]\lor\left\[(\neg p\lor q)\wedge p\right\]\\ \left\[(\neg p\wedge\neg q)\lor(q\wedge\neg q)\right\]\lor\left\[(\neg p\wedge p)\lor(q\wedge p)\right\]\\ (\neg p\wedge\neg q)\lor(q\wedge p)\\ \neg(p\lor q)\lor(q\wedge p) $$

Negating this proposition gives us

$$ (p\lor q)\wedge\neg(q\wedge p) $$

which is equivalent to \\$p\veebar q\\$, in haskell `p/=q`. Finally, `y` tests if any subsequence with length 4 from the original word is non-circular.

Here's a spaned version:

import Data.List

-- x
cuts (a:b:c:d:rest)
 | s <- \z-> min a b > z || z > max a b
 = s c /= s d
x _ = False

-- y
isNonCircular word = or $ map (cuts . concat) $ mapM (\a -> [[a],[]]) word
```
</code></pre>
> 2 votes

# Answer
# Ruby `-nl`, 70 bytes

An adaptation of the Perl answer, but Perl is apparently black magic with... whatever they're doing that lets them tersely get any 4 characters.

```
p$_.chars.combination(4).all?{|*m,c,d|(c=~r=/[#{m.sort*?-}]/)==(d=~r)}

```

Try it online!
> 1 votes

# Answer
# C (clang), ~~119~~ 114 bytes

```
c,n,b,j,o;g(char*w){for(int l[92]={j=o=c=0};n=*w;c=l[*w++])for(b=l[n],o|=b|c-j++&&c+~b&&b-c;n;)l[n--]++;return!o;}

```

Try it online!

```
We use an array representing the circle points ( we start from \0 instad of 'A' because it doesn't care)

We increment by 1 each point from current letter to 0.

The next point is valid if
 next == curr or
 next == curr - 1 or
 next == 0 and curr == j( iteration / left value )

LAKE
ABCDEFGHIJKLMN.. j   curr  next
00000000000000.. 0   0     L 0
11111111111*00.. 1   1     A 1
*1111111111100.. 2   2     K 2
3222222222*100.. 3   2     E 2
4333*222222100..

```

Thanks to @ceilingcat for saving 5
> 1 votes

---
Tags: code-golf, string, decision-problem
---


# Question
Title: Singly lossy integers: Concatenated sequences missing a single element
I define the method of combining a sequence to mean that every number in the sequence is concatenated as a string, then that result is made an integer.

```
[1, 2, 3] -> 123

```

For every finite sequence of at least 3 consecutive integers, missing exactly one element in the sequence, and this missing element may not be the first or last element in the sequence, output the integer resulting from the combined sequence. I am referring to this as a "singly lossy integer".

```
[1, 2, 3] -> {1, 3} (missing an element) -> 13

```

This sequence of singly lossy integers is the union of the following subsequences (partitions?):

The first subsequence `{n, n+2}` is A032607.

```
{n, n+2}            -> 13, 24, 35, 46, 57, 68, 79, 810, 911, 1012, ...
{n, n+1, n+3}       -> 124, 235, 346, ...
{n, n+2, n+3}       -> 134, 245, 356, ...
{n, n+1, n+2, n+4}  -> 1235, 2346, 3457, ...
{n, n+1, n+3, n+4}  -> 1245, 2356, 3467, ...
{n, n+2, n+3, n+4}  -> 1345, 2456, 3567, ...
...
for n ∈ ℕ (integers >= 1)

```

These integers must be printed in ascending order. **The first 25 singly lossy integers are below**:

```
13, 24, 35, 46, 57, 68, 79, 124, 134, 235, 245, 346, 356, 457, 467, 568, 578, 679, 689, 810, 911, 1012, 1113, 1214, 1235, ...

```

First 7597 Singly Lossy Integers

Ungolfed reference implementations. I made it to be faster, rather than smaller.

### Rules:

* Shortest code wins
* You may either (say which one):
    + Print the singly lossy integers forever
    + Given a positive integer *n*, print or return the first *n* elements as a list, or a comma- or whitespace- delimited string.
* You should support arbitrarily large integers if your language allows it, especially if you're printing forever.

Inspired by / Related

Note: There is not yet an entry in the OEIS for this sequence.

Another note: I named them the "Singly Lossy Integers" so that there could in turn be "Doubly Lossy Integers", "N-ly Lossy Integers", "(N+1)-ly Lossy Integers", and the "Lossy Integers" (union of all of these).

# Answer
# APL (Dyalog Unicode), 62 bytesSBCS

## Infinite printing full program, 63 bytes

```
s←⍎' '~⍨⍕
{⎕←s⊢a←⊃⍵⋄b←1+a⋄t←∪(b,⍨⊃a)(a,⊃⌽b)b,1↓⍵⋄t[⍋s¨t]}⍣≡⊂1 3

```

Try it online!

This one is pretty fast. Theoretically can be made faster using a min heap, but the challenge is code golf after all.

### How it works: the concept

If we denote each item in the sequence as a list of integers (`[1,3]` for 13, `[1,2,4]` for 124, and so on), observe that subsequent items can be derived from an existing item `x` in three ways:

* Add 1 to all numbers in `x`
* Add 1 to all numbers in `x`, and then prepend the first element of `x`
* Append 1 plus the last element of `x` to `x`

Therefore, the algorithm is to start with the single known value and infinitely run the following:

* Extract the smallest item and print it
* Derive three larger values from it and add them to the list of next candidate items

### How it works: the code

```
s←⍎' '~⍨⍕  ⍝ Helper function: concat a list of numbers
        ⍕  ⍝   Stringify entire array, which will contain blanks between items
   ' '~⍨   ⍝   Remove blanks
  ⍎        ⍝   Eval
s←         ⍝   Store the function to s

⍝ Main program: print all items in the sequence infinitely
{⎕←s⊢a←⊃⍵⋄b←1+a⋄t←∪(b,⍨⊃a)(a,⊃⌽b)b,1↓⍵⋄t[⍋s¨t]}⍣≡,⊂1 3
{...}⍣≡⊂1 3  ⍝ Specify starting item and infinite loop
       ⊂1 3  ⍝   singleton array containing [1 3]
{...}⍣≡      ⍝   Pass it to the infinite looping function

⎕←s⊢a←⊃⍵⋄b←1+a⋄t←∪(b,⍨⊃a)(a,⊃⌽b)b,1↓⍵⋄t[⍋s¨t]  ⍝ Single iteration
       ⍵  ⍝ Sorted candidate items
    a←⊃⍵  ⍝ Take the first element and store to a
⎕←s⊢a     ⍝ Concat and print it

b←1+a  ⍝ Add 1 to all items of a and store to b

t←∪(b,⍨⊃a)(a,⊃⌽b)b,1↓⍵  ⍝ Add next candidates
                   1↓⍵  ⍝ Remove the first item (already printed)
   (b,⍨⊃a)(a,⊃⌽b)b,     ⍝ Prepend three candidates:
                 b      ⍝   1+a
          (a,⊃⌽b)       ⍝   append 1+last element of a to a
   (b,⍨⊃a)              ⍝   prepend first element of a to 1+a
t←∪                     ⍝ Uniquify and store to t

t[⍋s¨t]  ⍝ t sorted with the key function s (concat'ed value)

```

## Function returning first `n` values, 62 bytes

```
⎕CY'dfns'
⊢↑∘{(⍋⊃¨⊂)⍵{a b c←⍵-1 0⍺⋄⍎dab⍕c↓a↓b~⍨⍳⍺}¨↓3cmat⍵}2+⊢

```

Try it online!

Slower, but still can handle 100 items in around 5 seconds.

### How it works: the concept

This solution uses a systematic way to generate all possible singly lossy integers from the list `1..n`. It is equivalent to selecting three members from `1..n`:

* Select three distinct integers `a < b < c` from `1..n`.
* Take the inclusive range `a..c` and discard `b`.

```
Original list: 1 2 3 4 5 6 7 8 9
Selection:       ^ ^       ^
                 a b       c
Take a..c:       2 3 4 5 6 7
Discard b:       2   4 5 6 7
Result: 24567

```

I use `dfns.cmat` to generate all 3-combinations, generate all singly lossy numbers, sort them and take first `n` elements. We need length `n+2` for the combinations because lower numbers won't give enough number of items.

### How it works: the code

```
⎕CY'dfns'  ⍝ Import dfns library, so that we can use cmat

⍝ Inner function: generate enough singly lossy integers
{(⍋⊃¨⊂)⍵{a b c←⍵-1 0⍺⋄⍎dab⍕c↓a↓b~⍨⍳⍺}¨↓3cmat⍵}  ⍝ Input: 2+n

⍵{...}¨↓3cmat⍵  ⍝ Generate all 3-combinations, and get singly lossy integers
        3cmat⍵  ⍝ 3-combinations of 1..2+n
⍵{   }¨↓        ⍝ Map the inner function to each row of above, with left arg 2+n

a b c←⍵-1 0⍺⋄⍎' '~⍨⍕c↓a↓b~⍨⍳⍺  ⍝ From 3-combination to a singly lossy integer
a b c←⍵-1 0⍺  ⍝ Setup the numbers so that
              ⍝ "remove b, drop first a and last c elements" gives desired value
⍎dab⍕c↓a↓b~⍨⍳⍺  ⍝ Compute the target number
     c↓a↓b~⍨⍳⍺  ⍝ Remove b, drop first a and last c elements from 1..2+n
⍎dab⍕           ⍝ Concat the numbers (dab stands for Delete All Blanks)

(⍋⊃¨⊂)  ⍝ APL idiom for sorting

⊢↑∘{...}2+⊢  ⍝ Outer function; input: n
  ∘{...}2+⊢  ⍝   Pass 2+n to the inner function
⊢↑           ⍝   Take first n elements from the result

```

---

# APL (Dyalog Extended), 49 bytesSBCS

```
⊢↑∘{∧⍵{a b c←⍵-1 0⍺⋄⍎⌂dab⍕c↓a↓b~⍨⍳⍺}¨↓3⌂cmat⍵}2+⊢

```

Try it online!

Simply uses extra built-ins provided in Extended version (dfns library pre-loaded as  functions,  for ascending sort).
> 4 votes

# Answer
# Haskell, ~~131~~, ~~114~~, 106 bytes

```
iterate(\n->minimum[x|x<-[read(show=<<filter(/=k)[i..j])::Int|i<-[1..n],j<-[i+2..n],k<-[i+1..j-1]],x>n])13

```

This is limited by the size of `Int`, but it can be easily extended by replacing `Int` with `Integer`.

Less golfed:

```
concatInt x = read (concatMap show x) ::Int
allUpToN n = [concatInt $ filter (/=k) [i..j] | i <- [1..n], j <- [i+2..n], k <- [i+1..j-1]]
f n = minimum[x | x <- allUpToN, x > n ]
iterate f 13

```

8 bytes golfed by @nimi.
> 3 votes

# Answer
# Mathematica, 101 bytes

```
Sort@Flatten@Table[FromDigits[""<>ToString/@(z~Range~x~Delete~y)],{x,3,#},{z,1,x-1},{y,2,x-z}][[1;;#]]&

```

Yay! For once I have the shortest answer! `Party[Hard]`
> 3 votes

# Answer
## Python 3, ~~136~~ ~~127~~ ~~126~~ 122 bytes

brute force solution, I don't even try n=7000 (it already take 10s for n = 100)

```
r=range
f=lambda n:sorted(int(''.join(str(i+k)for i in r(1,j)if l-i))for k in r(n)for j in r(4,n)for l in r(2,j-1))[:n]

```

## Explanation

```
# f=lambda n:sorted( int(''.join(str(i+k) for i in r(1,j)   if l-i)) for k in r(n) for j in r(4,n) for l in r(2,j-1))[:n]
#            ──┬──                        ───────┬───────    ───┬──  ──────┬──────  ──────┬──────  ────────┬──────── ─┬─
#              │                                 │              │          │              │                │          └── selection of the n first numbers
#              │                                 │              │          │              │                └── loop to remove missing element
#              │                                 │              │          │              └── loop for the dimension of the list n to be sure we miss nothing xD
#              │                                 │              │          └── loop on the n in op description
#              │                                 │              └── Test to remove missing element
#              │                                 └── loop on {n, n+1 ...} in the op description
#              └──── sort the list

```

## Results

```
>>> f(25)
[13, 24, 35, 46, 57, 68, 79, 124, 134, 235, 245, 346, 356, 457, 467, 568, 578, 679, 689, 810, 911, 1012, 1113, 1214, 1235]

>>> f(100)
[13, 24, 35, 46, 57, 68, 79, 124, 134, 235, 245, 346, 356, 457, 467, 568, 578, 679, 689, 810, 911, 1012, 1113, 1214, 1235, 1245, 1315, 1345, 1416, 1517, 1618, 1719, 1820, 1921, 2022, 2123, 2224, 2325, 2346, 2356, 2426, 2456, 2527, 2628, 2729, 2830, 2931, 3032, 3133, 3234, 3335, 3436, 3457, 3467, 3537, 3567, 3638, 3739, 3840, 3941, 4042, 4143, 4244, 4345, 4446, 4547, 4568, 4578, 4648, 4678, 4749, 4850, 4951, 5052, 5153, 5254, 5355, 5456, 5557, 5658, 5679, 5689, 5759, 5789, 5860, 5961, 6062, 6163, 6264, 6365, 6466, 6567, 6668, 6769, 6870, 6971, 7072, 7173, 7274, 7375]

```

*Thanks to @mbomb007 and @FricativeMelon for their help*
> 2 votes

# Answer
# Python 3, ~~319~~, ~~270~~, 251 bytes

```
t,h,n,k,q*=range,input(),1,2,
while h>len(q)or n*k<=len(str(q[h])):
 q+=[int("".join([str(c+s)for c in t(k+1)if c-y]))for s in t(10**~-n,10**n)for y in t(1,k)]
 if~-n:n*=k;k+=1
 else:n,k=k+1,2
 while n//k*k-n:k+=1
 n//=k;q.sort()
print(q[:h])

```

Takes an `h` as input from STDIN and prints an array of the first `h` singly-lossy integers. It is very fast as well, taking only a few seconds for `h=7000`.

**Explanation:** Note that, if we had infinite time, we could simply iterate over all `n,k` and for each pair drop each of `n+1,n+2,...,n+k-1` (`k-1` possibilities), and get all (infinitely many) values from those, then just sort the sequence in ascending order and truncate to `h` elements. Of course, we cannot actually do that, but if we can reach a point where the first sorted `h` elements can no longer change by adding the values of any future `n,k` pairs, we can just truncate then and be done, in finite time. For any `n,k` pair, it has at least `floor(log10(n)+1)*k` digits, possibly more. So lets group these pairs by the value `c(n,k)=floor(log10(n)+1)*k`, where we guarantee that if `c(a,b)<c(n,k)`, we process `a,b` before `n,k`. If we have the list sorted, and its last element has `d` digits, and `d<c(n,k)` for the next `n,k` we are going to process, we can stop, since we can no longer get a number with that many or fewer digits, since by our guarantee we should have already processed it then, and therefore no matter which numbers we would end up computing, the first `h` elements can not change, so we can just return them.

So now we just need the function that guarantees the stated order on `c(n,k)`. For each `y` obtainable for `c(n,k)`, we must process all `(n,k)` such that `y=c(n,k)`. Let's say `L=floor(log10(n)+1)` for some `n`. Therefore `y=L*k` must hold. Start with `k=2,L=y/2`, then do `k=3,L=y/3;k=4,L=y/4...k=y,L=1`, skipping non-integer values of `L`. To generate the whole `c(n,k)` function, start with `(1,2)` with `y=2`, and increase `y` by 1 and start again whenever you get `L==1`. Now we have an enumeration of pairs `(L,k)`, and it satisfies our condition. However, we need to retrieve all possible `n` from `L`, which we do by enumerating all integers with `L` digits. Then for each of those `(n,k)` pairs, for each of the `k-1` possible dropped elements we must generate the lossy number we get as a result, and add it to our list, which starts empty. Then we sort the list and repeat on the next `(L,k)` pair, stopping when we have `d<c(n,k)` as stated before.

Code breakdown (a little outdated):

```
t=range                     #shortens code
def f(r,n,k):               #helper function
 for s in t(10**~-n,10**n): #for the (L,k) pair, add value of (s,k,y)
  for y in t(1,k):r+=[(int("".join(map(str,[c+s for c in t(k+1)if c!=y]))))]
 if n>1:                    #case where L!=1
  n*=k;k+=1                 #multiply n (which is n'/k from prev iter), inc k
 else:n,k=k+1,2             #reset n and k
 while n//k*k-n:k+=1        #find next proper divisor of n
 return(r,n//k,k)           #divide by that divisor and return
def g(h):                   #main function
 q,a,b=[],1,2               #initial values
 while h>=len(q)or a*b<=len(str(q[h])):(q,a,b)=f(q,a,b);q.sort()
 return q[:h]               #continues until at least h numbers and surpassed current max

```
> 1 votes

# Answer
# 05AB1E, 17 bytes

```
∞ʒ.œD0Å?_*€¥1cP2å

```

Try it online!

Prints the singly lossy integers forever.
> 0 votes

---
Tags: code-golf, sequence
---


title: Prefix Notation to Postfix Notation

text:
# Question
Title: Prefix Notation to Postfix Notation
Disclaimer: **No, this is not a joke challenge to reverse a string.**

# Task

There is only one operation to support: subtraction (`-`).

You also only have two atoms to support: zero (`0`) and one (`1`).

Here, the prefix notation `-AB` is equivalent to the postfix notation `AB-`, where `A` and `B` are expressions.

Your task is to (recursively) convert an expression in prefix notation to its equivalent in postfix notation.

# Definitions

An expression in prefix notation is generated by the following grammar:

```
S > -SS
S > 0
S > 1

```

An expression in postfix notation is generated by the following grammar:

```
S > SS-
S > 0
S > 1

```

# Example

```
Prefix notation:  --01-0-01
Parentheses:      -(-01)(-0(-01))
Convert:          (01-)(0(01-)-)-
Postfix notation: 01-001---

```

# Rules and freedom

* You may rename the operation and the atoms to whichever character, as long as it is consistent.
* The input format must be consistent with the output format (apart from the fact that the input is in prefix notation and the output is in postfix notation).

# Testcase

```
Input       Output
1           1
0           0
-01         01-
-10         10-
--01-0-01   01-001---

```

Testcases credits to Dada.

# Answer
# brainfuck, 32 bytes

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

```

Try it online!

I used `@` as the operation, because its code point (64) is convenient. `U` is also possible with the same byte count, using 3\*85+1=256=0.

### Explanation

The tape is used as a stack. In each iteration of the main loop, the data pointer starts two cells right of the top of the stack.

```
,[                Take input and start main loop
  [->++++<<+>]    Push input, and compute 4*input
  >[              If 4*input is nonzero (and thus input is not @):
    [-]<<           Zero out this cell and move to top of stack
    [.[-]<]         Pop from stack and output until \0 is reached
  ]
  >,              Move pointer into the correct position.  If input was @, the earlier > pushed \0 onto the stack.
]

```
> 13 votes

# Answer
# Retina, ~~37~~ ~~30~~ 29 bytes

```
M!`-*.
+m`^-(.*)¶(\d.*)
$1$2-

```

Try it online! Saved 7 bytes by realising that terms always begin with a digit, so I don't have to limit the match to the last `-` any more (previously it was the only one guaranteed to be followed by two terms). Saved 1 byte by not putting `-`s on their own line. For example, `-01` becomes `-0¶1` which is then replaced with `01-`. Now, if I have `--010` i.e. `--0¶1¶0` then I want to change the inner `-0¶1` to `01-` so that I can replace the `-01-¶0` with `01-0-`, but it doesn't actually matter which of the two `-`s I remove, so I remove the one at the beginning of the line, as that's easier to test for.
> 6 votes

# Answer
# Haskell, ~~62~~ 59 bytes

```
f(x:r)|x>'-'=([x],r)|(a,(b,c))<-f<$>f r=(a++b++"-",c)
fst.f

```

Try it online! Usage: `fst.f $ "--01-0-01"`. `0` and `1` can be arbitrary characters that are larger than the character `-`.

**Edit:** -3 bytes thanks to Zgarb!

The function `f` recursively parses one expression and returns a tuple of this expression in postfix notation and the rest string, following the simple grammar from which valid prefix-expressions can be build:

```
<exp> ::= - <exp> <exp> | 0 | 1

```

If the first character `a` of the input string is larger than `-`, we are at an atomic expression and return a tuple of a string with character `a` and the rest of the input string.

If we find a `-`, two expressions need to be parsed. This can be achieved by `(a,x)<-f r` to get the first expression `a` and then parse the rest string `x` again `(b,c)<-f x` to get the second expression `b` and the final rest string `c`. `(a,(b,c))<-f<$>f r` does exactly this because `<$>` on tuples maps a function two the second element of a tuple while being three bytes shorter than `(a,x)<-f r,(b,c)<-f x`. After obtaining both expressions and the rest string, the expressions are concatenated and a "-" is appended: `(a++b++"-",c)`.
> 6 votes

# Answer
# Haskell, 54 bytes

```
v f""=""
v f(a:s)=last(v.v:[id|a>'-'])((a:).f)s
h=v h

```

The function `v` takes a string and a function, rearranges the initial sub-expression, then applies the function to the remainder of the string until everything has been rearranged. The call stack and function argument together keep track of what expression is being parsed. The function `h` answers the challenge, and is just `v` called with itself as a dummy first argument.
> 5 votes

# Answer
## Python 3, ~~117~~ ~~112~~ ~~105~~ ~~100~~ ~~98~~ ~~76~~ ~~62~~ ~~61~~ 59 bytes

```
def p(s):x=next(s);yield from[x]*(x>"-")or[*p(s),*p(s),"-"]

```

Changelog:

* removed linebreaks where possible (-5 bytes)
* lambda instead of a full function (-7 bytes, thanks @Dada)
* no else (-5 bytes, thanks @Leaky Nun)
* undo overzealous golfing (-2 bytes, thanks @Leaky Nun)
* work on a global list instead (-22 bytes)
* actually, let's work on iterators instead (-14 bytes)
* change `!=` to `>` (-1 byte, copied from @ovs' suggestion)
* lazy evaluation trickery (-2 bytes, thanks @ovs)

Use it like this:

```
>>> list(p(iter("--01-0-01")))
['0', '1', '-', '0', '0', '1', '-', '-', '-']

```
> 4 votes

# Answer
# Perl 5, 57 bytes

```
sub f{"@_"=~s/x((?0)|.)((?0)|.)/my$n=$2;f($1).f($n).x/re}

```

I use `x` as operator instead of `-` (see the TryItOnline link bellow).

Try it online!

**Explanations:**
`/x((?0)|.)((?0)|.)/` matches recursively a full expression: a `x` at the begining, then an expression `(?0)` (it's a recursive call) or an atom (`.`), followed by another expression-or-atom.
Then I need to save the second expression/atom (`my$n=$2;`) because otherwise the recursive calls will override it.
The function is then recursively called on the first expression (`f($1)`), then on the second `f($n)`, and the `x` is appended at the end (`.x`).
> 4 votes

# Answer
# Pyth, 20 bytes

```
L+&-hbTsyM.-Btbytbhb

```

This creates a function `y` that expects a string as parameter.

Try it online: Demonstration or Test Suite

### Explanation:

The function `y` will parse and convert the first prefix expression to a postfix expression. So if it is called like `y"10"` it will return only `1`.

```
L+&-hbTsyM.-Btbytbhb
L                      define a function y(b), that returns:
   -hbT                   remove the chars "10" from the first char b
                          (T=10, and - will convert a number to a string)
  &                       if this gives the empty string (a falsy value)
 +                hb         then append b[0] to it and return it
                             (so this will parse a digit 0 or 1 from the string)
  &                       otherwise (the first char is a -)
               ytb           parse the first prefix expression from b[1:]
                             (recursive call)
          .-Btb              remove this parsed expression bifurcated from b[1:]
                             this gives a tuple [b[1:], b[1:] without first expr]
        yM                   parse and convert an expression from each one
       s                     join the results
 +                hb         and append the b[0] (the minus) to it and return

```
> 3 votes

# Answer
# Retina, ~~34~~ ~~31~~ 29 bytes

```

;
-;
¶
+`¶(.+);(.+)
$1$2-
;

```

Try it online!

`;` are used to indicate nodes, which are initially composed by a single number and then grow to anything that has already been parsed. `-` are turned into newlines so that with `.+` we can grab anything that isn't an unparsed `-`.
> 2 votes

# Answer
# Unix TMG, 49 bytes

This translation-oriented language from 1972 makes this task trivial:

```
p:parse(b);b:<->b b={2 1<->}|<0>={<0>}|<1>={<1>};

```

I believe, this is the first solution in this language on this website, so I will explain a bit:

```
p: parse(b);                # parse() builtin: execute parsing rule `b` and output its translation
b: <-> b b = { 2 1 <-> }    # encountering "-" do recursion; translation rule is in braces
 | <0> = { <0> }            # otherwise: encountering "0" - translate as "0"
 | <1> = { <1> };           # otherwise: encountering "1" - translate as "1"

```
> 2 votes

# Answer
# Perl 6, 45 bytes

```
my&f={S[x(<~~>)**2|)>.]=$0&&$0>>.&f.join~'x'}

```

Try it online!
> 1 votes

# Answer
# Javascript (ES10), 118 bytes

`e=>[...e.matchAll(/(-*)(\d+)/g)].reduce((a,[_,m,[c,...s]])=>(o+=m.slice(l=s.length),a+c+s.join(d='-')+(l?d:s)),o='')+o`

**Runnable Snippet** (TIO doesn't have ES10's String.matchAll yet)

```
f = e =>
  [...e.matchAll(/(-*)(\d+)/g)].reduce((a, [_, m, [c,...s]]) =>
    (o += m.slice(l=s.length),
    a+c+s.join(d='-')+(l?d:s)), o='')+o;

['1', '0', '-01', '-10', '--01-0-01'].map(v =>
  console.log(`f('${v}') -> ${f(v)}`))
```
> 0 votes

---
Tags: code-golf, string
---


title: Draw the Sierpinski Arrowhead Curve

text:
# Question
Title: Draw the Sierpinski Arrowhead Curve
## Introduction

The Sierpinski Arrowhead Curve is a curve that's limit is Sierpinski's Triangle.

It first starts like this:

```
 _
/ \

```

Then, each line is replaced with a rotated version of the first one:

```
  _
 / \
 \ /
_/ \_

```

Next:

```
     _
    / \
    \ /
   _/ \_
  /     \
  \_   _/
 _  \ /  _
/ \_/ \_/ \

```

## Your task

Given a number *n*, output the *n*-th iteration of the Sierpinski Arrowhead Curve.

You may choose 0 or 1-indexed input, but please specify that in your answer.

You may generate an image, or use Ascii Art in the format I have given above.

You may not use built-ins to generate this curve.

Remember, this is , so the code with the fewest bytes wins.

# Answer
# Octave, ~~240 236~~ 221 bytes

This is made with the same idea used here but I had to change it to fit the sierpinsky arrowhead curve.

```
m=input(0);g=2*pi/6;u=cos(g);v=sin(g);A=[1,0];B=[u,v];C=[-u,v];D=-A;E=-B;F=-C;for k=1:m;f=[E;F;A];b=[A;B;C];A=[B;A;F];d=[C;D;E];C=[D;C;B];E=[F;E;D];B=b;D=d;F=f;end;A=[0,0;cumsum(A)];plot(A(:,1),A(:,2));axis off;axis equal

```
> 14 votes

# Answer
# Haskell + diagrams, 176 bytes

```
import Diagrams.Prelude
import Diagrams.Backend.SVG
g n=renderSVG"a"(mkWidth 99).strokeT.a n
a 0=hrule 1
a n|b<-a(n-1)=b%6<>b<>b%(-6);a%n=rotateBy(1/n).reflectY$a::Trail V2 Double

```

Makes a svg file with transparent background called "a".

`g 0` outputs a horizontal line, `g 1` is `/¯\`.
> 3 votes

# Answer
# MSWLogo (Version 6.5b), 102 bytes

Takes the two functions `shapeL`, `shapeR` given here and merges them by adding an extra argument `:a`, which calls the opposite function when negated.

```
to s :n :a :l
if :n=0[fd :l stop]
rt :a
s :n-1(-:a):l
lt :a
s :n-1 :a :l
lt :a
s :n-1(-:a):l
rt :a
end

```

A function `s` is defined, which takes number of iterations `:n` (1-based), angle `:a`, length `:l`. It is recursive, calling a lower iteration of itself with the angle `:a` negated in two instances to get the orientation correct.

* `rt :a`, `lt :a` rotate the turtle (triangle thingy whose path is traced) right, left by `:a` degrees.
* `fd :l` moves the turtle forward by `:l` steps.

The function is to be called with `:a` equal to 60.

Here, `repeat` is essentially a FOR loop, with built-in counter `repcount`. `pu` and `pd` mean "pen up" and "pen down", which stop the turtle from drawing while its position is being set using `setxy`.

The drawings of each iteration have been called with length `:l` equal to `power 2 (7-repcount)`, which decreases exponentially; this is because the definition uses the same `:l` in the recursive step, so with fixed `:l` the overall size of the output will increase exponentially with `:n`.
> 2 votes

# Answer
# Python 2, 124 bytes

Based off of the code in the Wikipedia article.

```
from turtle import*
def c(o,a):
 if o:o-=1;c(o,-a);lt(a);c(o,a);lt(a);c(o,-a)
 else:fd(9)
n=input()
if n%2==0:lt(60)
c(n,60)

```

Order 0 is a straight line.
> 2 votes

# Answer
# Mathematica / Wolfram Language 73 bytes

```
s=1;Region@Line@AnglePath[Nest[Join@@({#,s=-s,s}&/@#)&,{#~Mod~2},#]Pi/3]&

```

Simple explanation：
AnglePath\[{θ1,θ2,θ3,…}\] gives the list of 2D coordinates corresponding to a path that starts at {0,0}, then takes a series of steps of unit length at successive relative angles θi.

n=1

```
Graphics@Line@AnglePath[60°{1,-1,-1}]

```

n=2

```
Graphics@Line@AnglePath[60°{0,1,1, -1,-1,-1, -1,1,1}]

```

n=3

```
Graphics@Line@AnglePath[60°{1,-1,-1, 1,1,1, 1,-1,-1, -1,1,1, -1,-1,-1, -1,1,1, -1,-1,-1, 1,1,1, 1,-1,-1}]

```
> 2 votes

# Answer
# Mathematica, 62 bytes

```
Graphics@Line@AnglePath[Pi/3Nest[Flatten@{-#,1,#,1,-#}&,0,#]]&

```
> 0 votes

# Answer
## JavaScript (ES6), 180 bytes

```
f=(n,d=0,r=n=>` `.repeat(n))=>n?f(--n,d=3-d%3).map(s=>r([l=s.length/2,0,1,~n&1][d]+l)+s+r([,1,0,~n&1][d]+l)).concat(f(n,d+1).map(s=>s+r(!(d%3))+a.shift(),a=f(n,d+2))):[`_/\\`[d%3]]
```

```
<input type=number min=1 oninput=o.textContent=f(this.value).join`\n`><pre id=o>
```

Returns an array of strings. Getting the spacing right was the hardest part! Pure string version for 205 bytes:

```
f=(n,d=0,r=n=>` `.repeat(n))=>n?f(--n,d=3-d%3).replace(/.+/g,s=>r([l=s.length/2,0,1,~n&1][d]+l)+s+r([,1,0,~n&1][d]+l))+`\n`+f(n,d+1).replace(/.+/g,s=>s+r(!(d%3))+a.shift(),a=f(n,d+2).split`\n`):`_/\\`[d%3]

```
> 0 votes

---
Tags: code-golf, math, ascii-art, graphical-output
---